1 """
2 a helper library providing a number of fundamental tree data structures,
3 ultimately intended to improve performance in L{SimpleStringTree}. These data
4 structures are sufficiently generic that they might also be of use for other
5 purposes.
6 """
9 """
10 Node represents a node in a binary tree. It is entirely passive, acting
11 as a container much a like a C struct. Its unusual features include a
12 distinction between annotation and value, and references not only to its children
13 but also to its parent.
14 """
15 parent = None
16 """
17 @ivar: The parent of the node, or None if the node has no parent
18 @type: L{Node}
19 """
20 leftchild = None
21 """
22 @ivar: The left child of the node, or None if the node has no left child
23 @type: L{Node}
24 """
25 rightchild = None
26 """
27 @ivar: The right child of the node, or None if the node has no right child
28 @type: L{Node}
29 """
30 annotation = None
31 """
32 @ivar: A piece of data associated with a node, assigned by a
33 tree-specific function and satisfying a related constraint.
34 @type: tree-specific type
35 """
36 value = None
37 """
38 @ivar: A value assigned by the user of the tree. In monoid-annotated
39 trees, only the leaves typically have values, and internal nodes will
40 therefore have a value of None.
41 The purpose of
42 the annotation is to permit the construction of monoid-annotated trees,
43 which often have both highly constrained annotations and completely
44 unconstrained values.
45 See, for example,
46 U{http://scienceblogs.com/goodmath/2009/05/finally_finger_trees.php}.
47 Non-monoid-annotated trees may ignore this variable.
48 @type: typically unconstrained
49 """
50
52 """
53 An AANode is a L{Node} that can be used in an AA tree. AA trees require
54 that each node have an associated level.
55 """
56 level = 1
57 """
58 @ivar: The level index for the node. For more information on the level
59 in AA trees, see U{http://en.wikipedia.org/wiki/AA_tree}.
60 @type: int
61 """
62
64 """
65 A Walker walks up and down trees according to a specific objective. Its
66 goal is typically to find some particular element, such as the element
67 at a specific index, or with a specific value.
68
69 Walker is an abstract base class.
70 """
72 """
73 @type node: Node
74 @param node: A node from which to descend.
75 @rtype: int
76 @return: descend must return 0 if the node in question is the one desired,
77 -1 if the left child would be better, or 1 if the right child would be
78 better.
79 """
80 raise
82 """An optional method to prepare for descent"""
83 raise
85 """
86 @type node: Node
87 @param node: A node from which to ascend
88 @rtype: bool
89 @return: ascend should return True iff it should run again on the parent
90 of node. It should set the walker's internal state such that a
91 subsequent descent would retrace these steps."""
92 raise
94 """ An optional method to prepare for ascent"""
95 raise
96
98 """
99 A L{Walker} that can be used to search a classic binary tree. This class
100 exists solely to expose the concept of the Walker. As a convention, the
101 binary tree being search must satisfy::
102 leftchild.annotation < annotation < rightchild.annotation
103 """
104 val = 0
105 compare = cmp
115
117 """
118 An experimental Walker that could be used to select a random
119 sub-leaf position in a binary tree. ascent is not implemented.
120 """
122 from random import choice as choice
123 self.choice = choice
125 return self.choice((-1,1))
126
128 """
129 @type node: L{Node}
130 @param node: A node from which to start descent
131 @type walker: L{Walker}
132 @param walker: A L{Walker} to apply recursively from node.
133 @rtype: tuple(L{Node}, int)
134 @return: If the L{Walker} accepted a L{Node} n, the function
135 returns (n, 0). Otherwise, the function returns (L, 1), or (L, -1),
136 where L is a node that has no right or left child, respectively.
137 These return values typically indicate that the walker is looking for a
138 node that is not present in the tree, but, if it were present, would be
139 in the (currently empty) subtree right (or left) of L.
140 """
141 x = walker.descend(node)
142 while x != 0:
143 if x == 1:
144 if node.rightchild is None:
145 return (node, 1)
146 else:
147 node = node.rightchild
148 else:
149 if node.leftchild is None:
150 return (node, -1)
151 else:
152 node = node.leftchild
153 x = walker.descend(node)
154 return (node, 0)
155
157 """
158 @type node: L{Node}
159 @type walker: L{Walker}
160 @param node: the L{Node} from which to ascend.
161 @param walker: The L{walker} with which to ascend.
162 @rtype: None
163 ascend causes walker to ascend until walker asks to stop or the tree's
164 root node is reached. Nothing is returned; instead, state is accumulated
165 inside the walker
166 """
167 while node is not None and walker.ascend(node):
168 node = node.parent
169
171 """
172 @type root: L{Node}
173 @type val: comparable
174 Searches a correctly sorted binary tree, starting with the root Node, for
175 val. Returns a node that contains val if val is present, otherwise a node
176 for which val would be an acceptable child value.
177
178 Provided solely as an example."""
179 w = SearchWalker
180 w.prepared_descend(val)
181 return descend(root, w)
182
184 """
185 Simple search function for the leftmost element in a tree, or subtree.
186 @type root: L{Node}
187 @param root: The node from which to start walking.
188 @rtype: L{Node}
189 @return: the leftmost element in the subtree of root
190 """
191 while root.leftchild is not None:
192 root = root.leftchild
193 return root
194
196 """
197 Simple search function for the rightmost element in a tree, or subtree.
198 @type root: L{Node}
199 @param root: The node from which to start walking.
200 @rtype: L{Node}
201 @return: the rightmost element in the subtree of root
202 """
203 while root.rightchild is not None:
204 root = root.rightchild
205 return root
206
208 """
209 A Monoid Annotation Tree is a binary tree whose nodes are each annotated
210 by values from some monoid. The annotation of an internal node is computed
211 by applying the operation to the annotations of its children. The annotation of a leaf
212 node is specified by the user. Every node must either have two children or
213 be a leaf node.
214
215 Each leaf node may also be associated with an arbitrary opaque value of the user's
216 choosing. This node and value will remain associated."""
217 makenode = Node
218 """
219 @cvar: a factory function that returns nodes of the type required
220 for this tree. It is provided so that subclasses can easily override it
221 to use subtypes of L{Node}.
222 """
223 - def __init__(self, operation, rootnode):
224 """
225 Let M be the monoid type.
226 @type operation: f(M,M) -> M
227 @param operation: a function taking two arguments from the monoid set
228 and returning another element from the monoid set. The monoid
229 operation must obey an associativity criterion; see U{http://en.wikipedia.org/wiki/Monoid#Definition}.
230 @type rootnode: L{makenode}
231 @param rootnode: The root node for the tree. rootnode must have a valid annotation, and its parent and children must be None."""
232 self.op = operation
233 self.root = rootnode
234 - def _update(self, node, sentinel=None):
244 _update_add = _update
245 _update_del = _update
247 """Introduce and return a new node (newparent) between node and its parent"""
248 newparent = self.makenode()
249 newparent.parent = node.parent
250 if node.parent is not None:
251 if node.parent.leftchild is node:
252 node.parent.leftchild = newparent
253 else:
254 assert node.parent.rightchild is node
255 node.parent.rightchild = newparent
256 else:
257 self.root = newparent
258 node.parent = newparent
259 return newparent
261 """
262 Add a new leaf node to the left of an old leaf node. The new node's
263 parent will be assigned to be a new internal node.
264 @type new: makenode
265 @param new: a new node, not yet present in the tree
266 @type old: makenode
267 @param old: A leaf node currently in the tree.
268 """
269 newparent = self._split_link(old)
270 newparent.rightchild = old
271 newparent.leftchild = new
272 new.parent = newparent
273 self._update_add(newparent)
275 """
276 Add a new leaf node to the right of an old leaf node. The new node's
277 parent will be assigned to be a new internal node.
278 @type new: makenode
279 @param new: a new node, not yet present in the tree
280 @type old: makenode
281 @param old: A leaf node currently in the tree.
282 """
283 newparent = self._split_link(old)
284 newparent.rightchild = new
285 newparent.leftchild = old
286 new.parent = newparent
287 self._update_add(newparent)
288 - def add(self, new, walker):
289 """
290 Add a new leaf node at a position determined by walker. Acts as a
291 thin wrapper around L{aatree.descend} and addleft or addright.
292 If the walker descent process returns a position of zero, the new node
293 will be added left of the returned node.
294 @type new: makenode
295 @param new: a new node to add to the tree.
296 @type walker: L{Walker}
297 @param walker: A walker that will determine the insertion position
298 """
299 leaf, position = descend(self.root, walker)
300 assert leaf.leftchild is None
301 assert leaf.rightchild is None
302 if position == 1:
303 self.addright(new, leaf)
304 else:
305 self.addleft(new, leaf)
329 """
330 When changing the annotation of a leaf, it is required to use this method,
331 so that the change may be propagated up through the tree according to the
332 operation. Note that no such method is needed for the value of a leaf,
333 because the value is opaque to the tree.
334 @type leaf: makenode
335 @param leaf: the node whose annotation should be altered
336 @type newann: element of the monoid set
337 @param newann: the new annotation which should be associated with leaf
338 """
339 assert leaf.leftchild is None
340 assert leaf.rightchild is None
341 leaf.annotation = newann
342 self._update(leaf.parent)
343 - def getnext(self, leaf, skip=None):
344 """
345 Get the next rightward leaf node from leaf. Optionally, skip any nodes
346 meeting some criterion.
347 @type leaf: makenode
348 @param leaf: The leaf node whose next rightward neighbor will be returned
349 @type skip: f(makenode)->bool
350 @param skip: An optional function returning True if a given node should
351 be skipped. This function will be called on each internal node during
352 the search, not only on leaf nodes. It will typically implement a
353 criterion on the annotation such that a node will be skipped only
354 if every descendant of that node would also be skipped if considered
355 individually.
356 """
357 assert leaf.leftchild is None
358 assert leaf.rightchild is None
359 node = leaf
360 while ((node.parent is not None) and
361 ((node.parent.rightchild is node) or
362 ((skip is not None) and skip(node.parent.rightchild)))):
363
364 node = node.parent
365 if (node.parent is not None) and (node.parent.leftchild is node):
366 node = node.parent.rightchild
367 while node.leftchild is not None:
368
369 assert node.rightchild is not None
370 if (skip is not None) and skip(node.leftchild):
371 node = node.rightchild
372 else:
373 node = node.leftchild
374 return node
375 else:
376 raise StopIteration("No next node")
377
379
380
381
382 L = len(nodes)
383 if L == 1:
384 return nodes[0]
385 else:
386 next = []
387 sentinel = 'g'
388 if L % 2:
389 n2 = nodes.pop()
390 n1 = nodes.pop()
391 newnode = self.makenode()
392 newnode.parent=sentinel
393 newnode.leftchild = n1
394 n1.parent = newnode
395 newnode.rightchild = n2
396 n2.parent = newnode
397 self._update_add(newnode, sentinel)
398 nodes.append(newnode)
399 for i in xrange(0,L,2):
400 n1,n2 = nodes[i:(i+2)]
401 newnode = self.makenode()
402 newnode.parent=sentinel
403 newnode.leftchild = n1
404 n1.parent = newnode
405 newnode.rightchild = n2
406 n2.parent = newnode
407 self._update_add(newnode, sentinel)
408
412 """
413 SumWalker is designed to walk over full trees where each leaf has annotation 1
414 and the monoid is +. Target is the zero-indexed position of the target node.
415
416 There is one exception: the last node in every tree has annotation 0."""
417 target = None
418 offset = None
448
450 """Implements a list-like interface, backed by a MonoidTree"""
451 _treetype = MonoidTree
453 self._makenode = self._treetype.makenode
454 r = self._makenode()
455 r.annotation = 0
456 from operator import add
457 self._tree = self._treetype(add, r)
458 self._walker = SumWalker()
459
460
461 self._index = {}
465 self._walker.prepare_descend(i)
466 node, pos = descend(self._tree.root, self._walker)
467 assert pos == 0
468 return node
470 if isinstance(s, int):
471 node = self._getnode(s)
472 return node.value
473 else:
474 raise UnimplementedError
476 if isinstance(s, int):
477 if s < len(self):
478 node = self._getnode(s)
479 oldv = node.value
480 self._index[oldv].remove(node)
481 if not self._index[oldv]:
482 del self._index[oldv]
483 node.value = v
484 if v not in self._index:
485 self._index[v] = set()
486 self._index[v].add(node)
487 else:
488 self.insert(s, v)
489 else:
490 raise UnimplementedError
492 if isinstance(s, int):
493 if s < len(self):
494 node = self._getnode(s)
495 oldv = node.value
496 self._index[oldv].remove(node)
497 if not self._index[oldv]:
498 del self._index[oldv]
499 self._tree.remove(node)
500 else:
501 raise UnimplementedError
503 if p > len(self):
504 raise IndexError("Index out of range")
505 self._walker.prepare_descend(p)
506 newnode = self._makenode()
507 newnode.annotation = 1
508 newnode.value = v
509 self._tree.add(newnode, self._walker)
510 if v not in self._index:
511 self._index[v] = set()
512 self._index[v].add(newnode)
514 """index returns some index such that self[i] == v. No promises about ordering."""
515 self._walker.prepare_ascend()
516 for node in self._index[v]:
517 assert node.value == v
518 ascend(node, self._walker)
519 break
520 return self._walker.target
521
523 """Implements the EagerHideList interface, backed by a MonoidTree"""
524 _treetype = MonoidTree
560
561 @staticmethod
563
564 return (a[0] + b[0], a[1] + b[1])
565
566 @staticmethod
569
571 self._makenode = self._treetype.makenode
572 r = self._makenode()
573 r.annotation = (0, 0)
574 self._tree = self._treetype(self.op, r)
575 self._walker = self.MultiSumWalker()
576
577
578 self._index = {}
579 unique = True
580 if unique:
581 self._index_lookup = self._index.__getitem__
582 self._index_assign = self._index.__setitem__
583 else:
584 self._index_lookup = self._index_lookup_set
585 self._index_assign = self._index_assign_set
587 for v in self._index[item]:
588 return v
590 if key not in self._index:
591 self._index[key] = set()
592 self._index[key].add(value)
596 self._walker.prepare_descend(i, a)
597 node, pos = descend(self._tree.root, self._walker)
598 assert (pos == 0) or ((pos == -1) and (i == len(self)))
599 return node
601 if isinstance(s, int):
602 if s < len(self):
603 node = self._getnode(s, 0)
604 return node.value
605 else:
606 raise IndexError("Index out of range")
607 else:
608 start, stop, stride = s.indices(len(self))
609 if start == stop:
610 return []
611 elif stride == 1:
612
613 nodes = [self._getnode(start,0)]
614 k = stop - start
615 while len(nodes) < k:
616 nodes.append(self._tree.getnext(nodes[-1],self.skip))
617 return [n.value for n in nodes]
618 else:
619
620 return [self[i] for i in xrange(start,stop,stride)]
621 - def index(self, v, visible=True):
622 """index returns some index such that self[i] == v. No promises about ordering."""
623 self._walker.prepare_ascend(0 if visible else 1)
624 node = self._index_lookup(v)
625 assert node.value == v
626 ascend(node, self._walker)
627 return self._walker.target
628 - def hide(self, position, length):
636
637
639 if isinstance(s, int):
640 node = self._getnode(s, 1)
641 return node.value
642 else:
643
644 return [self.getitem_all(i) for i in xrange(*s.indices())]
646 return self.index(item, False)
651 node = self._index_lookup(item)
652 return node.annotation[0] == 1
660 for i in xrange(len(sequence)):
661 v = sequence[i]
662 viz = visibility[i]
663 newnode = self._makenode()
664 newnode.annotation = (1 if viz else 0, 1)
665 newnode.value = v
666 self._tree.addleft(newnode, node)
667 self._index_assign(v, newnode)
668
669
670
671
672
673 -def skew(node, op=None):
697
698 -def split(node, op=None):
729
740
777
780
783