### Navigation

- index
- modules |
- previous |
- Banyan 0.1.3 documentation »

# Reference

Fast augmentable sorted sets and dicts.

The examples in the documentation assume

    >>> from __future__ import print_function

if running pre Py3K, as well as

    >>> from banyan import *

## Collections

Can be used as drop-in sorted alternatives to Python’s built-in collection types.

### `SortedSet`

class `banyan.``SortedSet`(items=None, key_type=None, alg=0, key=None, compare=None, updator=None)

  A sorted set.

  `__and__`(other)

    Parameters: | other (iterable) – Other items.
    Returns: | The intersection of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) & [3, 1]
        SortedSet([1, 3])

    Parameters: | other (iterable) – Other items.
    Returns: | The intersection of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) & [3, 1]
        SortedSet([1, 3])

  `__contains__`()

    x.__contains__(y) <==> y in x

    Param : | y
    Returns: | Whether y is contained in the set’s keys.

    Examples:

        >>> t = FrozenSortedSet([1, 3])
        >>> assert 1 in t
        >>> assert 2 not in t

  `__eq__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is equal to the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]) == [1, 2, 3]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is equal to the set of other.

    Example:

        >>> assert SortedSet([1, 3, 2]) == [1, 2, 3]

  `__ge__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a superset of the set of other.

    Examples:

        >>> assert not SortedSet([1, 3, 2]).issuperset([1, 2, 3, 4])
        >>> assert not SortedSet([1, 4, 3]).issuperset([1, 4, 2, 3, 4])
        >>> assert SortedSet([1, 3, 2]).issuperset([])
        >>> assert SortedSet([1, 2, 3]).issuperset([1, 2, 3])
        >>> assert not SortedSet([1, 2, 3]) >= [1, 2, 3, 4]
        >>> assert not SortedSet([1, 2, 3]) >= [1, 4, 3, 2]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a superset of the set of other.

    Examples:

        >>> assert not SortedSet([1, 3, 2]).issuperset([1, 2, 3, 4])
        >>> assert not SortedSet([1, 4, 3]).issuperset([1, 4, 2, 3, 4])
        >>> assert SortedSet([1, 3, 2]).issuperset([])
        >>> assert SortedSet([1, 2, 3]).issuperset([1, 2, 3])
        >>> assert not SortedSet([1, 2, 3]) >= [1, 2, 3, 4]
        >>> assert not SortedSet([1, 2, 3]) >= [1, 4, 3, 2]

  `__gt__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a proper superset of the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]).issuperset([1, 2, 3])
        >>> assert SortedSet([1, 3, 2, 4]) > [1, 2, 3]
        >>> assert not SortedSet([1, 3, 2]) > [1, 2, 3]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a proper superset of the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]).issuperset([1, 2, 3])
        >>> assert SortedSet([1, 3, 2, 4]) > [1, 2, 3]
        >>> assert not SortedSet([1, 3, 2]) > [1, 2, 3]

  `__init__`(items=None, key_type=None, alg=0, key=None, compare=None, updator=None)

    Parameters: | items (iterable or `None`) – Sequence of initial items key_type (type or `None`) – Optional keys’ type, or `None` to show it is unknown or undefined (specifying the key type can greatly improve performance). alg (string) – Underlying algorithm string. Should be one of RED_BLACK_TREE, SPLAY_TREE, or SORTED_LIST key (function) – Key function: transforms the set’s keys into something that can be compared. compare (function or `None`) – Comparison function. Should take two parameters, say x and y, and return the a negative number, 0, or positive number, for the cases x < y, x == y, and x > y, respectively. updator (function or `None`) – Node updator

    Note

    The compare fuction is deprecated in favor of the key function.

    Examples:

        >>> # Red-black tree sorted set
        >>> t = SortedSet()
        >>>
        >>> # (Red-black tree) sorted set with initial items
        >>> t = SortedSet([1, 3, 2])
        >>> list(t)
        [1, 2, 3]
        >>>
        >>> # Splay-tree sorted set
        >>> t = SortedSet(alg = SPLAY_TREE)
        >>>
        >>> # Splay-tree larger-first sorted set with initial items.
        >>> t = SortedSet([1, 3, 2], alg = SPLAY_TREE, compare = lambda x, y: y - x)
        >>> list(t)
        [3, 2, 1]

    Key-Type Example:

        >>> # Almost no change!
        >>> t = SortedSet([1, 3, 2], key_type = int)
        >>> # Identical from here.

  `__iter__`()

    Iterates over all keys.

    Example:

        >>> t = SortedSet([2, 1, 3])
        >>> for e in t:
        ...     print(e)
        ...
        1
        2
        3

    Warning

    While iterating over a mapping (either directly or through a view), the mapping should not be modified - the behaviour is undefined in this case. A different alternative should be found. For example: in order to erase the even keys of a set `t`, instead of using a loop:

        >>> # Example of badness!
        >>> for e in t:
        ...     if e % 2:
        ...         t.remove(e)

    use comprehension:

        >>> t = SortedSet([k for k in t if k % 2 == 1])

    which is more efficient computationally anyway.

  `__le__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a subset of the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]).issubset([1, 2, 3, 4])
        >>> assert SortedSet([1, 4, 3]).issubset([1, 4, 2, 3, 4])
        >>> assert not SortedSet([1, 3, 2]).issubset([])
        >>> assert SortedSet([1, 2, 3]).issubset([1, 2, 3])
        >>> assert SortedSet([1, 2, 3]) <= [1, 2, 3, 4]
        >>> assert SortedSet([1, 2, 3]) <= [1, 4, 3, 2]

    Parameters: | other – A sequence of items.
    Returns: | Whether this set is a subset of the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]).issubset([1, 2, 3, 4])
        >>> assert SortedSet([1, 4, 3]).issubset([1, 4, 2, 3, 4])
        >>> assert not SortedSet([1, 3, 2]).issubset([])
        >>> assert SortedSet([1, 2, 3]).issubset([1, 2, 3])
        >>> assert SortedSet([1, 2, 3]) <= [1, 2, 3, 4]
        >>> assert SortedSet([1, 2, 3]) <= [1, 4, 3, 2]

  `__len__`() <==> len(x)

    Returns: | Number of items in the set.

    Example:

        >>> assert len(SortedSet([1, 3, 2, 2])) == 3

  `__lt__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a proper subset of the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]).issubset([1, 2, 3])
        >>> assert SortedSet([1, 3, 2]) < [1, 2, 3, 4]
        >>> assert not SortedSet([1, 3, 2]) < [1, 2, 3]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a proper subset of the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]).issubset([1, 2, 3])
        >>> assert SortedSet([1, 3, 2]) < [1, 2, 3, 4]
        >>> assert not SortedSet([1, 3, 2]) < [1, 2, 3]

  `__ne__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is unequal to the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]) != [1, 2, 3, 4]
        >>> assert not SortedSet([1, 3, 2]) != [1, 2, 3]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is unequal to the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]) != [1, 2, 3, 4]
        >>> assert not SortedSet([1, 3, 2]) != [1, 2, 3]

  `__or__`(other)

    Parameters: | other (iterable) – Other items.
    Returns: | The union of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) | [20]
        SortedSet([1, 2, 3, 20])

    Parameters: | other (iterable) – Other items.
    Returns: | The union of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) | [20]
        SortedSet([1, 2, 3, 20])

  `__reduce__`()

    Pickle support.

    Example:

        >>> import pickle
        >>>
        >>> t = SortedSet([2, 1, 3])
        >>> t.add(4)
        >>>
        >>> with open('data.pkl', 'wb') as output:
        ...     pickle.dump(t, output)
        ...
        >>> with open('data.pkl', 'rb') as input:
        ...     t1 = pickle.load(input)
        ...
        >>> assert t == t1

  `__sub__`(other)

    Parameters: | other (iterable) – Other items.
    Returns: | The difference of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) - [3, 1]
        SortedSet([2])

    Parameters: | other (iterable) – Other items.
    Returns: | The difference of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) - [3, 1]
        SortedSet([2])

  `__xor__`(other)

    Parameters: | other (iterable) – Other items.
    Returns: | The symmetric difference of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) ^ [3, 1, 5]
        SortedSet([2, 5])

    Parameters: | other (iterable) – Other items.
    Returns: | The symmetric difference of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) ^ [3, 1, 5]
        SortedSet([2, 5])

  `add`(item)

    Adds an item.

    Example:

        >>> t = SortedSet()
        >>> assert 1 not in t
        >>> t.add(1)
        >>> assert 1 in t
        >>> assert len(t) == 1
        >>> t.add(1)
        >>> assert len(t) == 1

  `pop`()

    Removes an arbitrary item from the set.

    Returns: | item removed.
    Raises : | `KeyError` if the set is empty.

    Example:

        >>> t = SortedSet([1, 2, 3])
        >>> len(t)
        3
        >>> t.pop()
        2
        >>> assert len(t) == 2

  `clear`()

    Clears all items.

    Example:

        >>> t = SortedSet([1, 2, 3])
        >>> t.clear()
        >>> t
        SortedSet([])

  `copy`()

    Returns: | A shallow copy.

    Example:

        >>> t = SortedSet([1, 3, 2])
        >>> t1 = t.copy()
        >>> assert t == t1

  `difference`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.
    Returns: | The difference of the elements in this set and those in others.

    Example:

        >>> SortedSet([1, 3, 2]).difference([3], [1])
        SortedSet([2])

  `difference_update`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.

    Update this set to the difference of its own items and those in others.

    Example:

        >>> t = SortedSet([1, 3, 2])
        >>> t.difference_update([20])
        >>> t
        SortedSet([1, 2, 3])

  `discard`()

    Parameters: | item – Item which should be removed.

    Removes item from the set if it is present.

    Example:

        >>> t = SortedSet()
        >>> t.remove(3)
        Traceback (most recent call last):
            ...
        KeyError: 3
        >>> t.discard(3)

  `f`()

    Returns: | A shallow copy.

    Example:

        >>> t = SortedSet([1, 3, 2])
        >>> t1 = t.copy()
        >>> assert t == t1

  `intersection`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.
    Returns: | The intersection of the elements in this set and those in others.

    Example:

        >>> SortedSet([1, 3, 2]).intersection([3, 1])
        SortedSet([1, 3])
        >>> SortedSet([1, 3, 2]).intersection([3], [1])
        SortedSet([])

  `intersection_update`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.

    Update this set to the intersection of its own items and those in others.

    Example:

        >>> t = SortedSet([1, 3, 2])
        >>> t.intersection_update([20])
        >>> t
        SortedSet([])
        >>> t = SortedSet([1, 3, 2])
        >>> t.intersection_update([1, 3], [3])
        >>> t
        SortedSet([3])

  `isdisjoint`(other)

    Checks whether there are no common items in this set and other.

    Examples: >>> assert SortedSet([1, 3, 2]).isdisjoint([42])

  `issubset`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a subset of the set of other.

    Examples:

        >>> assert SortedSet([1, 3, 2]).issubset([1, 2, 3, 4])
        >>> assert SortedSet([1, 4, 3]).issubset([1, 4, 2, 3, 4])
        >>> assert not SortedSet([1, 3, 2]).issubset([])
        >>> assert SortedSet([1, 2, 3]).issubset([1, 2, 3])
        >>> assert SortedSet([1, 2, 3]) <= [1, 2, 3, 4]
        >>> assert SortedSet([1, 2, 3]) <= [1, 4, 3, 2]

  `issuperset`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a superset of the set of other.

    Examples:

        >>> assert not SortedSet([1, 3, 2]).issuperset([1, 2, 3, 4])
        >>> assert not SortedSet([1, 4, 3]).issuperset([1, 4, 2, 3, 4])
        >>> assert SortedSet([1, 3, 2]).issuperset([])
        >>> assert SortedSet([1, 2, 3]).issuperset([1, 2, 3])
        >>> assert not SortedSet([1, 2, 3]) >= [1, 2, 3, 4]
        >>> assert not SortedSet([1, 2, 3]) >= [1, 4, 3, 2]

  `keys`(*args, **kwargs)

    Parameters: | start – optional parameter indicating, if given, the smallest element in the view (default `None`). stop – optional parameter, indicating, the smallest element that should be larger than all keys in the view (default `None`). reverse (boolean) – Whether to iterate in reverse order (default `False`).
    Returns: | A dynamic `KeysView` view of the set’s keys.

    Example:

        >>> t = SortedSet([1, 2])
        >>> v = t.keys()
        >>> v
        KeysView([1, 2])
        >>> t.remove(1)
        >>> v
        KeysView([2])

    Example using start and stop options:

        >>> t = SortedSet([1, 2, 3, 4])
        >>>
        >>> v = t.keys()
        >>> v
        KeysView([1, 2, 3, 4])
        >>>
        >>> v = t.keys(3)
        >>> v
        KeysView([1, 2])
        >>>
        >>> v = t.keys(3, reverse = True)
        >>> v
        KeysView([2, 1])
        >>>
        >>> v = t.keys(0, 3)
        >>> v
        KeysView([1, 2])
        >>>
        >>> v = t.keys(0, 23)
        >>> v
        KeysView([1, 2, 3, 4])
        >>>
        >>> v = t.keys(2.5)
        >>> v
        KeysView([1, 2])

  `remove`()

    Removes an item or items.

    Parameters: | item – If only a single parameter is given, then this the item which should be removed. If two parameters are given, then all items at least as large as this one should be removed. If two parameters are given, and this one is None, then all items smaller than the second parameter will be removed stop – optional parameter, indicating, the smallest element that should be retained. If this parameter is None, then all items at least as large as the first parameter will be removed.
    Raises : | `KeyError` if only a single parameter is given the set contains no such key.

    Remove Single Item Example:

        >>> t = SortedSet()
        >>> assert 1 not in t
        >>> t.add(1)
        >>> assert 1 in t
        >>> t.remove(1)
        >>> assert 1 not in t
        >>> t.remove(1)
        Traceback (most recent call last):
            ...
        KeyError: 1

    Remove Range Examples:

        >>> t = SortedSet([1, 3, 2, 5, 4, 6])
        >>> t
        SortedSet([1, 2, 3, 4, 5, 6])
        >>> # Remove everything in the range [2, 5)
        >>> t.remove(2, 5)
        >>> t
        SortedSet([1, 5, 6])
        >>>
        >>> t = SortedSet([1, 3, 2, 5, 4, 6])
        >>> t
        SortedSet([1, 2, 3, 4, 5, 6])
        >>> # Remove everything in the range [2, inf)
        >>> t.remove(2, None)
        >>> t
        SortedSet([1])
        >>>
        >>> t = SortedSet([1, 3, 2, 5, 4, 6])
        >>> t
        SortedSet([1, 2, 3, 4, 5, 6])
        >>> # Remove everything in the range [-inf, 5)
        >>> t.remove(None, 5)
        >>> t
        SortedSet([5, 6])
        >>>
        >>> t = SortedSet([1, 3, 2, 5, 4, 6])
        >>> t
        SortedSet([1, 2, 3, 4, 5, 6])
        >>> # Remove everything in the range [-inf, inf)
        >>> t.remove(None, None)
        >>> t
        SortedSet([])

  `root`

    Returns: | The root `Node` of the tree.

  `symmetric_difference`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.
    Returns: | The symmetric difference of the elements in this set and those in others.

    Example:

        >>> SortedSet([1, 3, 2]).symmetric_difference([4, 5, 1], [1])
        SortedSet([1, 2, 3, 4, 5])

  `symmetric_difference_update`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.

    Update this set to the symmetric difference of its own items and those in others.

    Example:

        >>> t = SortedSet([1, 3, 2])
        >>> t.symmetric_difference_update([2, 5])
        >>> t
        SortedSet([1, 3, 5])

  `union`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.
    Returns: | The union of the elements in this set and those in others.

    Example:

        >>> SortedSet([1, 3, 2]).union([20])
        SortedSet([1, 2, 3, 20])
        >>> SortedSet([1, 3, 2]).union([20], [30, 3])
        SortedSet([1, 2, 3, 20, 30])

  `update`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.

    Update this set to the union of its own items and those in others.

    Example:

        >>> t = SortedSet([1, 3, 2])
        >>> t.update([20])
        >>> t
        SortedSet([1, 2, 3, 20])
        >>>
        >>> t = SortedSet([1, 3, 2])
        >>> t.update([20], [30, 3])
        >>> t
        SortedSet([1, 2, 3, 20, 30])

### `SortedDict`

class `banyan.``SortedDict`(items=None, key_type=None, alg=0, key=None, compare=None, updator=None)

  A sorted dictionary.

  `__contains__`()

    x.__contains__(y) <==> y in x

    Param : | y
    Returns: | Whether y is contained in the dict’s keys.

    Examples:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (1, 'c')])
        >>> assert 1 in t
        >>> assert 3 not in t

  `__delitem__`()

    x.__delitem__(y) <==> del x[y]

    Parameters: | key (Key object or slice) – Key or key range.
    Raises : | `KeyError` if a single key is given, and the dict contains no such key.

    Single Key Example:

        >>> t = SortedDict([(2, 'b'), (3, 'c')])
        >>> assert t[2] == 'b'
        >>> del t[2]
        >>> assert 2 not in t

    Key Slice Examples:

        >>> t = SortedDict([(2, 'b'), (3, 'c'), (4, 'd')])
        >>> assert t[2] == 'b'
        >>> assert t[3] == 'c'
        >>> assert t[4] == 'd'
        >>> del t[2: 4]
        >>> assert 2 not in t
        >>> assert 3 not in t
        >>> assert 4 in t
        >>>
        >>> t = SortedDict([(2, 'b'), (3, 'c'), (4, 'd')])
        >>> assert t[2] == 'b'
        >>> assert t[3] == 'c'
        >>> assert t[4] == 'd'
        >>> del t[4: ]
        >>> assert 2 in t
        >>> assert 3 in t
        >>> assert 4 not in t

  `__getitem__`()

    x.__getitem__(y) <==> x[y]

    Parameters: | y (Key object or slice) – Key or key range.
    Returns: | The value mapped by y if key is a single key, oterwise a tuple of values.
    Raises : | `KeyError` if a single key is given, and x contains no such key.

    Single Key Example:

        >>> t = SortedDict([(2, 'b'), (3, 'c')])
        >>> assert t[2] == 'b'
        >>> assert t[4] == 'd'
        Traceback (most recent call last):
          ...
        KeyError: 4

    Key Slice Example:

        >>> t = SortedDict([(2, 'b'), (3, 'c'), (4, 'd')])
        >>> assert t[2] == 'b'
        >>> assert t[3] == 'c'
        >>> assert t[4] == 'd'
        >>> assert t[2: 5] == ('b', 'c', 'd')
        >>> assert t[18: 30] == ()
        >>> assert t[2: 3] == ('b', )

  `__init__`(items=None, key_type=None, alg=0, key=None, compare=None, updator=None)

    Parameters: | items (iterable or `None`) – Sequence or mapping of initial items. key_type (type or `None`) – Optional keys’ type, or `None` to show it is unknown or undefined (specifying the key type can greatly improve performance). alg (string) – Underlying algorithm string. Should be one of RED_BLACK_TREE, SPLAY_TREE, or SORTED_LIST key (function) – Key function: transforms the set’s keys into something that can be compared. compare (Function or `None`) – Comparison function. Should take two parameters, say x and y, and return the a negative number, 0, or positive number, for the cases x < y, x == y, and x > y, respectively. updator (Function or `None`) – Node updator

    Note

    The compare fuction is deprecated in favor of the key function.

    Examples:

        >>> # (Red-black tree) sorted dict with initial items
        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> list(t)
        [1, 2]
        >>> assert 1 in t
        >>> assert 4 not in t

    Key-Type Example:

        >>> # Almost no change!
        >>> t = SortedDict([(1, 'a'), (2, 'b')], key_type = int)
        >>> # Identical from here.

  `__iter__`()

    Iterates over all keys.

    Example:

        >>> t = SortedDict([(2, 'b'), (3, 'c')])
        >>> for e in t:
        ...     print(e)
        ...
        2
        3

    Warning

    While iterating over a mapping (either directly or through a view), the mapping should not be modified - the behaviour is undefined in this case. A different alternative should be found. For example: in order to erase the even keys of a dict `t`, instead of using a loop:

        >>> # Example of badness!
        >>> for e in t:
        ...     if e % 2:
        ...         del t[e]

    use comprehension:

        >>> t = SortedDict([(k, v) for (k, v) in t.items() if k % 2 == 1])

    which is more efficient computationally anyway.

  `__len__`() <==> len(x)

    Returns: | Number of items in the set.

    Example:

        >>> len(SortedDict([(1, 'a'), (2, 'b'), (1, 'c')]))
        2

  `__reduce__`()

    Pickle support.

    Example:

        >>> import pickle
        >>>
        >>> t = SortedDict([(2, 'b')])
        >>>
        >>> with open('data.pkl', 'wb') as output:
        ...     pickle.dump(t, output)
        ...
        >>> with open('data.pkl', 'rb') as input:
        ...     t1 = pickle.load(input)
        ...
        >>> assert list(t) == list(t1)

  `__setitem__`()

    x.__setitem__(i, y) <==> x[i]=y

    Parameters: | key (Key object or slice) – Key or key range. val – Value to be mapped to key, or iterable of values to be mapped to key range.
    Raises : | `ValueError` if a key range is given, and val is not a sequence of the same length, and `TypeError` if a step-specified slice is given.

    Single Key Example:

        >>> t = SortedDict([(1, 'a')])
        >>> t[1] = 'b'
        >>> t[1]
        'b'

    Key Slice Examples:

        >>> t = SortedDict([(2, 'b'), (3, 'c'), (4, 'd')])
        >>> t[2: 4] = ('a', 'a')
        >>> assert t[2: 5] == ('a', 'a', 'd')
        >>>
        >>> t[2: 4] = ('a', 'b', 'e')
        Traceback (most recent call last):
          ...
        ValueError: ('a', 'b', 'e')
        >>>
        >>> t[: 4] = ('f', 'f')
        >>>
        >>> t[2: 4: 1] = ('c', 'f')
        Traceback (most recent call last):
          ...
        TypeError: slice(2, 4, 1)

  `popitem`()

    Removes an arbitrary item from the dict.

    Returns: | item removed.
    Raises : | `KeyError` if the dict is empty.

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c')])
        >>> len(t)
        3
        >>> t.popitem()
        (2, 'b')
        >>> assert len(t) == 2

  `setdefault`()

    Parameters: | key – Key to be mapped default – Data to be mapped to key, if key is not in the dict (default `None`).

    Sets the value mapped by key to default, unless there is such a key already.

    Returns: | value mapped by key after this operation completes.

    Example:

        >>> t = SortedDict([(1, 'a')])
        >>> t.setdefault(1, 'b')
        'a'
        >>> t.setdefault(2, 'b')
        'b'

    Sets the value mapped by key to default, unless there is such a key already.

    Returns: | value mapped by key after this operation completes.

    Example:

        >>> t = SortedDict([(1, 'a')])
        >>> t.setdefault(1, 'b')
        'a'
        >>> t.setdefault(2, 'b')
        'b'

  `clear`()

    Clears all items.

    Example:

        >>> t = SortedDict([(1, 'a')])
        >>> t.clear()
        >>> t
        SortedDict({})

  classmethod `fromkeys`(keys, value=None, key_type=None, alg=2, key=None, compare=None, updator=None)

    Creates a sorted dict from keys and a value.

    Parameters: | keys – Sequence of keys. value – Value mapped to the keys key_type (type or `None`) – Optional keys’ type, or `None` to show it is unknown or undefined (specifying the key type can greatly improve performance). alg (string) – Underlying algorithm string. Should be one of RED_BLACK_TREE, SPLAY_TREE, or SORTED_LIST key (function) – Key function: transforms the set’s keys into something that can be compared. compare (function or `None`) – Comparison function. Should take two parameters, say x and y, and return the a negative number, 0, or positive number, for the cases x < y, x == y, and x > y, respectively. updator (function or `None`) – Node updator

    Note

    The compare fuction is deprecated in favor of the key function.

    Example:

        >>> t = SortedDict.fromkeys([1, 2], 'b')
        >>> assert t[1] == t[2] == 'b'

  `get`()

    Parameters: | key – Key default – default value
    Returns: | default if key is not in the dict, otherwise value mapped by key.

    Examples:

        >>> t = SortedDict([(2, 'b'), (3, 'c')])
        >>> assert t.get(2, 'a') == 'b'
        >>> assert t.get(0, 'a') == 'a'

  `items`(*args, **kwargs)

    Parameters: | start – optional parameter indicating, if given, the smallest key of the values in the view (default `None`). stop – optional parameter, indicating, the smallest key that should be larger than all of the keys corresponding to the values in the view (default `None`). reverse (bool) – Whether to iterate in reverse order.
    Returns: | A dynamic `ItemsView` view of the dict’s items (default `False`).

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.items()
        >>> v
        ItemsView([(1, 'a'), (2, 'b')])
        >>> del t[1]
        >>> v
        ItemsView([(2, 'b')])
        >>>
        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.items(reverse = True)
        >>> v
        ItemsView([(2, 'b'), (1, 'a')])
        >>> del t[1]
        >>> v
        ItemsView([(2, 'b')])

    Examples using start and stop options:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.items()
        >>> v
        ItemsView([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.items(3)
        >>> v
        ItemsView([(1, 'a'), (2, 'b')])
        >>>
        >>> v = t.items(3, reverse = True)
        >>> v
        ItemsView([(2, 'b'), (1, 'a')])
        >>>
        >>> v = t.items(0, 3)
        >>> v
        ItemsView([(1, 'a'), (2, 'b')])
        >>>
        >>> v = t.items(0, 23)
        >>> v
        ItemsView([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.items(2.5)
        >>> v
        ItemsView([(1, 'a'), (2, 'b')])
        >>>
        >>> v = t.items(2.5, 23)
        >>> v
        ItemsView([(3, 'c'), (4, 'd')])
        >>>

  `keys`(*args, **kwargs)

    Parameters: | start – optional parameter indicating, if given, the smallest element in the view (default `None`). stop – optional parameter, indicating, the smallest element that should be larger than all keys in the view (default `None`). reverse (boolean) – Whether to iterate in reverse order (default `False`).
    Returns: | A dynamic `KeysView` view of the set’s keys.

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.keys()
        >>> v
        KeysView([1, 2])
        >>> del t[1]
        >>> v
        KeysView([2])
        >>>
        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.keys(reverse = True)
        >>> v
        KeysView([2, 1])

    Example using start and stop options:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.keys()
        >>> v
        KeysView([1, 2, 3, 4])
        >>>
        >>> v = t.keys(3)
        >>> v
        KeysView([1, 2])
        >>>
        >>> v = t.keys(3, reverse = True)
        >>> v
        KeysView([2, 1])
        >>>
        >>> v = t.keys(0, 3)
        >>> v
        KeysView([1, 2])
        >>>
        >>> v = t.keys(0, 23)
        >>> v
        KeysView([1, 2, 3, 4])
        >>>
        >>> v = t.keys(2.5)
        >>> v
        KeysView([1, 2])

  `pop`()

    Parameters: | key – Key. default – optional default value
    Raises : | `KeyError` if default is not given, and the dict contains no such key.

    Example:

        >>> t = SortedDict([(2, 'b'), (3, 'c')])
        >>> assert t.pop(2) == 'b'
        >>> assert 2 not in t
        >>> assert t.pop(2, 'a') == 'a'
        >>> t.pop(2)
        Traceback (most recent call last):
          ...
        KeyError: 2

  `popitem`()

    Removes an arbitrary item from the dict.

    Returns: | item removed.
    Raises : | `KeyError` if the dict is empty.

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c')])
        >>> len(t)
        3
        >>> t.popitem()
        (2, 'b')
        >>> assert len(t) == 2

  `root`

    Returns: | The root `Node` of the DictTree.

  `setdefault`()

    Parameters: | key – Key to be mapped default – Data to be mapped to key, if key is not in the dict (default `None`).

    Sets the value mapped by key to default, unless there is such a key already.

    Returns: | value mapped by key after this operation completes.

    Example:

        >>> t = SortedDict([(1, 'a')])
        >>> t.setdefault(1, 'b')
        'a'
        >>> t.setdefault(2, 'b')
        'b'

  `update`(other)

    Parameters: | other – Other dict or pair-sequence.

    Updates items from other.

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> t
        SortedDict({1: 'a', 2: 'b'})
        >>> t.update([(2, 'c'), (3, 'f')])
        >>> t
        SortedDict({1: 'a', 2: 'c', 3: 'f'})
        >>> t.update(SortedDict([(4, 'm')]))
        >>> t
        SortedDict({1: 'a', 2: 'c', 3: 'f', 4: 'm'})

  `values`(*args, **kwargs)

    Parameters: | start – optional parameter indicating, if given, the smallest key of the values in the view (default `None`). stop – optional parameter, indicating, the smallest key that should be larger than all of the keys corresponding to the values in the view (default `None`). reverse (bool) – Whether to iterate in reverse order (default `False`).
    Returns: | A dynamic `ValuesView` view of the dict’s values.

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.values()
        >>> v
        ValuesView(['a', 'b'])
        >>> del t[1]
        >>> v
        ValuesView(['b'])
        >>>
        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.values(reverse = True)
        >>> v
        ValuesView(['b', 'a'])
        >>> del t[1]
        >>> v
        ValuesView(['b'])

    Examples using start and stop options:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.values()
        >>> v
        ValuesView(['a', 'b', 'c', 'd'])
        >>>
        >>> v = t.values(3)
        >>> v
        ValuesView(['a', 'b'])
        >>>
        >>> v = t.values(3, reverse = True)
        >>> v
        ValuesView(['b', 'a'])
        >>>
        >>> v = t.values(0, 3)
        >>> v
        ValuesView(['a', 'b'])
        >>>
        >>> v = t.values(0, 23)
        >>> v
        ValuesView(['a', 'b', 'c', 'd'])
        >>>
        >>> v = t.values(2.5)
        >>> v
        ValuesView(['a', 'b'])
        >>>
        >>> v = t.values(2.5, 23)
        >>> v
        ValuesView(['c', 'd'])

### `FrozenSortedSet`

class `banyan.``FrozenSortedSet`(items=None, key_type=None, alg=2, key=None, compare=None, updator=None)

  An immutable sorted set.

  `__and__`(other)

    Parameters: | other (iterable) – Other items.
    Returns: | The intersection of the items in this set and those in other.

    Example:

        >>> FrozenSortedSet([1, 3, 2]) & [3, 1]
        FrozenSortedSet([1, 3])

    Parameters: | other (iterable) – Other items.
    Returns: | The intersection of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) & [3, 1]
        SortedSet([1, 3])

  `__contains__`()

    x.__contains__(y) <==> y in x

    Param : | y
    Returns: | Whether y is contained in the set’s keys.

    Examples:

        >>> t = FrozenSortedSet([1, 3])
        >>> assert 1 in t
        >>> assert 2 not in t

  `__eq__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is equal to the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]) == [1, 2, 3]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is equal to the set of other.

    Example:

        >>> assert FrozenSortedSet([1, 3, 2]) == [1, 2, 3]

  `__ge__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a superset of the set of other.

    Examples:

        >>> assert not FrozenSortedSet([1, 3, 2]).issuperset([1, 2, 3, 4])
        >>> assert not FrozenSortedSet([1, 4, 3]).issuperset([1, 4, 2, 3, 4])
        >>> assert FrozenSortedSet([1, 3, 2]).issuperset([])
        >>> assert FrozenSortedSet([1, 2, 3]).issuperset([1, 2, 3])
        >>> assert not FrozenSortedSet([1, 2, 3]) >= [1, 2, 3, 4]
        >>> assert not FrozenSortedSet([1, 2, 3]) >= [1, 4, 3, 2]

  `__gt__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a proper superset of the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]).issuperset([1, 2, 3])
        >>> assert FrozenSortedSet([1, 3, 2, 4]) > [1, 2, 3]
        >>> assert not FrozenSortedSet([1, 3, 2]) > [1, 2, 3]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a proper superset of the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]).issuperset([1, 2, 3])
        >>> assert FrozenSortedSet([1, 3, 2, 4]) > [1, 2, 3]
        >>> assert not FrozenSortedSet([1, 3, 2]) > [1, 2, 3]

  `__hash__`()

    Returns: | Hash value based on the contents.

  `__init__`(items=None, key_type=None, alg=2, key=None, compare=None, updator=None)

    Parameters: | items (iterable or `None`) – Sequence of initial items key_type (type or `None`) – Optional keys’ type, or `None` to show it is unknown or undefined (specifying the key type can greatly improve performance). alg (string) – Underlying algorithm string. Should be one of RED_BLACK_TREE, SPLAY_TREE, or SORTED_LIST. key (function) – Key function: transforms the set’s keys into something that can be compared. compare (function or `None`) – Comparison function. Should take two parameters, say x and y, and return the a negative number, 0, or positive number, for the cases x < y, x == y, and x > y, respectively. updator (function or `None`) – Node updator

    Note

    The compare fuction is deprecated in favor of the key function.

    Examples:

        >>> # (Sorted-list) frozen sorted set with initial items
        >>> t = FrozenSortedSet([1, 3, 2])
        >>> list(t)
        [1, 2, 3]
        >>> assert 1 in t
        >>> assert 4 not in t
        >>> t.add(130)
        Traceback (most recent call last):
            ...
        AttributeError: 'FrozenSortedSet' object has no attribute 'add'

    Key-Type Example:

        >>> # Almost no change!
        >>> t = FrozenSortedSet([1, 3, 2], key_type = int)
        >>> # Identical from here.

  `__iter__`()

    Iterates over all keys.

    Example:

        >>> t = FrozenSortedSet([2, 1, 3])
        >>> for e in t:
        ...     print(e)
        ...
        1
        2
        3

  `__le__`(other)

    Parameters: | other – A sequence of items.
    Returns: | Whether this set is a subset of the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]).issubset([1, 2, 3, 4])
        >>> assert FrozenSortedSet([1, 4, 3]).issubset([1, 4, 2, 3, 4])
        >>> assert not FrozenSortedSet([1, 3, 2]).issubset([])
        >>> assert FrozenSortedSet([1, 2, 3]).issubset([1, 2, 3])
        >>> assert FrozenSortedSet([1, 2, 3]) <= [1, 2, 3, 4]
        >>> assert FrozenSortedSet([1, 2, 3]) <= [1, 4, 3, 2]

    Parameters: | other – A sequence of items.
    Returns: | Whether this set is a subset of the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]).issubset([1, 2, 3, 4])
        >>> assert FrozenSortedSet([1, 4, 3]).issubset([1, 4, 2, 3, 4])
        >>> assert not FrozenSortedSet([1, 3, 2]).issubset([])
        >>> assert FrozenSortedSet([1, 2, 3]).issubset([1, 2, 3])
        >>> assert FrozenSortedSet([1, 2, 3]) <= [1, 2, 3, 4]
        >>> assert FrozenSortedSet([1, 2, 3]) <= [1, 4, 3, 2]

  `__len__`() <==> len(x)

    Returns: | Number of items in the set.

    Example:

        >>> assert len(FrozenSortedSet([1, 3, 2, 2])) == 3

  `__lt__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a proper subset of the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]).issubset([1, 2, 3])
        >>> assert FrozenSortedSet([1, 3, 2]) < [1, 2, 3, 4]
        >>> assert not FrozenSortedSet([1, 3, 2]) < [1, 2, 3]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a proper subset of the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]).issubset([1, 2, 3])
        >>> assert FrozenSortedSet([1, 3, 2]) < [1, 2, 3, 4]
        >>> assert not FrozenSortedSet([1, 3, 2]) < [1, 2, 3]

  `__ne__`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is unequal to the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]) != [1, 2, 3, 4]
        >>> assert not FrozenSortedSet([1, 3, 2]) != [1, 2, 3]

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is unequal to the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]) != [1, 2, 3, 4]
        >>> assert not FrozenSortedSet([1, 3, 2]) != [1, 2, 3]

  `__or__`(other)

    Parameters: | other (iterable) – Other items.
    Returns: | The union of the items in this set and those in other.

    Example:

        >>> FrozenSortedSet([1, 3, 2]) | [20]
        FrozenSortedSet([1, 2, 3, 20])

    Parameters: | other (iterable) – Other items.
    Returns: | The union of the items in this set and those in other.

    Example:

        >>> SortedSet([1, 3, 2]) | [20]
        SortedSet([1, 2, 3, 20])

  `__reduce__`()

    Pickle support.

    Example:

        >>> import pickle
        >>>
        >>> t = FrozenSortedSet([2, 1, 3])
        >>>
        >>> with open('data.pkl', 'wb') as output:
        ...     pickle.dump(t, output)
        ...
        >>> with open('data.pkl', 'rb') as input:
        ...     t1 = pickle.load(input)
        ...
        >>> assert t == t1

  `__sub__`(other)

    Parameters: | other (iterable) – Other items.
    Returns: | The difference of the items in this set and those in other.

    Example:

        >>> FrozenSortedSet([1, 3, 2]) - [3, 1]
        FrozenSortedSet([2])

    Parameters: | other (iterable) – Other items.
    Returns: | The difference of the items in this set and those in other.

    Example:

        >>> FrozenSortedSet([1, 3, 2]) - [3, 1]
        FrozenSortedSet([2])

  `__xor__`(other)

    Parameters: | other (iterable) – Other items.
    Returns: | The symmetric difference of the items in this set and those in other.

    Example:

        >>> FrozenSortedSet([1, 3, 2]) ^ [3, 1, 5]
        FrozenSortedSet([2, 5])

    Parameters: | other (iterable) – Other items.
    Returns: | The symmetric difference of the items in this set and those in other.

    Example:

        >>> FrozenSortedSet([1, 3, 2]) ^ [3, 1, 5]
        FrozenSortedSet([2, 5])

  `copy`()

    Returns: | A shallow copy.

    Example:

        >>> t = FrozenSortedSet([1, 3, 2])
        >>> t1 = t.copy()
        >>> assert t == t1

  `difference`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.
    Returns: | The difference of the elements in this set and those in others.

    Example:

        >>> FrozenSortedSet([1, 3, 2]).difference([3, 1])
        FrozenSortedSet([2])

  `intersection`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.
    Returns: | The intersection of the elements in this set and those in others.

    Example:

        >>> FrozenSortedSet([1, 3, 2]).intersection([3, 1])
        FrozenSortedSet([1, 3])
        >>> FrozenSortedSet([1, 3, 2]).intersection([3], [1])
        FrozenSortedSet([])

  `isdisjoint`(other)

    Checks whether there are no common items in this set and other.

    Examples: >>> assert FrozenSortedSet([1, 3, 2]).isdisjoint([42])

  `issubset`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a subset of the set of other.

    Examples:

        >>> assert FrozenSortedSet([1, 3, 2]).issubset([1, 2, 3, 4])
        >>> assert FrozenSortedSet([1, 4, 3]).issubset([1, 4, 2, 3, 4])
        >>> assert not FrozenSortedSet([1, 3, 2]).issubset([])
        >>> assert FrozenSortedSet([1, 2, 3]).issubset([1, 2, 3])
        >>> assert FrozenSortedSet([1, 2, 3]) <= [1, 2, 3, 4]
        >>> assert FrozenSortedSet([1, 2, 3]) <= [1, 4, 3, 2]

  `issuperset`(other)

    Parameters: | other (iterable) – A sequence of items.
    Returns: | Whether this set is a superset of the set of other.

    Examples:

        >>> assert not FrozenSortedSet([1, 3, 2]).issuperset([1, 2, 3, 4])
        >>> assert not FrozenSortedSet([1, 4, 3]).issuperset([1, 4, 2, 3, 4])
        >>> assert FrozenSortedSet([1, 3, 2]).issuperset([])
        >>> assert FrozenSortedSet([1, 2, 3]).issuperset([1, 2, 3])
        >>> assert not FrozenSortedSet([1, 2, 3]) >= [1, 2, 3, 4]
        >>> assert not FrozenSortedSet([1, 2, 3]) >= [1, 4, 3, 2]

  `keys`(*args, **kwargs)

    Parameters: | start – optional parameter indicating, if given, the smallest element in the view (default `None`). stop – optional parameter, indicating, the smallest element that should be larger than all keys in the view (default `None`). reverse (boolean) – Whether to iterate in reverse order (default `False`).
    Returns: | A dynamic `KeysView` view of the set’s keys.

    Example:

        >>> t = FrozenSortedSet([1, 2])
        >>> v = t.keys(reverse = True)
        >>> v
        KeysView([2, 1])

    Example using start and stop options:

        >>> t = FrozenSortedSet([1, 2, 3, 4])
        >>>
        >>> v = t.keys()
        >>> v
        KeysView([1, 2, 3, 4])
        >>>
        >>> v = t.keys(3)
        >>> v
        KeysView([1, 2])
        >>>
        >>> v = t.keys(3, reverse = True)
        >>> v
        KeysView([2, 1])
        >>>
        >>> v = t.keys(0, 3)
        >>> v
        KeysView([1, 2])
        >>>
        >>> v = t.keys(0, 23)
        >>> v
        KeysView([1, 2, 3, 4])
        >>>
        >>> v = t.keys(2.5)
        >>> v
        KeysView([1, 2])

  `root`

    Returns: | The root `Node` of the set.

  `symmetric_difference`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.
    Returns: | The symmetric difference of the elements in this set and those in others.

    Example:

        >>> FrozenSortedSet([1, 3, 2]).symmetric_difference([2, 4])
        FrozenSortedSet([1, 3, 4])

  `union`(*others)

    Parameters: | others (iterable or multiple iterables) – Other elemens.
    Returns: | The union of the elements in this set and those in others.

    Example:

        >>> FrozenSortedSet([1, 3, 2]).union([20])
        FrozenSortedSet([1, 2, 3, 20])
        >>> FrozenSortedSet([1, 3, 2]).union([20], [30, 3])
        FrozenSortedSet([1, 2, 3, 20, 30])

### `FrozenSortedDict`

class `banyan.``FrozenSortedDict`(items=None, key_type=None, alg=0, key=None, compare=None, updator=None)

  An immutable sorted dictionary.

  Note

  PEP 0416 explicitly rejects frozen dictionaries, but, as opposed to regular dictionaries, sorted frozen dictionaries do have an algorithm particularly suited to it (sorted lists), and it’s convenient to have such a class with this algorithm as the default implementation.

  `__contains__`()

    x.__contains__(y) <==> y in x

    Param : | y
    Returns: | Whether y is contained in the dict’s keys.

    Examples:

        >>> t = FrozenSortedDict([(1, 'a'), (2, 'b'), (1, 'c')])
        >>> assert 1 in t
        >>> assert 3 not in t

  `__getitem__`()

    x.__getitem__(y) <==> x[y]

    Parameters: | key (Key object or slice) – Key or key range.
    Returns: | The value mapped by key if key is a single key, oterwise a tuple of values.
    Raises : | `KeyError` if a single key is given, and the dict contains no such key.

    Single Key Example:

        >>> t = FrozenSortedDict([(2, 'b'), (3, 'c')])
        >>> assert t[2] == 'b'
        >>> assert t[4] == 'd'
        Traceback (most recent call last):
          ...
        KeyError: 4

    Key Slice Example:

        >>> t = FrozenSortedDict([(2, 'b'), (3, 'c'), (4, 'd')])
        >>> assert t[2] == 'b'
        >>> assert t[3] == 'c'
        >>> assert t[4] == 'd'
        >>> assert t[2: 5] == ('b', 'c', 'd')
        >>> assert t[18: 30] == ()
        >>> assert t[2: 3] == ('b', )

  `__init__`(items=None, key_type=None, alg=0, key=None, compare=None, updator=None)

    Parameters: | items (iterable or `None`) – Sequence or mapping of initial items. key_type (type or `None`) – Optional keys’ type, or `None` to show it is unknown or undefined (specifying the key type can greatly improve performance). alg (string) – Underlying algorithm string. Should be one of RED_BLACK_TREE, SPLAY_TREE, or SORTED_LIST key (function) – Key function: transforms the set’s keys into something that can be compared. compare (Function or `None`) – Comparison function. Should take two parameters, say x and y, and return the a negative number, 0, or positive number, for the cases x < y, x == y, and x > y, respectively. updator (Function or `None`) – Node updator

    Note

    The compare fuction is deprecated in favor of the key function.

    Example:

        >>> # (Sorted-list) frozen sorted dict with initial items
        >>> t = FrozenSortedDict([(1, 'a'), (2, 'b')])
        >>> list(t)
        [1, 2]
        >>> assert 1 in t
        >>> assert 4 not in t
        >>> t[130] = 'koko'
        Traceback (most recent call last):
          File "<stdin>", line 1, in <module>
        TypeError: 'FrozenSortedDict' object does not support item assignment

    Key-Type Example:

        >>> # Almost no change!
        >>> t = FrozenSortedDict([(1, 'a'), (2, 'b')], key_type = int)
        >>> # Identical from here.

  `__hash__`()

    Returns: | Hash value based on the contents.

  `__iter__`()

    Iterates over all keys.

    Example:

        >>> t = SortedDict([(2, 'b'), (3, 'c')])
        >>> for e in t:
        ...     print(e)
        ...
        2
        3

  `__len__`() <==> len(x)

    Returns: | Number of items in the set.

    Example:

        >>> len(FrozenSortedDict([(1, 'a'), (2, 'b'), (1, 'c')]))
        2

  `__reduce__`()

    Pickle support.

    Example:

        >>> import pickle
        >>>
        >>> t = SortedDict([(2, 'b')])
        >>>
        >>> with open('data.pkl', 'wb') as output:
        ...     pickle.dump(t, output)
        ...
        >>> with open('data.pkl', 'rb') as input:
        ...     t1 = pickle.load(input)
        ...
        >>> assert list(t) == list(t1)

  classmethod `fromkeys`(keys, value=None, key_type=None, alg=2, key=None, compare=None, updator=None)

    Creates a frozen sorted dict from keys and a value.

    Parameters: | keys – Sequence of keys. value – Value mapped to the keys key_type (type or `None`) – Optional keys’ type, or `None` to show it is unknown or undefined (specifying the key type can greatly improve performance). alg (string) – Underlying algorithm string. Should be one of RED_BLACK_TREE, SPLAY_TREE, or SORTED_LIST key (function) – Key function: transforms the set’s keys into something that can be compared. compare (function or `None`) – Comparison function. Should take two parameters, say x and y, and return the a negative number, 0, or positive number, for the cases x < y, x == y, and x > y, respectively. updator (function or `None`) – Node updator

    Note

    The compare fuction is deprecated in favor of the key function.

    Example:

        >>> t = FrozenSortedDict.fromkeys([1, 2], 'b')
        >>> assert t[1] == t[2] == 'b'

  `get`(key, default=None)

    Parameters: | key – Key default – default value
    Returns: | default if key is not in the dict, otherwise value mapped by key.

    Examples:

        >>> t = SortedDict([(2, 'b'), (3, 'c')])
        >>> assert t.get(2, 'a') == 'b'
        >>> assert t.get(0, 'a') == 'a'

  `items`(*args, **kwargs)

    Parameters: | start – optional parameter indicating, if given, the smallest key of the values in the view (default `None`). stop – optional parameter, indicating, the smallest key that should be larger than all of the keys corresponding to the values in the view (default `None`). reverse (bool) – Whether to iterate in reverse order.
    Returns: | A dynamic `ItemsView` view of the dict’s items (default `False`).

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.items()
        >>> v
        ItemsView([(1, 'a'), (2, 'b')])
        >>> del t[1]
        >>> v
        ItemsView([(2, 'b')])
        >>>
        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.items(reverse = True)
        >>> v
        ItemsView([(2, 'b'), (1, 'a')])
        >>> del t[1]
        >>> v
        ItemsView([(2, 'b')])

    Examples using start and stop options:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.items()
        >>> v
        ItemsView([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.items(3)
        >>> v
        ItemsView([(1, 'a'), (2, 'b')])
        >>>
        >>> v = t.items(3, reverse = True)
        >>> v
        ItemsView([(2, 'b'), (1, 'a')])
        >>>
        >>> v = t.items(0, 3)
        >>> v
        ItemsView([(1, 'a'), (2, 'b')])
        >>>
        >>> v = t.items(0, 23)
        >>> v
        ItemsView([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.items(2.5)
        >>> v
        ItemsView([(1, 'a'), (2, 'b')])
        >>>
        >>> v = t.items(2.5, 23)
        >>> v
        ItemsView([(3, 'c'), (4, 'd')])
        >>>

  `keys`(*args, **kwargs)

    Parameters: | start – optional parameter indicating, if given, the smallest element in the view (default `None`). stop – optional parameter, indicating, the smallest element that should be larger than all keys in the view (default `None`). reverse (boolean) – Whether to iterate in reverse order (default `False`).
    Returns: | A dynamic `KeysView` view of the set’s keys.

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.keys()
        >>> v
        KeysView([1, 2])
        >>> del t[1]
        >>> v
        KeysView([2])
        >>>
        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.keys(reverse = True)
        >>> v
        KeysView([2, 1])

    Example using start and stop options:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.keys()
        >>> v
        KeysView([1, 2, 3, 4])
        >>>
        >>> v = t.keys(3)
        >>> v
        KeysView([1, 2])
        >>>
        >>> v = t.keys(3, reverse = True)
        >>> v
        KeysView([2, 1])
        >>>
        >>> v = t.keys(0, 3)
        >>> v
        KeysView([1, 2])
        >>>
        >>> v = t.keys(0, 23)
        >>> v
        KeysView([1, 2, 3, 4])
        >>>
        >>> v = t.keys(2.5)
        >>> v
        KeysView([1, 2])

  `root`

    Returns: | The root `Node` of the dict.

  `values`(*args, **kwargs)

    Parameters: | start – optional parameter indicating, if given, the smallest key of the values in the view (default `None`). stop – optional parameter, indicating, the smallest key that should be larger than all of the keys corresponding to the values in the view (default `None`). reverse (bool) – Whether to iterate in reverse order (default `False`).
    Returns: | A dynamic `ValuesView` view of the dict’s values.

    Example:

        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.values()
        >>> v
        ValuesView(['a', 'b'])
        >>> del t[1]
        >>> v
        ValuesView(['b'])
        >>>
        >>> t = SortedDict([(1, 'a'), (2, 'b')])
        >>> v = t.values(reverse = True)
        >>> v
        ValuesView(['b', 'a'])
        >>> del t[1]
        >>> v
        ValuesView(['b'])

    Examples using start and stop options:

        >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')])
        >>>
        >>> v = t.values()
        >>> v
        ValuesView(['a', 'b', 'c', 'd'])
        >>>
        >>> v = t.values(3)
        >>> v
        ValuesView(['a', 'b'])
        >>>
        >>> v = t.values(3, reverse = True)
        >>> v
        ValuesView(['b', 'a'])
        >>>
        >>> v = t.values(0, 3)
        >>> v
        ValuesView(['a', 'b'])
        >>>
        >>> v = t.values(0, 23)
        >>> v
        ValuesView(['a', 'b', 'c', 'd'])
        >>>
        >>> v = t.values(2.5)
        >>> v
        ValuesView(['a', 'b'])
        >>>
        >>> v = t.values(2.5, 23)
        >>> v
        ValuesView(['c', 'd'])

## Views

Dynamic views of containers, allowing iteration and queries.

Note

Since the views are to sorted mappings, there are two ways in which they extend Python’s mappings’ views:

- They can be created to reflect a range of keys. For example:

    >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')])
    >>> # Create a view of the items whose keys are at leas 2 an less than 5.
    >>> v = t.items(2, 5)
    >>> v
    ItemsView([(2, 'b'), (3, 'c'), (4, 'd')])
    >>> assert (5, 'e') not in v
    >>> assert (3, 'c') in v
    >>> del t[3]
    >>> assert (3, 'c') not in v

- They can be created in reverse order. For example:

    >>> t = SortedDict([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')])
    >>> v = t.items(reverse = True)
    >>> v
    ItemsView([(5, 'e'), (4, 'd'), (3, 'c'), (2, 'b'), (1, 'a')])
    >>> v = t.items(2, 5, reverse = True)
    >>> v
    ItemsView([(4, 'd'), (3, 'c'), (2, 'b')])

Warning

While iterating over a mapping (either directly or through a view), the mapping should not be modified - the behaviour is undefined in this case. A different alternative should be found. For example: in order to erase the even keys of a dictionary `t`, instead of using a loop:

    >>> # Example of badness!
    >>> for e in t:
    ...     if e % 2:
    ...         del t[e]

use comprehension:

    >>> t = SortedDict([(k, v) for (k, v) in t.items() if k % 2 == 1])

which is more efficient computationally anyway.

### `KeysView`

A dynamic keys view of the dict’s or set’s keys.

class `banyan.``KeysView`(_tree, *args, **kwargs)

### `ValuesView`

A dynamic values view of the dict’s values.

class `banyan.``ValuesView`(_tree, *args, **kwargs)

### `ItemsView`

A dynamic items view of the dict’s items.

class `banyan.``ItemsView`(_tree, *args, **kwargs)

### `Node`

class `banyan.``Node`(c_node)

  Encapsulation of a tree node. Node objects can be used to iterate over the tree in flexible ways. This is useful primarily (and perhaps exclusively) in conjunction with tree node metadata updators. Once a useful metadata update scheme has been conceived, it is possible to implement addtional tree methods using `Node` objects to iterate over the tree in some manner that depends on the metadata.

  A `Node` object is obtained from a tree object through the latter’s `root` method. Given a `Node` object, it is possible to obtain its content itme, metadata, and left and right children, via properties. For example, here is a toy ufnction that takes a node, and prints the subtree structure (rotated 90 degrees counter-clockwise):

      >>> def trace(node, indent = 0):
      ...     if node is None:
      ...         return
      ...
      ...     trace(node.right, indent + 1)
      ...
      ...     node_content = ' ' * indent + str(node.key)
      ...     if node.metadata is not None:
      ...         node_content += ' [ ' + str(node.metadata) + ' ]'
      ...     print(node_content)
      ...
      ...     trace(node.left, indent + 1)
      ...

  Here are two examples of its output (with different updators):

      >>> t = SortedSet(range(25), updator = RankUpdator)
      >>> trace(t.root)
         24 [ 2 ]
          23 [ 1 ]
        22 [ 5 ]
         21 [ 2 ]
          20 [ 1 ]
       19 [ 12 ]
         18 [ 2 ]
          17 [ 1 ]
        16 [ 6 ]
          15 [ 1 ]
         14 [ 3 ]
          13 [ 1 ]
      12 [ 25 ]
         11 [ 2 ]
          10 [ 1 ]
        9 [ 5 ]
         8 [ 2 ]
          7 [ 1 ]
       6 [ 12 ]
         5 [ 2 ]
          4 [ 1 ]
        3 [ 6 ]
          2 [ 1 ]
         1 [ 3 ]
          0 [ 1 ]
      >>> t = SortedSet(range(25))
      >>> trace(t.root)
         24
          23
        22
         21
          20
       19
         18
          17
        16
          15
         14
          13
      12
         11
          10
        9
         8
          7
       6
         5
          4
        3
          2
         1
          0

  `key`

    Returns: | Key stored in this node.

  `key_fn`

    Returns: | A function mapping items’ keys to comparable keys.

    This function is synthesized from the parameters passed to the container (either a key
      function, a comparison function, or none), and is guaranteed to produce the same ordering used by the tree.
  `left`

    Returns: | Left child node, or `None` if there isn’t any.

  `metadata`

    Returns: | Metadata stored in this node, or `None` if there isn’t any.

  `right`

    Returns: | Right child node, or `None` if there isn’t any.

## Node Updators

Optional node-updating classes which can be used to augment functionality. See Augmenting Trees for a detailed explanation.

Note

This section can be skipped if all that is needed are efficient sorted drop-in replacemnt containers for Python’s sets and dicts.

### `OverlappingIntervalsUpdator`

class `banyan.``OverlappingIntervalsUpdator`
  Updates nodes by the maximum of the intervals specified by their keys. Allows trees employing this to
    efficiently answer which intervals overlap a point or interval.

  Example:

      >>> t = SortedSet([(1, 3), (2, 4), (-2, 9)], updator = OverlappingIntervalsUpdator)
      >>>
      >>> print(t.overlap_point(-5))
      []
      >>> print(t.overlap_point(5))
      [(-2, 9)]
      >>> print(t.overlap_point(3.5))
      [(-2, 9), (2, 4)]
      >>>
      >>> print(t.overlap((-10, 10)))
      [(1, 3), (-2, 9), (2, 4)]

  Note

  The keys used with this updator must support the sequence protocol and be rich comparable, otherwise an exception will be thrown. The begining and end of an interval k are k[0] and k[1].

  Examples:

      >>> SortedSet([1, 3, 2], updator = OverlappingIntervalsUpdator)
      Traceback (most recent call last):
        ...
      TypeError: 2
      >>>
      >>> t = SortedSet([(1, 2, 3), (4, 5, 6, 7)], updator = OverlappingIntervalsUpdator)
      >>> # As far as this tree is concerened, the intervals are (1, 2) and (4, 5).
      >>> print(t.overlap_point(1.5))
      [(1, 2, 3)]

  `overlap`(range_)

    Returns: | Keys overlapping range_.

    Example:

        >>> t = SortedDict.fromkeys([(1, 3), (2, 4), (-2, 9)], updator = OverlappingIntervalsUpdator)
        >>> print(t.overlap((-10, 10)))
        [(1, 3), (-2, 9), (2, 4)]

  `overlap_point`(point)

    Returns: | Keys overlapping point.

    Example:

        >>> t = SortedDict.fromkeys([(1, 3), (2, 4), (-2, 9)], updator = OverlappingIntervalsUpdator)
        >>> print(t.overlap_point(-5))
        []
        >>> print(t.overlap_point(5))
        [(-2, 9)]
        >>> print(t.overlap_point(3.5))
        [(-2, 9), (2, 4)]

### `RankUpdator`

class `banyan.``RankUpdator`
  Updates nodes by the size of their subtree. Allows trees employing this to efficiently answer
    queries such as “what is the k-th key?” and “what is the order of key ‘a’ in the collection?”.

  Example:

      >>> t = SortedSet(['hao', 'jiu', 'mei', 'jian'], updator = RankUpdator)
      >>> t
      SortedSet(['hao', 'jian', 'jiu', 'mei'])
      >>>
      >>> # 'hao' is item no. 0
      >>> t.kth(0)
      'hao'
      >>> t.order('hao')
      0
      >>>
      >>> # 'mei' is item no. 3
      >>> t.kth(3)
      'mei'
      >>> t.order('mei')
      3

  `kth`(k)

    Returns: | k-th key
    Raises : | `IndexError` if k is too small (negative) or too large (exceeds the order of the largest item).

  `order`(key)

    Returns: | The order of key in the keys of the container.

### `MinGapUpdator`

class `banyan.``MinGapUpdator`
  Updates nodes by the minimum, maximum, and min-gaps of their subtrees. Allows trees employing this to
    efficiently answer what is the smallest gap in their keys.

  Example:

      >>> t = SortedSet([1, 3, 2], updator = MinGapUpdator)
      >>>
      >>> t
      SortedSet([1, 2, 3])
      >>> print(t.min_gap())
      1
      >>>
      >>> t.remove(2)
      >>> t
      SortedSet([1, 3])
      >>> print(t.min_gap())
      2
      >>> t.add(1.0001)
      >>> t
      SortedSet([1, 1.0001, 3])
      >>> print(t.min_gap())
      0.0001

  Note

  The keys used with this updator must support the number protocol and be rich comparable, otherwise an exception will be thrown.

  Example:

      >>> t = SortedSet(['1', '3', '2'], updator = MinGapUpdator)
      Traceback (most recent call last):
        ...
      TypeError: Failed to subtract

  `min_gap`()

    Returns: | Smallest gap between the keys.
    Raises : | `RuntimeError` if there are fewer than two keys in the set.

    Example:

        >>> t = SortedSet([1, 3, 2], updator = MinGapUpdator)
        >>>
        >>> t.min_gap()
        1
        >>> t.remove(2)
        >>> t.min_gap()
        2
        >>> t.remove(1)
        >>> # The min gap is now undefined.
        >>> t.min_gap()
        Traceback (most recent call last):
          ...
        RuntimeError: Min-gap undefined

### Navigation

- index
- modules |
- previous |
- Banyan 0.1.3 documentation »