src/third_party/bintrees/bintrees/__init__.py

   1 #!/usr/bin/env python
   2 #coding:utf-8
   3 # Author:  mozman
   4 # Purpose: binary trees package
   5 # Created: 03.05.2010
   6 # Copyright (c) 2010-2013 by Manfred Moitzi
   7 # License: MIT License
   8
   9 from __future__ import absolute_import
  10
  11 __doc__ = """
  12 Binary Tree Package
  13 ===================
  14
  15 Python Trees
  16 ------------
  17
  18 Balanced and unbalance binary trees written in pure Python with a dict-like API.
  19
  20 Classes
  21 ~~~~~~~
  22 * BinaryTree -- unbalanced binary tree
  23 * AVLTree -- balanced AVL-Tree
  24 * RBTree -- balanced Red-Black-Tree
  25
  26 Cython Trees
  27 ------------
  28
  29 Basic tree functions written in Cython, merged with TreeMixin to provide the
  30 full API of the Python Trees.
  31
  32 Classes
  33 ~~~~~~~
  34
  35 * FastBinaryTree -- unbalanced binary tree
  36 * FastAVLTree -- balanced AVLTree
  37 * FastRBTree -- balanced Red-Black-Tree
  38
  39 Overview of API for all Classes
  40 ===============================
  41
  42 * TreeClass ([compare]) -> new empty tree.
  43 * TreeClass(mapping, [compare]) -> new tree initialized from a mapping
  44 * TreeClass(seq, [compare]) -> new tree initialized from seq [(k1, v1), (k2, v2), ... (kn, vn)]
  45
  46 Methods
  47 -------
  48
  49 * __contains__(k) -> True if T has a key k, else False, O(log(n))
  50 * __delitem__(y) <==> del T[y], O(log(n))
  51 * __getitem__(y) <==> T[y], O(log(n))
  52 * __iter__() <==> iter(T)
  53 * __len__() <==> len(T), O(1)
  54 * __max__() <==> max(T), get max item (k,v) of T, O(log(n))
  55 * __min__() <==> min(T), get min item (k,v) of T, O(log(n))
  56 * __and__(other) <==> T & other, intersection
  57 * __or__(other) <==> T | other, union
  58 * __sub__(other) <==> T - other, difference
  59 * __xor__(other) <==> T ^ other, symmetric_difference
  60 * __repr__() <==> repr(T)
  61 * __setitem__(k, v) <==> T[k] = v, O(log(n))
  62 * clear() -> None, Remove all items from T, , O(n)
  63 * copy() -> a shallow copy of T, O(n*log(n))
  64 * discard(k) -> None, remove k from T, if k is present, O(log(n))
  65 * get(k[,d]) -> T[k] if k in T, else d, O(log(n))
  66 * is_empty() -> True if len(T) == 0, O(1)
  67 * items([reverse]) -> list of T's (k, v) pairs, as 2-tuples, O(n)
  68 * keys([reverse]) -> list of T's keys, O(n)
  69 * pop(k[,d]) -> v, remove specified key and return the corresponding value, O(log(n))
  70 * popitem() -> (k, v), remove and return some (key, value) pair as a 2-tuple, O(log(n))
  71 * setdefault(k[,d]) -> T.get(k, d), also set T[k]=d if k not in T, O(log(n))
  72 * update(E) -> None.  Update T from dict/iterable E, O(E*log(n))
  73 * values([reverse]) -> list of T's values, O(n)
  74
  75 walk forward/backward, O(log(n))
  76
  77 * prev_item(key) -> get (k, v) pair, where k is predecessor to key, O(log(n))
  78 * prev_key(key) -> k, get the predecessor of key, O(log(n))
  79 * succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key, O(log(n))
  80 * succ_key(key) -> k, get the successor of key, O(log(n))
  81
  82 slicing by keys
  83
  84 * itemslice(s, e) -> generator for (k, v) items of T for s <= key < e, O(n)
  85 * keyslice(s, e) -> generator for keys of T for s <= key < e, O(n)
  86 * valueslice(s, e) -> generator for values of T for s <= key < e, O(n)
  87 * T[s:e] -> TreeSlice object, with keys in range s <= key < e, O(n)
  88 * del T[s:e] -> remove items by key slicing, for s <= key < e, O(n)
  89
  90 if 's' is None or T[:e] TreeSlice/iterator starts with value of min_key()
  91 if 'e' is None or T[s:] TreeSlice/iterator ends with value of max_key()
  92 T[:] is a TreeSlice which represents the whole tree.
  93
  94 TreeSlice is a tree wrapper with range check, and contains no references
  95 to objects, deleting objects in the associated tree also deletes the object
  96 in the TreeSlice.
  97
  98 * TreeSlice[k] -> get value for key k, raises KeyError if k not exists in range s:e
  99 * TreeSlice[s1:e1] -> TreeSlice object, with keys in range s1 <= key < e1
 100
 101   * new lower bound is max(s, s1)
 102   * new upper bound is min(e, e1)
 103
 104 TreeSlice methods:
 105
 106 * items() -> generator for (k, v) items of T, O(n)
 107 * keys() -> generator for keys of T, O(n)
 108 * values() -> generator for values of  T, O(n)
 109 * __iter__ <==> keys()
 110 * __repr__ <==> repr(T)
 111 * __contains__(key)-> True if TreeSlice has a key k, else False, O(log(n))
 112
 113 Heap methods
 114
 115 * max_item() -> get biggest (key, value) pair of T, O(log(n))
 116 * max_key() -> get biggest key of T, O(log(n))
 117 * min_item() -> get smallest (key, value) pair of T, O(log(n))
 118 * min_key() -> get smallest key of T, O(log(n))
 119 * pop_min() -> (k, v), remove item with minimum key, O(log(n))
 120 * pop_max() -> (k, v), remove item with maximum key, O(log(n))
 121 * nlargest(i[,pop]) -> get list of i largest items (k, v), O(i*log(n))
 122 * nsmallest(i[,pop]) -> get list of i smallest items (k, v), O(i*log(n))
 123
 124 Set methods (using frozenset)
 125
 126 * intersection(t1, t2, ...) -> Tree with keys *common* to all trees
 127 * union(t1, t2, ...) -> Tree with keys from *either* trees
 128 * difference(t1, t2, ...) -> Tree with keys in T but not any of t1, t2, ...
 129 * symmetric_difference(t1) -> Tree with keys in either T and t1  but not both
 130 * issubset(S) -> True if every element in T is in S
 131 * issuperset(S) -> True if every element in S is in T
 132 * isdisjoint(S) ->  True if T has a null intersection with S
 133
 134 Classmethods
 135
 136 * fromkeys(S[,v]) -> New tree with keys from S and values equal to v.
 137 """
 138
 139 __all__ = [
 140     'FastBinaryTree',
 141     'FastAVLTree',
 142     'FastRBTree',
 143     'BinaryTree',
 144     'AVLTree',
 145     'RBTree'
 146 ]
 147
 148 from .treemixin import TreeMixin
 149 from .bintree import BinaryTree
 150 from .avltree import AVLTree
 151 from .rbtree import RBTree
 152
 153 try:
 154     from .qbintree import cBinaryTree
 155
 156     class FastBinaryTree(cBinaryTree, TreeMixin):
 157         """ Faster unbalanced binary tree  written in Cython with C-Code. """
 158 except ImportError:  # fall back to pure Python version
 159     FastBinaryTree = BinaryTree
 160 except ValueError:  # for pypy
 161     FastBinaryTree = BinaryTree
 162
 163 try:
 164     from .qavltree import cAVLTree
 165
 166     class FastAVLTree(cAVLTree, TreeMixin):
 167         """ Faster balanced AVL-Tree written in Cython with C-Code. """
 168 except ImportError:  # fall back to pure Python version
 169     FastAVLTree = AVLTree
 170 except ValueError:  # for pypy
 171     FastAVLTree = AVLTree
 172
 173 try:
 174     from .qrbtree import cRBTree
 175
 176     class FastRBTree(cRBTree, TreeMixin):
 177         """ Faster balanced Red-Black-Tree  written in Cython with C-Code. """
 178 except ImportError:  # fall back to pure Python version
 179     FastRBTree = RBTree
 180 except ValueError:  # for pypy
 181     FastRBTree = RBTree