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 9from __future__ import absolute_import 10 11__doc__ = """ 12Binary Tree Package 13=================== 14 15Python Trees 16------------ 17 18Balanced and unbalance binary trees written in pure Python with a dict-like API. 19 20Classes 21~~~~~~~ 22* BinaryTree -- unbalanced binary tree 23* AVLTree -- balanced AVL-Tree 24* RBTree -- balanced Red-Black-Tree 25 26Cython Trees 27------------ 28 29Basic tree functions written in Cython, merged with TreeMixin to provide the 30full API of the Python Trees. 31 32Classes 33~~~~~~~ 34 35* FastBinaryTree -- unbalanced binary tree 36* FastAVLTree -- balanced AVLTree 37* FastRBTree -- balanced Red-Black-Tree 38 39Overview 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 46Methods 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 75walk 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 82slicing 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 90if 's' is None or T[:e] TreeSlice/iterator starts with value of min_key() 91if 'e' is None or T[s:] TreeSlice/iterator ends with value of max_key() 92T[:] is a TreeSlice which represents the whole tree. 93 94TreeSlice is a tree wrapper with range check, and contains no references 95to objects, deleting objects in the associated tree also deletes the object 96in 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 104TreeSlice 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 113Heap 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 124Set 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 134Classmethods 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 148from .treemixin import TreeMixin 149from .bintree import BinaryTree 150from .avltree import AVLTree 151from .rbtree import RBTree 152 153try: 154 from .qbintree import cBinaryTree 155 156 class FastBinaryTree(cBinaryTree, TreeMixin): 157 """ Faster unbalanced binary tree written in Cython with C-Code. """ 158except ImportError: # fall back to pure Python version 159 FastBinaryTree = BinaryTree 160except ValueError: # for pypy 161 FastBinaryTree = BinaryTree 162 163try: 164 from .qavltree import cAVLTree 165 166 class FastAVLTree(cAVLTree, TreeMixin): 167 """ Faster balanced AVL-Tree written in Cython with C-Code. """ 168except ImportError: # fall back to pure Python version 169 FastAVLTree = AVLTree 170except ValueError: # for pypy 171 FastAVLTree = AVLTree 172 173try: 174 from .qrbtree import cRBTree 175 176 class FastRBTree(cRBTree, TreeMixin): 177 """ Faster balanced Red-Black-Tree written in Cython with C-Code. """ 178except ImportError: # fall back to pure Python version 179 FastRBTree = RBTree 180except ValueError: # for pypy 181 FastRBTree = RBTree 182