dendroid
========
[](https://github.com/lycantropos/dendroid/actions/workflows/ci.yml "Github Actions")
[](https://codecov.io/gh/lycantropos/dendroid "Codecov")
[](https://github.com/lycantropos/dendroid/blob/master/LICENSE "License")
[](https://badge.fury.io/py/dendroid "PyPI")
In what follows `python` is an alias for `python3.7` or `pypy3.7`
or any later version (`python3.8`, `pypy3.8` and so on).
Installation
------------
Install the latest `pip` & `setuptools` packages versions
```bash
python -m pip install --upgrade pip setuptools
```
### User
Download and install the latest stable version from `PyPI` repository
```bash
python -m pip install --upgrade dendroid
```
### Developer
Download the latest version from `GitHub` repository
```bash
git clone https://github.com/lycantropos/dendroid.git
cd dendroid
```
Install dependencies
```bash
python -m pip install -r requirements.txt
```
Install
```bash
python setup.py install
```
Usage
-----
```python
>>> from dendroid import avl, red_black, splay
>>> from random import sample
>>> min_value, max_value = -100, 100
>>> size = (max_value - min_value) // 2
>>> values = sample(range(min_value, max_value), size)
>>> avl_set, red_black_set, splay_set = (avl.set_(*values),
... red_black.set_(*values),
... splay.set_(*values))
>>> len(avl_set) == len(red_black_set) == len(splay_set) == size
True
>>> max_value not in avl_set and max_value not in red_black_set and max_value not in splay_set
True
>>> list(avl_set) == list(red_black_set) == list(splay_set) == sorted(values)
True
>>> avl_set.add(max_value)
>>> red_black_set.add(max_value)
>>> splay_set.add(max_value)
>>> len(avl_set) == len(red_black_set) == len(splay_set) == size + 1
True
>>> max_value in avl_set and max_value in red_black_set and max_value in splay_set
True
>>> list(avl_set) == list(red_black_set) == list(splay_set) == sorted(values) + [max_value]
True
>>> prev_max_value = max(values)
>>> avl_set.prev(max_value) == red_black_set.prev(max_value) == splay_set.prev(max_value) == prev_max_value
True
>>> avl_set.next(prev_max_value) == red_black_set.next(prev_max_value) == splay_set.next(prev_max_value) == max_value
True
>>> avl_set.remove(max_value)
>>> red_black_set.remove(max_value)
>>> splay_set.remove(max_value)
>>> len(avl_set) == len(red_black_set) == len(splay_set) == len(values)
True
>>> max_value not in avl_set and max_value not in red_black_set and max_value not in splay_set
True
>>> list(avl_set) == list(red_black_set) == list(splay_set) == sorted(values)
True
>>> avl_set.max() == red_black_set.max() == splay_set.max() == max(values)
True
>>> avl_set.min() == red_black_set.min() == splay_set.min() == min(values)
True
>>> avl_set.max() == red_black_set.max() == splay_set.max() == max(values)
True
>>> avl_set.min() == red_black_set.min() == splay_set.min() == min(values)
True
>>> avl_set.add(max_value)
>>> red_black_set.add(max_value)
>>> splay_set.add(max_value)
>>> avl_set.popmax() == red_black_set.popmax() == splay_set.popmax() == max_value
True
>>> avl_set.add(min_value)
>>> red_black_set.add(min_value)
>>> splay_set.add(min_value)
>>> avl_set.popmin() == red_black_set.popmin() == splay_set.popmin() == min_value
True
>>> min_key, max_key = min_value, max_value
>>> keys = sample(range(min_key, max_key), size)
>>> items = list(zip(keys, values))
>>> avl_map, red_black_map, splay_map = (avl.map_(*items),
... red_black.map_(*items),
... splay.map_(*items))
>>> len(avl_map) == len(red_black_map) == len(splay_map) == size
True
>>> max_key not in avl_map and max_key not in red_black_map and max_key not in splay_map
True
>>> list(avl_map) == list(red_black_map) == list(splay_map) == sorted(keys)
True
>>> avl_map[max_key] = red_black_map[max_key] = splay_map[max_key] = max_value
>>> len(avl_map) == len(red_black_map) == len(splay_map) == size + 1
True
>>> max_key in avl_map and max_key in red_black_map and max_key in splay_map
True
>>> avl_map[max_key] == red_black_map[max_key] == splay_map[max_key] == max_value
True
>>> list(avl_map) == list(red_black_map) == list(splay_map) == sorted(keys) + [max_key]
True
>>> prev_max_key, prev_max_value = items[max(range(size), key=keys.__getitem__)]
>>> avl_map.prev(max_key) == red_black_map.prev(max_key) == splay_map.prev(max_key) == prev_max_value
True
>>> avl_map.next(prev_max_key) == red_black_map.next(prev_max_key) == splay_map.next(prev_max_key) == max_value
True
>>> del avl_map[max_key], red_black_map[max_key], splay_map[max_key]
>>> len(avl_map) == len(red_black_map) == len(splay_map) == size
True
>>> max_key not in avl_map and max_key not in red_black_map and max_key not in splay_map
True
>>> list(avl_map) == list(red_black_map) == list(splay_map) == sorted(keys)
True
>>> avl_map.max() == red_black_map.max() == splay_map.max() == values[max(range(size), key=keys.__getitem__)]
True
>>> avl_map.min() == red_black_map.min() == splay_map.min() == values[min(range(size), key=keys.__getitem__)]
True
>>> avl_map[max_key] = red_black_map[max_key] = splay_map[max_key] = max_value
>>> avl_map.popmax() == red_black_map.popmax() == splay_map.popmax() == max_value
True
>>> avl_map[min_key] = red_black_map[min_key] = splay_map[min_key] = min_value
>>> avl_map.popmin() == red_black_map.popmin() == splay_map.popmin() == min_value
True
```
Development
-----------
### Bumping version
#### Preparation
Install
[bump2version](https://github.com/c4urself/bump2version#installation).
#### Pre-release
Choose which version number category to bump following [semver
specification](http://semver.org/).
Test bumping version
```bash
bump2version --dry-run --verbose $CATEGORY
```
where `$CATEGORY` is the target version number category name, possible
values are `patch`/`minor`/`major`.
Bump version
```bash
bump2version --verbose $CATEGORY
```
This will set version to `major.minor.patch-alpha`.
#### Release
Test bumping version
```bash
bump2version --dry-run --verbose release
```
Bump version
```bash
bump2version --verbose release
```
This will set version to `major.minor.patch`.
### Running tests
Install dependencies
```bash
python -m pip install -r requirements-tests.txt
```
Plain
```bash
pytest
```
Inside `Docker` container:
- with `CPython`
```bash
docker-compose --file docker-compose.cpython.yml up
```
- with `PyPy`
```bash
docker-compose --file docker-compose.pypy.yml up
```
`Bash` script:
- with `CPython`
```bash
./run-tests.sh
```
or
```bash
./run-tests.sh cpython
```
- with `PyPy`
```bash
./run-tests.sh pypy
```
`PowerShell` script:
- with `CPython`
```powershell
.\run-tests.ps1
```
or
```powershell
.\run-tests.ps1 cpython
```
- with `PyPy`
```powershell
.\run-tests.ps1 pypy
```
Raw data
{
"_id": null,
"home_page": "https://github.com/lycantropos/dendroid/",
"name": "dendroid",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "",
"author": "Azat Ibrakov",
"author_email": "azatibrakov@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/6a/2f/16c1f2c787512c42fa25460af808146e084f89898c3165882e00af8b7b92/dendroid-1.6.1.tar.gz",
"platform": null,
"description": "dendroid\n========\n\n[](https://github.com/lycantropos/dendroid/actions/workflows/ci.yml \"Github Actions\")\n[](https://codecov.io/gh/lycantropos/dendroid \"Codecov\")\n[](https://github.com/lycantropos/dendroid/blob/master/LICENSE \"License\")\n[](https://badge.fury.io/py/dendroid \"PyPI\")\n\nIn what follows `python` is an alias for `python3.7` or `pypy3.7`\nor any later version (`python3.8`, `pypy3.8` and so on).\n\nInstallation\n------------\n\nInstall the latest `pip` & `setuptools` packages versions\n```bash\npython -m pip install --upgrade pip setuptools\n```\n\n### User\n\nDownload and install the latest stable version from `PyPI` repository\n```bash\npython -m pip install --upgrade dendroid\n```\n\n### Developer\n\nDownload the latest version from `GitHub` repository\n```bash\ngit clone https://github.com/lycantropos/dendroid.git\ncd dendroid\n```\n\nInstall dependencies\n```bash\npython -m pip install -r requirements.txt\n```\n\nInstall\n```bash\npython setup.py install\n```\n\nUsage\n-----\n\n```python\n>>> from dendroid import avl, red_black, splay\n>>> from random import sample\n>>> min_value, max_value = -100, 100\n>>> size = (max_value - min_value) // 2\n>>> values = sample(range(min_value, max_value), size)\n>>> avl_set, red_black_set, splay_set = (avl.set_(*values),\n... red_black.set_(*values),\n... splay.set_(*values))\n>>> len(avl_set) == len(red_black_set) == len(splay_set) == size\nTrue\n>>> max_value not in avl_set and max_value not in red_black_set and max_value not in splay_set\nTrue\n>>> list(avl_set) == list(red_black_set) == list(splay_set) == sorted(values)\nTrue\n>>> avl_set.add(max_value)\n>>> red_black_set.add(max_value)\n>>> splay_set.add(max_value)\n>>> len(avl_set) == len(red_black_set) == len(splay_set) == size + 1\nTrue\n>>> max_value in avl_set and max_value in red_black_set and max_value in splay_set\nTrue\n>>> list(avl_set) == list(red_black_set) == list(splay_set) == sorted(values) + [max_value]\nTrue\n>>> prev_max_value = max(values)\n>>> avl_set.prev(max_value) == red_black_set.prev(max_value) == splay_set.prev(max_value) == prev_max_value\nTrue\n>>> avl_set.next(prev_max_value) == red_black_set.next(prev_max_value) == splay_set.next(prev_max_value) == max_value\nTrue\n>>> avl_set.remove(max_value)\n>>> red_black_set.remove(max_value)\n>>> splay_set.remove(max_value)\n>>> len(avl_set) == len(red_black_set) == len(splay_set) == len(values)\nTrue\n>>> max_value not in avl_set and max_value not in red_black_set and max_value not in splay_set\nTrue\n>>> list(avl_set) == list(red_black_set) == list(splay_set) == sorted(values)\nTrue\n>>> avl_set.max() == red_black_set.max() == splay_set.max() == max(values)\nTrue\n>>> avl_set.min() == red_black_set.min() == splay_set.min() == min(values)\nTrue\n>>> avl_set.max() == red_black_set.max() == splay_set.max() == max(values)\nTrue\n>>> avl_set.min() == red_black_set.min() == splay_set.min() == min(values)\nTrue\n>>> avl_set.add(max_value)\n>>> red_black_set.add(max_value)\n>>> splay_set.add(max_value)\n>>> avl_set.popmax() == red_black_set.popmax() == splay_set.popmax() == max_value\nTrue\n>>> avl_set.add(min_value)\n>>> red_black_set.add(min_value)\n>>> splay_set.add(min_value)\n>>> avl_set.popmin() == red_black_set.popmin() == splay_set.popmin() == min_value\nTrue\n>>> min_key, max_key = min_value, max_value\n>>> keys = sample(range(min_key, max_key), size)\n>>> items = list(zip(keys, values))\n>>> avl_map, red_black_map, splay_map = (avl.map_(*items),\n... red_black.map_(*items),\n... splay.map_(*items))\n>>> len(avl_map) == len(red_black_map) == len(splay_map) == size\nTrue\n>>> max_key not in avl_map and max_key not in red_black_map and max_key not in splay_map\nTrue\n>>> list(avl_map) == list(red_black_map) == list(splay_map) == sorted(keys)\nTrue\n>>> avl_map[max_key] = red_black_map[max_key] = splay_map[max_key] = max_value\n>>> len(avl_map) == len(red_black_map) == len(splay_map) == size + 1\nTrue\n>>> max_key in avl_map and max_key in red_black_map and max_key in splay_map\nTrue\n>>> avl_map[max_key] == red_black_map[max_key] == splay_map[max_key] == max_value\nTrue\n>>> list(avl_map) == list(red_black_map) == list(splay_map) == sorted(keys) + [max_key]\nTrue\n>>> prev_max_key, prev_max_value = items[max(range(size), key=keys.__getitem__)]\n>>> avl_map.prev(max_key) == red_black_map.prev(max_key) == splay_map.prev(max_key) == prev_max_value\nTrue\n>>> avl_map.next(prev_max_key) == red_black_map.next(prev_max_key) == splay_map.next(prev_max_key) == max_value\nTrue\n>>> del avl_map[max_key], red_black_map[max_key], splay_map[max_key]\n>>> len(avl_map) == len(red_black_map) == len(splay_map) == size\nTrue\n>>> max_key not in avl_map and max_key not in red_black_map and max_key not in splay_map\nTrue\n>>> list(avl_map) == list(red_black_map) == list(splay_map) == sorted(keys)\nTrue\n>>> avl_map.max() == red_black_map.max() == splay_map.max() == values[max(range(size), key=keys.__getitem__)]\nTrue\n>>> avl_map.min() == red_black_map.min() == splay_map.min() == values[min(range(size), key=keys.__getitem__)]\nTrue\n>>> avl_map[max_key] = red_black_map[max_key] = splay_map[max_key] = max_value\n>>> avl_map.popmax() == red_black_map.popmax() == splay_map.popmax() == max_value\nTrue\n>>> avl_map[min_key] = red_black_map[min_key] = splay_map[min_key] = min_value\n>>> avl_map.popmin() == red_black_map.popmin() == splay_map.popmin() == min_value\nTrue\n\n```\n\nDevelopment\n-----------\n\n### Bumping version\n\n#### Preparation\n\nInstall\n[bump2version](https://github.com/c4urself/bump2version#installation).\n\n#### Pre-release\n\nChoose which version number category to bump following [semver\nspecification](http://semver.org/).\n\nTest bumping version\n```bash\nbump2version --dry-run --verbose $CATEGORY\n```\n\nwhere `$CATEGORY` is the target version number category name, possible\nvalues are `patch`/`minor`/`major`.\n\nBump version\n```bash\nbump2version --verbose $CATEGORY\n```\n\nThis will set version to `major.minor.patch-alpha`. \n\n#### Release\n\nTest bumping version\n```bash\nbump2version --dry-run --verbose release\n```\n\nBump version\n```bash\nbump2version --verbose release\n```\n\nThis will set version to `major.minor.patch`.\n\n### Running tests\n\nInstall dependencies\n```bash\npython -m pip install -r requirements-tests.txt\n```\n\nPlain\n```bash\npytest\n```\n\nInside `Docker` container:\n- with `CPython`\n ```bash\n docker-compose --file docker-compose.cpython.yml up\n ```\n- with `PyPy`\n ```bash\n docker-compose --file docker-compose.pypy.yml up\n ```\n\n`Bash` script:\n- with `CPython`\n ```bash\n ./run-tests.sh\n ```\n or\n ```bash\n ./run-tests.sh cpython\n ```\n\n- with `PyPy`\n ```bash\n ./run-tests.sh pypy\n ```\n\n`PowerShell` script:\n- with `CPython`\n ```powershell\n .\\run-tests.ps1\n ```\n or\n ```powershell\n .\\run-tests.ps1 cpython\n ```\n- with `PyPy`\n ```powershell\n .\\run-tests.ps1 pypy\n ```\n",
"bugtrack_url": null,
"license": "MIT License",
"summary": "Search trees.",
"version": "1.6.1",
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "a13dba386450a9106fe228a25d43746245aad3d705103d3b6ff6953ac9ede976",
"md5": "ad4e2401f91c97f5e858d1b9c1a13eda",
"sha256": "07d8e80593d9ef4c51a92c1e9a2901a0bd7030c3eae61b20b311037e7e74a63b"
},
"downloads": -1,
"filename": "dendroid-1.6.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "ad4e2401f91c97f5e858d1b9c1a13eda",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 21612,
"upload_time": "2023-03-27T01:08:05",
"upload_time_iso_8601": "2023-03-27T01:08:05.384420Z",
"url": "https://files.pythonhosted.org/packages/a1/3d/ba386450a9106fe228a25d43746245aad3d705103d3b6ff6953ac9ede976/dendroid-1.6.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "6a2f16c1f2c787512c42fa25460af808146e084f89898c3165882e00af8b7b92",
"md5": "b1e4327217df210d2585a0ea9b58d28b",
"sha256": "929470d26d5b9bc3a93461b3227d208812a8fae30358eb47da8b159d53c8dd37"
},
"downloads": -1,
"filename": "dendroid-1.6.1.tar.gz",
"has_sig": false,
"md5_digest": "b1e4327217df210d2585a0ea9b58d28b",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 16231,
"upload_time": "2023-03-27T01:08:06",
"upload_time_iso_8601": "2023-03-27T01:08:06.993208Z",
"url": "https://files.pythonhosted.org/packages/6a/2f/16c1f2c787512c42fa25460af808146e084f89898c3165882e00af8b7b92/dendroid-1.6.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-03-27 01:08:06",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "lycantropos",
"github_project": "dendroid",
"travis_ci": false,
"coveralls": true,
"github_actions": true,
"requirements": [],
"lcname": "dendroid"
}
JSON
