artemis.externals.accumulation_tree.abctree

Module Contents

artemis.externals.accumulation_tree.abctree.PYPY

class artemis.externals.accumulation_tree.abctree._ABCTree

Bases: object

Abstract-Base-Class for ABCTree and Cython trees.

count – get node count

get_value(…)

get_value(key) -> returns value for key

insert(…)

insert(key, value) <==> T[key] = value, insert key into T

remove(…)

remove(key) <==> del T[key], remove key from T

clear(…)

T.clear() -> None. Remove all items from T.

iter_items(…)

iter_items(s, e, [reverse]) -> iterate over all items with keys in range s <= key < e, yielding (k, v) tuple

foreach(…)

foreach(f, [order]) -> visit all nodes of tree and call f(k, v) for each node

pop_item(…)

T.pop_item() -> (k, v), remove and return some (key, value)

min_item(…)

min_item() -> get smallest (key, value) pair of T

max_item(…)

max_item() -> get largest (key, value) pair of T

prev_item(…)

prev_item(key) -> get (k, v) pair, where k is predecessor to key

succ_item(…)

succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key

floor_item(…)

floor_item(key) -> get (k, v) pair, where k is the greatest key less than or equal to key

ceiling_item(…)

ceiling_item(key) -> get (k, v) pair, where k is the smallest key greater than or equal to key

• __contains__(k) -> True if T has a key k, else False, O(log(n))

• __delitem__(y) <==> del T[y], del T[s:e], O(log(n))

• __getitem__(y) <==> T[y], T[s:e], O(log(n))

• __iter__() <==> iter(T)

• __len__() <==> len(T), O(1)

• __max__() <==> max(T), get max item (k,v) of T, O(log(n))

• __min__() <==> min(T), get min item (k,v) of T, O(log(n))

• __and__(other) <==> T & other, intersection

• __or__(other) <==> T | other, union

• __sub__(other) <==> T - other, difference

• __xor__(other) <==> T ^ other, symmetric_difference

• __repr__() <==> repr(T)

• __setitem__(k, v) <==> T[k] = v, O(log(n))

• clear() -> None, remove all items from T, , O(n)

• remove_items(keys) -> None, remove items by keys

• copy() -> a shallow copy of T, O(n*log(n))

• discard(k) -> None, remove k from T, if k is present, O(log(n))

• get(k[,d]) -> T[k] if k in T, else d, O(log(n))

• is_empty() -> True if len(T) == 0, O(1)

• keys([reverse]) -> generator for keys of T, O(n)

• values([reverse]) -> generator for values of T, O(n)

• pop(k[,d]) ->

  v, remove specified key and return the corresponding value, O(log(n))

• set_default(k[,d]) ->

  value, T.get(k, d), also set T[k]=d if k not in T, O(log(n))

• update(E) -> None. Update T from dict/iterable E, O(E*log(n))

slicing by keys

• key_slice(s, e[, reverse]) ->

  generator for keys of T for s <= key < e, O(n)

• value_slice(s, e[, reverse]) ->

  generator for values of T for s <= key < e, O(n)

• item_slice(s, e[, reverse]) ->

  generator for items of T for s <= key < e, O(n)

• T[s:e] -> TreeSlice object, with keys in range s <= key < e, O(n)

• del T[s:e] -> remove items by key slicing, for s <= key < e, O(n)

if ‘s’ is None or T[:e] TreeSlice/iterator starts with value of min_key() if ‘e’ is None or T[s:] TreeSlice/iterator ends with value of max_key() T[:] is a TreeSlice which represents the whole tree.

TreeSlice is a tree wrapper with range check and contains no references to objects, deleting objects in the associated tree also deletes the object in the TreeSlice.

• TreeSlice[k] ->

  get value for key k, raises KeyError if k not exists in range s:e

• TreeSlice[s1:e1] -> TreeSlice object, with keys in range s1 <= key < e1

  • new lower bound is max(s, s1)

  • new upper bound is min(e, e1)

TreeSlice methods:

• items() -> generator for (k, v) items of T, O(n)

• keys() -> generator for keys of T, O(n)

• values() -> generator for values of T, O(n)

• __iter__ <==> keys()

• __repr__ <==> repr(T)

• __contains__(key)-> True if TreeSlice has a key k, else False, O(log(n))

prev/succ operations

• prev_key(key) -> k, get the predecessor of key, O(log(n))

• succ_key(key) -> k, get the successor of key, O(log(n))

• floor_key(key) -> k,

  get the greatest key less than or equal to key, O(log(n))

• ceiling_key(key) -> k,

  get the smallest key greater than or equal to key, O(log(n))

Heap methods

• max_key() -> get largest key of T, O(log(n))

• min_key() -> get smallest key of T, O(log(n))

• pop_min() -> (k, v), remove item with minimum key, O(log(n))

• pop_max() -> (k, v), remove item with maximum key, O(log(n))

• nlargest(i[,pop]) -> get list of i largest items (k, v), O(i*log(n))

• nsmallest(i[,pop]) -> get list of i smallest items (k, v), O(i*log(n))

Set methods (using frozenset)

• intersection(t1, t2, …) -> Tree with keys common to all trees

• union(t1, t2, …) -> Tree with keys from either trees

• difference(t1, t2, …) -> Tree with keys in T but not any of t1, t2, …

• symmetric_difference(t1) ->

  Tree with keys in either T and t1 but not both

• is_subset(S) -> True if every element in T is in S

• is_superset(S) -> True if every element in S is in T

• is_disjoint(S) -> True if T has a null intersection with S

Classmethods

• from_keys(S[,v]) -> New tree with keys from S and values equal to v.

__copy__

__iter__

setdefault

fromkeys

issubset

issuperset

isdisjoint

__repr__(self)

T.__repr__(…) <==> repr(x)

copy(self)

T.copy() -> get a shallow copy of T.

__contains__(self, key)

k in T -> True if T has a key k, else False

__len__(self)

T.__len__() <==> len(x)

__min__(self)

T.__min__() <==> min(x)

__max__(self)

T.__max__() <==> max(x)

__and__(self, other)

T.__and__(other) <==> self & other

__or__(self, other)

T.__or__(other) <==> self | other

__sub__(self, other)

T.__sub__(other) <==> self - other

__xor__(self, other)

T.__xor__(other) <==> self ^ other

discard(self, key)

T.discard(k) -> None, remove k from T, if k is present

is_empty(self)

T.is_empty() -> False if T contains any items else True

keys(self, reverse=False)

T.keys([reverse]) -> an iterator over the keys of T, in ascending order if reverse is True, iterate in descending order, reverse defaults to False

__reversed__(self)

values(self, reverse=False)

T.values([reverse]) -> an iterator over the values of T, in ascending order if reverse is True, iterate in descending order, reverse defaults to False

items(self, reverse=False)

T.items([reverse]) -> an iterator over the (key, value) items of T, in ascending order if reverse is True, iterate in descending order, reverse defaults to False

__getitem__(self, key)

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

__setitem__(self, key, value)

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

__delitem__(self, key)

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

remove_items(self, keys)

T.remove_items(keys) -> None, remove items by keys

key_slice(self, start_key, end_key, reverse=False)

T.key_slice(start_key, end_key) -> key iterator: start_key <= key < end_key.

Yields keys in ascending order if reverse is False else in descending order.

value_slice(self, start_key, end_key, reverse=False)

T.value_slice(start_key, end_key) -> value iterator: start_key <= key < end_key.

Yields values in ascending key order if reverse is False else in descending key order.

item_slice(self, start_key, end_key, reverse=False)

T.item_slice(start_key, end_key) -> item iterator: start_key <= key < end_key.

Yields items in ascending key order if reverse is False else in descending key order.

__getstate__(self)

__setstate__(self, state)

set_default(self, key, default=None)

T.set_default(k[,d]) -> T.get(k,d), also set T[k]=d if k not in T

update(self, *args)

T.update(E) -> None. Update T from E : for (k, v) in E: T[k] = v

classmethod from_keys(cls, iterable, value=None)

T.from_keys(S[,v]) -> New tree with keys from S and values equal to v.

get(self, key, default=None)

T.get(k[,d]) -> T[k] if k in T, else d. d defaults to None.

pop(self, key, *args)

T.pop(k[,d]) -> v, remove specified key and return the corresponding value. If key is not found, d is returned if given, otherwise KeyError is raised

prev_key(self, key)

Get predecessor to key, raises KeyError if key is min key or key does not exist.

succ_key(self, key)

Get successor to key, raises KeyError if key is max key or key does not exist.

floor_key(self, key)

Get the greatest key less than or equal to the given key, raises KeyError if there is no such key.

ceiling_key(self, key)

Get the smallest key greater than or equal to the given key, raises KeyError if there is no such key.

pop_min(self)

T.pop_min() -> (k, v), remove item with minimum key, raise ValueError if T is empty.

pop_max(self)

T.pop_max() -> (k, v), remove item with maximum key, raise ValueError if T is empty.

min_key(self)

Get min key of tree, raises ValueError if tree is empty.

max_key(self)

Get max key of tree, raises ValueError if tree is empty.

nsmallest(self, n, pop=False)

T.nsmallest(n) -> get list of n smallest items (k, v). If pop is True, remove items from T.

nlargest(self, n, pop=False)

T.nlargest(n) -> get list of n largest items (k, v). If pop is True remove items from T.

intersection(self, *trees)

T.intersection(t1, t2, …) -> Tree, with keys common to all trees

union(self, *trees)

T.union(t1, t2, …) -> Tree with keys from either trees

difference(self, *trees)

T.difference(t1, t2, …) -> Tree with keys in T but not any of t1, t2, …

symmetric_difference(self, tree)

T.symmetric_difference(t1) -> Tree with keys in either T and t1 but not both

is_subset(self, tree)

T.issubset(tree) -> True if every element in x is in tree

is_superset(self, tree)

T.issubset(tree) -> True if every element in tree is in x

is_disjoint(self, tree)

T.isdisjoint(S) -> True if x has a null intersection with tree

artemis.externals.accumulation_tree.abctree._build_sets(trees)

artemis.externals.accumulation_tree.abctree._multi_tree_get(trees, key)

class artemis.externals.accumulation_tree.abctree.CPYTHON_ABCTree(items=None)

Bases: artemis.externals.accumulation_tree.abctree._ABCTree

Base class for the Python implementation of trees.

insert(…)

insert(key, value) <==> T[key] = value, insert key into T

remove(…)

remove(key) <==> del T[key], remove key from T

• count -> get item count of tree

• __init__() Tree initializer

• get_value(key) -> returns value for key

• clear() -> None. Remove all items from tree.

• iter_items(start_key, end_key, [reverse]) ->

  iterate over all items, yielding (k, v) tuple

• foreach(f, [order]) ->

  visit all nodes of tree and call f(k, v) for each node, O(n)

• pop_item() -> (k, v), remove and return some (key, value)

• min_item() -> get smallest (key, value) pair of T, O(log(n))

• max_item() -> get largest (key, value) pair of T, O(log(n))

• prev_item(key) ->

  get (k, v) pair, where k is predecessor to key, O(log(n))

• succ_item(key) ->

  get (k,v) pair as a 2-tuple, where k is successor to key, O(log(n))

• floor_item(key) ->

  get (k, v) pair, where k is the greatest key less than or equal to key, O(log(n))

• ceiling_item(key) ->

  get (k, v) pair, where k is the smallest key greater than or equal to key, O(log(n))

popitem

clear(self)

T.clear() -> None. Remove all items from T.

property count(self)

Get items count.

get_value(self, key)

pop_item(self)

T.pop_item() -> (k, v), remove and return some (key, value) pair as a 2-tuple; but raise KeyError if T is empty.

foreach(self, func, order=0)

Visit all tree nodes and process key, value.

parm func: function(key, value) param int order: inorder = 0, preorder = -1, postorder = +1

min_item(self)

Get item with min key of tree, raises ValueError if tree is empty.

max_item(self)

Get item with max key of tree, raises ValueError if tree is empty.

succ_item(self, key)

Get successor (k,v) pair of key, raises KeyError if key is max key or key does not exist. optimized for pypy.

prev_item(self, key)

Get predecessor (k,v) pair of key, raises KeyError if key is min key or key does not exist. optimized for pypy.

floor_item(self, key)

Get the element (k,v) pair associated with the greatest key less than or equal to the given key, raises KeyError if there is no such key.

ceiling_item(self, key)

Get the element (k,v) pair associated with the smallest key greater than or equal to the given key, raises KeyError if there is no such key.

iter_items(self, start_key=None, end_key=None, reverse=False)

Iterates over the (key, value) items of the associated tree, in ascending order if reverse is True, iterate in descending order, reverse defaults to False

_iter_items_forward(self, start_key=None, end_key=None)

_iter_items_backward(self, start_key=None, end_key=None)

_iter_items(self, left=attrgetter('left'), right=attrgetter('right'), start_key=None, end_key=None)

_get_in_range_func(self, start_key, end_key)

class artemis.externals.accumulation_tree.abctree.PYPY_ABCTree

Bases: artemis.externals.accumulation_tree.abctree.CPYTHON_ABCTree

iter_items(self, start_key=None, end_key=None, reverse=False)

Iterates over the (key, value) items of the associated tree, in ascending order if reverse is True, iterate in descending order, reverse defaults to False

artemis.externals.accumulation_tree.abctree.ABCTree