1 /*
2
3 $Id: tree_msvc7.hpp 103491 2007-05-04 17:18:18Z kazimird $
4
5 STL-like templated tree class.
6 Copyright (C) 2001 Kasper Peeters <k.peeters@damtp.cam.ac.uk>
7
8 See
9
10 http://www.damtp.cam.ac.uk/user/kp229/tree/
11
12 for more information and documentation. See the Changelog file for
13 other credits.
14
15 This program is free software; you can redistribute it and/or modify
16 it under the terms of the GNU General Public License as published by
17 the Free Software Foundation; version 2.
18
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27
28 TODO: - 'Move' members are long overdue; will hopefully be incorporated in the
29 next release.
30 - Fixed depth iterators do not iterate over the entire range if there
31 are 'holes' in the tree.
32 - If a range uses const iter_base& as end iterator, things will
33 inevitably go wrong, because upcast from iter_base to a non-sibling_iter
34 is incorrect. This upcast should be removed (and then all illegal uses
35 as previously in 'equal' will be flagged by the compiler). This requires
36 new copy constructors though.
37 - There's a bug in replace(sibling_iterator, ...) when the ranges
38 sit next to each other. Turned up in append_child(iter,iter)
39 but has been avoided now.
40 - "std::operator<" does not work correctly on our iterators, and for some
41 reason a globally defined template operator< did not get picked up.
42 Using a comparison class now, but this should be investigated.
43 */
44
45 #ifndef tree_hh_
46 #define tree_hh_
47
48 #include <assert.h>
49 #include <memory>
50 #include <stdexcept>
51 #include <iterator>
52 #include <set>
53
54 // HP-style construct/destroy have gone from the standard,
55 // so here is a copy.
56
57 namespace kp {
58
59 template <class T1, class T2>
constructor(T1 * p,T2 & val)60 inline void constructor(T1* p, T2& val)
61 {
62 new ((void *) p) T1(val);
63 }
64
65 template <class T1>
constructor(T1 * p)66 inline void constructor(T1* p)
67 {
68 new ((void *) p) T1;
69 }
70
71 template <class T1>
destructor(T1 * p)72 inline void destructor(T1* p)
73 {
74 p->~T1();
75 }
76
77 }
78
79 template<class T>
80 class NCBI_CDUTILS_EXPORT tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
81 public:
82 tree_node_<T> *parent;
83 tree_node_<T> *first_child, *last_child;
84 tree_node_<T> *prev_sibling, *next_sibling;
85 T data;
86 };
87
88 template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
89 class NCBI_CDUTILS_EXPORT tree {
90 protected:
91 public:
92 typedef tree_node_<T> tree_node;
93 typedef T value_type;
94
95 class iterator_base;
96 class pre_order_iterator;
97 class post_order_iterator;
98 class sibling_iterator;
99
100 tree();
101 tree(const T&);
102 tree(const iterator_base&);
103 tree(const tree<T, tree_node_allocator>&);
104 ~tree();
105 void operator=(const tree<T, tree_node_allocator>&);
106
107 #ifdef __SGI_STL_PORT
108 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
109 #else
110 class iterator_base {
111 #endif
112 public:
113 typedef T value_type;
114 typedef T* pointer;
115 typedef T& reference;
116 typedef size_t size_type;
117 typedef ptrdiff_t difference_type;
118 typedef std::bidirectional_iterator_tag iterator_category;
119
120 iterator_base();
121 iterator_base(tree_node *);
122
123 T& operator*() const;
124 T* operator->() const;
125
126 void skip_children(); // do not iterate over children of this node
127 unsigned int number_of_children() const;
128
129 sibling_iterator begin() const;
130 sibling_iterator end() const;
131 // ADDED BY VAHAN while conerting CDTRee2 from msvc6 to msvc7
is_valid() const132 bool is_valid() const { return node ? true : false ;}
133
134 tree_node *node;
135 protected:
136 bool skip_current_children_;
137 };
138
139 class pre_order_iterator : public iterator_base {
140 public:
141 pre_order_iterator();
142 pre_order_iterator(tree_node *);
143 pre_order_iterator(const iterator_base&);
144 pre_order_iterator(const sibling_iterator&);
145
146 bool operator==(const pre_order_iterator&) const;
147 bool operator!=(const pre_order_iterator&) const;
148 pre_order_iterator& operator++();
149 pre_order_iterator& operator--();
150 pre_order_iterator operator++(int);
151 pre_order_iterator operator--(int);
152 pre_order_iterator& operator+=(unsigned int);
153 pre_order_iterator& operator-=(unsigned int);
154 };
155
156 class post_order_iterator : public iterator_base {
157 public:
158 post_order_iterator();
159 post_order_iterator(tree_node *);
160 post_order_iterator(const iterator_base&);
161 post_order_iterator(const sibling_iterator&);
162
163 bool operator==(const post_order_iterator&) const;
164 bool operator!=(const post_order_iterator&) const;
165 post_order_iterator& operator++();
166 post_order_iterator& operator--();
167 post_order_iterator operator++(int);
168 post_order_iterator operator--(int);
169 post_order_iterator& operator+=(unsigned int);
170 post_order_iterator& operator-=(unsigned int);
171
172 void descend_all();
173 };
174
175 typedef pre_order_iterator iterator;
176
177 class fixed_depth_iterator : public iterator_base {
178 public:
179 fixed_depth_iterator();
180 fixed_depth_iterator(tree_node *);
181 fixed_depth_iterator(const iterator_base&);
182 fixed_depth_iterator(const sibling_iterator&);
183 fixed_depth_iterator(const fixed_depth_iterator&);
184
185 bool operator==(const fixed_depth_iterator&) const;
186 bool operator!=(const fixed_depth_iterator&) const;
187 fixed_depth_iterator& operator++();
188 fixed_depth_iterator& operator--();
189 fixed_depth_iterator operator++(int);
190 fixed_depth_iterator operator--(int);
191 fixed_depth_iterator& operator+=(unsigned int);
192 fixed_depth_iterator& operator-=(unsigned int);
193
194 tree_node *first_parent_;
195 private:
196 void set_first_parent_();
197 void find_leftmost_parent_();
198 };
199
200 class sibling_iterator : public iterator_base {
201 public:
202 sibling_iterator();
203 sibling_iterator(tree_node *);
204 sibling_iterator(const sibling_iterator&);
205 sibling_iterator(const iterator_base&);
206
207 bool operator==(const sibling_iterator&) const;
208 bool operator!=(const sibling_iterator&) const;
209 sibling_iterator& operator++();
210 sibling_iterator& operator--();
211 sibling_iterator operator++(int);
212 sibling_iterator operator--(int);
213 sibling_iterator& operator+=(unsigned int);
214 sibling_iterator& operator-=(unsigned int);
215
216 tree_node *range_first() const;
217 tree_node *range_last() const;
218 tree_node *parent_;
219 private:
220 void set_parent_();
221 };
222
223 // begin/end of tree
224 pre_order_iterator begin() const;
225 pre_order_iterator end() const;
226 post_order_iterator begin_post() const;
227 post_order_iterator end_post() const;
228 fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
229 fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
230 // begin/end of children of node
231 sibling_iterator begin(const iterator_base&) const;
232 sibling_iterator end(const iterator_base&) const;
233
234 template<typename iter> iter parent(iter) const;
235 sibling_iterator previous_sibling(const iterator_base&) const;
236 sibling_iterator next_sibling(const iterator_base&) const;
237
238 void clear();
239 // erase element at position pointed to by iterator, increment iterator
240 template<typename iter> iter erase(iter);
241 // erase all children of the node pointed to by iterator
242 void erase_children(const iterator_base&);
243
244 // insert node as last child of node pointed to by position (first one inserts empty node)
245 template<typename iter> iter append_child(iter position);
246 template<typename iter> iter append_child(iter position, const T& x);
247 // the following two append nodes plus their children
248 template<typename iter> iter append_child(iter position, iter other_position);
249 template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
250
251 // short-hand to insert topmost node in otherwise empty tree
252 pre_order_iterator set_head(const T& x);
253 // insert node as previous sibling of node pointed to by position
254 template<typename iter> iter insert(iter position, const T& x);
255 // specialisation: insert node as previous sibling of node pointed to by position
256 //pre_order_iterator insert(sibling_iterator position, const T& x);
257 sibling_iterator insert(sibling_iterator position, const T& x);
258 // insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
259 template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
260 // insert node as next sibling of node pointed to by position
261 template<typename iter> iter insert_after(iter position, const T& x);
262
263 // replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
264 template<typename iter> iter replace(iter position, const T& x);
265 // replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
266 template<typename iter> iter replace(iter position, const iterator_base& from);
267 // replace string of siblings (plus their children) with copy of a new string (with children); see above
268 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
269 sibling_iterator new_begin, sibling_iterator new_end);
270
271 // move all children of node at 'position' to be siblings, returns position
272 template<typename iter> iter flatten(iter position);
273 // move nodes in range to be children of 'position'
274 template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
275 // ditto, the range being all children of the 'from' node
276 template<typename iter> iter reparent(iter position, iter from);
277
278 // new style move members, moving nodes plus children to a different
279 template<typename iter> iter move_after(iter target, iter source);
280 template<typename iter> iter move_before(iter target, iter source);
281 template<typename iter> iter move_below(iter target, iter source);
282
283 // merge with other tree, creating new branches and leaves only if they are not already present
284 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
285 bool duplicate_leaves=false);
286 // sort (std::sort only moves values of nodes, this one moves children as well)
287 void sort(sibling_iterator from, sibling_iterator to, bool deep=false);
288 template<class StrictWeakOrdering>
289 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
290 // compare two ranges of nodes (compares nodes as well as tree structure)
291 template<typename iter>
292 bool equal(const iter& one, const iter& two, const iter& three) const;
293 template<typename iter, class BinaryPredicate>
294 bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
295 template<typename iter>
296 bool equal_subtree(const iter& one, const iter& two) const;
297 template<typename iter, class BinaryPredicate>
298 bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
299 // extract a new tree formed by the range of siblings plus all their children
300 tree subtree(sibling_iterator from, sibling_iterator to) const;
301 void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
302 // exchange the node (plus subtree) with its sibling node (do nothing if no sibling present)
303 void swap(sibling_iterator it);
304 // find a subtree
305 // template<class BinaryPredicate>
306 // iterator find_subtree(sibling_iterator, sibling_iterator, iterator from, iterator to, BinaryPredicate) const;
307
308 // count the total number of nodes
309 int size() const;
310 // check if tree is empty
311 bool empty() const;
312 // compute the depth to the root
313 int depth(const iterator_base&) const;
314 // count the number of children of node at position
315 unsigned int number_of_children(const iterator_base&) const;
316 // count the number of 'next' siblings of node at iterator
317 unsigned int number_of_siblings(const iterator_base&) const;
318 // determine whether node at position is in the subtrees with root in the range
319 bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
320 const iterator_base& end) const;
321 // determine whether the iterator is an 'end' iterator and thus not actually
322 // pointing to a node
323 bool is_valid(const iterator_base&) const;
324
325 // determine the index of a node in the range of siblings to which it belongs.
326 unsigned int index(sibling_iterator it) const;
327 // inverse of 'index': return the n-th child of the node at position
328 sibling_iterator child(const iterator_base& position, unsigned int) const;
329
330 class iterator_base_less {
331 public:
operator ()(const typename tree<T,tree_node_allocator>::iterator_base & one,const typename tree<T,tree_node_allocator>::iterator_base & two) const332 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
333 const typename tree<T, tree_node_allocator>::iterator_base& two) const
334 {
335 return one.node < two.node;
336 }
337 };
338 tree_node *head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid
339
340 // Return a new tree that is a restructuring of oldTree (*this) after
341 // re-rooting at the node 'newRoot'. Any properties of the nodes
342 // that depend on tree structure (e.g. branch length) are NOT
343 // adjusted. User will need to pre-process the nodes to deal
344 // with such node-specific issues.
345
346 // Added by CJL: not part of distributed code
reroot(iterator newRoot)347 tree reroot(iterator newRoot) {
348
349 tree newTree;
350 iterator attachNode, oldParent, z, zz;
351 int nChildren;
352 int nTopLevelNodes = number_of_siblings(begin());
353
354 // start new tree at selected node
355 newTree = subtree(newRoot, next_sibling(newRoot));
356 attachNode = newTree.begin();
357 oldParent = parent(newRoot);
358 erase(newRoot);
359
360 // climb old tree; attach old parent to its old child in the new tree
361 while(oldParent.is_valid()) {
362 z = parent(oldParent);
363 attachNode = newTree.reparent(attachNode, oldParent, next_sibling(oldParent));
364 oldParent = z;
365 }
366
367 // Move over any sibling subtrees also attached to head as needed.
368 // Avoid spuriously creating an internal node corresp to 'root' of
369 // an old tree if not needed.
370
371 if (nTopLevelNodes > 1) {
372 if (nTopLevelNodes > 2) {
373 attachNode = newTree.append_child(attachNode, value_type());
374 }
375 z = begin();
376 while (z.is_valid() && z != end()) {
377 zz = next_sibling(z);
378 newTree.reparent(attachNode, z, zz);
379 z = zz;
380
381 }
382 }
383
384 // If old root has only one child, remove it and reparent its children
385
386 nChildren = newTree.number_of_children(attachNode);
387 if (nChildren <= 1) {
388 oldParent = newTree.parent(attachNode);
389 if (nChildren == 1) {
390 z = newTree.reparent(oldParent, attachNode.begin(), next_sibling(attachNode.begin()));
391 }
392 newTree.erase(attachNode);
393 }
394
395 return newTree;
396 }
397 // End CJL addition
398
399 private:
400 tree_node_allocator alloc_;
401 void head_initialise_();
402 void copy_(const tree<T, tree_node_allocator>& other);
403 template<class StrictWeakOrdering>
404 class compare_nodes {
405 public:
406 bool operator()(const tree_node*, const tree_node *);
407 };
408 };
409
410 //template <class T, class tree_node_allocator>
411 //class iterator_base_less {
412 // public:
413 // bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
414 // const typename tree<T, tree_node_allocator>::iterator_base& two) const
415 // {
416 // txtout << "operatorclass<" << one.node < two.node << std::endl;
417 // return one.node < two.node;
418 // }
419 //};
420
421 //template <class T, class tree_node_allocator>
422 //bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
423 // const typename tree<T, tree_node_allocator>::iterator& two)
424 // {
425 // txtout << "operator< " << one.node < two.node << std::endl;
426 // if(one.node < two.node) return true;
427 // return false;
428 // }
429
430 template <class T, class tree_node_allocator>
431 NCBI_CDUTILS_EXPORT
operator >(const typename tree<T,tree_node_allocator>::iterator_base & one,const typename tree<T,tree_node_allocator>::iterator_base & two)432 bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
433 const typename tree<T, tree_node_allocator>::iterator_base& two)
434 {
435 if(one.node > two.node) return true;
436 return false;
437 }
438
439
440
441 // Tree
442
443 template <class T, class tree_node_allocator>
tree()444 tree<T, tree_node_allocator>::tree()
445 {
446 head_initialise_();
447 }
448
449 template <class T, class tree_node_allocator>
tree(const T & x)450 tree<T, tree_node_allocator>::tree(const T& x)
451 {
452 head_initialise_();
453 set_head(x);
454 }
455
456 template <class T, class tree_node_allocator>
tree(const iterator_base & other)457 tree<T, tree_node_allocator>::tree(const iterator_base& other)
458 {
459 head_initialise_();
460 set_head((*other));
461 replace(begin(), other);
462 }
463
464 template <class T, class tree_node_allocator>
~tree()465 tree<T, tree_node_allocator>::~tree()
466 {
467 clear();
468 alloc_.deallocate(head,1);
469 alloc_.deallocate(feet,1);
470 }
471
472 template <class T, class tree_node_allocator>
head_initialise_()473 void tree<T, tree_node_allocator>::head_initialise_()
474 {
475 head = (tree_node*) alloc_.allocate(1,0); // MSVC does not have default second argument
476 feet = (tree_node*) alloc_.allocate(1,0);
477
478 head->parent=0;
479 head->first_child=0;
480 head->last_child=0;
481 head->prev_sibling=0; //head;
482 head->next_sibling=feet; //head;
483
484 feet->parent=0;
485 feet->first_child=0;
486 feet->last_child=0;
487 feet->prev_sibling=head;
488 feet->next_sibling=0;
489 }
490
491 template <class T, class tree_node_allocator>
operator =(const tree<T,tree_node_allocator> & other)492 void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
493 {
494 copy_(other);
495 }
496
497 template <class T, class tree_node_allocator>
tree(const tree<T,tree_node_allocator> & other)498 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
499 {
500 head_initialise_();
501 copy_(other);
502 }
503
504 template <class T, class tree_node_allocator>
copy_(const tree<T,tree_node_allocator> & other)505 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)
506 {
507 clear();
508 pre_order_iterator it=other.begin(), to=begin();
509 while(it!=other.end()) {
510 to=insert(to, (*it));
511 it.skip_children();
512 ++it;
513 }
514 to=begin();
515 it=other.begin();
516 while(it!=other.end()) {
517 to=replace(to, it);
518 to.skip_children();
519 it.skip_children();
520 ++to;
521 ++it;
522 }
523 }
524
525 template <class T, class tree_node_allocator>
clear()526 void tree<T, tree_node_allocator>::clear()
527 {
528 if(head)
529 while(head->next_sibling!=feet)
530 erase(pre_order_iterator(head->next_sibling));
531 }
532
533 template<class T, class tree_node_allocator>
erase_children(const iterator_base & it)534 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
535 {
536 tree_node *cur=it.node->first_child;
537 tree_node *prev=0;
538
539 while(cur!=0) {
540 prev=cur;
541 cur=cur->next_sibling;
542 erase_children(pre_order_iterator(prev));
543 kp::destructor(&prev->data);
544 alloc_.deallocate(prev,1);
545 }
546 it.node->first_child=0;
547 it.node->last_child=0;
548 }
549
550 template<class T, class tree_node_allocator>
551 template<class iter>
erase(iter it)552 iter tree<T, tree_node_allocator>::erase(iter it)
553 {
554 tree_node *cur=it.node;
555 assert(cur!=head);
556 iter ret=it;
557 ret.skip_children();
558 ++ret;
559 erase_children(it);
560 if(cur->prev_sibling==0) {
561 cur->parent->first_child=cur->next_sibling;
562 }
563 else {
564 cur->prev_sibling->next_sibling=cur->next_sibling;
565 }
566 if(cur->next_sibling==0) {
567 cur->parent->last_child=cur->prev_sibling;
568 }
569 else {
570 cur->next_sibling->prev_sibling=cur->prev_sibling;
571 }
572
573 kp::destructor(&cur->data);
574 alloc_.deallocate(cur,1);
575 return ret;
576 }
577
578 template <class T, class tree_node_allocator>
begin() const579 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const
580 {
581 return pre_order_iterator(head->next_sibling);
582 }
583
584 template <class T, class tree_node_allocator>
end() const585 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const
586 {
587 return pre_order_iterator(feet);
588 }
589
590 template <class T, class tree_node_allocator>
begin_post() const591 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const
592 {
593 tree_node *tmp=head->next_sibling;
594 if(tmp!=feet) {
595 while(tmp->first_child)
596 tmp=tmp->first_child;
597 }
598 return post_order_iterator(tmp);
599 }
600
601 template <class T, class tree_node_allocator>
end_post() const602 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const
603 {
604 return post_order_iterator(feet);
605 }
606
607 template <class T, class tree_node_allocator>
begin_fixed(const iterator_base & pos,unsigned int dp) const608 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const
609 {
610 tree_node *tmp=pos.node;
611 unsigned int curdepth=0;
612 while(curdepth<dp) { // go down one level
613 while(tmp->first_child==0) {
614 tmp=tmp->next_sibling;
615 if(tmp==0)
616 throw std::range_error("tree: begin_fixed out of range");
617 }
618 tmp=tmp->first_child;
619 ++curdepth;
620 }
621 return tmp;
622 }
623
624 template <class T, class tree_node_allocator>
end_fixed(const iterator_base & pos,unsigned int dp) const625 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
626 {
627 assert(1==0); // FIXME: not correct yet
628 tree_node *tmp=pos.node;
629 unsigned int curdepth=1;
630 while(curdepth<dp) { // go down one level
631 while(tmp->first_child==0) {
632 tmp=tmp->next_sibling;
633 if(tmp==0)
634 throw std::range_error("tree: end_fixed out of range");
635 }
636 tmp=tmp->first_child;
637 ++curdepth;
638 }
639 return tmp;
640 }
641
642 template <class T, class tree_node_allocator>
begin(const iterator_base & pos) const643 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const
644 {
645 if(pos.node->first_child==0) {
646 return end(pos);
647 }
648 return pos.node->first_child;
649 }
650
651 template <class T, class tree_node_allocator>
end(const iterator_base & pos) const652 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const
653 {
654 sibling_iterator ret(0);
655 ret.parent_=pos.node;
656 return ret;
657 }
658
659 template <class T, class tree_node_allocator>
660 template <typename iter>
parent(iter position) const661 iter tree<T, tree_node_allocator>::parent(iter position) const
662 {
663 assert(position.node!=0);
664 return iter(position.node->parent);
665 }
666
667 template <class T, class tree_node_allocator>
previous_sibling(const iterator_base & position) const668 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::previous_sibling(const iterator_base& position) const
669 {
670 assert(position.node!=0);
671 return sibling_iterator(position.node->prev_sibling);
672 }
673
674 template <class T, class tree_node_allocator>
next_sibling(const iterator_base & position) const675 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::next_sibling(const iterator_base& position) const
676 {
677 assert(position.node!=0);
678 if(position.node->next_sibling==0)
679 return end(pre_order_iterator(position.node->parent));
680 else
681 return sibling_iterator(position.node->next_sibling);
682 }
683
684 template <class T, class tree_node_allocator>
685 template <typename iter>
append_child(iter position)686 iter tree<T, tree_node_allocator>::append_child(iter position)
687 {
688 assert(position.node!=head);
689
690 tree_node* tmp = (tree_node*) alloc_.allocate(1,0);
691 kp::constructor(&tmp->data);
692 tmp->first_child=0;
693 tmp->last_child=0;
694
695 tmp->parent=position.node;
696 if(position.node->last_child!=0) {
697 position.node->last_child->next_sibling=tmp;
698 }
699 else {
700 position.node->first_child=tmp;
701 }
702 tmp->prev_sibling=position.node->last_child;
703 position.node->last_child=tmp;
704 tmp->next_sibling=0;
705 return tmp;
706 }
707
708 template <class T, class tree_node_allocator>
709 template <class iter>
append_child(iter position,const T & x)710 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
711 {
712 // If your program fails here you probably used 'append_child' to add the top
713 // node to an empty tree. From version 1.45 the top element should be added
714 // using 'insert'. See the documentation for further information, and sorry about
715 // the API change.
716 assert(position.node!=head);
717
718 tree_node* tmp = (tree_node*) alloc_.allocate(1,0);
719 kp::constructor(&tmp->data, x);
720 tmp->first_child=0;
721 tmp->last_child=0;
722
723 tmp->parent=position.node;
724 if(position.node->last_child!=0) {
725 position.node->last_child->next_sibling=tmp;
726 }
727 else {
728 position.node->first_child=tmp;
729 }
730 tmp->prev_sibling=position.node->last_child;
731 position.node->last_child=tmp;
732 tmp->next_sibling=0;
733 return tmp;
734 }
735
736 template <class T, class tree_node_allocator>
737 template <class iter>
append_child(iter position,iter other)738 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
739 {
740 assert(position.node!=head);
741
742 sibling_iterator aargh=append_child(position, value_type());
743 return replace(aargh, other);
744 }
745
746 template <class T, class tree_node_allocator>
747 template <class iter>
append_children(iter position,sibling_iterator from,sibling_iterator to)748 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
749 {
750 iter ret=from;
751
752 while(from!=to) {
753 insert_subtree(position.end(), from);
754 ++from;
755 }
756 return ret;
757 }
758
759 template <class T, class tree_node_allocator>
set_head(const T & x)760 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)
761 {
762 assert(head->next_sibling==feet);
763 return insert(iterator(feet), x);
764 }
765
766 template <class T, class tree_node_allocator>
767 template <class iter>
insert(iter position,const T & x)768 iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
769 {
770 if(position.node==0) {
771 position.node=feet; // Backward compatibility: when calling insert on a null node,
772 // insert before the feet.
773 }
774 tree_node* tmp = (tree_node*) alloc_.allocate(1,0);
775 kp::constructor(&tmp->data, x);
776 tmp->first_child=0;
777 tmp->last_child=0;
778
779 tmp->parent=position.node->parent;
780 tmp->next_sibling=position.node;
781 tmp->prev_sibling=position.node->prev_sibling;
782 position.node->prev_sibling=tmp;
783
784 if(tmp->prev_sibling==0)
785 tmp->parent->first_child=tmp;
786 else
787 tmp->prev_sibling->next_sibling=tmp;
788 return tmp;
789 }
790
791 template <class T, class tree_node_allocator>
insert(sibling_iterator position,const T & x)792 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
793 {
794 tree_node* tmp = (tree_node*) alloc_.allocate(1,0);
795 kp::constructor(&tmp->data, x);
796 tmp->first_child=0;
797 tmp->last_child=0;
798
799 tmp->next_sibling=position.node;
800 if(position.node==0) { // iterator points to end of a subtree
801 tmp->parent=position.parent_;
802 tmp->prev_sibling=position.range_last();
803 tmp->parent->last_child=tmp;
804 }
805 else {
806 tmp->parent=position.node->parent;
807 tmp->prev_sibling=position.node->prev_sibling;
808 position.node->prev_sibling=tmp;
809 }
810
811 if(tmp->prev_sibling==0)
812 tmp->parent->first_child=tmp;
813 else
814 tmp->prev_sibling->next_sibling=tmp;
815 return tmp;
816 }
817
818 template <class T, class tree_node_allocator>
819 template <class iter>
insert_after(iter position,const T & x)820 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
821 {
822 tree_node* tmp = (tree_node*) alloc_.allocate(1,0);
823 kp::constructor(&tmp->data, x);
824 tmp->first_child=0;
825 tmp->last_child=0;
826
827 tmp->parent=position.node->parent;
828 tmp->prev_sibling=position.node;
829 tmp->next_sibling=position.node->next_sibling;
830 position.node->next_sibling=tmp;
831
832 if(tmp->next_sibling==0) {
833 if(tmp->parent) // when adding nodes at the head, there is no parent
834 tmp->parent->last_child=tmp;
835 }
836 else {
837 tmp->next_sibling->prev_sibling=tmp;
838 }
839 return tmp;
840 }
841
842 template <class T, class tree_node_allocator>
843 template <class iter>
insert_subtree(iter position,const iterator_base & subtree)844 iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
845 {
846 // insert dummy
847 iter it=insert(position, value_type());
848 // replace dummy with subtree
849 return replace(it, subtree);
850 }
851
852 // template <class T, class tree_node_allocator>
853 // template <class iter>
854 // iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
855 // {
856 // // insert dummy
857 // iter it(insert(position, value_type()));
858 // // replace dummy with subtree
859 // return replace(it, subtree);
860 // }
861
862 template <class T, class tree_node_allocator>
863 template <class iter>
replace(iter position,const T & x)864 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
865 {
866 kp::destructor(&position.node->data);
867 kp::constructor(&position.node->data, x);
868 return position;
869 }
870
871 template <class T, class tree_node_allocator>
872 template <class iter>
replace(iter position,const iterator_base & from)873 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
874 {
875 assert(position.node!=head);
876 tree_node *current_from=from.node;
877 tree_node *start_from=from.node;
878 tree_node *current_to =position.node;
879
880 // replace the node at position with head of the replacement tree at from
881 erase_children(position);
882 tree_node* tmp = (tree_node*) alloc_.allocate(1,0);
883 kp::constructor(&tmp->data, (*from));
884 tmp->first_child=0;
885 tmp->last_child=0;
886 if(current_to->prev_sibling==0) {
887 current_to->parent->first_child=tmp;
888 }
889 else {
890 current_to->prev_sibling->next_sibling=tmp;
891 }
892 tmp->prev_sibling=current_to->prev_sibling;
893 if(current_to->next_sibling==0) {
894 current_to->parent->last_child=tmp;
895 }
896 else {
897 current_to->next_sibling->prev_sibling=tmp;
898 }
899 tmp->next_sibling=current_to->next_sibling;
900 tmp->parent=current_to->parent;
901 kp::destructor(¤t_to->data);
902 alloc_.deallocate(current_to,1);
903 current_to=tmp;
904
905 // only at this stage can we fix 'last'
906 tree_node *last=from.node->next_sibling;
907
908 pre_order_iterator toit=tmp;
909 // copy all children
910 do {
911 assert(current_from!=0);
912 if(current_from->first_child != 0) {
913 current_from=current_from->first_child;
914 toit=append_child(toit, current_from->data);
915 }
916 else {
917 while(current_from->next_sibling==0 && current_from!=start_from) {
918 current_from=current_from->parent;
919 toit=parent(toit);
920 assert(current_from!=0);
921 }
922 current_from=current_from->next_sibling;
923 if(current_from!=last) {
924 toit=append_child(parent(toit), current_from->data);
925 }
926 }
927 } while(current_from!=last);
928
929 return current_to;
930 }
931
932 template <class T, class tree_node_allocator>
replace(sibling_iterator orig_begin,sibling_iterator orig_end,sibling_iterator new_begin,sibling_iterator new_end)933 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
934 sibling_iterator orig_begin,
935 sibling_iterator orig_end,
936 sibling_iterator new_begin,
937 sibling_iterator new_end)
938 {
939 tree_node *orig_first=orig_begin.node;
940 tree_node *new_first=new_begin.node;
941 tree_node *orig_last=orig_first;
942 while((++orig_begin)!=orig_end)
943 orig_last=orig_last->next_sibling;
944 tree_node *new_last=new_first;
945 while((++new_begin)!=new_end)
946 new_last=new_last->next_sibling;
947
948 // insert all siblings in new_first..new_last before orig_first
949 bool first=true;
950 pre_order_iterator ret;
951 while(1==1) {
952 pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
953 if(first) {
954 ret=tt;
955 first=false;
956 }
957 if(new_first==new_last)
958 break;
959 new_first=new_first->next_sibling;
960 }
961
962 // erase old range of siblings
963 bool last=false;
964 tree_node *next=orig_first;
965 while(1==1) {
966 if(next==orig_last)
967 last=true;
968 next=next->next_sibling;
969 erase((pre_order_iterator)orig_first);
970 if(last)
971 break;
972 orig_first=next;
973 }
974 return ret;
975 }
976
977 template <class T, class tree_node_allocator>
978 template <typename iter>
flatten(iter position)979 iter tree<T, tree_node_allocator>::flatten(iter position)
980 {
981 if(position.node->first_child==0)
982 return position;
983
984 tree_node *tmp=position.node->first_child;
985 while(tmp) {
986 tmp->parent=position.node->parent;
987 tmp=tmp->next_sibling;
988 }
989 if(position.node->next_sibling) {
990 position.node->last_child->next_sibling=position.node->next_sibling;
991 position.node->next_sibling->prev_sibling=position.node->last_child;
992 }
993 else {
994 position.node->parent->last_child=position.node->last_child;
995 }
996 position.node->next_sibling=position.node->first_child;
997 position.node->next_sibling->prev_sibling=position.node;
998 position.node->first_child=0;
999 position.node->last_child=0;
1000
1001 return position;
1002 }
1003
1004
1005 template <class T, class tree_node_allocator>
1006 template <typename iter>
reparent(iter position,sibling_iterator begin,sibling_iterator end)1007 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
1008 {
1009 tree_node *first=begin.node;
1010 tree_node *last=first;
1011 if(begin==end) return begin;
1012 // determine last node
1013 while((++begin)!=end) {
1014 last=last->next_sibling;
1015 }
1016 // move subtree
1017 if(first->prev_sibling==0) {
1018 first->parent->first_child=last->next_sibling;
1019 }
1020 else {
1021 first->prev_sibling->next_sibling=last->next_sibling;
1022 }
1023 if(last->next_sibling==0) {
1024 last->parent->last_child=first->prev_sibling;
1025 }
1026 else {
1027 last->next_sibling->prev_sibling=first->prev_sibling;
1028 }
1029 if(position.node->first_child==0) {
1030 position.node->first_child=first;
1031 position.node->last_child=last;
1032 first->prev_sibling=0;
1033 }
1034 else {
1035 position.node->last_child->next_sibling=first;
1036 first->prev_sibling=position.node->last_child;
1037 position.node->last_child=last;
1038 }
1039 last->next_sibling=0;
1040
1041 tree_node *pos=first;
1042 while(1==1) {
1043 pos->parent=position.node;
1044 if(pos==last) break;
1045 pos=pos->next_sibling;
1046 }
1047
1048 return first;
1049 }
1050
1051 template <class T, class tree_node_allocator>
reparent(iter position,iter from)1052 template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
1053 {
1054 if(from.node->first_child==0) return position;
1055 return reparent(position, from.node->first_child, end(from));
1056 }
1057
1058 template <class T, class tree_node_allocator>
move_before(iter target,iter source)1059 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
1060 {
1061 tree_node *dst=target.node;
1062 tree_node *src=source.node;
1063 assert(dst);
1064 assert(src);
1065
1066 if(dst==src) return source;
1067
1068 // take src out of the tree
1069 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1070 else src->parent->first_child=src->next_sibling;
1071 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1072 else src->parent->last_child=src->prev_sibling;
1073
1074 // connect it to the new point
1075 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
1076 else dst->parent->first_child=src;
1077 src->prev_sibling=dst->prev_sibling;
1078 dst->prev_sibling=src;
1079 src->next_sibling=dst;
1080 src->parent=dst->parent;
1081 return src;
1082 }
1083
1084 template <class T, class tree_node_allocator>
merge(sibling_iterator to1,sibling_iterator to2,sibling_iterator from1,sibling_iterator from2,bool duplicate_leaves)1085 void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,
1086 sibling_iterator from1, sibling_iterator from2,
1087 bool duplicate_leaves)
1088 {
1089 sibling_iterator fnd;
1090 while(from1!=from2) {
1091 if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
1092 if(from1.begin()==from1.end()) { // full depth reached
1093 if(duplicate_leaves)
1094 append_child(parent(to1), (*from1));
1095 }
1096 else { // descend further
1097 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1098 }
1099 }
1100 else { // element missing
1101 insert_subtree(to2, from1);
1102 }
1103 ++from1;
1104 }
1105 }
1106
1107 template <class T, class tree_node_allocator>
1108 template <class StrictWeakOrdering>
operator ()(const tree_node * a,const tree_node * b)1109 bool tree<T, tree_node_allocator>::compare_nodes<StrictWeakOrdering>::operator()(const tree_node *a,
1110 const tree_node *b)
1111 {
1112 static StrictWeakOrdering comp;
1113
1114 return comp(a->data, b->data);
1115 }
1116
1117 template <class T, class tree_node_allocator>
sort(sibling_iterator from,sibling_iterator to,bool deep)1118 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
1119 {
1120 std::less<T> comp;
1121 sort(from, to, comp, deep);
1122 }
1123
1124 template <class T, class tree_node_allocator>
1125 template <class StrictWeakOrdering>
sort(sibling_iterator from,sibling_iterator to,StrictWeakOrdering comp,bool deep)1126 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
1127 StrictWeakOrdering comp, bool deep)
1128 {
1129 if(from==to) return;
1130 // make list of sorted nodes
1131 // CHECK: if multiset stores equivalent nodes in the order in which they
1132 // are inserted, then this routine should be called 'stable_sort'.
1133 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes;
1134 sibling_iterator it=from, it2=to;
1135 while(it != to) {
1136 nodes.insert(it.node);
1137 ++it;
1138 }
1139 // reassemble
1140 --it2;
1141
1142 // prev and next are the nodes before and after the sorted range
1143 tree_node *prev=from.node->prev_sibling;
1144 tree_node *next=it2.node->next_sibling;
1145 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
1146 if(prev==0) {
1147 if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1148 (*nit)->parent->first_child=(*nit);
1149 }
1150 else prev->next_sibling=(*nit);
1151
1152 --eit;
1153 while(nit!=eit) {
1154 (*nit)->prev_sibling=prev;
1155 if(prev)
1156 prev->next_sibling=(*nit);
1157 prev=(*nit);
1158 ++nit;
1159 }
1160 // prev now points to the last-but-one node in the sorted range
1161 if(prev)
1162 prev->next_sibling=(*eit);
1163
1164 // eit points to the last node in the sorted range.
1165 (*eit)->next_sibling=next;
1166 (*eit)->prev_sibling=prev; // missed in the loop above
1167 if(next==0) {
1168 if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1169 (*eit)->parent->last_child=(*eit);
1170 }
1171 else next->prev_sibling=(*eit);
1172
1173 if(deep) { // sort the children of each node too
1174 sibling_iterator bcs(*nodes.begin());
1175 sibling_iterator ecs(*eit);
1176 ++ecs;
1177 while(bcs!=ecs) {
1178 sort(begin(bcs), end(bcs), comp, deep);
1179 ++bcs;
1180 }
1181 }
1182 }
1183
1184 template <class T, class tree_node_allocator>
1185 template <typename iter>
equal(const iter & one_,const iter & two,const iter & three_) const1186 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
1187 {
1188 std::equal_to<T> comp;
1189 return equal(one_, two, three_, comp);
1190 }
1191
1192 template <class T, class tree_node_allocator>
1193 template <typename iter>
equal_subtree(const iter & one_,const iter & two_) const1194 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
1195 {
1196 std::equal_to<T> comp;
1197 return equal_subtree(one_, two_, comp);
1198 }
1199
1200 template <class T, class tree_node_allocator>
1201 template <typename iter, class BinaryPredicate>
equal(const iter & one_,const iter & two,const iter & three_,BinaryPredicate fun) const1202 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
1203 {
1204 pre_order_iterator one(one_), three(three_);
1205
1206 // if(one==two && is_valid(three) && three.number_of_children()!=0)
1207 // return false;
1208 while(one!=two && is_valid(three)) {
1209 if(!fun(*one,*three))
1210 return false;
1211 if(one.number_of_children()!=three.number_of_children())
1212 return false;
1213 ++one;
1214 ++three;
1215 }
1216 return true;
1217 }
1218
1219 template <class T, class tree_node_allocator>
1220 template <typename iter, class BinaryPredicate>
equal_subtree(const iter & one_,const iter & two_,BinaryPredicate fun) const1221 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
1222 {
1223 pre_order_iterator one(one_), two(two_);
1224
1225 if(!fun(*one,*two)) return false;
1226 if(number_of_children(one)!=number_of_children(two)) return false;
1227 return equal(begin(one),end(one),begin(two),fun);
1228 }
1229
1230 template <class T, class tree_node_allocator>
subtree(sibling_iterator from,sibling_iterator to) const1231 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
1232 {
1233 tree tmp;
1234 tmp.set_head(value_type());
1235 tmp.replace(tmp.begin(), tmp.end(), from, to);
1236 return tmp;
1237 }
1238
1239 template <class T, class tree_node_allocator>
subtree(tree & tmp,sibling_iterator from,sibling_iterator to) const1240 void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
1241 {
1242 tmp.set_head(value_type());
1243 tmp.replace(tmp.begin(), tmp.end(), from, to);
1244 }
1245
1246 template <class T, class tree_node_allocator>
size() const1247 int tree<T, tree_node_allocator>::size() const
1248 {
1249 int i=0;
1250 pre_order_iterator it=begin(), eit=end();
1251 while(it!=eit) {
1252 ++i;
1253 ++it;
1254 }
1255 return i;
1256 }
1257
1258 template <class T, class tree_node_allocator>
empty() const1259 bool tree<T, tree_node_allocator>::empty() const
1260 {
1261 pre_order_iterator it=begin(), eit=end();
1262 return (it==eit);
1263 }
1264
1265 template <class T, class tree_node_allocator>
depth(const iterator_base & it) const1266 int tree<T, tree_node_allocator>::depth(const iterator_base& it) const
1267 {
1268 tree_node* pos=it.node;
1269 assert(pos!=0);
1270 int ret=0;
1271 while(pos->parent!=0) {
1272 pos=pos->parent;
1273 ++ret;
1274 }
1275 return ret;
1276 }
1277
1278 template <class T, class tree_node_allocator>
number_of_children(const iterator_base & it) const1279 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it) const
1280 {
1281 tree_node *pos=it.node->first_child;
1282 if(pos==0) return 0;
1283
1284 unsigned int ret=1;
1285 // while(pos!=it.node->last_child) {
1286 // ++ret;
1287 // pos=pos->next_sibling;
1288 // }
1289 while((pos=pos->next_sibling))
1290 ++ret;
1291 return ret;
1292 }
1293
1294 template <class T, class tree_node_allocator>
number_of_siblings(const iterator_base & it) const1295 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
1296 {
1297 tree_node *pos=it.node;
1298 unsigned int ret=1;
1299 while(pos->next_sibling && pos->next_sibling!=head) {
1300 ++ret;
1301 pos=pos->next_sibling;
1302 }
1303 return ret;
1304 }
1305
1306 template <class T, class tree_node_allocator>
swap(sibling_iterator it)1307 void tree<T, tree_node_allocator>::swap(sibling_iterator it)
1308 {
1309 tree_node *nxt=it.node->next_sibling;
1310 if(nxt) {
1311 if(it.node->prev_sibling)
1312 it.node->prev_sibling->next_sibling=nxt;
1313 else
1314 it.node->parent->first_child=nxt;
1315 nxt->prev_sibling=it.node->prev_sibling;
1316 tree_node *nxtnxt=nxt->next_sibling;
1317 if(nxtnxt)
1318 nxtnxt->prev_sibling=it.node;
1319 else
1320 it.node->parent->last_child=it.node;
1321 nxt->next_sibling=it.node;
1322 it.node->prev_sibling=nxt;
1323 it.node->next_sibling=nxtnxt;
1324 }
1325 }
1326
1327 // template <class BinaryPredicate>
1328 // tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
1329 // sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
1330 // BinaryPredicate fun) const
1331 // {
1332 // assert(1==0); // this routine is not finished yet.
1333 // while(from!=to) {
1334 // if(fun(*subfrom, *from)) {
1335 //
1336 // }
1337 // }
1338 // return to;
1339 // }
1340
1341 template <class T, class tree_node_allocator>
is_in_subtree(const iterator_base & it,const iterator_base & begin,const iterator_base & end) const1342 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,
1343 const iterator_base& end) const
1344 {
1345 // FIXME: this should be optimised.
1346 pre_order_iterator tmp=begin;
1347 while(tmp!=end) {
1348 if(tmp==it) return true;
1349 ++tmp;
1350 }
1351 return false;
1352 }
1353
1354 template <class T, class tree_node_allocator>
is_valid(const iterator_base & it) const1355 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
1356 {
1357 if(it.node==0 || it.node==feet) return false;
1358 else return true;
1359 }
1360
1361 template <class T, class tree_node_allocator>
index(sibling_iterator it) const1362 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
1363 {
1364 unsigned int ind=0;
1365 if(it.node->parent==0) {
1366 while(it.node->prev_sibling!=head) {
1367 it.node=it.node->prev_sibling;
1368 ++ind;
1369 }
1370 }
1371 else {
1372 while(it.node->prev_sibling!=0) {
1373 it.node=it.node->prev_sibling;
1374 ++ind;
1375 }
1376 }
1377 return ind;
1378 }
1379
1380
1381 template <class T, class tree_node_allocator>
child(const iterator_base & it,unsigned int num) const1382 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num) const
1383 {
1384 tree_node *tmp=it.node->first_child;
1385 while(num--) {
1386 assert(tmp!=0);
1387 tmp=tmp->next_sibling;
1388 }
1389 return tmp;
1390 }
1391
1392
1393
1394
1395 // Iterator base
1396
1397 template <class T, class tree_node_allocator>
iterator_base()1398 tree<T, tree_node_allocator>::iterator_base::iterator_base()
1399 : node(0), skip_current_children_(false)
1400 {
1401 }
1402
1403 template <class T, class tree_node_allocator>
iterator_base(tree_node * tn)1404 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
1405 : node(tn), skip_current_children_(false)
1406 {
1407 }
1408
1409 template <class T, class tree_node_allocator>
1410 T& tree<T, tree_node_allocator>::iterator_base::operator*() const
1411 {
1412 return node->data;
1413 }
1414
1415 template <class T, class tree_node_allocator>
1416 T* tree<T, tree_node_allocator>::iterator_base::operator->() const
1417 {
1418 return &(node->data);
1419 }
1420
1421 template <class T, class tree_node_allocator>
operator !=(const post_order_iterator & other) const1422 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
1423 {
1424 if(other.node!=this->node) return true;
1425 else return false;
1426 }
1427
1428 template <class T, class tree_node_allocator>
operator ==(const post_order_iterator & other) const1429 bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
1430 {
1431 if(other.node==this->node) return true;
1432 else return false;
1433 }
1434
1435 template <class T, class tree_node_allocator>
operator !=(const pre_order_iterator & other) const1436 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
1437 {
1438 if(other.node!=this->node) return true;
1439 else return false;
1440 }
1441
1442 template <class T, class tree_node_allocator>
operator ==(const pre_order_iterator & other) const1443 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
1444 {
1445 if(other.node==this->node) return true;
1446 else return false;
1447 }
1448
1449 template <class T, class tree_node_allocator>
operator !=(const sibling_iterator & other) const1450 bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
1451 {
1452 if(other.node!=this->node) return true;
1453 else return false;
1454 }
1455
1456 template <class T, class tree_node_allocator>
operator ==(const sibling_iterator & other) const1457 bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
1458 {
1459 if(other.node==this->node) return true;
1460 else return false;
1461 }
1462
1463 template <class T, class tree_node_allocator>
begin() const1464 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const
1465 {
1466 sibling_iterator ret(node->first_child);
1467 ret.parent_=this->node;
1468 return ret;
1469 }
1470
1471 template <class T, class tree_node_allocator>
end() const1472 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const
1473 {
1474 sibling_iterator ret(0);
1475 ret.parent_=node;
1476 return ret;
1477 }
1478
1479 template <class T, class tree_node_allocator>
skip_children()1480 void tree<T, tree_node_allocator>::iterator_base::skip_children()
1481 {
1482 skip_current_children_=true;
1483 }
1484
1485 template <class T, class tree_node_allocator>
number_of_children() const1486 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
1487 {
1488 tree_node *pos=node->first_child;
1489 if(pos==0) return 0;
1490
1491 unsigned int ret=1;
1492 while(pos!=node->last_child) {
1493 ++ret;
1494 pos=pos->next_sibling;
1495 }
1496 return ret;
1497 }
1498
1499
1500
1501 // Pre-order iterator
1502
1503 template <class T, class tree_node_allocator>
pre_order_iterator()1504 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
1505 : iterator_base(0)
1506 {
1507 }
1508
1509 template <class T, class tree_node_allocator>
pre_order_iterator(tree_node * tn)1510 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
1511 : iterator_base(tn)
1512 {
1513 }
1514
1515 template <class T, class tree_node_allocator>
pre_order_iterator(const iterator_base & other)1516 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)
1517 : iterator_base(other.node)
1518 {
1519 }
1520
1521 template <class T, class tree_node_allocator>
pre_order_iterator(const sibling_iterator & other)1522 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
1523 : iterator_base(other.node)
1524 {
1525 if(this->node==0) {
1526 if(other.range_last()!=0)
1527 this->node=other.range_last();
1528 else
1529 this->node=other.parent_;
1530 this->skip_children();
1531 ++(*this);
1532 }
1533 }
1534
1535 template <class T, class tree_node_allocator>
operator ++()1536 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
1537 {
1538 assert(this->node!=0);
1539 if(!this->skip_current_children_ && this->node->first_child != 0) {
1540 this->node=this->node->first_child;
1541 }
1542 else {
1543 this->skip_current_children_=false;
1544 while(this->node->next_sibling==0) {
1545 this->node=this->node->parent;
1546 if(this->node==0)
1547 return *this;
1548 }
1549 this->node=this->node->next_sibling;
1550 }
1551 return *this;
1552 }
1553
1554 template <class T, class tree_node_allocator>
operator --()1555 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
1556 {
1557 assert(this->node!=0);
1558 if(this->node->prev_sibling) {
1559 this->node=this->node->prev_sibling;
1560 while(this->node->last_child)
1561 this->node=this->node->last_child;
1562 }
1563 else {
1564 this->node=this->node->parent;
1565 if(this->node==0)
1566 return *this;
1567 }
1568 return *this;
1569 }
1570
1571 template <class T, class tree_node_allocator>
operator ++(int n)1572 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int n)
1573 {
1574 pre_order_iterator copy = *this;
1575 ++(*this);
1576 return copy;
1577 }
1578
1579 template <class T, class tree_node_allocator>
operator --(int n)1580 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int n)
1581 {
1582 pre_order_iterator copy = *this;
1583 --(*this);
1584 return copy;
1585 }
1586
1587 template <class T, class tree_node_allocator>
operator +=(unsigned int num)1588 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
1589 {
1590 while(num>0) {
1591 ++(*this);
1592 --num;
1593 }
1594 return (*this);
1595 }
1596
1597 template <class T, class tree_node_allocator>
operator -=(unsigned int num)1598 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
1599 {
1600 while(num>0) {
1601 --(*this);
1602 --num;
1603 }
1604 return (*this);
1605 }
1606
1607
1608
1609 // Post-order iterator
1610
1611 template <class T, class tree_node_allocator>
post_order_iterator()1612 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
1613 : iterator_base(0)
1614 {
1615 }
1616
1617 template <class T, class tree_node_allocator>
post_order_iterator(tree_node * tn)1618 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
1619 : iterator_base(tn)
1620 {
1621 }
1622
1623 template <class T, class tree_node_allocator>
post_order_iterator(const iterator_base & other)1624 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)
1625 : iterator_base(other.node)
1626 {
1627 }
1628
1629 template <class T, class tree_node_allocator>
post_order_iterator(const sibling_iterator & other)1630 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)
1631 : iterator_base(other.node)
1632 {
1633 if(this->node==0) {
1634 if(other.range_last()!=0)
1635 this->node=other.range_last();
1636 else
1637 this->node=other.parent_;
1638 this->skip_children();
1639 ++(*this);
1640 }
1641 }
1642
1643 template <class T, class tree_node_allocator>
operator ++()1644 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
1645 {
1646 assert(this->node!=0);
1647 if(this->node->next_sibling==0)
1648 this->node=this->node->parent;
1649 else {
1650 this->node=this->node->next_sibling;
1651 if(this->skip_current_children_) {
1652 this->skip_current_children_=false;
1653 }
1654 else {
1655 while(this->node->first_child)
1656 this->node=this->node->first_child;
1657 }
1658 }
1659 return *this;
1660 }
1661
1662 template <class T, class tree_node_allocator>
operator --()1663 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
1664 {
1665 assert(this->node!=0);
1666 if(this->skip_current_children_ || this->node->last_child==0) {
1667 this->skip_current_children_=false;
1668 while(this->node->prev_sibling==0)
1669 this->node=this->node->parent;
1670 this->node=this->node->prev_sibling;
1671 }
1672 else {
1673 this->node=this->node->last_child;
1674 }
1675 return *this;
1676 }
1677
1678 template <class T, class tree_node_allocator>
operator ++(int)1679 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
1680 {
1681 post_order_iterator copy = *this;
1682 ++(*this);
1683 return copy;
1684 }
1685
1686 template <class T, class tree_node_allocator>
operator --(int)1687 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
1688 {
1689 post_order_iterator copy = *this;
1690 --(*this);
1691 return copy;
1692 }
1693
1694
1695 template <class T, class tree_node_allocator>
operator +=(unsigned int num)1696 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
1697 {
1698 while(num>0) {
1699 ++(*this);
1700 --num;
1701 }
1702 return (*this);
1703 }
1704
1705 template <class T, class tree_node_allocator>
operator -=(unsigned int num)1706 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
1707 {
1708 while(num>0) {
1709 --(*this);
1710 --num;
1711 }
1712 return (*this);
1713 }
1714
1715 template <class T, class tree_node_allocator>
descend_all()1716 void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
1717 {
1718 assert(this->node!=0);
1719 while(this->node->first_child)
1720 this->node=this->node->first_child;
1721 }
1722
1723
1724 // Fixed depth iterator
1725
1726 template <class T, class tree_node_allocator>
fixed_depth_iterator()1727 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
1728 : iterator_base()
1729 {
1730 set_first_parent_();
1731 }
1732
1733 template <class T, class tree_node_allocator>
fixed_depth_iterator(tree_node * tn)1734 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
1735 : iterator_base(tn)
1736 {
1737 set_first_parent_();
1738 }
1739
1740 template <class T, class tree_node_allocator>
fixed_depth_iterator(const iterator_base & other)1741 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)
1742 : iterator_base(other.node)
1743 {
1744 set_first_parent_();
1745 }
1746
1747 template <class T, class tree_node_allocator>
fixed_depth_iterator(const sibling_iterator & other)1748 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
1749 : iterator_base(other.node), first_parent_(other.parent_)
1750 {
1751 find_leftmost_parent_();
1752 }
1753
1754 template <class T, class tree_node_allocator>
fixed_depth_iterator(const fixed_depth_iterator & other)1755 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)
1756 : iterator_base(other.node), first_parent_(other.first_parent_)
1757 {
1758 }
1759
1760 template <class T, class tree_node_allocator>
set_first_parent_()1761 void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
1762 {
1763 return; // FIXME: we do not use first_parent_ yet, and it actually needs some serious reworking if
1764 // it is ever to work at the 'head' level.
1765 first_parent_=0;
1766 if(this->node==0) return;
1767 if(this->node->parent!=0)
1768 first_parent_=this->node->parent;
1769 if(first_parent_)
1770 find_leftmost_parent_();
1771 }
1772
1773 template <class T, class tree_node_allocator>
find_leftmost_parent_()1774 void tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()
1775 {
1776 return; // FIXME: see 'set_first_parent()'
1777 tree_node *tmppar=first_parent_;
1778 while(tmppar->prev_sibling) {
1779 tmppar=tmppar->prev_sibling;
1780 if(tmppar->first_child)
1781 first_parent_=tmppar;
1782 }
1783 }
1784
1785 template <class T, class tree_node_allocator>
operator ++()1786 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
1787 {
1788 assert(this->node!=0);
1789 if(this->node->next_sibling!=0) {
1790 this->node=this->node->next_sibling;
1791 assert(this->node!=0);
1792 if(this->node->parent==0 && this->node->next_sibling==0) // feet element
1793 this->node=0;
1794 }
1795 else {
1796 tree_node *par=this->node->parent;
1797 do {
1798 par=par->next_sibling;
1799 if(par==0) { // FIXME: need to keep track of this!
1800 this->node=0;
1801 return *this;
1802 }
1803 } while(par->first_child==0);
1804 this->node=par->first_child;
1805 }
1806 return *this;
1807 }
1808
1809 template <class T, class tree_node_allocator>
operator --()1810 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
1811 {
1812 assert(this->node!=0);
1813 if(this->node->prev_sibling!=0) {
1814 this->node=this->node->prev_sibling;
1815 assert(this->node!=0);
1816 if(this->node->parent==0 && this->node->prev_sibling==0) // head element
1817 this->node=0;
1818 }
1819 else {
1820 tree_node *par=this->node->parent;
1821 do {
1822 par=par->prev_sibling;
1823 if(par==0) { // FIXME: need to keep track of this!
1824 this->node=0;
1825 return *this;
1826 }
1827 } while(par->last_child==0);
1828 this->node=par->last_child;
1829 }
1830 return *this;
1831 }
1832
1833 template <class T, class tree_node_allocator>
operator ++(int)1834 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)
1835 {
1836 fixed_depth_iterator copy = *this;
1837 ++(*this);
1838 return copy;
1839 }
1840
1841 template <class T, class tree_node_allocator>
operator --(int)1842 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)
1843 {
1844 fixed_depth_iterator copy = *this;
1845 --(*this);
1846 return copy;
1847 }
1848
1849 template <class T, class tree_node_allocator>
operator -=(unsigned int num)1850 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
1851 {
1852 while(num>0) {
1853 --(*this);
1854 --(num);
1855 }
1856 return (*this);
1857 }
1858
1859 template <class T, class tree_node_allocator>
operator +=(unsigned int num)1860 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
1861 {
1862 while(num>0) {
1863 ++(*this);
1864 --(num);
1865 }
1866 return *this;
1867 }
1868
1869 // FIXME: add the other members of fixed_depth_iterator.
1870
1871
1872 // Sibling iterator
1873
1874 template <class T, class tree_node_allocator>
sibling_iterator()1875 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
1876 : iterator_base()
1877 {
1878 set_parent_();
1879 }
1880
1881 template <class T, class tree_node_allocator>
sibling_iterator(tree_node * tn)1882 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
1883 : iterator_base(tn)
1884 {
1885 set_parent_();
1886 }
1887
1888 template <class T, class tree_node_allocator>
sibling_iterator(const iterator_base & other)1889 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)
1890 : iterator_base(other.node)
1891 {
1892 set_parent_();
1893 }
1894
1895 template <class T, class tree_node_allocator>
sibling_iterator(const sibling_iterator & other)1896 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)
1897 : iterator_base(other), parent_(other.parent_)
1898 {
1899 }
1900
1901 template <class T, class tree_node_allocator>
set_parent_()1902 void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
1903 {
1904 parent_=0;
1905 if(this->node==0) return;
1906 if(this->node->parent!=0)
1907 parent_=this->node->parent;
1908 }
1909
1910 template <class T, class tree_node_allocator>
operator ++()1911 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
1912 {
1913 if(this->node)
1914 this->node=this->node->next_sibling;
1915 return *this;
1916 }
1917
1918 template <class T, class tree_node_allocator>
operator --()1919 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
1920 {
1921 if(this->node) this->node=this->node->prev_sibling;
1922 else {
1923 assert(parent_);
1924 this->node=parent_->last_child;
1925 }
1926 return *this;
1927 }
1928
1929 template <class T, class tree_node_allocator>
operator ++(int)1930 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)
1931 {
1932 sibling_iterator copy = *this;
1933 ++(*this);
1934 return copy;
1935 }
1936
1937 template <class T, class tree_node_allocator>
operator --(int)1938 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)
1939 {
1940 sibling_iterator copy = *this;
1941 --(*this);
1942 return copy;
1943 }
1944
1945 template <class T, class tree_node_allocator>
operator +=(unsigned int num)1946 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
1947 {
1948 while(num>0) {
1949 ++(*this);
1950 --num;
1951 }
1952 return (*this);
1953 }
1954
1955 template <class T, class tree_node_allocator>
operator -=(unsigned int num)1956 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
1957 {
1958 while(num>0) {
1959 --(*this);
1960 --num;
1961 }
1962 return (*this);
1963 }
1964
1965 template <class T, class tree_node_allocator>
range_first() const1966 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const
1967 {
1968 tree_node *tmp=parent_->first_child;
1969 return tmp;
1970 }
1971
1972 template <class T, class tree_node_allocator>
range_last() const1973 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const
1974 {
1975 return parent_->last_child;
1976 }
1977
1978
1979 #endif
1980
1981 // Local variables:
1982 // default-tab-width: 3
1983 // End:
1984