========= Reference ========= .. automodule:: banyan ----------- Collections ----------- Can be used as drop-in sorted alternatives to Python's `built-in collection types`_. .. _`built-in collection types`: http://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset .. _sorted_set_class: ``SortedSet`` ~~~~~~~~~~~~~ .. autoclass:: SortedSet :members: :inherited-members: .. automethod:: __and__ :param iterable other: 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]) .. automethod:: __contains__ :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 .. automethod:: __eq__ :param iterable other: A sequence of items. :returns: Whether this set is equal to the set of other. Example: :: >>> assert SortedSet([1, 3, 2]) == [1, 2, 3] .. automethod:: __ge__ :param iterable other: 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] .. automethod:: __gt__ :param other: A sequence of items. :type other: iterable :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] .. automethod:: __init__ .. automethod:: __iter__ .. automethod:: __le__ :param other: A sequence of items. :type others: iterable :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] .. automethod:: __len__ :returns: Number of items in the set. Example: :: >>> assert len(SortedSet([1, 3, 2, 2])) == 3 .. automethod:: __lt__ :param iterable other: 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] .. automethod:: __ne__ :param other: A sequence of items. :type other: iterable :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] .. automethod:: __or__ :param iterable other: 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]) .. automethod:: __reduce__ .. automethod:: __sub__ :param iterable other: Other items. :returns: The difference of the items in this set and those in other. Example: :: >>> SortedSet([1, 3, 2]) - [3, 1] SortedSet([2]) .. automethod:: __xor__ :param iterable other: 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]) .. automethod:: 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 .. automethod:: pop Removes an arbitrary item from the set. :returns: item removed. :raises: :py:exc:`KeyError` if the set is empty. Example: :: >>> t = SortedSet([1, 2, 3]) >>> len(t) 3 >>> t.pop() 1 >>> assert len(t) == 2 .. _sorted_dict_class: ``SortedDict`` ~~~~~~~~~~~~~~ .. autoclass:: SortedDict :members: :inherited-members: .. automethod:: __contains__ :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 .. automethod:: __delitem__ :param key: Key or key range. :type key: Key object or slice :raises: :py:exc:`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 .. automethod:: __getitem__ :param y: Key or key range. :type y: Key object or slice :returns: The value mapped by y if key is a single key, oterwise a tuple of values. :raises: :py:exc:`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', ) .. automethod:: __init__ .. automethod:: __iter__ .. automethod:: __len__ :returns: Number of items in the set. Example: :: >>> len(SortedDict([(1, 'a'), (2, 'b'), (1, 'c')])) 2 .. automethod:: __reduce__ .. automethod:: __setitem__ :param key: Key or key range. :type key: Key object or slice :param val: Value to be mapped to key, or iterable of values to be mapped to key range. :raises: :py:exc:`ValueError` if a key range is given, and val is not a sequence of the same length, and :py:exc:`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) .. automethod:: popitem .. automethod:: setdefault 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' .. _frozen_sorted_set_class: ``FrozenSortedSet`` ~~~~~~~~~~~~~~~~~~~ .. autoclass:: FrozenSortedSet :members: :inherited-members: .. automethod:: __and__ :param iterable other: 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]) .. automethod:: __contains__ :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 .. automethod:: __eq__ :param other: A sequence of items. :type other: iterable :returns: Whether this set is equal to the set of other. Example: :: >>> assert FrozenSortedSet([1, 3, 2]) == [1, 2, 3] .. automethod:: __ge__ .. automethod:: __gt__ :param other: A sequence of items. :type other: iterable :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] .. automethod:: __hash__ .. automethod:: __init__ .. automethod:: __iter__ .. automethod:: __le__ :param other: A sequence of items. :type others: iterable :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] .. automethod:: __len__ :returns: Number of items in the set. Example: :: >>> assert len(FrozenSortedSet([1, 3, 2, 2])) == 3 .. automethod:: __lt__ :param iterable other: 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] .. automethod:: __ne__ :param other: A sequence of items. :type other: iterable :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] .. automethod:: __or__ :param iterable other: 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]) .. automethod:: __reduce__ .. automethod:: __sub__ :param iterable other: Other items. :returns: The difference of the items in this set and those in other. Example: :: >>> FrozenSortedSet([1, 3, 2]) - [3, 1] FrozenSortedSet([2]) .. automethod:: __xor__ :param iterable other: 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]) .. _frozen_sorted_dict_class: ``FrozenSortedDict`` ~~~~~~~~~~~~~~~~~~~~ .. autoclass:: FrozenSortedDict :members: :inherited-members: .. automethod:: __contains__ :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 .. automethod:: __getitem__ :param key: Key or key range. :type key: Key object or slice :returns: The value mapped by key if key is a single key, oterwise a tuple of values. :raises: :py:exc:`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', ) .. automethod:: __init__ .. automethod:: __hash__ .. automethod:: __iter__ .. automethod:: __len__ :returns: Number of items in the set. Example: :: >>> len(FrozenSortedDict([(1, 'a'), (2, 'b'), (1, 'c')])) 2 .. automethod:: __reduce__ ----- 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. .. _`keys view`: http://docs.python.org/dev/library/stdtypes.html#dict-views .. autoclass:: KeysView ``ValuesView`` ~~~~~~~~~~~~~~ A dynamic `values view`_ of the dict's values. .. _`values view`: http://docs.python.org/dev/library/stdtypes.html#dict-views .. autoclass:: ValuesView ``ItemsView`` ~~~~~~~~~~~~~ A dynamic `items view`_ of the dict's items. .. _`items view`: http://docs.python.org/dev/library/stdtypes.html#dict-views .. autoclass:: ItemsView .. node_class: ``Node`` ~~~~~~~~ .. autoclass:: Node :members: .. _predf_node_updators: ------------- Node Updators ------------- Optional node-updating classes which can be used to `augment functionality`_. See :doc:`augmenting` for a detailed explanation. .. _`augment functionality`: http://www.cs.cmu.edu/~avrim/451/lectures/lect0927.txt .. 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`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. autoclass:: OverlappingIntervalsUpdator :members: ``RankUpdator`` ~~~~~~~~~~~~~~~ .. autoclass:: RankUpdator :members: ``MinGapUpdator`` ~~~~~~~~~~~~~~~~~ .. autoclass:: MinGapUpdator :members: