Metadata-Version: 2.4
Name: dendroid
Version: 2.1.0
Summary: Search trees.
Home-page: https://github.com/lycantropos/dendroid/
Download-URL: https://github.com/lycantropos/dendroid/archive/master.zip
Author-email: Azat Ibrakov <azatibrakov@gmail.com>
License: MIT License
        
        Copyright (c) 2019 Azat Ibrakov
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Programming Language :: Python :: Implementation :: PyPy
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: reprit<1.0.0,>=0.9.0
Requires-Dist: typing-extensions<5.0,>=4.15.0
Provides-Extra: docs
Requires-Dist: Sphinx<9.0,>=7.2.6; extra == "docs"
Requires-Dist: sphinx-rtd-theme<3.0,>=2.0.0; extra == "docs"
Provides-Extra: tests
Requires-Dist: hypothesis<7.0,>=6.148.2; extra == "tests"
Requires-Dist: pytest<10.0,>=9.0.1; extra == "tests"
Dynamic: download-url
Dynamic: home-page
Dynamic: license-file

# dendroid

[![Github Actions](https://github.com/lycantropos/dendroid/workflows/CI/badge.svg)](https://github.com/lycantropos/dendroid/actions/workflows/ci.yml "Github Actions")
[![Codecov](https://codecov.io/gh/lycantropos/dendroid/branch/master/graph/badge.svg)](https://codecov.io/gh/lycantropos/dendroid "Codecov")
[![License](https://img.shields.io/github/license/lycantropos/dendroid.svg)](https://github.com/lycantropos/dendroid/blob/master/LICENSE "License")
[![PyPI](https://badge.fury.io/py/dendroid.svg)](https://badge.fury.io/py/dendroid "PyPI")

In what follows `python` is an alias for `python3.10` or `pypy3.10`
or any later version (`python3.11`, `pypy3.11` and so on).

## Installation

### Prerequisites

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

```bash
python -m pip install -e '.'
```

## 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

#### Prerequisites

Install [bump-my-version](https://github.com/callowayproject/bump-my-version#installation).

#### Release

Choose which version number category to bump following [semver
specification](http://semver.org/).

Test bumping version

```bash
bump-my-version bump --dry-run --verbose $CATEGORY
```

where `$CATEGORY` is the target version number category name, possible
values are `patch`/`minor`/`major`.

Bump version

```bash
bump-my-version bump --verbose $CATEGORY
```

This will set version to `major.minor.patch`.

### Running tests

#### Plain

Install with dependencies

```bash
python -m pip install -e '.[tests]'
```

Run

```bash
pytest
```

#### `Docker` container

Run

- with `CPython`

  ```bash
  docker-compose --file docker-compose.cpython.yml up
  ```

- with `PyPy`

  ```bash
  docker-compose --file docker-compose.pypy.yml up
  ```

#### `Bash` script

Run

- with `CPython`

  ```bash
  ./run-tests.sh
  ```

  or

  ```bash
  ./run-tests.sh cpython
  ```

- with `PyPy`

  ```bash
  ./run-tests.sh pypy
  ```

#### `PowerShell` script

Run

- with `CPython`

  ```powershell
  .\run-tests.ps1
  ```

  or

  ```powershell
  .\run-tests.ps1 cpython
  ```

- with `PyPy`

  ```powershell
  .\run-tests.ps1 pypy
  ```
