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