12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Binary Tree Package 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)=================== 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Abstract 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======== 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)This package provides Binary- RedBlack- and AVL-Trees written in Python and Cython. 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)This Classes are much slower than the built-in dict class, but all 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)iterators/generators yielding data in sorted key order. 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Source of Algorithms 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)-------------------- 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)AVL- and RBTree algorithms taken from Julienne Walker: http://eternallyconfuzzled.com/jsw_home.aspx 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Trees written in Python (only standard library) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)----------------------------------------------- 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) - *BinaryTree* -- unbalanced binary tree 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) - *AVLTree* -- balanced AVL-Tree 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) - *RBTree* -- balanced Red-Black-Tree 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Trees written with C-Functions and Cython as wrapper 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)---------------------------------------------------- 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) - *FastBinaryTree* -- unbalanced binary tree 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) - *FastAVLTree* -- balanced AVL-Tree 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) - *FastRBTree* -- balanced Red-Black-Tree 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)All trees provides the same API, the pickle protocol is supported. 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)FastXTrees has C-structs as tree-node structure and C-implementation for low level 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)operations: insert, remove, get_value, max_item, min_item. 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Constructor 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)~~~~~~~~~~~ 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Tree() -> new empty tree; 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Tree(mapping) -> new tree initialized from a mapping (requires only an items() method) 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Tree(seq) -> new tree initialized from seq [(k1, v1), (k2, v2), ... (kn, vn)] 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Methods 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)~~~~~~~ 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __contains__(k) -> True if T has a key k, else False, O(log(n)) 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __delitem__(y) <==> del T[y], del[s:e], O(log(n)) 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __getitem__(y) <==> T[y], T[s:e], O(log(n)) 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __iter__() <==> iter(T) 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __len__() <==> len(T), O(1) 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __max__() <==> max(T), get max item (k,v) of T, O(log(n)) 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __min__() <==> min(T), get min item (k,v) of T, O(log(n)) 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __and__(other) <==> T & other, intersection 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __or__(other) <==> T | other, union 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __sub__(other) <==> T - other, difference 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __xor__(other) <==> T ^ other, symmetric_difference 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __repr__() <==> repr(T) 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __setitem__(k, v) <==> T[k] = v, O(log(n)) 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * clear() -> None, remove all items from T, O(n) 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * copy() -> a shallow copy of T, O(n*log(n)) 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * discard(k) -> None, remove k from T, if k is present, O(log(n)) 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * get(k[,d]) -> T[k] if k in T, else d, O(log(n)) 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * is_empty() -> True if len(T) == 0, O(1) 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * items([reverse]) -> generator for (k, v) items of T, O(n) 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * keys([reverse]) -> generator for keys of T, O(n) 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * values([reverse]) -> generator for values of T, O(n) 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * pop(k[,d]) -> v, remove specified key and return the corresponding value, O(log(n)) 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * popitem() -> (k, v), remove and return some (key, value) pair as a 2-tuple, O(log(n)) 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * setdefault(k[,d]) -> T.get(k, d), also set T[k]=d if k not in T, O(log(n)) 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * update(E) -> None. Update T from dict/iterable E, O(E*log(n)) 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * 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) 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)slicing by keys 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)~~~~~~~~~~~~~~~ 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * itemslice(s, e) -> generator for (k, v) items of T for s <= key < e, O(n) 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * keyslice(s, e) -> generator for keys of T for s <= key < e, O(n) 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * valueslice(s, e) -> generator for values of T for s <= key < e, O(n) 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * T[s:e] -> TreeSlice object, with keys in range s <= key < e, O(n) 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * del T[s:e] -> remove items by key slicing, for s <= key < e, O(n) 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) start/end parameter: 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * if 's' is None or T[:e] TreeSlice/iterator starts with value of min_key(); 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * if 'e' is None or T[s:] TreeSlice/iterator ends with value of max_key(); 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * T[:] is a TreeSlice which represents the whole tree; 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) TreeSlice is a tree wrapper with range check, and contains no references 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) to objects, deleting objects in the associated tree also deletes the object 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) in the TreeSlice. 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * TreeSlice[k] -> get value for key k, raises KeyError if k not exists in range s:e 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * TreeSlice[s1:e1] -> TreeSlice object, with keys in range s1 <= key < e1 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) - new lower bound is max(s, s1) 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) - new upper bound is min(e, e1) 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) TreeSlice methods: 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * items() -> generator for (k, v) items of T, O(n) 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * keys() -> generator for keys of T, O(n) 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * values() -> generator for values of T, O(n) 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __iter__ <==> keys() 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __repr__ <==> repr(T) 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * __contains__(key)-> True if TreeSlice has a key k, else False, O(log(n)) 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)prev/succ operations 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)~~~~~~~~~~~~~~~~~~~~ 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * prev_item(key) -> get (k, v) pair, where k is predecessor to key, O(log(n)) 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * prev_key(key) -> k, get the predecessor of key, O(log(n)) 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key, O(log(n)) 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * succ_key(key) -> k, get the successor of key, O(log(n)) 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * floor_item(key) -> get (k, v) pair, where k is the greatest key less than or equal to key, O(log(n)) 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * floor_key(key) -> k, get the greatest key less than or equal to key, O(log(n)) 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * ceiling_item(key) -> get (k, v) pair, where k is the smallest key greater than or equal to key, O(log(n)) 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * ceiling_key(key) -> k, get the smallest key greater than or equal to key, O(log(n)) 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Heap methods 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)~~~~~~~~~~~~ 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * max_item() -> get largest (key, value) pair of T, O(log(n)) 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * max_key() -> get largest key of T, O(log(n)) 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * min_item() -> get smallest (key, value) pair of T, O(log(n)) 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * min_key() -> get smallest key of T, O(log(n)) 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * pop_min() -> (k, v), remove item with minimum key, O(log(n)) 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * pop_max() -> (k, v), remove item with maximum key, O(log(n)) 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * nlargest(i[,pop]) -> get list of i largest items (k, v), O(i*log(n)) 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * nsmallest(i[,pop]) -> get list of i smallest items (k, v), O(i*log(n)) 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Set methods (using frozenset) 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * intersection(t1, t2, ...) -> Tree with keys *common* to all trees 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * union(t1, t2, ...) -> Tree with keys from *either* trees 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * difference(t1, t2, ...) -> Tree with keys in T but not any of t1, t2, ... 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * symmetric_difference(t1) -> Tree with keys in either T and t1 but not both 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * issubset(S) -> True if every element in T is in S 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * issuperset(S) -> True if every element in S is in T 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * isdisjoint(S) -> True if T has a null intersection with S 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Classmethods 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)~~~~~~~~~~~~ 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * fromkeys(S[,v]) -> New tree with keys from S and values equal to v. 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Performance 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)=========== 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Profiling with timeit(): 5000 unique random int keys, time in seconds 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)unbalanced Trees CPython 2.7.2 FastBinaryTree ipy 2.7.0 pypy 1.7.0 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)build time 100x 7,55 0,60 2,51 0,29 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)build & delete time 100x 13,34 1,48 4,45 0,47 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)search 100x all keys 2,86 0,96 0,27 0,06 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)AVLTrees CPython 2.7.2 FastAVLTree ipy 2.7.0 pypy 1.7.0 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)build time 100x 22,66 0,65 10,45 1,29 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)build & delete time 100x 36,71 1,47 20,89 3,02 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)search 100x all keys 2,34 0,85 0,89 0,14 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)RBTrees CPython 2.7.2 FastRBTree ipy 2.7.0 pypy 1.7.0 1692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)build time 100x 14,78 0,65 4,43 0,49 1712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)build & delete time 100x 39,34 1,63 12,43 1,32 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)search 100x all keys 2,32 0,86 0,86 0,13 1732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======================== ============= ============== ============== ============== 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)News 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)==== 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Version 1.0.1 February 2013 1792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * bug fixes 1812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * refactorings by graingert 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * skip useless tests for pypy 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * new license: MIT License 1842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * tested with CPython2.7, CPython3.2, CPython3.3, pypy-1.9, pypy-2.0-beta1 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * unified line endings to LF 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * PEP8 refactorings 1872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * added floor_item/key, ceiling_item/key methods, thanks to Dai Mikurube 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Version 1.0.0 1902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * bug fixes 1922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * status: 5 - Production/Stable 1932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * removed useless TreeIterator() class and T.treeiter() method. 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * patch from Max Motovilov to use Visual Studio 2008 for building C-extensions 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Version 0.4.0 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * API change!!! 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * full Python 3 support, also for Cython implementations 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * removed user defined compare() function - keys have to be comparable! 2012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * removed T.has_key(), use 'key in T' 2022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * keys(), items(), values() generating 'views' 2032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * removed iterkeys(), itervalues(), iteritems() methods 2042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * replaced index slicing by key slicing 2052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * removed index() and item_at() 2062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * repr() produces a correct representation 2072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * installs on systems without cython (tested with pypy) 2082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * new license: GNU Library or Lesser General Public License (LGPL) 2092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Installation 2112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)============ 2122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)from source:: 2142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) python setup.py install 2162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Download 2182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)======== 2192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)http://bitbucket.org/mozman/bintrees/downloads 2212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)Documentation 2232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)============= 2242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)this README.txt 2262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bintrees can be found on bitbucket.org at: 2282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)http://bitbucket.org/mozman/bintrees 230