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 (int, float, str, bytes, unicode (for pre Py3) , (int, int), (float, float), 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()
1
>>> 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 (int, float, str, bytes, unicode (for pre Py3) , (int, int), (float, float), 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()
(1, 'a')
>>> 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()
(1, 'a')
>>> 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 (int, float, str, bytes, unicode (for pre Py3) , (int, int), (float, float), 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 (int, float, str, bytes, unicode (for pre Py3) , (int, int), (float, float), 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)))
[(-2, 9), (1, 3), (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)))
[(-2, 9), (1, 3), (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

Reference¶

Collections¶

`SortedSet`¶

`SortedDict`¶

`FrozenSortedSet`¶

`FrozenSortedDict`¶

Views¶

`KeysView`¶

`ValuesView`¶

`ItemsView`¶

`Node`¶

Node Updators¶

`OverlappingIntervalsUpdator`¶

`RankUpdator`¶

`MinGapUpdator`¶

Table Of Contents

Previous topic

This Page

Navigation

Reference¶

Collections¶

SortedSet¶

SortedDict¶

FrozenSortedSet¶

FrozenSortedDict¶

Views¶

KeysView¶

ValuesView¶

ItemsView¶

Node¶

Node Updators¶

OverlappingIntervalsUpdator¶

RankUpdator¶

MinGapUpdator¶

Table Of Contents

Previous topic

This Page

Quick search

Navigation

`SortedSet`¶

`SortedDict`¶

`FrozenSortedSet`¶

`FrozenSortedDict`¶

`KeysView`¶

`ValuesView`¶

`ItemsView`¶

`Node`¶

`OverlappingIntervalsUpdator`¶

`RankUpdator`¶

`MinGapUpdator`¶