liborigin 2.0.0
/usr/src/slapt-src/libraries/liborigin/liborigin/tree.hh
Go to the documentation of this file.
1/*
2
3 $Id: tree.hh,v 1.147 2007/10/19 11:24:24 peekas Exp $
4
5 STL-like templated tree class.
6 Copyright (C) 2001-2006 Kasper Peeters <kasper.peeters@aei.mpg.de>.
7
8*/
9
26/*
27 The tree.hh code is free software; you can redistribute it and/or modify
28 it under the terms of the GNU General Public License as published by
29 the Free Software Foundation; version 2 or 3.
30
31 This program is distributed in the hope that it will be useful,
32 but WITHOUT ANY WARRANTY; without even the implied warranty of
33 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
34 GNU General Public License for more details.
35
36 You should have received a copy of the GNU General Public License
37 along with this program; if not, write to the Free Software
38 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
39*/
40
60#ifndef tree_hh_
61#define tree_hh_
62
63#include <cassert>
64#include <memory>
65#include <stdexcept>
66#include <iterator>
67#include <set>
68#include <queue>
69#include <iostream>
70
71// HP-style construct/destroy have gone from the standard,
72// so here is a copy.
73
74namespace kp {
75
76template <class T1, class T2>
77void constructor(T1* p, T2& val)
78 {
79 new ((void *) p) T1(val);
80 }
81
82template <class T1>
83void constructor(T1* p)
84 {
85 new ((void *) p) T1;
86 }
87
88template <class T1>
89void destructor(T1* p)
90 {
91 p->~T1();
92 }
93
94};
95
97template<class T>
98class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
99 public:
104}; // __attribute__((packed));
105
106template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
107class tree {
108 protected:
110 public:
112 typedef T value_type;
113
114 class iterator_base;
115 class pre_order_iterator;
117 class sibling_iterator;
118 class leaf_iterator;
119
121 tree(const T&);
122 tree(const iterator_base&);
126
128#ifdef __SGI_STL_PORT
129 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
130#else
132#endif
133 public:
134 typedef T value_type;
135 typedef T* pointer;
136 typedef T& reference;
137 typedef size_t size_type;
138 typedef ptrdiff_t difference_type;
139 typedef std::bidirectional_iterator_tag iterator_category;
140
143
144 T& operator*() const;
145 T* operator->() const;
146
150 unsigned int number_of_children() const;
151
152 sibling_iterator begin() const;
153 sibling_iterator end() const;
154
156 protected:
158 };
159
162 public:
163 pre_order_iterator();
164 pre_order_iterator(tree_node *);
165 pre_order_iterator(const iterator_base&);
166 pre_order_iterator(const sibling_iterator&);
167
168 bool operator==(const pre_order_iterator&) const;
169 bool operator!=(const pre_order_iterator&) const;
170 pre_order_iterator& operator++();
171 pre_order_iterator& operator--();
172 pre_order_iterator operator++(int);
173 pre_order_iterator operator--(int);
174 pre_order_iterator& operator+=(unsigned int);
175 pre_order_iterator& operator-=(unsigned int);
176 };
177
180 public:
181 post_order_iterator();
182 post_order_iterator(tree_node *);
183 post_order_iterator(const iterator_base&);
184 post_order_iterator(const sibling_iterator&);
185
186 bool operator==(const post_order_iterator&) const;
187 bool operator!=(const post_order_iterator&) const;
188 post_order_iterator& operator++();
189 post_order_iterator& operator--();
190 post_order_iterator operator++(int);
191 post_order_iterator operator--(int);
192 post_order_iterator& operator+=(unsigned int);
193 post_order_iterator& operator-=(unsigned int);
194
196 void descend_all();
197 };
198
201 public:
202 breadth_first_queued_iterator();
203 breadth_first_queued_iterator(tree_node *);
204 breadth_first_queued_iterator(const iterator_base&);
205
206 bool operator==(const breadth_first_queued_iterator&) const;
207 bool operator!=(const breadth_first_queued_iterator&) const;
208 breadth_first_queued_iterator& operator++();
209 breadth_first_queued_iterator operator++(int);
210 breadth_first_queued_iterator& operator+=(unsigned int);
211
212 private:
213 std::queue<tree_node *> traversal_queue;
214 };
215
219
222 public:
223 fixed_depth_iterator();
224 fixed_depth_iterator(tree_node *);
225 fixed_depth_iterator(const iterator_base&);
226 fixed_depth_iterator(const sibling_iterator&);
227 fixed_depth_iterator(const fixed_depth_iterator&);
228
229 bool operator==(const fixed_depth_iterator&) const;
230 bool operator!=(const fixed_depth_iterator&) const;
231 fixed_depth_iterator& operator++();
232 fixed_depth_iterator& operator--();
233 fixed_depth_iterator operator++(int);
234 fixed_depth_iterator operator--(int);
235 fixed_depth_iterator& operator+=(unsigned int);
236 fixed_depth_iterator& operator-=(unsigned int);
237
239 private:
240 void set_first_parent_();
241 void find_leftmost_parent_();
242 };
243
246 public:
247 sibling_iterator();
248 sibling_iterator(tree_node *);
249 sibling_iterator(const sibling_iterator&);
250 sibling_iterator(const iterator_base&);
251
252 bool operator==(const sibling_iterator&) const;
253 bool operator!=(const sibling_iterator&) const;
254 sibling_iterator& operator++();
255 sibling_iterator& operator--();
256 sibling_iterator operator++(int);
257 sibling_iterator operator--(int);
258 sibling_iterator& operator+=(unsigned int);
259 sibling_iterator& operator-=(unsigned int);
260
261 tree_node *range_first() const;
262 tree_node *range_last() const;
264 private:
265 void set_parent_();
266 };
267
270 public:
271 leaf_iterator();
272 leaf_iterator(tree_node *);
273 leaf_iterator(const sibling_iterator&);
274 leaf_iterator(const iterator_base&);
275
276 bool operator==(const leaf_iterator&) const;
277 bool operator!=(const leaf_iterator&) const;
278 leaf_iterator& operator++();
279 leaf_iterator& operator--();
280 leaf_iterator operator++(int);
281 leaf_iterator operator--(int);
282 leaf_iterator& operator+=(unsigned int);
283 leaf_iterator& operator-=(unsigned int);
284 };
285
287 inline pre_order_iterator begin() const;
289 inline pre_order_iterator end() const;
291 post_order_iterator begin_post() const;
293 post_order_iterator end_post() const;
295 fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
297 fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
299 breadth_first_queued_iterator begin_breadth_first() const;
301 breadth_first_queued_iterator end_breadth_first() const;
303 sibling_iterator begin(const iterator_base&) const;
305 sibling_iterator end(const iterator_base&) const;
307 leaf_iterator begin_leaf() const;
309 leaf_iterator end_leaf() const;
310
312 template<typename iter> static iter parent(iter);
314 template<typename iter> iter previous_sibling(iter) const;
316 template<typename iter> iter next_sibling(iter) const;
318 template<typename iter> iter next_at_same_depth(iter) const;
319
321 void clear();
323 template<typename iter> iter erase(iter);
326
328 template<typename iter> iter append_child(iter position);
329 template<typename iter> iter prepend_child(iter position);
331 template<typename iter> iter append_child(iter position, const T& x);
332 template<typename iter> iter prepend_child(iter position, const T& x);
334 template<typename iter> iter append_child(iter position, iter other_position);
335 template<typename iter> iter prepend_child(iter position, iter other_position);
337 template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
338 template<typename iter> iter prepend_children(iter position, sibling_iterator from, sibling_iterator to);
339
341 pre_order_iterator set_head(const T& x);
343 template<typename iter> iter insert(iter position, const T& x);
345 sibling_iterator insert(sibling_iterator position, const T& x);
347 template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
349 template<typename iter> iter insert_after(iter position, const T& x);
351 template<typename iter> iter insert_subtree_after(iter position, const iterator_base& subtree);
352
354 template<typename iter> iter replace(iter position, const T& x);
356 template<typename iter> iter replace(iter position, const iterator_base& from);
358 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
359 sibling_iterator new_begin, sibling_iterator new_end);
360
362 template<typename iter> iter flatten(iter position);
364 template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
366 template<typename iter> iter reparent(iter position, iter from);
367
369 template<typename iter> iter wrap(iter position, const T& x);
370
372 template<typename iter> iter move_after(iter target, iter source);
374 template<typename iter> iter move_before(iter target, iter source);
375 sibling_iterator move_before(sibling_iterator target, sibling_iterator source);
377 template<typename iter> iter move_ontop(iter target, iter source);
378
380 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
381 bool duplicate_leaves=false);
383 void sort(sibling_iterator from, sibling_iterator to, bool deep=false);
384 template<class StrictWeakOrdering>
385 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
387 template<typename iter>
388 bool equal(const iter& one, const iter& two, const iter& three) const;
389 template<typename iter, class BinaryPredicate>
390 bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
391 template<typename iter>
392 bool equal_subtree(const iter& one, const iter& two) const;
393 template<typename iter, class BinaryPredicate>
394 bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
396 tree subtree(sibling_iterator from, sibling_iterator to) const;
397 void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
399 void swap(sibling_iterator it);
402
404 int size() const;
406 int size(const iterator_base&) const;
408 bool empty() const;
410 int depth(const iterator_base&) const;
412 int max_depth() const;
414 int max_depth(const iterator_base&) const;
416 static unsigned int number_of_children(const iterator_base&);
418 unsigned int number_of_siblings(const iterator_base&) const;
420 bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
421 const iterator_base& end) const;
423 bool is_valid(const iterator_base&) const;
424
426 unsigned int index(sibling_iterator it) const;
428 sibling_iterator child(const iterator_base& position, unsigned int) const;
429
432 public:
434 const typename tree<T, tree_node_allocator>::iterator_base& two) const
435 {
436 return one.node < two.node;
437 }
438 };
439 tree_node *head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid
440 private:
441 tree_node_allocator alloc_;
444
446 template<class StrictWeakOrdering>
448 public:
449 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
450
451 bool operator()(const tree_node *a, const tree_node *b)
452 {
453 static StrictWeakOrdering comp;
454 return comp(a->data, b->data);
455 }
456 private:
457 StrictWeakOrdering comp_;
458 };
459};
460
461//template <class T, class tree_node_allocator>
462//class iterator_base_less {
463// public:
464// bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
465// const typename tree<T, tree_node_allocator>::iterator_base& two) const
466// {
467// txtout << "operatorclass<" << one.node < two.node << std::endl;
468// return one.node < two.node;
469// }
470//};
471
472// template <class T, class tree_node_allocator>
473// bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
474// const typename tree<T, tree_node_allocator>::iterator& two)
475// {
476// txtout << "operator< " << one.node < two.node << std::endl;
477// if(one.node < two.node) return true;
478// return false;
479// }
480//
481// template <class T, class tree_node_allocator>
482// bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
483// const typename tree<T, tree_node_allocator>::iterator& two)
484// {
485// txtout << "operator== " << one.node == two.node << std::endl;
486// if(one.node == two.node) return true;
487// return false;
488// }
489//
490// template <class T, class tree_node_allocator>
491// bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
492// const typename tree<T, tree_node_allocator>::iterator_base& two)
493// {
494// txtout << "operator> " << one.node < two.node << std::endl;
495// if(one.node > two.node) return true;
496// return false;
497// }
498
499
500
501// Tree
502
503template <class T, class tree_node_allocator>
505 {
507 }
508
509template <class T, class tree_node_allocator>
511 {
513 set_head(x);
514 }
515
516template <class T, class tree_node_allocator>
518 {
520 set_head((*other));
521 replace(begin(), other);
522 }
523
524template <class T, class tree_node_allocator>
526 {
527 clear();
528 alloc_.deallocate(head,1);
529 alloc_.deallocate(feet,1);
530 }
531
532template <class T, class tree_node_allocator>
534 {
535 head = alloc_.allocate(1,0); // MSVC does not have default second argument
536 feet = alloc_.allocate(1,0);
537
538 head->parent=0;
539 head->first_child=0;
540 head->last_child=0;
541 head->prev_sibling=0; //head;
542 head->next_sibling=feet; //head;
543
544 feet->parent=0;
545 feet->first_child=0;
546 feet->last_child=0;
549 }
550
551template <class T, class tree_node_allocator>
553 {
554 copy_(other);
555 }
556
557template <class T, class tree_node_allocator>
559 {
561 copy_(other);
562 }
563
564template <class T, class tree_node_allocator>
566 {
567 clear();
568 pre_order_iterator it=other.begin(), to=begin();
569 while(it!=other.end()) {
570 to=insert(to, (*it));
571 it.skip_children();
572 ++it;
573 }
574 to=begin();
575 it=other.begin();
576 while(it!=other.end()) {
577 to=replace(to, it);
578 to.skip_children();
579 it.skip_children();
580 ++to;
581 ++it;
582 }
583 }
584
585template <class T, class tree_node_allocator>
587 {
588 if(head)
589 while(head->next_sibling!=feet)
591 }
592
593template<class T, class tree_node_allocator>
595 {
596// std::cout << "erase_children " << it.node << std::endl;
597 if(it.node==0) return;
598
599 tree_node *cur=it.node->first_child;
600 tree_node *prev=0;
601
602 while(cur!=0) {
603 prev=cur;
604 cur=cur->next_sibling;
606 kp::destructor(&prev->data);
607 alloc_.deallocate(prev,1);
608 }
609 it.node->first_child=0;
610 it.node->last_child=0;
611// std::cout << "exit" << std::endl;
612 }
613
614template<class T, class tree_node_allocator>
615template<class iter>
617 {
618 tree_node *cur=it.node;
619 assert(cur!=head);
620 iter ret=it;
621 ret.skip_children();
622 ++ret;
623 erase_children(it);
624 if(cur->prev_sibling==0) {
625 cur->parent->first_child=cur->next_sibling;
626 }
627 else {
628 cur->prev_sibling->next_sibling=cur->next_sibling;
629 }
630 if(cur->next_sibling==0) {
631 cur->parent->last_child=cur->prev_sibling;
632 }
633 else {
634 cur->next_sibling->prev_sibling=cur->prev_sibling;
635 }
636
637 kp::destructor(&cur->data);
638 alloc_.deallocate(cur,1);
639 return ret;
640 }
641
642template <class T, class tree_node_allocator>
644 {
646 }
647
648template <class T, class tree_node_allocator>
650 {
651 return pre_order_iterator(feet);
652 }
653
654template <class T, class tree_node_allocator>
656 {
658 }
659
660template <class T, class tree_node_allocator>
662 {
664 }
665
666template <class T, class tree_node_allocator>
668 {
670 if(tmp!=feet) {
671 while(tmp->first_child)
672 tmp=tmp->first_child;
673 }
674 return post_order_iterator(tmp);
675 }
676
677template <class T, class tree_node_allocator>
679 {
681 }
682
683template <class T, class tree_node_allocator>
685 {
686 tree_node *tmp=pos.node;
687 unsigned int curdepth=0;
688 while(curdepth<dp) { // go down one level
689 while(tmp->first_child==0) {
690 if(tmp->next_sibling==0) {
691 // try to walk up and then right again
692 do {
693 tmp=tmp->parent;
694 if(tmp==0)
695 throw std::range_error("tree: begin_fixed out of range");
696 --curdepth;
697 } while(tmp->next_sibling==0);
698 }
699 tmp=tmp->next_sibling;
700 }
701 tmp=tmp->first_child;
702 ++curdepth;
703 }
704 return tmp;
705 }
706
707template <class T, class tree_node_allocator>
709 {
710 assert(1==0); // FIXME: not correct yet: use is_valid() as a temporary workaround
711 tree_node *tmp=pos.node;
712 unsigned int curdepth=1;
713 while(curdepth<dp) { // go down one level
714 while(tmp->first_child==0) {
715 tmp=tmp->next_sibling;
716 if(tmp==0)
717 throw std::range_error("tree: end_fixed out of range");
718 }
719 tmp=tmp->first_child;
720 ++curdepth;
721 }
722 return tmp;
723 }
724
725template <class T, class tree_node_allocator>
727 {
728 assert(pos.node!=0);
729 if(pos.node->first_child==0) {
730 return end(pos);
731 }
732 return pos.node->first_child;
733 }
734
735template <class T, class tree_node_allocator>
737 {
738 sibling_iterator ret(0);
739 ret.parent_=pos.node;
740 return ret;
741 }
742
743template <class T, class tree_node_allocator>
745 {
747 if(tmp!=feet) {
748 while(tmp->first_child)
749 tmp=tmp->first_child;
750 }
751 return leaf_iterator(tmp);
752 }
753
754template <class T, class tree_node_allocator>
756 {
757 return leaf_iterator(feet);
758 }
759
760template <class T, class tree_node_allocator>
761template <typename iter>
763 {
764 assert(position.node!=0);
765 return iter(position.node->parent);
766 }
767
768template <class T, class tree_node_allocator>
769template <typename iter>
771 {
772 assert(position.node!=0);
773 iter ret(position);
774 ret.node=position.node->prev_sibling;
775 return ret;
776 }
777
778template <class T, class tree_node_allocator>
779template <typename iter>
781 {
782 assert(position.node!=0);
783 iter ret(position);
784 ret.node=position.node->next_sibling;
785 return ret;
786 }
787
788template <class T, class tree_node_allocator>
789template <typename iter>
791 {
792 assert(position.node!=0);
793 iter ret(position);
794
795 if(position.node->next_sibling) {
796 ret.node=position.node->next_sibling;
797 }
798 else {
799 int relative_depth=0;
800 upper:
801 do {
802 ret.node=ret.node->parent;
803 if(ret.node==0) return ret;
804 --relative_depth;
805 } while(ret.node->next_sibling==0);
806 lower:
807 ret.node=ret.node->next_sibling;
808 while(ret.node->first_child==0) {
809 if(ret.node->next_sibling==0)
810 goto upper;
811 ret.node=ret.node->next_sibling;
812 if(ret.node==0) return ret;
813 }
814 while(relative_depth<0 && ret.node->first_child!=0) {
815 ret.node=ret.node->first_child;
816 ++relative_depth;
817 }
818 if(relative_depth<0) {
819 if(ret.node->next_sibling==0) goto upper;
820 else goto lower;
821 }
822 }
823 return ret;
824 }
825
826template <class T, class tree_node_allocator>
827template <typename iter>
829 {
830 assert(position.node!=head);
831 assert(position.node);
832
833 tree_node *tmp=alloc_.allocate(1,0);
834 kp::constructor(&tmp->data);
835 tmp->first_child=0;
836 tmp->last_child=0;
837
838 tmp->parent=position.node;
839 if(position.node->last_child!=0) {
840 position.node->last_child->next_sibling=tmp;
841 }
842 else {
843 position.node->first_child=tmp;
844 }
845 tmp->prev_sibling=position.node->last_child;
846 position.node->last_child=tmp;
847 tmp->next_sibling=0;
848 return tmp;
849 }
850
851template <class T, class tree_node_allocator>
852template <typename iter>
854 {
855 assert(position.node!=head);
856 assert(position.node);
857
858 tree_node *tmp=alloc_.allocate(1,0);
859 kp::constructor(&tmp->data);
860 tmp->first_child=0;
861 tmp->last_child=0;
862
863 tmp->parent=position.node;
864 if(position.node->first_child!=0) {
865 position.node->first_child->prev_sibling=tmp;
866 }
867 else {
868 position.node->last_child=tmp;
869 }
870 tmp->next_sibling=position.node->first_child;
871 position.node->prev_child=tmp;
872 tmp->prev_sibling=0;
873 return tmp;
874 }
875
876template <class T, class tree_node_allocator>
877template <class iter>
878iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
879 {
880 // If your program fails here you probably used 'append_child' to add the top
881 // node to an empty tree. From version 1.45 the top element should be added
882 // using 'insert'. See the documentation for further information, and sorry about
883 // the API change.
884 assert(position.node!=head);
885 assert(position.node);
886
887 tree_node* tmp = alloc_.allocate(1,0);
888 kp::constructor(&tmp->data, x);
889 tmp->first_child=0;
890 tmp->last_child=0;
891
892 tmp->parent=position.node;
893 if(position.node->last_child!=0) {
894 position.node->last_child->next_sibling=tmp;
895 }
896 else {
897 position.node->first_child=tmp;
898 }
899 tmp->prev_sibling=position.node->last_child;
900 position.node->last_child=tmp;
901 tmp->next_sibling=0;
902 return tmp;
903 }
904
905template <class T, class tree_node_allocator>
906template <class iter>
907iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
908 {
909 assert(position.node!=head);
910 assert(position.node);
911
912 tree_node* tmp = alloc_.allocate(1,0);
913 kp::constructor(&tmp->data, x);
914 tmp->first_child=0;
915 tmp->last_child=0;
916
917 tmp->parent=position.node;
918 if(position.node->first_child!=0) {
919 position.node->first_child->prev_sibling=tmp;
920 }
921 else {
922 position.node->last_child=tmp;
923 }
924 tmp->next_sibling=position.node->first_child;
925 position.node->first_child=tmp;
926 tmp->prev_sibling=0;
927 return tmp;
928 }
929
930template <class T, class tree_node_allocator>
931template <class iter>
932iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
933 {
934 assert(position.node!=head);
935 assert(position.node);
936
937 sibling_iterator aargh=append_child(position, value_type());
938 return replace(aargh, other);
939 }
940
941template <class T, class tree_node_allocator>
942template <class iter>
943iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)
944 {
945 assert(position.node!=head);
946 assert(position.node);
947
948 sibling_iterator aargh=prepend_child(position, value_type());
949 return replace(aargh, other);
950 }
951
952template <class T, class tree_node_allocator>
953template <class iter>
955 {
956 assert(position.node!=head);
957 assert(position.node);
958
959 iter ret=from;
960
961 while(from!=to) {
962 insert_subtree(position.end(), from);
963 ++from;
964 }
965 return ret;
966 }
967
968template <class T, class tree_node_allocator>
969template <class iter>
971 {
972 assert(position.node!=head);
973 assert(position.node);
974
975 iter ret=from;
976
977 while(from!=to) {
978 insert_subtree(position.begin(), from);
979 ++from;
980 }
981 return ret;
982 }
983
984template <class T, class tree_node_allocator>
986 {
987 assert(head->next_sibling==feet);
988 return insert(iterator(feet), x);
989 }
990
991template <class T, class tree_node_allocator>
992template <class iter>
993iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
994 {
995 if(position.node==0) {
996 position.node=feet; // Backward compatibility: when calling insert on a null node,
997 // insert before the feet.
998 }
999 tree_node* tmp = alloc_.allocate(1,0);
1000 kp::constructor(&tmp->data, x);
1001 tmp->first_child=0;
1002 tmp->last_child=0;
1003
1004 tmp->parent=position.node->parent;
1005 tmp->next_sibling=position.node;
1006 tmp->prev_sibling=position.node->prev_sibling;
1007 position.node->prev_sibling=tmp;
1008
1009 if(tmp->prev_sibling==0) {
1010 if(tmp->parent) // when inserting nodes at the head, there is no parent
1011 tmp->parent->first_child=tmp;
1012 }
1013 else
1014 tmp->prev_sibling->next_sibling=tmp;
1015 return tmp;
1016 }
1017
1018template <class T, class tree_node_allocator>
1020 {
1021 tree_node* tmp = alloc_.allocate(1,0);
1022 kp::constructor(&tmp->data, x);
1023 tmp->first_child=0;
1024 tmp->last_child=0;
1025
1026 tmp->next_sibling=position.node;
1027 if(position.node==0) { // iterator points to end of a subtree
1028 tmp->parent=position.parent_;
1029 tmp->prev_sibling=position.range_last();
1030 tmp->parent->last_child=tmp;
1031 }
1032 else {
1033 tmp->parent=position.node->parent;
1034 tmp->prev_sibling=position.node->prev_sibling;
1035 position.node->prev_sibling=tmp;
1036 }
1037
1038 if(tmp->prev_sibling==0) {
1039 if(tmp->parent) // when inserting nodes at the head, there is no parent
1040 tmp->parent->first_child=tmp;
1041 }
1042 else
1043 tmp->prev_sibling->next_sibling=tmp;
1044 return tmp;
1045 }
1046
1047template <class T, class tree_node_allocator>
1048template <class iter>
1049iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
1050 {
1051 tree_node* tmp = alloc_.allocate(1,0);
1052 kp::constructor(&tmp->data, x);
1053 tmp->first_child=0;
1054 tmp->last_child=0;
1055
1056 tmp->parent=position.node->parent;
1057 tmp->prev_sibling=position.node;
1058 tmp->next_sibling=position.node->next_sibling;
1059 position.node->next_sibling=tmp;
1060
1061 if(tmp->next_sibling==0) {
1062 if(tmp->parent) // when inserting nodes at the head, there is no parent
1063 tmp->parent->last_child=tmp;
1064 }
1065 else {
1066 tmp->next_sibling->prev_sibling=tmp;
1067 }
1068 return tmp;
1069 }
1070
1071template <class T, class tree_node_allocator>
1072template <class iter>
1074 {
1075 // insert dummy
1076 iter it=insert(position, value_type());
1077 // replace dummy with subtree
1078 return replace(it, subtree);
1079 }
1080
1081template <class T, class tree_node_allocator>
1082template <class iter>
1084 {
1085 // insert dummy
1086 iter it=insert_after(position, value_type());
1087 // replace dummy with subtree
1088 return replace(it, subtree);
1089 }
1090
1091// template <class T, class tree_node_allocator>
1092// template <class iter>
1093// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
1094// {
1095// // insert dummy
1096// iter it(insert(position, value_type()));
1097// // replace dummy with subtree
1098// return replace(it, subtree);
1099// }
1100
1101template <class T, class tree_node_allocator>
1102template <class iter>
1103iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
1104 {
1105 kp::destructor(&position.node->data);
1106 kp::constructor(&position.node->data, x);
1107 return position;
1108 }
1109
1110template <class T, class tree_node_allocator>
1111template <class iter>
1113 {
1114 assert(position.node!=head);
1115 tree_node *current_from=from.node;
1116 tree_node *start_from=from.node;
1117 tree_node *current_to =position.node;
1118
1119 // replace the node at position with head of the replacement tree at from
1120// std::cout << "warning!" << position.node << std::endl;
1121 erase_children(position);
1122// std::cout << "no warning!" << std::endl;
1123 tree_node* tmp = alloc_.allocate(1,0);
1124 kp::constructor(&tmp->data, (*from));
1125 tmp->first_child=0;
1126 tmp->last_child=0;
1127 if(current_to->prev_sibling==0) {
1128 if(current_to->parent!=0)
1129 current_to->parent->first_child=tmp;
1130 }
1131 else {
1132 current_to->prev_sibling->next_sibling=tmp;
1133 }
1134 tmp->prev_sibling=current_to->prev_sibling;
1135 if(current_to->next_sibling==0) {
1136 if(current_to->parent!=0)
1137 current_to->parent->last_child=tmp;
1138 }
1139 else {
1140 current_to->next_sibling->prev_sibling=tmp;
1141 }
1142 tmp->next_sibling=current_to->next_sibling;
1143 tmp->parent=current_to->parent;
1144 kp::destructor(&current_to->data);
1145 alloc_.deallocate(current_to,1);
1146 current_to=tmp;
1147
1148 // only at this stage can we fix 'last'
1149 tree_node *last=from.node->next_sibling;
1150
1151 pre_order_iterator toit=tmp;
1152 // copy all children
1153 do {
1154 assert(current_from!=0);
1155 if(current_from->first_child != 0) {
1156 current_from=current_from->first_child;
1157 toit=append_child(toit, current_from->data);
1158 }
1159 else {
1160 while(current_from->next_sibling==0 && current_from!=start_from) {
1161 current_from=current_from->parent;
1162 toit=parent(toit);
1163 assert(current_from!=0);
1164 }
1165 current_from=current_from->next_sibling;
1166 if(current_from!=last) {
1167 toit=append_child(parent(toit), current_from->data);
1168 }
1169 }
1170 } while(current_from!=last);
1171
1172 return current_to;
1173 }
1174
1175template <class T, class tree_node_allocator>
1177 sibling_iterator orig_begin,
1178 sibling_iterator orig_end,
1179 sibling_iterator new_begin,
1180 sibling_iterator new_end)
1181 {
1182 tree_node *orig_first=orig_begin.node;
1183 tree_node *new_first=new_begin.node;
1184 tree_node *orig_last=orig_first;
1185 while((++orig_begin)!=orig_end)
1186 orig_last=orig_last->next_sibling;
1187 tree_node *new_last=new_first;
1188 while((++new_begin)!=new_end)
1189 new_last=new_last->next_sibling;
1190
1191 // insert all siblings in new_first..new_last before orig_first
1192 bool first=true;
1194 while(1==1) {
1196 if(first) {
1197 ret=tt;
1198 first=false;
1199 }
1200 if(new_first==new_last)
1201 break;
1202 new_first=new_first->next_sibling;
1203 }
1204
1205 // erase old range of siblings
1206 bool last=false;
1207 tree_node *next=orig_first;
1208 while(1==1) {
1209 if(next==orig_last)
1210 last=true;
1211 next=next->next_sibling;
1212 erase((pre_order_iterator)orig_first);
1213 if(last)
1214 break;
1215 orig_first=next;
1216 }
1217 return ret;
1218 }
1219
1220template <class T, class tree_node_allocator>
1221template <typename iter>
1223 {
1224 if(position.node->first_child==0)
1225 return position;
1226
1227 tree_node *tmp=position.node->first_child;
1228 while(tmp) {
1229 tmp->parent=position.node->parent;
1230 tmp=tmp->next_sibling;
1231 }
1232 if(position.node->next_sibling) {
1233 position.node->last_child->next_sibling=position.node->next_sibling;
1234 position.node->next_sibling->prev_sibling=position.node->last_child;
1235 }
1236 else {
1237 position.node->parent->last_child=position.node->last_child;
1238 }
1239 position.node->next_sibling=position.node->first_child;
1240 position.node->next_sibling->prev_sibling=position.node;
1241 position.node->first_child=0;
1242 position.node->last_child=0;
1243
1244 return position;
1245 }
1246
1247
1248template <class T, class tree_node_allocator>
1249template <typename iter>
1251 {
1252 tree_node *first=begin.node;
1253 tree_node *last=first;
1254
1255 assert(first!=position.node);
1256
1257 if(begin==end) return begin;
1258 // determine last node
1259 while((++begin)!=end) {
1260 last=last->next_sibling;
1261 }
1262 // move subtree
1263 if(first->prev_sibling==0) {
1264 first->parent->first_child=last->next_sibling;
1265 }
1266 else {
1267 first->prev_sibling->next_sibling=last->next_sibling;
1268 }
1269 if(last->next_sibling==0) {
1270 last->parent->last_child=first->prev_sibling;
1271 }
1272 else {
1273 last->next_sibling->prev_sibling=first->prev_sibling;
1274 }
1275 if(position.node->first_child==0) {
1276 position.node->first_child=first;
1277 position.node->last_child=last;
1278 first->prev_sibling=0;
1279 }
1280 else {
1281 position.node->last_child->next_sibling=first;
1282 first->prev_sibling=position.node->last_child;
1283 position.node->last_child=last;
1284 }
1285 last->next_sibling=0;
1286
1287 tree_node *pos=first;
1288 while(1==1) {
1289 pos->parent=position.node;
1290 if(pos==last) break;
1291 pos=pos->next_sibling;
1292 }
1293
1294 return first;
1295 }
1296
1297template <class T, class tree_node_allocator>
1298template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
1299 {
1300 if(from.node->first_child==0) return position;
1301 return reparent(position, from.node->first_child, end(from));
1302 }
1303
1304template <class T, class tree_node_allocator>
1305template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter position, const T& x)
1306 {
1307 assert(position.node!=0);
1308 sibling_iterator fr=position, to=position;
1309 ++to;
1310 iter ret = insert(position, x);
1311 reparent(ret, fr, to);
1312 return ret;
1313 }
1314
1315template <class T, class tree_node_allocator>
1316template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
1317 {
1318 tree_node *dst=target.node;
1319 tree_node *src=source.node;
1320 assert(dst);
1321 assert(src);
1322
1323 if(dst==src) return source;
1324 if(dst->next_sibling)
1325 if(dst->next_sibling==src) // already in the right spot
1326 return source;
1327
1328 // take src out of the tree
1329 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1330 else src->parent->first_child=src->next_sibling;
1331 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1332 else src->parent->last_child=src->prev_sibling;
1333
1334 // connect it to the new point
1335 if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
1336 else dst->parent->last_child=src;
1337 src->next_sibling=dst->next_sibling;
1338 dst->next_sibling=src;
1339 src->prev_sibling=dst;
1340 src->parent=dst->parent;
1341 return src;
1342 }
1343
1344template <class T, class tree_node_allocator>
1345template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
1346 {
1347 tree_node *dst=target.node;
1348 tree_node *src=source.node;
1349 assert(dst);
1350 assert(src);
1351
1352 if(dst==src) return source;
1353 if(dst->prev_sibling)
1354 if(dst->prev_sibling==src) // already in the right spot
1355 return source;
1356
1357 // take src out of the tree
1358 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1359 else src->parent->first_child=src->next_sibling;
1360 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1361 else src->parent->last_child=src->prev_sibling;
1362
1363 // connect it to the new point
1364 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
1365 else dst->parent->first_child=src;
1366 src->prev_sibling=dst->prev_sibling;
1367 dst->prev_sibling=src;
1368 src->next_sibling=dst;
1369 src->parent=dst->parent;
1370 return src;
1371 }
1372
1373// specialisation for sibling_iterators
1374template <class T, class tree_node_allocator>
1376 sibling_iterator source)
1377 {
1378 tree_node *dst=target.node;
1379 tree_node *src=source.node;
1380 tree_node *dst_prev_sibling;
1381 if(dst==0) { // must then be an end iterator
1382 dst_prev_sibling=target.parent_->last_child;
1383 assert(dst_prev_sibling);
1384 }
1385 else dst_prev_sibling=dst->prev_sibling;
1386 assert(src);
1387
1388 if(dst==src) return source;
1389 if(dst_prev_sibling)
1390 if(dst_prev_sibling==src) // already in the right spot
1391 return source;
1392
1393 // take src out of the tree
1394 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1395 else src->parent->first_child=src->next_sibling;
1396 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1397 else src->parent->last_child=src->prev_sibling;
1398
1399 // connect it to the new point
1400 if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
1401 else target.parent_->first_child=src;
1402 src->prev_sibling=dst_prev_sibling;
1403 if(dst) {
1404 dst->prev_sibling=src;
1405 src->parent=dst->parent;
1406 }
1407 src->next_sibling=dst;
1408 return src;
1409 }
1410
1411template <class T, class tree_node_allocator>
1412template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
1413 {
1414 tree_node *dst=target.node;
1415 tree_node *src=source.node;
1416 assert(dst);
1417 assert(src);
1418
1419 if(dst==src) return source;
1420
1421 // remember connection points
1422 tree_node *b_prev_sibling=dst->prev_sibling;
1423 tree_node *b_next_sibling=dst->next_sibling;
1424 tree_node *b_parent=dst->parent;
1425
1426 // remove target
1427 erase(target);
1428
1429 // take src out of the tree
1430 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1431 else src->parent->first_child=src->next_sibling;
1432 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1433 else src->parent->last_child=src->prev_sibling;
1434
1435 // connect it to the new point
1436 if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
1437 else b_parent->first_child=src;
1438 if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
1439 else b_parent->last_child=src;
1440 src->prev_sibling=b_prev_sibling;
1441 src->next_sibling=b_next_sibling;
1442 src->parent=b_parent;
1443 return src;
1444 }
1445
1446template <class T, class tree_node_allocator>
1449 bool duplicate_leaves)
1450 {
1451 sibling_iterator fnd;
1452 while(from1!=from2) {
1453 if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
1454 if(from1.begin()==from1.end()) { // full depth reached
1455 if(duplicate_leaves)
1456 append_child(parent(to1), (*from1));
1457 }
1458 else { // descend further
1459 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1460 }
1461 }
1462 else { // element missing
1463 insert_subtree(to2, from1);
1464 }
1465 ++from1;
1466 }
1467 }
1468
1469
1470template <class T, class tree_node_allocator>
1472 {
1473 std::less<T> comp;
1474 sort(from, to, comp, deep);
1475 }
1476
1477template <class T, class tree_node_allocator>
1478template <class StrictWeakOrdering>
1480 StrictWeakOrdering comp, bool deep)
1481 {
1482 if(from==to) return;
1483 // make list of sorted nodes
1484 // CHECK: if multiset stores equivalent nodes in the order in which they
1485 // are inserted, then this routine should be called 'stable_sort'.
1486 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1487 sibling_iterator it=from, it2=to;
1488 while(it != to) {
1489 nodes.insert(it.node);
1490 ++it;
1491 }
1492 // reassemble
1493 --it2;
1494
1495 // prev and next are the nodes before and after the sorted range
1496 tree_node *prev=from.node->prev_sibling;
1497 tree_node *next=it2.node->next_sibling;
1498 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
1499 if(prev==0) {
1500 if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1501 (*nit)->parent->first_child=(*nit);
1502 }
1503 else prev->next_sibling=(*nit);
1504
1505 --eit;
1506 while(nit!=eit) {
1507 (*nit)->prev_sibling=prev;
1508 if(prev)
1509 prev->next_sibling=(*nit);
1510 prev=(*nit);
1511 ++nit;
1512 }
1513 // prev now points to the last-but-one node in the sorted range
1514 if(prev)
1515 prev->next_sibling=(*eit);
1516
1517 // eit points to the last node in the sorted range.
1518 (*eit)->next_sibling=next;
1519 (*eit)->prev_sibling=prev; // missed in the loop above
1520 if(next==0) {
1521 if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1522 (*eit)->parent->last_child=(*eit);
1523 }
1524 else next->prev_sibling=(*eit);
1525
1526 if(deep) { // sort the children of each node too
1527 sibling_iterator bcs(*nodes.begin());
1528 sibling_iterator ecs(*eit);
1529 ++ecs;
1530 while(bcs!=ecs) {
1531 sort(begin(bcs), end(bcs), comp, deep);
1532 ++bcs;
1533 }
1534 }
1535 }
1536
1537template <class T, class tree_node_allocator>
1538template <typename iter>
1539bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
1540 {
1541 std::equal_to<T> comp;
1542 return equal(one_, two, three_, comp);
1543 }
1544
1545template <class T, class tree_node_allocator>
1546template <typename iter>
1547bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
1548 {
1549 std::equal_to<T> comp;
1550 return equal_subtree(one_, two_, comp);
1551 }
1552
1553template <class T, class tree_node_allocator>
1554template <typename iter, class BinaryPredicate>
1555bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
1556 {
1557 pre_order_iterator one(one_), three(three_);
1558
1559// if(one==two && is_valid(three) && three.number_of_children()!=0)
1560// return false;
1561 while(one!=two && is_valid(three)) {
1562 if(!fun(*one,*three))
1563 return false;
1564 if(one.number_of_children()!=three.number_of_children())
1565 return false;
1566 ++one;
1567 ++three;
1568 }
1569 return true;
1570 }
1571
1572template <class T, class tree_node_allocator>
1573template <typename iter, class BinaryPredicate>
1574bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
1575 {
1576 pre_order_iterator one(one_), two(two_);
1577
1578 if(!fun(*one,*two)) return false;
1579 if(number_of_children(one)!=number_of_children(two)) return false;
1580 return equal(begin(one),end(one),begin(two),fun);
1581 }
1582
1583template <class T, class tree_node_allocator>
1585 {
1586 tree tmp;
1587 tmp.set_head(value_type());
1588 tmp.replace(tmp.begin(), tmp.end(), from, to);
1589 return tmp;
1590 }
1591
1592template <class T, class tree_node_allocator>
1594 {
1595 tmp.set_head(value_type());
1596 tmp.replace(tmp.begin(), tmp.end(), from, to);
1597 }
1598
1599template <class T, class tree_node_allocator>
1601 {
1602 int i=0;
1603 pre_order_iterator it=begin(), eit=end();
1604 while(it!=eit) {
1605 ++i;
1606 ++it;
1607 }
1608 return i;
1609 }
1610
1611template <class T, class tree_node_allocator>
1613 {
1614 int i=0;
1615 pre_order_iterator it=top, eit=top;
1616 eit.skip_children();
1617 ++eit;
1618 while(it!=eit) {
1619 ++i;
1620 ++it;
1621 }
1622 return i;
1623 }
1624
1625template <class T, class tree_node_allocator>
1627 {
1628 pre_order_iterator it=begin(), eit=end();
1629 return (it==eit);
1630 }
1631
1632template <class T, class tree_node_allocator>
1634 {
1635 tree_node* pos=it.node;
1636 assert(pos!=0);
1637 int ret=0;
1638 while(pos->parent!=0) {
1639 pos=pos->parent;
1640 ++ret;
1641 }
1642 return ret;
1643 }
1644
1645template <class T, class tree_node_allocator>
1647 {
1648 return max_depth(begin());
1649 }
1650
1651
1652template <class T, class tree_node_allocator>
1654 {
1655 tree_node *tmp=pos.node;
1656 int curdepth=0, maxdepth=0;
1657 while(true) { // try to walk the bottom of the tree
1658 while(tmp->first_child==0) {
1659 if(tmp==pos.node) return maxdepth;
1660 if(tmp->next_sibling==0) {
1661 // try to walk up and then right again
1662 do {
1663 tmp=tmp->parent;
1664 if(tmp==0) return maxdepth;
1665 --curdepth;
1666 } while(tmp->next_sibling==0);
1667 }
1668 if(tmp==pos.node) return maxdepth;
1669 tmp=tmp->next_sibling;
1670 }
1671 tmp=tmp->first_child;
1672 ++curdepth;
1673 maxdepth=std::max(curdepth, maxdepth);
1674 }
1675 }
1676
1677template <class T, class tree_node_allocator>
1679 {
1680 tree_node *pos=it.node->first_child;
1681 if(pos==0) return 0;
1682
1683 unsigned int ret=1;
1684// while(pos!=it.node->last_child) {
1685// ++ret;
1686// pos=pos->next_sibling;
1687// }
1688 while((pos=pos->next_sibling))
1689 ++ret;
1690 return ret;
1691 }
1692
1693template <class T, class tree_node_allocator>
1695 {
1696 tree_node *pos=it.node;
1697 unsigned int ret=0;
1698 // count forward
1699 while(pos->next_sibling &&
1700 pos->next_sibling!=head &&
1701 pos->next_sibling!=feet) {
1702 ++ret;
1703 pos=pos->next_sibling;
1704 }
1705 // count backward
1706 pos=it.node;
1707 while(pos->prev_sibling &&
1708 pos->prev_sibling!=head &&
1709 pos->prev_sibling!=feet) {
1710 ++ret;
1711 pos=pos->prev_sibling;
1712 }
1713
1714 return ret;
1715 }
1716
1717template <class T, class tree_node_allocator>
1719 {
1720 tree_node *nxt=it.node->next_sibling;
1721 if(nxt) {
1722 if(it.node->prev_sibling)
1723 it.node->prev_sibling->next_sibling=nxt;
1724 else
1725 it.node->parent->first_child=nxt;
1727 tree_node *nxtnxt=nxt->next_sibling;
1728 if(nxtnxt)
1729 nxtnxt->prev_sibling=it.node;
1730 else
1731 it.node->parent->last_child=it.node;
1732 nxt->next_sibling=it.node;
1733 it.node->prev_sibling=nxt;
1734 it.node->next_sibling=nxtnxt;
1735 }
1736 }
1737
1738template <class T, class tree_node_allocator>
1740 {
1741 // if one and two are adjacent siblings, use the sibling swap
1742 if(one.node->next_sibling==two.node) swap(one);
1743 else if(two.node->next_sibling==one.node) swap(two);
1744 else {
1745 tree_node *nxt1=one.node->next_sibling;
1746 tree_node *nxt2=two.node->next_sibling;
1747 tree_node *pre1=one.node->prev_sibling;
1748 tree_node *pre2=two.node->prev_sibling;
1749 tree_node *par1=one.node->parent;
1750 tree_node *par2=two.node->parent;
1751
1752 // reconnect
1753 one.node->parent=par2;
1754 one.node->next_sibling=nxt2;
1755 if(nxt2) nxt2->prev_sibling=one.node;
1756 else par2->last_child=one.node;
1757 one.node->prev_sibling=pre2;
1758 if(pre2) pre2->next_sibling=one.node;
1759 else par2->first_child=one.node;
1760
1761 two.node->parent=par1;
1762 two.node->next_sibling=nxt1;
1763 if(nxt1) nxt1->prev_sibling=two.node;
1764 else par1->last_child=two.node;
1765 two.node->prev_sibling=pre1;
1766 if(pre1) pre1->next_sibling=two.node;
1767 else par1->first_child=two.node;
1768 }
1769 }
1770
1771// template <class BinaryPredicate>
1772// tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
1773// sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
1774// BinaryPredicate fun) const
1775// {
1776// assert(1==0); // this routine is not finished yet.
1777// while(from!=to) {
1778// if(fun(*subfrom, *from)) {
1779//
1780// }
1781// }
1782// return to;
1783// }
1784
1785template <class T, class tree_node_allocator>
1787 const iterator_base& end) const
1788 {
1789 // FIXME: this should be optimised.
1791 while(tmp!=end) {
1792 if(tmp==it) return true;
1793 ++tmp;
1794 }
1795 return false;
1796 }
1797
1798template <class T, class tree_node_allocator>
1800 {
1801 if(it.node==0 || it.node==feet || it.node==head) return false;
1802 else return true;
1803 }
1804
1805template <class T, class tree_node_allocator>
1807 {
1808 unsigned int ind=0;
1809 if(it.node->parent==0) {
1810 while(it.node->prev_sibling!=head) {
1811 it.node=it.node->prev_sibling;
1812 ++ind;
1813 }
1814 }
1815 else {
1816 while(it.node->prev_sibling!=0) {
1817 it.node=it.node->prev_sibling;
1818 ++ind;
1819 }
1820 }
1821 return ind;
1822 }
1823
1824
1825template <class T, class tree_node_allocator>
1827 {
1828 tree_node *tmp=it.node->first_child;
1829 while(num--) {
1830 assert(tmp!=0);
1831 tmp=tmp->next_sibling;
1832 }
1833 return tmp;
1834 }
1835
1836
1837
1838
1839// Iterator base
1840
1841template <class T, class tree_node_allocator>
1843 : node(0), skip_current_children_(false)
1844 {
1845 }
1846
1847template <class T, class tree_node_allocator>
1849 : node(tn), skip_current_children_(false)
1850 {
1851 }
1852
1853template <class T, class tree_node_allocator>
1855 {
1856 return node->data;
1857 }
1858
1859template <class T, class tree_node_allocator>
1861 {
1862 return &(node->data);
1863 }
1864
1865template <class T, class tree_node_allocator>
1867 {
1868 if(other.node!=this->node) return true;
1869 else return false;
1870 }
1871
1872template <class T, class tree_node_allocator>
1874 {
1875 if(other.node==this->node) return true;
1876 else return false;
1877 }
1878
1879template <class T, class tree_node_allocator>
1881 {
1882 if(other.node!=this->node) return true;
1883 else return false;
1884 }
1885
1886template <class T, class tree_node_allocator>
1888 {
1889 if(other.node==this->node) return true;
1890 else return false;
1891 }
1892
1893template <class T, class tree_node_allocator>
1895 {
1896 if(other.node!=this->node) return true;
1897 else return false;
1898 }
1899
1900template <class T, class tree_node_allocator>
1902 {
1903 if(other.node==this->node) return true;
1904 else return false;
1905 }
1906
1907template <class T, class tree_node_allocator>
1909 {
1910 if(other.node!=this->node) return true;
1911 else return false;
1912 }
1913
1914template <class T, class tree_node_allocator>
1916 {
1917 if(other.node==this->node) return true;
1918 else return false;
1919 }
1920
1921template <class T, class tree_node_allocator>
1923 {
1924 if(node->first_child==0)
1925 return end();
1926
1927 sibling_iterator ret(node->first_child);
1928 ret.parent_=this->node;
1929 return ret;
1930 }
1931
1932template <class T, class tree_node_allocator>
1934 {
1935 sibling_iterator ret(0);
1936 ret.parent_=node;
1937 return ret;
1938 }
1939
1940template <class T, class tree_node_allocator>
1942 {
1943 skip_current_children_=true;
1944 }
1945
1946template <class T, class tree_node_allocator>
1948 {
1949 tree_node *pos=node->first_child;
1950 if(pos==0) return 0;
1951
1952 unsigned int ret=1;
1953 while(pos!=node->last_child) {
1954 ++ret;
1955 pos=pos->next_sibling;
1956 }
1957 return ret;
1958 }
1959
1960
1961
1962// Pre-order iterator
1963
1964template <class T, class tree_node_allocator>
1966 : iterator_base(0)
1967 {
1968 }
1969
1970template <class T, class tree_node_allocator>
1972 : iterator_base(tn)
1973 {
1974 }
1975
1976template <class T, class tree_node_allocator>
1978 : iterator_base(other.node)
1979 {
1980 }
1981
1982template <class T, class tree_node_allocator>
1984 : iterator_base(other.node)
1985 {
1986 if(this->node==0) {
1987 if(other.range_last()!=0)
1988 this->node=other.range_last();
1989 else
1990 this->node=other.parent_;
1991 this->skip_children();
1992 ++(*this);
1993 }
1994 }
1995
1996template <class T, class tree_node_allocator>
1998 {
1999 assert(this->node!=0);
2000 if(!this->skip_current_children_ && this->node->first_child != 0) {
2001 this->node=this->node->first_child;
2002 }
2003 else {
2004 this->skip_current_children_=false;
2005 while(this->node->next_sibling==0) {
2006 this->node=this->node->parent;
2007 if(this->node==0)
2008 return *this;
2009 }
2010 this->node=this->node->next_sibling;
2011 }
2012 return *this;
2013 }
2014
2015template <class T, class tree_node_allocator>
2017 {
2018 assert(this->node!=0);
2019 if(this->node->prev_sibling) {
2020 this->node=this->node->prev_sibling;
2021 while(this->node->last_child)
2022 this->node=this->node->last_child;
2023 }
2024 else {
2025 this->node=this->node->parent;
2026 if(this->node==0)
2027 return *this;
2028 }
2029 return *this;
2030}
2031
2032template <class T, class tree_node_allocator>
2034 {
2035 pre_order_iterator copy = *this;
2036 ++(*this);
2037 return copy;
2038 }
2039
2040template <class T, class tree_node_allocator>
2042{
2043 pre_order_iterator copy = *this;
2044 --(*this);
2045 return copy;
2046}
2047
2048template <class T, class tree_node_allocator>
2050 {
2051 while(num>0) {
2052 ++(*this);
2053 --num;
2054 }
2055 return (*this);
2056 }
2057
2058template <class T, class tree_node_allocator>
2060 {
2061 while(num>0) {
2062 --(*this);
2063 --num;
2064 }
2065 return (*this);
2066 }
2067
2068
2069
2070// Post-order iterator
2071
2072template <class T, class tree_node_allocator>
2074 : iterator_base(0)
2075 {
2076 }
2077
2078template <class T, class tree_node_allocator>
2080 : iterator_base(tn)
2081 {
2082 }
2083
2084template <class T, class tree_node_allocator>
2086 : iterator_base(other.node)
2087 {
2088 }
2089
2090template <class T, class tree_node_allocator>
2092 : iterator_base(other.node)
2093 {
2094 if(this->node==0) {
2095 if(other.range_last()!=0)
2096 this->node=other.range_last();
2097 else
2098 this->node=other.parent_;
2099 this->skip_children();
2100 ++(*this);
2101 }
2102 }
2103
2104template <class T, class tree_node_allocator>
2106 {
2107 assert(this->node!=0);
2108 if(this->node->next_sibling==0) {
2109 this->node=this->node->parent;
2110 this->skip_current_children_=false;
2111 }
2112 else {
2113 this->node=this->node->next_sibling;
2114 if(this->skip_current_children_) {
2115 this->skip_current_children_=false;
2116 }
2117 else {
2118 while(this->node->first_child)
2119 this->node=this->node->first_child;
2120 }
2121 }
2122 return *this;
2123 }
2124
2125template <class T, class tree_node_allocator>
2127 {
2128 assert(this->node!=0);
2129 if(this->skip_current_children_ || this->node->last_child==0) {
2130 this->skip_current_children_=false;
2131 while(this->node->prev_sibling==0)
2132 this->node=this->node->parent;
2133 this->node=this->node->prev_sibling;
2134 }
2135 else {
2136 this->node=this->node->last_child;
2137 }
2138 return *this;
2139 }
2140
2141template <class T, class tree_node_allocator>
2143 {
2144 post_order_iterator copy = *this;
2145 ++(*this);
2146 return copy;
2147 }
2148
2149template <class T, class tree_node_allocator>
2151 {
2152 post_order_iterator copy = *this;
2153 --(*this);
2154 return copy;
2155 }
2156
2157
2158template <class T, class tree_node_allocator>
2160 {
2161 while(num>0) {
2162 ++(*this);
2163 --num;
2164 }
2165 return (*this);
2166 }
2167
2168template <class T, class tree_node_allocator>
2170 {
2171 while(num>0) {
2172 --(*this);
2173 --num;
2174 }
2175 return (*this);
2176 }
2177
2178template <class T, class tree_node_allocator>
2180 {
2181 assert(this->node!=0);
2182 while(this->node->first_child)
2183 this->node=this->node->first_child;
2184 }
2185
2186
2187// Breadth-first iterator
2188
2189template <class T, class tree_node_allocator>
2191 : iterator_base()
2192 {
2193 }
2194
2195template <class T, class tree_node_allocator>
2197 : iterator_base(tn)
2198 {
2199 traversal_queue.push(tn);
2200 }
2201
2202template <class T, class tree_node_allocator>
2204 : iterator_base(other.node)
2205 {
2206 traversal_queue.push(other.node);
2207 }
2208
2209template <class T, class tree_node_allocator>
2211 {
2212 if(other.node!=this->node) return true;
2213 else return false;
2214 }
2215
2216template <class T, class tree_node_allocator>
2218 {
2219 if(other.node==this->node) return true;
2220 else return false;
2221 }
2222
2223template <class T, class tree_node_allocator>
2225 {
2226 assert(this->node!=0);
2227
2228 // Add child nodes and pop current node
2229 sibling_iterator sib=this->begin();
2230 while(sib!=this->end()) {
2231 traversal_queue.push(sib.node);
2232 ++sib;
2233 }
2234 traversal_queue.pop();
2235 if(traversal_queue.size()>0)
2236 this->node=traversal_queue.front();
2237 else
2238 this->node=0;
2239 return (*this);
2240 }
2241
2242template <class T, class tree_node_allocator>
2244 {
2245 breadth_first_queued_iterator copy = *this;
2246 ++(*this);
2247 return copy;
2248 }
2249
2250template <class T, class tree_node_allocator>
2252 {
2253 while(num>0) {
2254 ++(*this);
2255 --num;
2256 }
2257 return (*this);
2258 }
2259
2260
2261
2262// Fixed depth iterator
2263
2264template <class T, class tree_node_allocator>
2266 : iterator_base()
2267 {
2269 }
2270
2271template <class T, class tree_node_allocator>
2273 : iterator_base(tn)
2274 {
2276 }
2277
2278template <class T, class tree_node_allocator>
2280 : iterator_base(other.node)
2281 {
2283 }
2284
2285template <class T, class tree_node_allocator>
2287 : iterator_base(other.node), first_parent_(other.parent_)
2288 {
2290 }
2291
2292template <class T, class tree_node_allocator>
2294 : iterator_base(other.node), first_parent_(other.first_parent_)
2295 {
2296 }
2297
2298template <class T, class tree_node_allocator>
2300 {
2301 if(other.node==this->node && other.first_parent_==first_parent_) return true;
2302 else return false;
2303 }
2304
2305template <class T, class tree_node_allocator>
2307 {
2308 if(other.node!=this->node || other.first_parent_!=first_parent_) return true;
2309 else return false;
2310 }
2311
2312template <class T, class tree_node_allocator>
2314 {
2315 return; // FIXME: we do not use first_parent_ yet, and it actually needs some serious reworking if
2316 // it is ever to work at the 'head' level.
2317 first_parent_=0;
2318 if(this->node==0) return;
2319 if(this->node->parent!=0)
2320 first_parent_=this->node->parent;
2321 if(first_parent_)
2322 find_leftmost_parent_();
2323 }
2324
2325template <class T, class tree_node_allocator>
2327 {
2328 return; // FIXME: see 'set_first_parent()'
2329 tree_node *tmppar=first_parent_;
2330 while(tmppar->prev_sibling) {
2331 tmppar=tmppar->prev_sibling;
2332 if(tmppar->first_child)
2333 first_parent_=tmppar;
2334 }
2335 }
2336
2337template <class T, class tree_node_allocator>
2339 {
2340 assert(this->node!=0);
2341
2342 if(this->node->next_sibling) {
2343 this->node=this->node->next_sibling;
2344 }
2345 else {
2346 int relative_depth=0;
2347 upper:
2348 do {
2349 this->node=this->node->parent;
2350 if(this->node==0) return *this;
2351 --relative_depth;
2352 } while(this->node->next_sibling==0);
2353 lower:
2354 this->node=this->node->next_sibling;
2355 while(this->node->first_child==0) {
2356 if(this->node->next_sibling==0)
2357 goto upper;
2358 this->node=this->node->next_sibling;
2359 if(this->node==0) return *this;
2360 }
2361 while(relative_depth<0 && this->node->first_child!=0) {
2362 this->node=this->node->first_child;
2363 ++relative_depth;
2364 }
2365 if(relative_depth<0) {
2366 if(this->node->next_sibling==0) goto upper;
2367 else goto lower;
2368 }
2369 }
2370 return *this;
2371
2372// if(this->node->next_sibling!=0) {
2373// this->node=this->node->next_sibling;
2374// assert(this->node!=0);
2375// if(this->node->parent==0 && this->node->next_sibling==0) // feet element
2376// this->node=0;
2377// }
2378// else {
2379// tree_node *par=this->node->parent;
2380// do {
2381// par=par->next_sibling;
2382// if(par==0) { // FIXME: need to keep track of this!
2383// this->node=0;
2384// return *this;
2385// }
2386// } while(par->first_child==0);
2387// this->node=par->first_child;
2388// }
2389 return *this;
2390 }
2391
2392template <class T, class tree_node_allocator>
2394 {
2395 assert(this->node!=0);
2396 if(this->node->prev_sibling!=0) {
2397 this->node=this->node->prev_sibling;
2398 assert(this->node!=0);
2399 if(this->node->parent==0 && this->node->prev_sibling==0) // head element
2400 this->node=0;
2401 }
2402 else {
2403 tree_node *par=this->node->parent;
2404 do {
2405 par=par->prev_sibling;
2406 if(par==0) { // FIXME: need to keep track of this!
2407 this->node=0;
2408 return *this;
2409 }
2410 } while(par->last_child==0);
2411 this->node=par->last_child;
2412 }
2413 return *this;
2414}
2415
2416template <class T, class tree_node_allocator>
2418 {
2419 fixed_depth_iterator copy = *this;
2420 ++(*this);
2421 return copy;
2422 }
2423
2424template <class T, class tree_node_allocator>
2426{
2427 fixed_depth_iterator copy = *this;
2428 --(*this);
2429 return copy;
2430}
2431
2432template <class T, class tree_node_allocator>
2434 {
2435 while(num>0) {
2436 --(*this);
2437 --(num);
2438 }
2439 return (*this);
2440 }
2441
2442template <class T, class tree_node_allocator>
2444 {
2445 while(num>0) {
2446 ++(*this);
2447 --(num);
2448 }
2449 return *this;
2450 }
2451
2452// FIXME: add the other members of fixed_depth_iterator.
2453
2454
2455// Sibling iterator
2456
2457template <class T, class tree_node_allocator>
2459 : iterator_base()
2460 {
2461 set_parent_();
2462 }
2463
2464template <class T, class tree_node_allocator>
2466 : iterator_base(tn)
2467 {
2468 set_parent_();
2469 }
2470
2471template <class T, class tree_node_allocator>
2473 : iterator_base(other.node)
2474 {
2475 set_parent_();
2476 }
2477
2478template <class T, class tree_node_allocator>
2480 : iterator_base(other), parent_(other.parent_)
2481 {
2482 }
2483
2484template <class T, class tree_node_allocator>
2486 {
2487 parent_=0;
2488 if(this->node==0) return;
2489 if(this->node->parent!=0)
2490 parent_=this->node->parent;
2491 }
2492
2493template <class T, class tree_node_allocator>
2495 {
2496 if(this->node)
2497 this->node=this->node->next_sibling;
2498 return *this;
2499 }
2500
2501template <class T, class tree_node_allocator>
2503 {
2504 if(this->node) this->node=this->node->prev_sibling;
2505 else {
2506 assert(parent_);
2507 this->node=parent_->last_child;
2508 }
2509 return *this;
2510}
2511
2512template <class T, class tree_node_allocator>
2514 {
2515 sibling_iterator copy = *this;
2516 ++(*this);
2517 return copy;
2518 }
2519
2520template <class T, class tree_node_allocator>
2522 {
2523 sibling_iterator copy = *this;
2524 --(*this);
2525 return copy;
2526 }
2527
2528template <class T, class tree_node_allocator>
2530 {
2531 while(num>0) {
2532 ++(*this);
2533 --num;
2534 }
2535 return (*this);
2536 }
2537
2538template <class T, class tree_node_allocator>
2540 {
2541 while(num>0) {
2542 --(*this);
2543 --num;
2544 }
2545 return (*this);
2546 }
2547
2548template <class T, class tree_node_allocator>
2550 {
2551 tree_node *tmp=parent_->first_child;
2552 return tmp;
2553 }
2554
2555template <class T, class tree_node_allocator>
2557 {
2558 return parent_->last_child;
2559 }
2560
2561// Leaf iterator
2562
2563template <class T, class tree_node_allocator>
2565 : iterator_base(0)
2566 {
2567 }
2568
2569template <class T, class tree_node_allocator>
2571 : iterator_base(tn)
2572 {
2573 }
2574
2575template <class T, class tree_node_allocator>
2577 : iterator_base(other.node)
2578 {
2579 }
2580
2581template <class T, class tree_node_allocator>
2583 : iterator_base(other.node)
2584 {
2585 if(this->node==0) {
2586 if(other.range_last()!=0)
2587 this->node=other.range_last();
2588 else
2589 this->node=other.parent_;
2590 ++(*this);
2591 }
2592 }
2593
2594template <class T, class tree_node_allocator>
2596 {
2597 assert(this->node!=0);
2598 while(this->node->next_sibling==0) {
2599 if (this->node->parent==0) return *this;
2600 this->node=this->node->parent;
2601 }
2602 this->node=this->node->next_sibling;
2603 while(this->node->first_child)
2604 this->node=this->node->first_child;
2605 return *this;
2606 }
2607
2608template <class T, class tree_node_allocator>
2610 {
2611 assert(this->node!=0);
2612 while (this->node->prev_sibling==0) {
2613 if (this->node->parent==0) return *this;
2614 this->node=this->node->parent;
2615 }
2616 this->node=this->node->prev_sibling;
2617 while(this->node->last_child)
2618 this->node=this->node->last_child;
2619 return *this;
2620 }
2621
2622template <class T, class tree_node_allocator>
2624 {
2625 leaf_iterator copy = *this;
2626 ++(*this);
2627 return copy;
2628 }
2629
2630template <class T, class tree_node_allocator>
2632 {
2633 leaf_iterator copy = *this;
2634 --(*this);
2635 return copy;
2636 }
2637
2638
2639template <class T, class tree_node_allocator>
2641 {
2642 while(num>0) {
2643 ++(*this);
2644 --num;
2645 }
2646 return (*this);
2647 }
2648
2649template <class T, class tree_node_allocator>
2651 {
2652 while(num>0) {
2653 --(*this);
2654 --num;
2655 }
2656 return (*this);
2657 }
2658
2659#endif
2660
2661// Local variables:
2662// default-tab-width: 3
2663// End:
Breadth-first iterator, using a queue.
Definition: tree.hh:200
bool operator!=(const breadth_first_queued_iterator &) const
Definition: tree.hh:2210
breadth_first_queued_iterator()
Definition: tree.hh:2190
std::queue< tree_node * > traversal_queue
Definition: tree.hh:213
bool operator==(const breadth_first_queued_iterator &) const
Definition: tree.hh:2217
breadth_first_queued_iterator & operator++()
Definition: tree.hh:2224
breadth_first_queued_iterator & operator+=(unsigned int)
Definition: tree.hh:2251
Comparator class for two nodes of a tree (used for sorting and searching).
Definition: tree.hh:447
StrictWeakOrdering comp_
Definition: tree.hh:457
bool operator()(const tree_node *a, const tree_node *b)
Definition: tree.hh:451
compare_nodes(StrictWeakOrdering comp)
Definition: tree.hh:449
Iterator which traverses only the nodes at a given depth from the root.
Definition: tree.hh:221
fixed_depth_iterator()
Definition: tree.hh:2265
fixed_depth_iterator & operator--()
Definition: tree.hh:2393
bool operator!=(const fixed_depth_iterator &) const
Definition: tree.hh:2306
tree_node * first_parent_
Definition: tree.hh:238
fixed_depth_iterator & operator+=(unsigned int)
Definition: tree.hh:2443
fixed_depth_iterator & operator++()
Definition: tree.hh:2338
void find_leftmost_parent_()
Definition: tree.hh:2326
bool operator==(const fixed_depth_iterator &) const
Definition: tree.hh:2299
void set_first_parent_()
Definition: tree.hh:2313
fixed_depth_iterator & operator-=(unsigned int)
Definition: tree.hh:2433
Comparator class for iterators (compares pointer values; why doesn't this work automatically?...
Definition: tree.hh:431
bool operator()(const typename tree< T, tree_node_allocator >::iterator_base &one, const typename tree< T, tree_node_allocator >::iterator_base &two) const
Definition: tree.hh:433
Base class for iterators, only pointers stored, no traversal logic.
Definition: tree.hh:131
T & reference
Definition: tree.hh:136
T * pointer
Definition: tree.hh:135
iterator_base()
Definition: tree.hh:1842
sibling_iterator end() const
Definition: tree.hh:1933
std::bidirectional_iterator_tag iterator_category
Definition: tree.hh:139
bool skip_current_children_
Definition: tree.hh:157
tree_node * node
Definition: tree.hh:155
T * operator->() const
Definition: tree.hh:1860
void skip_children()
When called, the next increment/decrement skips children of this node.
Definition: tree.hh:1941
size_t size_type
Definition: tree.hh:137
T value_type
Definition: tree.hh:134
T & operator*() const
Definition: tree.hh:1854
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
Definition: tree.hh:1947
sibling_iterator begin() const
Definition: tree.hh:1922
ptrdiff_t difference_type
Definition: tree.hh:138
Iterator which traverses only the leaves.
Definition: tree.hh:269
bool operator!=(const leaf_iterator &) const
Definition: tree.hh:1908
leaf_iterator & operator--()
Definition: tree.hh:2609
leaf_iterator()
Definition: tree.hh:2564
bool operator==(const leaf_iterator &) const
Definition: tree.hh:1915
leaf_iterator & operator++()
Definition: tree.hh:2595
leaf_iterator & operator-=(unsigned int)
Definition: tree.hh:2650
leaf_iterator & operator+=(unsigned int)
Definition: tree.hh:2640
Depth-first iterator, first accessing the children, then the node itself.
Definition: tree.hh:179
post_order_iterator & operator+=(unsigned int)
Definition: tree.hh:2159
post_order_iterator & operator-=(unsigned int)
Definition: tree.hh:2169
post_order_iterator & operator++()
Definition: tree.hh:2105
bool operator!=(const post_order_iterator &) const
Definition: tree.hh:1866
bool operator==(const post_order_iterator &) const
Definition: tree.hh:1873
void descend_all()
Set iterator to the first child as deep as possible down the tree.
Definition: tree.hh:2179
post_order_iterator()
Definition: tree.hh:2073
post_order_iterator & operator--()
Definition: tree.hh:2126
Depth-first iterator, first accessing the node, then its children.
Definition: tree.hh:161
pre_order_iterator & operator++()
Definition: tree.hh:1997
pre_order_iterator & operator--()
Definition: tree.hh:2016
pre_order_iterator & operator+=(unsigned int)
Definition: tree.hh:2049
bool operator==(const pre_order_iterator &) const
Definition: tree.hh:1887
pre_order_iterator & operator-=(unsigned int)
Definition: tree.hh:2059
bool operator!=(const pre_order_iterator &) const
Definition: tree.hh:1880
pre_order_iterator()
Definition: tree.hh:1965
Iterator which traverses only the nodes which are siblings of each other.
Definition: tree.hh:245
void set_parent_()
Definition: tree.hh:2485
tree_node * parent_
Definition: tree.hh:263
tree_node * range_first() const
Definition: tree.hh:2549
sibling_iterator & operator--()
Definition: tree.hh:2502
tree_node * range_last() const
Definition: tree.hh:2556
sibling_iterator & operator++()
Definition: tree.hh:2494
bool operator!=(const sibling_iterator &) const
Definition: tree.hh:1894
bool operator==(const sibling_iterator &) const
Definition: tree.hh:1901
sibling_iterator & operator+=(unsigned int)
Definition: tree.hh:2529
sibling_iterator()
Definition: tree.hh:2458
sibling_iterator & operator-=(unsigned int)
Definition: tree.hh:2539
A node in the tree, combining links to other nodes as well as the actual data.
Definition: tree.hh:98
tree_node_< T > * next_sibling
Definition: tree.hh:102
T data
Definition: tree.hh:103
tree_node_< T > * parent
Definition: tree.hh:100
tree_node_< T > * last_child
Definition: tree.hh:101
tree_node_< T > * first_child
Definition: tree.hh:101
tree_node_< T > * prev_sibling
Definition: tree.hh:102
Definition: tree.hh:107
post_order_iterator begin_post() const
Return post-order iterator to the beginning of the tree.
Definition: tree.hh:667
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
Definition: tree.hh:594
bool equal_subtree(const iter &one, const iter &two) const
Definition: tree.hh:1547
bool equal(const iter &one, const iter &two, const iter &three) const
Compare two ranges of nodes (compares nodes as well as tree structure).
Definition: tree.hh:1539
tree_node * head
Definition: tree.hh:439
sibling_iterator child(const iterator_base &position, unsigned int) const
Inverse of 'index': return the n-th child of the node at position.
Definition: tree.hh:1826
void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, bool duplicate_leaves=false)
Merge with other tree, creating new branches and leaves only if they are not already present.
Definition: tree.hh:1447
T value_type
Value of the data stored at a node.
Definition: tree.hh:112
pre_order_iterator iterator
The default iterator types throughout the tree class.
Definition: tree.hh:217
static unsigned int number_of_children(const iterator_base &)
Count the number of children of node at position.
Definition: tree.hh:1678
iter insert_after(iter position, const T &x)
Insert node as next sibling of node pointed to by position.
Definition: tree.hh:1049
void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)
Definition: tree.hh:1479
sibling_iterator move_before(sibling_iterator target, sibling_iterator source)
Definition: tree.hh:1375
iter move_ontop(iter target, iter source)
Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
Definition: tree.hh:1412
void copy_(const tree< T, tree_node_allocator > &other)
Definition: tree.hh:565
leaf_iterator end_leaf() const
Return leaf iterator to the last leaf of the tree.
Definition: tree.hh:755
sibling_iterator insert(sibling_iterator position, const T &x)
Specialisation of previous member.
Definition: tree.hh:1019
static iter parent(iter)
Return iterator to the parent of a node.
Definition: tree.hh:762
void sort(sibling_iterator from, sibling_iterator to, bool deep=false)
Sort (std::sort only moves values of nodes, this one moves children as well).
Definition: tree.hh:1471
iter previous_sibling(iter) const
Return iterator to the previous sibling of a node.
Definition: tree.hh:770
void head_initialise_()
Definition: tree.hh:533
tree(const T &)
Definition: tree.hh:510
breadth_first_queued_iterator breadth_first_iterator
Definition: tree.hh:218
tree_node_< T > tree_node
Definition: tree.hh:109
iter insert_subtree(iter position, const iterator_base &subtree)
Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.
Definition: tree.hh:1073
iter insert_subtree_after(iter position, const iterator_base &subtree)
Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.
Definition: tree.hh:1083
tree_node_allocator alloc_
Definition: tree.hh:441
iter reparent(iter position, iter from)
Move all child nodes of 'from' to be children of 'position'.
Definition: tree.hh:1298
int depth(const iterator_base &) const
Compute the depth to the root.
Definition: tree.hh:1633
sibling_iterator end(const iterator_base &) const
Return sibling iterator to the end of the children of a given node.
Definition: tree.hh:736
breadth_first_queued_iterator end_breadth_first() const
Return breadth-first iterator to end of the nodes at given depth.
Definition: tree.hh:661
bool is_valid(const iterator_base &) const
Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.
Definition: tree.hh:1799
iter append_child(iter position, iter other_position)
Append the node (plus its children) at other_position as last/first child of position.
Definition: tree.hh:932
post_order_iterator end_post() const
Return post-order iterator to the end of the tree.
Definition: tree.hh:678
void operator=(const tree< T, tree_node_allocator > &)
Definition: tree.hh:552
iter append_child(iter position)
Insert empty node as last/first child of node pointed to by position.
Definition: tree.hh:828
iter next_sibling(iter) const
Return iterator to the next sibling of a node.
Definition: tree.hh:780
iter prepend_child(iter position, const T &x)
Definition: tree.hh:907
tree()
Definition: tree.hh:504
iter prepend_child(iter position)
Definition: tree.hh:853
unsigned int index(sibling_iterator it) const
Determine the index of a node in the range of siblings to which it belongs.
Definition: tree.hh:1806
iter wrap(iter position, const T &x)
Replace node with a new node, making the old node a child of the new node.
Definition: tree.hh:1305
void subtree(tree &, sibling_iterator from, sibling_iterator to) const
Definition: tree.hh:1593
bool is_in_subtree(const iterator_base &position, const iterator_base &begin, const iterator_base &end) const
Determine whether node at position is in the subtrees with root in the range.
Definition: tree.hh:1786
void clear()
Erase all nodes of the tree.
Definition: tree.hh:586
sibling_iterator begin(const iterator_base &) const
Return sibling iterator to the first child of given node.
Definition: tree.hh:726
leaf_iterator begin_leaf() const
Return leaf iterator to the first leaf of the tree.
Definition: tree.hh:744
iter prepend_children(iter position, sibling_iterator from, sibling_iterator to)
Definition: tree.hh:970
iter replace(iter position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
Definition: tree.hh:1103
iter move_after(iter target, iter source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
Definition: tree.hh:1316
bool equal(const iter &one, const iter &two, const iter &three, BinaryPredicate) const
Definition: tree.hh:1555
iter append_children(iter position, sibling_iterator from, sibling_iterator to)
Append the nodes in the from-to range (plus their children) as last/first children of position.
Definition: tree.hh:954
tree(const iterator_base &)
Definition: tree.hh:517
pre_order_iterator begin() const
Return iterator to the beginning of the tree.
Definition: tree.hh:643
int size(const iterator_base &) const
Count the total number of nodes below the indicated node (plus one).
Definition: tree.hh:1612
iter insert(iter position, const T &x)
Insert node as previous sibling of node pointed to by position.
Definition: tree.hh:993
fixed_depth_iterator begin_fixed(const iterator_base &, unsigned int) const
Return fixed-depth iterator to the first node at a given depth from the given iterator.
Definition: tree.hh:684
int max_depth() const
Determine the maximal depth of the tree.
Definition: tree.hh:1646
breadth_first_queued_iterator begin_breadth_first() const
Return breadth-first iterator to the first node at a given depth.
Definition: tree.hh:655
fixed_depth_iterator end_fixed(const iterator_base &, unsigned int) const
Return fixed-depth iterator to end of the nodes at given depth from the given iterator.
Definition: tree.hh:708
bool equal_subtree(const iter &one, const iter &two, BinaryPredicate) const
Definition: tree.hh:1574
iter prepend_child(iter position, iter other_position)
Definition: tree.hh:943
void swap(iterator, iterator)
Exchange two nodes (plus subtrees)
Definition: tree.hh:1739
iter append_child(iter position, const T &x)
Insert node as last/first child of node pointed to by position.
Definition: tree.hh:878
iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
Move nodes in range to be children of 'position'.
Definition: tree.hh:1250
tree_node * feet
Definition: tree.hh:439
bool empty() const
Check if tree is empty.
Definition: tree.hh:1626
void swap(sibling_iterator it)
Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
Definition: tree.hh:1718
tree(const tree< T, tree_node_allocator > &)
Definition: tree.hh:558
int max_depth(const iterator_base &) const
Determine the maximal depth of the tree below a given one.
Definition: tree.hh:1653
int size() const
Count the total number of nodes.
Definition: tree.hh:1600
~tree()
Definition: tree.hh:525
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty tree.
Definition: tree.hh:985
iter flatten(iter position)
Move all children of node at 'position' to be siblings, returns position.
Definition: tree.hh:1222
iter replace(iter position, const iterator_base &from)
Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see abov...
Definition: tree.hh:1112
unsigned int number_of_siblings(const iterator_base &) const
Count the number of 'next' siblings of node at iterator.
Definition: tree.hh:1694
iter erase(iter)
Erase element at position pointed to by iterator, return incremented iterator.
Definition: tree.hh:616
tree subtree(sibling_iterator from, sibling_iterator to) const
Extract a new tree formed by the range of siblings plus all their children.
Definition: tree.hh:1584
iter next_at_same_depth(iter) const
Return iterator to the next node at a given depth.
Definition: tree.hh:790
pre_order_iterator end() const
Return iterator to the end of the tree.
Definition: tree.hh:649
sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end, sibling_iterator new_begin, sibling_iterator new_end)
Replace string of siblings (plus their children) with copy of a new string (with children); see above...
Definition: tree.hh:1176
iter move_before(iter target, iter source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
Definition: tree.hh:1345
Definition: tree.hh:74
void destructor(T1 *p)
Definition: tree.hh:89
void constructor(T1 *p, T2 &val)
Definition: tree.hh:77