third_party/bintrees/README.txt

   1 Binary Tree Package
   2 ===================
   3
   4 Abstract
   5 ========
   6
   7 This package provides Binary- RedBlack- and AVL-Trees written in Python and Cython.
   8
   9 This Classes are much slower than the built-in dict class, but all
  10 iterators/generators yielding data in sorted key order.
  11
  12 Source of Algorithms
  13 --------------------
  14
  15 AVL- and RBTree algorithms taken from Julienne Walker: http://eternallyconfuzzled.com/jsw_home.aspx
  16
  17 Trees written in Python (only standard library)
  18 -----------------------------------------------
  19
  20     - *BinaryTree* -- unbalanced binary tree
  21     - *AVLTree* -- balanced AVL-Tree
  22     - *RBTree* -- balanced Red-Black-Tree
  23
  24 Trees written with C-Functions and Cython as wrapper
  25 ----------------------------------------------------
  26
  27     - *FastBinaryTree* -- unbalanced binary tree
  28     - *FastAVLTree* -- balanced AVL-Tree
  29     - *FastRBTree* -- balanced Red-Black-Tree
  30
  31 All trees provides the same API, the pickle protocol is supported.
  32
  33 FastXTrees has C-structs as tree-node structure and C-implementation for low level
  34 operations: insert, remove, get_value, max_item, min_item.
  35
  36 Constructor
  37 ~~~~~~~~~~~
  38
  39     * Tree() -> new empty tree;
  40     * Tree(mapping) -> new tree initialized from a mapping (requires only an items() method)
  41     * Tree(seq) -> new tree initialized from seq [(k1, v1), (k2, v2), ... (kn, vn)]
  42
  43 Methods
  44 ~~~~~~~
  45
  46     * __contains__(k) -> True if T has a key k, else False, O(log(n))
  47     * __delitem__(y) <==> del T[y], del[s:e], O(log(n))
  48     * __getitem__(y) <==> T[y], T[s:e], O(log(n))
  49     * __iter__() <==> iter(T)
  50     * __len__() <==> len(T), O(1)
  51     * __max__() <==> max(T), get max item (k,v) of T, O(log(n))
  52     * __min__() <==> min(T), get min item (k,v) of T, O(log(n))
  53     * __and__(other) <==> T & other, intersection
  54     * __or__(other) <==> T | other, union
  55     * __sub__(other) <==> T - other, difference
  56     * __xor__(other) <==> T ^ other, symmetric_difference
  57     * __repr__() <==> repr(T)
  58     * __setitem__(k, v) <==> T[k] = v, O(log(n))
  59     * clear() -> None, remove all items from T, O(n)
  60     * copy() -> a shallow copy of T, O(n*log(n))
  61     * discard(k) -> None, remove k from T, if k is present, O(log(n))
  62     * get(k[,d]) -> T[k] if k in T, else d, O(log(n))
  63     * is_empty() -> True if len(T) == 0, O(1)
  64     * items([reverse]) -> generator for (k, v) items of T, O(n)
  65     * keys([reverse]) -> generator for keys of T, O(n)
  66     * values([reverse]) -> generator for values of  T, O(n)
  67     * pop(k[,d]) -> v, remove specified key and return the corresponding value, O(log(n))
  68     * popitem() -> (k, v), remove and return some (key, value) pair as a 2-tuple, O(log(n))
  69     * setdefault(k[,d]) -> T.get(k, d), also set T[k]=d if k not in T, O(log(n))
  70     * update(E) -> None.  Update T from dict/iterable E, O(E*log(n))
  71     * foreach(f, [order]) -> visit all nodes of tree (0 = 'inorder', -1 = 'preorder' or +1 = 'postorder') and call f(k, v) for each node, O(n)
  72
  73 slicing by keys
  74 ~~~~~~~~~~~~~~~
  75
  76     * itemslice(s, e) -> generator for (k, v) items of T for s <= key < e, O(n)
  77     * keyslice(s, e) -> generator for keys of T for s <= key < e, O(n)
  78     * valueslice(s, e) -> generator for values of T for s <= key < e, O(n)
  79     * T[s:e] -> TreeSlice object, with keys in range s <= key < e, O(n)
  80     * del T[s:e] -> remove items by key slicing, for s <= key < e, O(n)
  81
  82     start/end parameter:
  83
  84     * if 's' is None or T[:e] TreeSlice/iterator starts with value of min_key();
  85     * if 'e' is None or T[s:] TreeSlice/iterator ends with value of max_key();
  86     * T[:] is a TreeSlice which represents the whole tree;
  87
  88     TreeSlice is a tree wrapper with range check, and contains no references
  89     to objects, deleting objects in the associated tree also deletes the object
  90     in the TreeSlice.
  91
  92     * TreeSlice[k] -> get value for key k, raises KeyError if k not exists in range s:e
  93     * TreeSlice[s1:e1] -> TreeSlice object, with keys in range s1 <= key < e1
  94         - new lower bound is max(s, s1)
  95         - new upper bound is min(e, e1)
  96
  97     TreeSlice methods:
  98
  99     * items() -> generator for (k, v) items of T, O(n)
 100     * keys() -> generator for keys of T, O(n)
 101     * values() -> generator for values of  T, O(n)
 102     * __iter__ <==> keys()
 103     * __repr__ <==> repr(T)
 104     * __contains__(key)-> True if TreeSlice has a key k, else False, O(log(n))
 105
 106 prev/succ operations
 107 ~~~~~~~~~~~~~~~~~~~~
 108
 109     * prev_item(key) -> get (k, v) pair, where k is predecessor to key, O(log(n))
 110     * prev_key(key) -> k, get the predecessor of key, O(log(n))
 111     * succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key, O(log(n))
 112     * succ_key(key) -> k, get the successor of key, O(log(n))
 113     * floor_item(key) -> get (k, v) pair, where k is the greatest key less than or equal to key, O(log(n))
 114     * floor_key(key) -> k, get the greatest key less than or equal to key, O(log(n))
 115     * ceiling_item(key) -> get (k, v) pair, where k is the smallest key greater than or equal to key, O(log(n))
 116     * ceiling_key(key) -> k, get the smallest key greater than or equal to key, O(log(n))
 117
 118 Heap methods
 119 ~~~~~~~~~~~~
 120
 121     * max_item() -> get largest (key, value) pair of T, O(log(n))
 122     * max_key() -> get largest key of T, O(log(n))
 123     * min_item() -> get smallest (key, value) pair of T, O(log(n))
 124     * min_key() -> get smallest key of T, O(log(n))
 125     * pop_min() -> (k, v), remove item with minimum key, O(log(n))
 126     * pop_max() -> (k, v), remove item with maximum key, O(log(n))
 127     * nlargest(i[,pop]) -> get list of i largest items (k, v), O(i*log(n))
 128     * nsmallest(i[,pop]) -> get list of i smallest items (k, v), O(i*log(n))
 129
 130 Set methods (using frozenset)
 131 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 132
 133     * intersection(t1, t2, ...) -> Tree with keys *common* to all trees
 134     * union(t1, t2, ...) -> Tree with keys from *either* trees
 135     * difference(t1, t2, ...) -> Tree with keys in T but not any of t1, t2, ...
 136     * symmetric_difference(t1) -> Tree with keys in either T and t1  but not both
 137     * issubset(S) -> True if every element in T is in S
 138     * issuperset(S) -> True if every element in S is in T
 139     * isdisjoint(S) ->  True if T has a null intersection with S
 140
 141 Classmethods
 142 ~~~~~~~~~~~~
 143
 144     * fromkeys(S[,v]) -> New tree with keys from S and values equal to v.
 145
 146 Performance
 147 ===========
 148
 149 Profiling with timeit(): 5000 unique random int keys, time in seconds
 150
 151 ========================  =============  ==============  ==============  ==============
 152 unbalanced Trees          CPython 2.7.2  FastBinaryTree  ipy 2.7.0       pypy 1.7.0
 153 ========================  =============  ==============  ==============  ==============
 154 build time 100x            7,55           0,60            2,51            0,29
 155 build & delete time 100x  13,34           1,48            4,45            0,47
 156 search 100x all keys       2,86           0,96            0,27            0,06
 157 ========================  =============  ==============  ==============  ==============
 158
 159 ========================  =============  ==============  ==============  ==============
 160 AVLTrees                  CPython 2.7.2  FastAVLTree     ipy 2.7.0       pypy 1.7.0
 161 ========================  =============  ==============  ==============  ==============
 162 build time 100x           22,66           0,65           10,45            1,29
 163 build & delete time 100x  36,71           1,47           20,89            3,02
 164 search 100x all keys       2,34           0,85            0,89            0,14
 165 ========================  =============  ==============  ==============  ==============
 166
 167 ========================  =============  ==============  ==============  ==============
 168 RBTrees                   CPython 2.7.2  FastRBTree      ipy 2.7.0       pypy 1.7.0
 169 ========================  =============  ==============  ==============  ==============
 170 build time 100x           14,78           0,65            4,43            0,49
 171 build & delete time 100x  39,34           1,63           12,43            1,32
 172 search 100x all keys       2,32           0,86            0,86            0,13
 173 ========================  =============  ==============  ==============  ==============
 174
 175 News
 176 ====
 177
 178 Version 1.0.1 February 2013
 179
 180   * bug fixes
 181   * refactorings by graingert
 182   * skip useless tests for pypy
 183   * new license: MIT License
 184   * tested with CPython2.7, CPython3.2, CPython3.3, pypy-1.9, pypy-2.0-beta1
 185   * unified line endings to LF
 186   * PEP8 refactorings
 187   * added floor_item/key, ceiling_item/key methods, thanks to Dai Mikurube
 188
 189 Version 1.0.0
 190
 191   * bug fixes
 192   * status: 5 - Production/Stable
 193   * removed useless TreeIterator() class and T.treeiter() method.
 194   * patch from Max Motovilov to use Visual Studio 2008 for building C-extensions
 195
 196 Version 0.4.0
 197
 198   * API change!!!
 199   * full Python 3 support, also for Cython implementations
 200   * removed user defined compare() function - keys have to be comparable!
 201   * removed T.has_key(), use 'key in T'
 202   * keys(), items(), values() generating 'views'
 203   * removed iterkeys(), itervalues(), iteritems() methods
 204   * replaced index slicing by key slicing
 205   * removed index() and item_at()
 206   * repr() produces a correct representation
 207   * installs on systems without cython (tested with pypy)
 208   * new license: GNU Library or Lesser General Public License (LGPL)
 209
 210 Installation
 211 ============
 212
 213 from source::
 214
 215     python setup.py install
 216
 217 Download
 218 ========
 219
 220 http://bitbucket.org/mozman/bintrees/downloads
 221
 222 Documentation
 223 =============
 224
 225 this README.txt
 226
 227 bintrees can be found on bitbucket.org at:
 228
 229 http://bitbucket.org/mozman/bintrees