LibOFX
tree.hh
1/*
2
3 $Id: tree.hh,v 1.6 2006-07-20 04:41:16 benoitg Exp $
4
5 STL-like templated tree class.
6 Copyright (C) 2001-2005 Kasper Peeters <kasper.peeters@aei.mpg.de>.
7
8*/
9
26/*
27 This program 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.
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
58#ifndef tree_hh_
59#define tree_hh_
60
61#include <cassert>
62#include <cstddef> // for ptrdiff_t
63#include <memory>
64#include <stdexcept>
65#include <iterator>
66#include <set>
67
68// HP-style construct/destroy have gone from the standard,
69// so here is a copy.
70
71namespace kp
72{
73
74template <class T1, class T2>
75void constructor(T1* p, T2& val)
76{
77 new ((void *) p) T1(val);
78}
79
80template <class T1>
81void constructor(T1* p)
82{
83 new ((void *) p) T1;
84}
85
86template <class T1>
87void destructor(T1* p)
88{
89 p->~T1();
90}
91
92}
93
95template<class T>
96class tree_node_ // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
97{
98public:
99 tree_node_<T> *parent;
100 tree_node_<T> *first_child, *last_child;
101 tree_node_<T> *prev_sibling, *next_sibling;
102 T data;
103}; // __attribute__((packed));
104
105template < class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
106class tree
107{
108protected:
109 typedef tree_node_<T> tree_node;
110public:
112 typedef T value_type;
113
114 class iterator_base;
115 class pre_order_iterator;
117 class sibling_iterator;
118
119 tree();
120 tree(const T&);
121 tree(const iterator_base&);
123 ~tree();
124 void operator=(const tree<T, tree_node_allocator>&);
125
127#ifdef __SGI_STL_PORT
128 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t>
129 {
130#else
132 {
133#endif
134 public:
135 typedef T value_type;
136 typedef T* pointer;
137 typedef T& reference;
138 typedef size_t size_type;
139 typedef ptrdiff_t difference_type;
140 typedef std::bidirectional_iterator_tag iterator_category;
141
144
145 T& operator*() const;
146 T* operator->() const;
147
151 unsigned int number_of_children() const;
152
153 sibling_iterator begin() const;
154 sibling_iterator end() const;
155
156 tree_node *node;
157 protected:
158 bool skip_current_children_;
159 };
160
163 {
164 public:
169
170 bool operator==(const pre_order_iterator&) const;
171 bool operator!=(const pre_order_iterator&) const;
172 pre_order_iterator& operator++();
173 pre_order_iterator& operator--();
174 pre_order_iterator operator++(int);
175 pre_order_iterator operator--(int);
176 pre_order_iterator& operator+=(unsigned int);
177 pre_order_iterator& operator-=(unsigned int);
178 };
179
182 {
183 public:
188
189 bool operator==(const post_order_iterator&) const;
190 bool operator!=(const post_order_iterator&) const;
191 post_order_iterator& operator++();
192 post_order_iterator& operator--();
193 post_order_iterator operator++(int);
194 post_order_iterator operator--(int);
195 post_order_iterator& operator+=(unsigned int);
196 post_order_iterator& operator-=(unsigned int);
197
199 void descend_all();
200 };
201
204
207 {
208 public:
214
215 bool operator==(const fixed_depth_iterator&) const;
216 bool operator!=(const fixed_depth_iterator&) const;
217 fixed_depth_iterator& operator++();
218 fixed_depth_iterator& operator--();
219 fixed_depth_iterator operator++(int);
220 fixed_depth_iterator operator--(int);
221 fixed_depth_iterator& operator+=(unsigned int);
222 fixed_depth_iterator& operator-=(unsigned int);
223
224 tree_node *first_parent_;
225 private:
226 void set_first_parent_();
227 void find_leftmost_parent_();
228 };
229
232 {
233 public:
238
239 bool operator==(const sibling_iterator&) const;
240 bool operator!=(const sibling_iterator&) const;
241 sibling_iterator& operator++();
242 sibling_iterator& operator--();
243 sibling_iterator operator++(int);
244 sibling_iterator operator--(int);
245 sibling_iterator& operator+=(unsigned int);
246 sibling_iterator& operator-=(unsigned int);
247
248 tree_node *range_first() const;
249 tree_node *range_last() const;
250 tree_node *parent_;
251 private:
252 void set_parent_();
253 };
254
256 inline pre_order_iterator begin() const;
258 inline pre_order_iterator end() const;
260 post_order_iterator begin_post() const;
262 post_order_iterator end_post() const;
264 fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
266 fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
268 sibling_iterator begin(const iterator_base&) const;
270 sibling_iterator end(const iterator_base&) const;
271
273 template<typename iter> iter parent(iter) const;
275 template<typename iter> iter previous_sibling(iter) const;
277 template<typename iter> iter next_sibling(iter) const;
279 template<typename iter> iter next_at_same_depth(iter) const;
280
282 void clear();
284 template<typename iter> iter erase(iter);
286 void erase_children(const iterator_base&);
287
289 template<typename iter> iter append_child(iter position);
291 template<typename iter> iter append_child(iter position, const T& x);
293 template<typename iter> iter append_child(iter position, iter other_position);
295 template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
296
298 pre_order_iterator set_head(const T& x);
300 template<typename iter> iter insert(iter position, const T& x);
302 sibling_iterator insert(sibling_iterator position, const T& x);
304 template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
306 template<typename iter> iter insert_after(iter position, const T& x);
307
309 template<typename iter> iter replace(iter position, const T& x);
311 template<typename iter> iter replace(iter position, const iterator_base& from);
313 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
314 sibling_iterator new_begin, sibling_iterator new_end);
315
317 template<typename iter> iter flatten(iter position);
319 template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
321 template<typename iter> iter reparent(iter position, iter from);
322
324 template<typename iter> iter move_after(iter target, iter source);
326 template<typename iter> iter move_before(iter target, iter source);
328 template<typename iter> iter move_ontop(iter target, iter source);
329
331 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
332 bool duplicate_leaves = false);
334 void sort(sibling_iterator from, sibling_iterator to, bool deep = false);
335 template<class StrictWeakOrdering>
336 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep = false);
338 template<typename iter>
339 bool equal(const iter& one, const iter& two, const iter& three) const;
340 template<typename iter, class BinaryPredicate>
341 bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
342 template<typename iter>
343 bool equal_subtree(const iter& one, const iter& two) const;
344 template<typename iter, class BinaryPredicate>
345 bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
347 tree subtree(sibling_iterator from, sibling_iterator to) const;
348 void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
350 void swap(sibling_iterator it);
351
353 int size() const;
355 bool empty() const;
357 int depth(const iterator_base&) const;
359 unsigned int number_of_children(const iterator_base&) const;
361 unsigned int number_of_siblings(const iterator_base&) const;
363 bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
364 const iterator_base& end) const;
366 bool is_valid(const iterator_base&) const;
367
369 unsigned int index(sibling_iterator it) const;
371 sibling_iterator child(const iterator_base& position, unsigned int) const;
372
375 {
376 public:
377 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
378 const typename tree<T, tree_node_allocator>::iterator_base& two) const
379 {
380 return one.node < two.node;
381 }
382 };
383 tree_node *head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid
384private:
385 tree_node_allocator alloc_;
386 void head_initialise_();
387 void copy_(const tree<T, tree_node_allocator>& other);
388
390 template<class StrictWeakOrdering>
391 class compare_nodes
392 {
393 public:
394 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
395
396 bool operator()(const tree_node *a, const tree_node *b)
397 {
398 static StrictWeakOrdering comp;
399 return comp(a->data, b->data);
400 }
401 private:
402 StrictWeakOrdering comp_;
403 };
404};
405
406//template <class T, class tree_node_allocator>
407//class iterator_base_less {
408// public:
409// bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
410// const typename tree<T, tree_node_allocator>::iterator_base& two) const
411// {
412// txtout << "operatorclass<" << one.node < two.node << std::endl;
413// return one.node < two.node;
414// }
415//};
416
417//template <class T, class tree_node_allocator>
418//bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
419// const typename tree<T, tree_node_allocator>::iterator& two)
420// {
421// txtout << "operator< " << one.node < two.node << std::endl;
422// if(one.node < two.node) return true;
423// return false;
424// }
425
426template <class T, class tree_node_allocator>
427bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
429{
430 if (one.node > two.node) return true;
431 return false;
432}
433
434
435
436// Tree
437
438template <class T, class tree_node_allocator>
440{
441 head_initialise_();
442}
443
444template <class T, class tree_node_allocator>
446{
447 head_initialise_();
448 set_head(x);
449}
450
451template <class T, class tree_node_allocator>
452tree<T, tree_node_allocator>::tree(const iterator_base& other)
453{
454 head_initialise_();
455 set_head((*other));
456 replace(begin(), other);
457}
458
459template <class T, class tree_node_allocator>
461{
462 clear();
463 alloc_.deallocate(head, 1);
464 alloc_.deallocate(feet, 1);
465}
466
467template <class T, class tree_node_allocator>
469{
470 head = alloc_.allocate(1, 0); // MSVC does not have default second argument
471 feet = alloc_.allocate(1, 0);
472
473 head->parent = 0;
474 head->first_child = 0;
475 head->last_child = 0;
476 head->prev_sibling = 0; //head;
477 head->next_sibling = feet; //head;
478
479 feet->parent = 0;
480 feet->first_child = 0;
481 feet->last_child = 0;
482 feet->prev_sibling = head;
483 feet->next_sibling = 0;
484}
485
486template <class T, class tree_node_allocator>
488{
489 copy_(other);
490}
491
492template <class T, class tree_node_allocator>
494{
495 head_initialise_();
496 copy_(other);
497}
498
499template <class T, class tree_node_allocator>
501{
502 clear();
503 pre_order_iterator it = other.begin(), to = begin();
504 while (it != other.end())
505 {
506 to = insert(to, (*it));
507 it.skip_children();
508 ++it;
509 }
510 to = begin();
511 it = other.begin();
512 while (it != other.end())
513 {
514 to = replace(to, it);
515 to.skip_children();
516 it.skip_children();
517 ++to;
518 ++it;
519 }
520}
521
522template <class T, class tree_node_allocator>
524{
525 if (head)
526 while (head->next_sibling != feet)
527 erase(pre_order_iterator(head->next_sibling));
528}
529
530template<class T, class tree_node_allocator>
532{
533 tree_node *cur = it.node->first_child;
534 tree_node *prev = 0;
535
536 while (cur != 0)
537 {
538 prev = cur;
539 cur = cur->next_sibling;
541 kp::destructor(&prev->data);
542 alloc_.deallocate(prev, 1);
543 }
544 it.node->first_child = 0;
545 it.node->last_child = 0;
546}
547
548template<class T, class tree_node_allocator>
549template<class iter>
551{
552 tree_node *cur = it.node;
553 assert(cur != head);
554 iter ret = it;
555 ret.skip_children();
556 ++ret;
557 erase_children(it);
558 if (cur->prev_sibling == 0)
559 {
560 cur->parent->first_child = cur->next_sibling;
561 }
562 else
563 {
564 cur->prev_sibling->next_sibling = cur->next_sibling;
565 }
566 if (cur->next_sibling == 0)
567 {
568 cur->parent->last_child = cur->prev_sibling;
569 }
570 else
571 {
572 cur->next_sibling->prev_sibling = cur->prev_sibling;
573 }
574
575 kp::destructor(&cur->data);
576 alloc_.deallocate(cur, 1);
577 return ret;
578}
579
580template <class T, class tree_node_allocator>
585
586template <class T, class tree_node_allocator>
591
592template <class T, class tree_node_allocator>
594{
595 tree_node *tmp = head->next_sibling;
596 if (tmp != feet)
597 {
598 while (tmp->first_child)
599 tmp = tmp->first_child;
600 }
601 return post_order_iterator(tmp);
602}
603
604template <class T, class tree_node_allocator>
609
610template <class T, class tree_node_allocator>
612{
613 tree_node *tmp = pos.node;
614 unsigned int curdepth = 0;
615 while (curdepth < dp) // go down one level
616 {
617 while (tmp->first_child == 0)
618 {
619 tmp = tmp->next_sibling;
620 if (tmp == 0)
621 throw std::range_error("tree: begin_fixed out of range");
622 }
623 tmp = tmp->first_child;
624 ++curdepth;
625 }
626 return tmp;
627}
628
629template <class T, class tree_node_allocator>
631{
632 assert(1 == 0); // FIXME: not correct yet
633 tree_node *tmp = pos.node;
634 unsigned int curdepth = 1;
635 while (curdepth < dp) // go down one level
636 {
637 while (tmp->first_child == 0)
638 {
639 tmp = tmp->next_sibling;
640 if (tmp == 0)
641 throw std::range_error("tree: end_fixed out of range");
642 }
643 tmp = tmp->first_child;
644 ++curdepth;
645 }
646 return tmp;
647}
648
649template <class T, class tree_node_allocator>
651{
652 if (pos.node->first_child == 0)
653 {
654 return end(pos);
655 }
656 return pos.node->first_child;
657}
658
659template <class T, class tree_node_allocator>
661{
662 sibling_iterator ret(0);
663 ret.parent_ = pos.node;
664 return ret;
665}
666
667template <class T, class tree_node_allocator>
668template <typename iter>
670{
671 assert(position.node != 0);
672 return iter(position.node->parent);
673}
674
675template <class T, class tree_node_allocator>
676template <typename iter>
678{
679 assert(position.node != 0);
680 iter ret(position);
681 ret.node = position.node->prev_sibling;
682 return ret;
683}
684
685template <class T, class tree_node_allocator>
686template <typename iter>
688{
689 assert(position.node != 0);
690 iter ret(position);
691 ret.node = position.node->next_sibling;
692 return ret;
693}
694
695template <class T, class tree_node_allocator>
696template <typename iter>
698{
699 assert(position.node != 0);
700 iter ret(position);
701
702 if (position.node->next_sibling)
703 {
704 ret.node = position.node->next_sibling;
705 }
706 else
707 {
708 int relative_depth = 0;
709upper:
710 do
711 {
712 ret.node = ret.node->parent;
713 if (ret.node == 0) return ret;
714 --relative_depth;
715 }
716 while (ret.node->next_sibling == 0);
717lower:
718 ret.node = ret.node->next_sibling;
719 while (ret.node->first_child == 0)
720 {
721 if (ret.node->next_sibling == 0)
722 goto upper;
723 ret.node = ret.node->next_sibling;
724 if (ret.node == 0) return ret;
725 }
726 while (relative_depth < 0 && ret.node->first_child != 0)
727 {
728 ret.node = ret.node->first_child;
729 ++relative_depth;
730 }
731 if (relative_depth < 0)
732 {
733 if (ret.node->next_sibling == 0) goto upper;
734 else goto lower;
735 }
736 }
737 return ret;
738}
739
740template <class T, class tree_node_allocator>
741template <typename iter>
743{
744 assert(position.node != head);
745
746 tree_node* tmp = alloc_.allocate(1, 0);
747 kp::constructor(&tmp->data);
748 tmp->first_child = 0;
749 tmp->last_child = 0;
750
751 tmp->parent = position.node;
752 if (position.node->last_child != 0)
753 {
754 position.node->last_child->next_sibling = tmp;
755 }
756 else
757 {
758 position.node->first_child = tmp;
759 }
760 tmp->prev_sibling = position.node->last_child;
761 position.node->last_child = tmp;
762 tmp->next_sibling = 0;
763 return tmp;
764}
765
766template <class T, class tree_node_allocator>
767template <class iter>
769{
770 // If your program fails here you probably used 'append_child' to add the top
771 // node to an empty tree. From version 1.45 the top element should be added
772 // using 'insert'. See the documentation for further information, and sorry about
773 // the API change.
774 assert(position.node != head);
775
776 tree_node* tmp = alloc_.allocate(1, 0);
777 kp::constructor(&tmp->data, x);
778 tmp->first_child = 0;
779 tmp->last_child = 0;
780
781 tmp->parent = position.node;
782 if (position.node->last_child != 0)
783 {
784 position.node->last_child->next_sibling = tmp;
785 }
786 else
787 {
788 position.node->first_child = tmp;
789 }
790 tmp->prev_sibling = position.node->last_child;
791 position.node->last_child = tmp;
792 tmp->next_sibling = 0;
793 return tmp;
794}
795
796template <class T, class tree_node_allocator>
797template <class iter>
799{
800 assert(position.node != head);
801
803 return replace(aargh, other);
804}
805
806template <class T, class tree_node_allocator>
807template <class iter>
809{
810 iter ret = from;
811
812 while (from != to)
813 {
814 insert_subtree(position.end(), from);
815 ++from;
816 }
817 return ret;
818}
819
820template <class T, class tree_node_allocator>
822{
823 assert(head->next_sibling == feet);
824 return insert(iterator(feet), x);
825}
826
827template <class T, class tree_node_allocator>
828template <class iter>
830{
831 if (position.node == 0)
832 {
833 position.node = feet; // Backward compatibility: when calling insert on a null node,
834 // insert before the feet.
835 }
836 tree_node* tmp = alloc_.allocate(1, 0);
837 kp::constructor(&tmp->data, x);
838 tmp->first_child = 0;
839 tmp->last_child = 0;
840
841 tmp->parent = position.node->parent;
842 tmp->next_sibling = position.node;
843 tmp->prev_sibling = position.node->prev_sibling;
844 position.node->prev_sibling = tmp;
845
846 if (tmp->prev_sibling == 0)
847 {
848 if (tmp->parent) // when inserting nodes at the head, there is no parent
849 tmp->parent->first_child = tmp;
850 }
851 else
852 tmp->prev_sibling->next_sibling = tmp;
853 return tmp;
854}
855
856template <class T, class tree_node_allocator>
858{
859 tree_node* tmp = alloc_.allocate(1, 0);
860 kp::constructor(&tmp->data, x);
861 tmp->first_child = 0;
862 tmp->last_child = 0;
863
864 tmp->next_sibling = position.node;
865 if (position.node == 0) // iterator points to end of a subtree
866 {
867 tmp->parent = position.parent_;
868 tmp->prev_sibling = position.range_last();
869 tmp->parent->last_child = tmp;
870 }
871 else
872 {
873 tmp->parent = position.node->parent;
874 tmp->prev_sibling = position.node->prev_sibling;
875 position.node->prev_sibling = tmp;
876 }
877
878 if (tmp->prev_sibling == 0)
879 {
880 if (tmp->parent) // when inserting nodes at the head, there is no parent
881 tmp->parent->first_child = tmp;
882 }
883 else
884 tmp->prev_sibling->next_sibling = tmp;
885 return tmp;
886}
887
888template <class T, class tree_node_allocator>
889template <class iter>
891{
892 tree_node* tmp = alloc_.allocate(1, 0);
893 kp::constructor(&tmp->data, x);
894 tmp->first_child = 0;
895 tmp->last_child = 0;
896
897 tmp->parent = position.node->parent;
898 tmp->prev_sibling = position.node;
899 tmp->next_sibling = position.node->next_sibling;
900 position.node->next_sibling = tmp;
901
902 if (tmp->next_sibling == 0)
903 {
904 if (tmp->parent) // when inserting nodes at the head, there is no parent
905 tmp->parent->last_child = tmp;
906 }
907 else
908 {
909 tmp->next_sibling->prev_sibling = tmp;
910 }
911 return tmp;
912}
913
914template <class T, class tree_node_allocator>
915template <class iter>
917{
918 // insert dummy
919 iter it = insert(position, value_type());
920 // replace dummy with subtree
921 return replace(it, subtree);
922}
923
924// template <class T, class tree_node_allocator>
925// template <class iter>
926// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
927// {
928// // insert dummy
929// iter it(insert(position, value_type()));
930// // replace dummy with subtree
931// return replace(it, subtree);
932// }
933
934template <class T, class tree_node_allocator>
935template <class iter>
937{
938 kp::destructor(&position.node->data);
939 kp::constructor(&position.node->data, x);
940 return position;
941}
942
943template <class T, class tree_node_allocator>
944template <class iter>
946{
947 assert(position.node != head);
948 tree_node *current_from = from.node;
949 tree_node *start_from = from.node;
950 tree_node *current_to = position.node;
951
952 // replace the node at position with head of the replacement tree at from
954 tree_node* tmp = alloc_.allocate(1, 0);
955 kp::constructor(&tmp->data, (*from));
956 tmp->first_child = 0;
957 tmp->last_child = 0;
958 if (current_to->prev_sibling == 0)
959 {
960 current_to->parent->first_child = tmp;
961 }
962 else
963 {
964 current_to->prev_sibling->next_sibling = tmp;
965 }
966 tmp->prev_sibling = current_to->prev_sibling;
967 if (current_to->next_sibling == 0)
968 {
969 current_to->parent->last_child = tmp;
970 }
971 else
972 {
973 current_to->next_sibling->prev_sibling = tmp;
974 }
975 tmp->next_sibling = current_to->next_sibling;
976 tmp->parent = current_to->parent;
977 kp::destructor(&current_to->data);
978 alloc_.deallocate(current_to, 1);
979 current_to = tmp;
980
981 // only at this stage can we fix 'last'
982 tree_node *last = from.node->next_sibling;
983
984 pre_order_iterator toit = tmp;
985 // copy all children
986 do
987 {
988 assert(current_from != 0);
989 if (current_from->first_child != 0)
990 {
991 current_from = current_from->first_child;
992 toit = append_child(toit, current_from->data);
993 }
994 else
995 {
996 while (current_from->next_sibling == 0 && current_from != start_from)
997 {
998 current_from = current_from->parent;
999 toit = parent(toit);
1000 assert(current_from != 0);
1001 }
1002 current_from = current_from->next_sibling;
1003 if (current_from != last)
1004 {
1005 toit = append_child(parent(toit), current_from->data);
1006 }
1007 }
1008 }
1009 while (current_from != last);
1010
1011 return current_to;
1012}
1013
1014template <class T, class tree_node_allocator>
1016 sibling_iterator orig_begin,
1017 sibling_iterator orig_end,
1018 sibling_iterator new_begin,
1019 sibling_iterator new_end)
1020{
1021 tree_node *orig_first = orig_begin.node;
1022 tree_node *new_first = new_begin.node;
1023 tree_node *orig_last = orig_first;
1024 while ((++orig_begin) != orig_end)
1025 orig_last = orig_last->next_sibling;
1026 tree_node *new_last = new_first;
1027 while ((++new_begin) != new_end)
1028 new_last = new_last->next_sibling;
1029
1030 // insert all siblings in new_first..new_last before orig_first
1031 bool first = true;
1033 while (1 == 1)
1034 {
1036 if (first)
1037 {
1038 ret = tt;
1039 first = false;
1040 }
1041 if (new_first == new_last)
1042 break;
1043 new_first = new_first->next_sibling;
1044 }
1045
1046 // erase old range of siblings
1047 bool last = false;
1048 tree_node *next = orig_first;
1049 while (1 == 1)
1050 {
1051 if (next == orig_last)
1052 last = true;
1053 next = next->next_sibling;
1054 erase((pre_order_iterator)orig_first);
1055 if (last)
1056 break;
1057 orig_first = next;
1058 }
1059 return ret;
1060}
1061
1062template <class T, class tree_node_allocator>
1063template <typename iter>
1065{
1066 if (position.node->first_child == 0)
1067 return position;
1068
1069 tree_node *tmp = position.node->first_child;
1070 while (tmp)
1071 {
1072 tmp->parent = position.node->parent;
1073 tmp = tmp->next_sibling;
1074 }
1075 if (position.node->next_sibling)
1076 {
1077 position.node->last_child->next_sibling = position.node->next_sibling;
1078 position.node->next_sibling->prev_sibling = position.node->last_child;
1079 }
1080 else
1081 {
1082 position.node->parent->last_child = position.node->last_child;
1083 }
1084 position.node->next_sibling = position.node->first_child;
1085 position.node->next_sibling->prev_sibling = position.node;
1086 position.node->first_child = 0;
1087 position.node->last_child = 0;
1088
1089 return position;
1090}
1091
1092
1093template <class T, class tree_node_allocator>
1094template <typename iter>
1096{
1097 tree_node *first = begin.node;
1098 tree_node *last = first;
1099 if (begin == end) return begin;
1100 // determine last node
1101 while ((++begin) != end)
1102 {
1103 last = last->next_sibling;
1104 }
1105 // move subtree
1106 if (first->prev_sibling == 0)
1107 {
1108 first->parent->first_child = last->next_sibling;
1109 }
1110 else
1111 {
1112 first->prev_sibling->next_sibling = last->next_sibling;
1113 }
1114 if (last->next_sibling == 0)
1115 {
1116 last->parent->last_child = first->prev_sibling;
1117 }
1118 else
1119 {
1120 last->next_sibling->prev_sibling = first->prev_sibling;
1121 }
1122 if (position.node->first_child == 0)
1123 {
1124 position.node->first_child = first;
1125 position.node->last_child = last;
1126 first->prev_sibling = 0;
1127 }
1128 else
1129 {
1130 position.node->last_child->next_sibling = first;
1131 first->prev_sibling = position.node->last_child;
1132 position.node->last_child = last;
1133 }
1134 last->next_sibling = 0;
1135
1136 tree_node *pos = first;
1137 while (1 == 1)
1138 {
1139 pos->parent = position.node;
1140 if (pos == last) break;
1141 pos = pos->next_sibling;
1142 }
1143
1144 return first;
1145}
1146
1147template <class T, class tree_node_allocator>
1148template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
1149{
1150 if (from.node->first_child == 0) return position;
1151 return reparent(position, from.node->first_child, end(from));
1152}
1153
1154template <class T, class tree_node_allocator>
1155template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
1156{
1157 tree_node *dst = target.node;
1158 tree_node *src = source.node;
1159 assert(dst);
1160 assert(src);
1161
1162 if (dst == src) return source;
1163
1164 // take src out of the tree
1165 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1166 else src->parent->first_child = src->next_sibling;
1167 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1168 else src->parent->last_child = src->prev_sibling;
1169
1170 // connect it to the new point
1171 if (dst->next_sibling != 0) dst->next_sibling->prev_sibling = src;
1172 else dst->parent->last_child = src;
1173 src->next_sibling = dst->next_sibling;
1174 dst->next_sibling = src;
1175 src->prev_sibling = dst;
1176 src->parent = dst->parent;
1177 return src;
1178}
1179
1180
1181template <class T, class tree_node_allocator>
1182template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
1183{
1184 tree_node *dst = target.node;
1185 tree_node *src = source.node;
1186 assert(dst);
1187 assert(src);
1188
1189 if (dst == src) return source;
1190
1191 // take src out of the tree
1192 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1193 else src->parent->first_child = src->next_sibling;
1194 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1195 else src->parent->last_child = src->prev_sibling;
1196
1197 // connect it to the new point
1198 if (dst->prev_sibling != 0) dst->prev_sibling->next_sibling = src;
1199 else dst->parent->first_child = src;
1200 src->prev_sibling = dst->prev_sibling;
1201 dst->prev_sibling = src;
1202 src->next_sibling = dst;
1203 src->parent = dst->parent;
1204 return src;
1205}
1206
1207template <class T, class tree_node_allocator>
1208template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
1209{
1210 tree_node *dst = target.node;
1211 tree_node *src = source.node;
1212 assert(dst);
1213 assert(src);
1214
1215 if (dst == src) return source;
1216
1217 // remember connection points
1218 tree_node *b_prev_sibling = dst->prev_sibling;
1219 tree_node *b_next_sibling = dst->next_sibling;
1220 tree_node *b_parent = dst->parent;
1221
1222 // remove target
1223 erase(target);
1224
1225 // take src out of the tree
1226 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1227 else src->parent->first_child = src->next_sibling;
1228 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1229 else src->parent->last_child = src->prev_sibling;
1230
1231 // connect it to the new point
1232 if (b_prev_sibling != 0) b_prev_sibling->next_sibling = src;
1233 else b_parent->first_child = src;
1234 if (b_next_sibling != 0) b_next_sibling->prev_sibling = src;
1235 else b_parent->last_child = src;
1236 src->prev_sibling = b_prev_sibling;
1237 src->next_sibling = b_next_sibling;
1238 src->parent = b_parent;
1239 return src;
1240}
1241
1242template <class T, class tree_node_allocator>
1245 bool duplicate_leaves)
1246{
1247 sibling_iterator fnd;
1248 while (from1 != from2)
1249 {
1250 if ((fnd = std::find(to1, to2, (*from1))) != to2) // element found
1251 {
1252 if (from1.begin() == from1.end()) // full depth reached
1253 {
1254 if (duplicate_leaves)
1255 append_child(parent(to1), (*from1));
1256 }
1257 else // descend further
1258 {
1259 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1260 }
1261 }
1262 else // element missing
1263 {
1264 insert_subtree(to2, from1);
1265 }
1266 ++from1;
1267 }
1268}
1269
1270
1271template <class T, class tree_node_allocator>
1273{
1274 std::less<T> comp;
1275 sort(from, to, comp, deep);
1276}
1277
1278template <class T, class tree_node_allocator>
1279template <class StrictWeakOrdering>
1280void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
1281 StrictWeakOrdering comp, bool deep)
1282{
1283 if (from == to) return;
1284 // make list of sorted nodes
1285 // CHECK: if multiset stores equivalent nodes in the order in which they
1286 // are inserted, then this routine should be called 'stable_sort'.
1287 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1288 sibling_iterator it = from, it2 = to;
1289 while (it != to)
1290 {
1291 nodes.insert(it.node);
1292 ++it;
1293 }
1294 // reassemble
1295 --it2;
1296
1297 // prev and next are the nodes before and after the sorted range
1298 tree_node *prev = from.node->prev_sibling;
1299 tree_node *next = it2.node->next_sibling;
1300 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit = nodes.begin(), eit = nodes.end();
1301 if (prev == 0)
1302 {
1303 if ((*nit)->parent != 0) // to catch "sorting the head" situations, when there is no parent
1304 (*nit)->parent->first_child = (*nit);
1305 }
1306 else prev->next_sibling = (*nit);
1307
1308 --eit;
1309 while (nit != eit)
1310 {
1311 (*nit)->prev_sibling = prev;
1312 if (prev)
1313 prev->next_sibling = (*nit);
1314 prev = (*nit);
1315 ++nit;
1316 }
1317 // prev now points to the last-but-one node in the sorted range
1318 if (prev)
1319 prev->next_sibling = (*eit);
1320
1321 // eit points to the last node in the sorted range.
1322 (*eit)->next_sibling = next;
1323 (*eit)->prev_sibling = prev; // missed in the loop above
1324 if (next == 0)
1325 {
1326 if ((*eit)->parent != 0) // to catch "sorting the head" situations, when there is no parent
1327 (*eit)->parent->last_child = (*eit);
1328 }
1329 else next->prev_sibling = (*eit);
1330
1331 if (deep) // sort the children of each node too
1332 {
1333 sibling_iterator bcs(*nodes.begin());
1334 sibling_iterator ecs(*eit);
1335 ++ecs;
1336 while (bcs != ecs)
1337 {
1338 sort(begin(bcs), end(bcs), comp, deep);
1339 ++bcs;
1340 }
1341 }
1342}
1343
1344template <class T, class tree_node_allocator>
1345template <typename iter>
1346bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
1347{
1348 std::equal_to<T> comp;
1349 return equal(one_, two, three_, comp);
1350}
1351
1352template <class T, class tree_node_allocator>
1353template <typename iter>
1354bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
1355{
1356 std::equal_to<T> comp;
1357 return equal_subtree(one_, two_, comp);
1358}
1359
1360template <class T, class tree_node_allocator>
1361template <typename iter, class BinaryPredicate>
1362bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
1363{
1364 pre_order_iterator one(one_), three(three_);
1365
1366// if(one==two && is_valid(three) && three.number_of_children()!=0)
1367// return false;
1368 while (one != two && is_valid(three))
1369 {
1370 if (!fun(*one, *three))
1371 return false;
1372 if (one.number_of_children() != three.number_of_children())
1373 return false;
1374 ++one;
1375 ++three;
1376 }
1377 return true;
1378}
1379
1380template <class T, class tree_node_allocator>
1381template <typename iter, class BinaryPredicate>
1382bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
1383{
1384 pre_order_iterator one(one_), two(two_);
1385
1386 if (!fun(*one, *two)) return false;
1387 if (number_of_children(one) != number_of_children(two)) return false;
1388 return equal(begin(one), end(one), begin(two), fun);
1389}
1390
1391template <class T, class tree_node_allocator>
1393{
1394 tree tmp;
1395 tmp.set_head(value_type());
1396 tmp.replace(tmp.begin(), tmp.end(), from, to);
1397 return tmp;
1398}
1399
1400template <class T, class tree_node_allocator>
1401void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
1402{
1403 tmp.set_head(value_type());
1404 tmp.replace(tmp.begin(), tmp.end(), from, to);
1405}
1406
1407template <class T, class tree_node_allocator>
1409{
1410 int i = 0;
1411 pre_order_iterator it = begin(), eit = end();
1412 while (it != eit)
1413 {
1414 ++i;
1415 ++it;
1416 }
1417 return i;
1418}
1419
1420template <class T, class tree_node_allocator>
1422{
1423 pre_order_iterator it = begin(), eit = end();
1424 return (it == eit);
1425}
1426
1427template <class T, class tree_node_allocator>
1429{
1430 tree_node* pos = it.node;
1431 assert(pos != 0);
1432 int ret = 0;
1433 while (pos->parent != 0)
1434 {
1435 pos = pos->parent;
1436 ++ret;
1437 }
1438 return ret;
1439}
1440
1441template <class T, class tree_node_allocator>
1443{
1444 tree_node *pos = it.node->first_child;
1445 if (pos == 0) return 0;
1446
1447 unsigned int ret = 1;
1448// while(pos!=it.node->last_child) {
1449// ++ret;
1450// pos=pos->next_sibling;
1451// }
1452 while ((pos = pos->next_sibling))
1453 ++ret;
1454 return ret;
1455}
1456
1457template <class T, class tree_node_allocator>
1459{
1460 tree_node *pos = it.node;
1461 unsigned int ret = 0;
1462 while (pos->next_sibling &&
1463 pos->next_sibling != head &&
1464 pos->next_sibling != feet)
1465 {
1466 ++ret;
1467 pos = pos->next_sibling;
1468 }
1469 return ret;
1470}
1471
1472template <class T, class tree_node_allocator>
1474{
1475 tree_node *nxt = it.node->next_sibling;
1476 if (nxt)
1477 {
1478 if (it.node->prev_sibling)
1479 it.node->prev_sibling->next_sibling = nxt;
1480 else
1481 it.node->parent->first_child = nxt;
1482 nxt->prev_sibling = it.node->prev_sibling;
1483 tree_node *nxtnxt = nxt->next_sibling;
1484 if (nxtnxt)
1485 nxtnxt->prev_sibling = it.node;
1486 else
1487 it.node->parent->last_child = it.node;
1488 nxt->next_sibling = it.node;
1489 it.node->prev_sibling = nxt;
1490 it.node->next_sibling = nxtnxt;
1491 }
1492}
1493
1494// template <class BinaryPredicate>
1495// tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
1496// sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
1497// BinaryPredicate fun) const
1498// {
1499// assert(1==0); // this routine is not finished yet.
1500// while(from!=to) {
1501// if(fun(*subfrom, *from)) {
1502//
1503// }
1504// }
1505// return to;
1506// }
1507
1508template <class T, class tree_node_allocator>
1510 const iterator_base& end) const
1511{
1512 // FIXME: this should be optimised.
1514 while (tmp != end)
1515 {
1516 if (tmp == it) return true;
1517 ++tmp;
1518 }
1519 return false;
1520}
1521
1522template <class T, class tree_node_allocator>
1524{
1525 if (it.node == 0 || it.node == feet) return false;
1526 else return true;
1527}
1528
1529template <class T, class tree_node_allocator>
1531{
1532 unsigned int ind = 0;
1533 if (it.node->parent == 0)
1534 {
1535 while (it.node->prev_sibling != head)
1536 {
1537 it.node = it.node->prev_sibling;
1538 ++ind;
1539 }
1540 }
1541 else
1542 {
1543 while (it.node->prev_sibling != 0)
1544 {
1545 it.node = it.node->prev_sibling;
1546 ++ind;
1547 }
1548 }
1549 return ind;
1550}
1551
1552
1553template <class T, class tree_node_allocator>
1555{
1556 tree_node *tmp = it.node->first_child;
1557 while (num--)
1558 {
1559 assert(tmp != 0);
1560 tmp = tmp->next_sibling;
1561 }
1562 return tmp;
1563}
1564
1565
1566
1567
1568// Iterator base
1569
1570template <class T, class tree_node_allocator>
1572 : node(0), skip_current_children_(false)
1573{
1574}
1575
1576template <class T, class tree_node_allocator>
1578 : node(tn), skip_current_children_(false)
1579{
1580}
1581
1582template <class T, class tree_node_allocator>
1584{
1585 return node->data;
1586}
1587
1588template <class T, class tree_node_allocator>
1590{
1591 return &(node->data);
1592}
1593
1594template <class T, class tree_node_allocator>
1595bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
1596{
1597 if (other.node != this->node) return true;
1598 else return false;
1599}
1600
1601template <class T, class tree_node_allocator>
1602bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
1603{
1604 if (other.node == this->node) return true;
1605 else return false;
1606}
1607
1608template <class T, class tree_node_allocator>
1609bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
1610{
1611 if (other.node != this->node) return true;
1612 else return false;
1613}
1614
1615template <class T, class tree_node_allocator>
1616bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
1617{
1618 if (other.node == this->node) return true;
1619 else return false;
1620}
1621
1622template <class T, class tree_node_allocator>
1623bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
1624{
1625 if (other.node != this->node) return true;
1626 else return false;
1627}
1628
1629template <class T, class tree_node_allocator>
1630bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
1631{
1632 if (other.node == this->node) return true;
1633 else return false;
1634}
1635
1636template <class T, class tree_node_allocator>
1638{
1639 sibling_iterator ret(node->first_child);
1640 ret.parent_ = this->node;
1641 return ret;
1642}
1643
1644template <class T, class tree_node_allocator>
1646{
1647 sibling_iterator ret(0);
1648 ret.parent_ = node;
1649 return ret;
1650}
1651
1652template <class T, class tree_node_allocator>
1654{
1655 skip_current_children_ = true;
1656}
1657
1658template <class T, class tree_node_allocator>
1660{
1661 tree_node *pos = node->first_child;
1662 if (pos == 0) return 0;
1663
1664 unsigned int ret = 1;
1665 while (pos != node->last_child)
1666 {
1667 ++ret;
1668 pos = pos->next_sibling;
1669 }
1670 return ret;
1671}
1672
1673
1674
1675// Pre-order iterator
1676
1677template <class T, class tree_node_allocator>
1679 : iterator_base(0)
1680{
1681}
1682
1683template <class T, class tree_node_allocator>
1685 : iterator_base(tn)
1686{
1687}
1688
1689template <class T, class tree_node_allocator>
1691 : iterator_base(other.node)
1692{
1693}
1694
1695template <class T, class tree_node_allocator>
1697 : iterator_base(other.node)
1698{
1699 if (this->node == 0)
1700 {
1701 if (other.range_last() != 0)
1702 this->node = other.range_last();
1703 else
1704 this->node = other.parent_;
1705 this->skip_children();
1706 ++(*this);
1707 }
1708}
1709
1710template <class T, class tree_node_allocator>
1712{
1713 assert(this->node != 0);
1714 if (!this->skip_current_children_ && this->node->first_child != 0)
1715 {
1716 this->node = this->node->first_child;
1717 }
1718 else
1719 {
1720 this->skip_current_children_ = false;
1721 while (this->node->next_sibling == 0)
1722 {
1723 this->node = this->node->parent;
1724 if (this->node == 0)
1725 return *this;
1726 }
1727 this->node = this->node->next_sibling;
1728 }
1729 return *this;
1730}
1731
1732template <class T, class tree_node_allocator>
1734{
1735 assert(this->node != 0);
1736 if (this->node->prev_sibling)
1737 {
1738 this->node = this->node->prev_sibling;
1739 while (this->node->last_child)
1740 this->node = this->node->last_child;
1741 }
1742 else
1743 {
1744 this->node = this->node->parent;
1745 if (this->node == 0)
1746 return *this;
1747 }
1748 return *this;
1749}
1750
1751template <class T, class tree_node_allocator>
1753{
1754 pre_order_iterator copy = *this;
1755 ++(*this);
1756 return copy;
1757}
1758
1759template <class T, class tree_node_allocator>
1761{
1762 pre_order_iterator copy = *this;
1763 --(*this);
1764 return copy;
1765}
1766
1767template <class T, class tree_node_allocator>
1769{
1770 while (num > 0)
1771 {
1772 ++(*this);
1773 --num;
1774 }
1775 return (*this);
1776}
1777
1778template <class T, class tree_node_allocator>
1780{
1781 while (num > 0)
1782 {
1783 --(*this);
1784 --num;
1785 }
1786 return (*this);
1787}
1788
1789
1790
1791// Post-order iterator
1792
1793template <class T, class tree_node_allocator>
1795 : iterator_base(0)
1796{
1797}
1798
1799template <class T, class tree_node_allocator>
1801 : iterator_base(tn)
1802{
1803}
1804
1805template <class T, class tree_node_allocator>
1807 : iterator_base(other.node)
1808{
1809}
1810
1811template <class T, class tree_node_allocator>
1813 : iterator_base(other.node)
1814{
1815 if (this->node == 0)
1816 {
1817 if (other.range_last() != 0)
1818 this->node = other.range_last();
1819 else
1820 this->node = other.parent_;
1821 this->skip_children();
1822 ++(*this);
1823 }
1824}
1825
1826template <class T, class tree_node_allocator>
1828{
1829 assert(this->node != 0);
1830 if (this->node->next_sibling == 0)
1831 {
1832 this->node = this->node->parent;
1833 this->skip_current_children_ = false;
1834 }
1835 else
1836 {
1837 this->node = this->node->next_sibling;
1838 if (this->skip_current_children_)
1839 {
1840 this->skip_current_children_ = false;
1841 }
1842 else
1843 {
1844 while (this->node->first_child)
1845 this->node = this->node->first_child;
1846 }
1847 }
1848 return *this;
1849}
1850
1851template <class T, class tree_node_allocator>
1853{
1854 assert(this->node != 0);
1855 if (this->skip_current_children_ || this->node->last_child == 0)
1856 {
1857 this->skip_current_children_ = false;
1858 while (this->node->prev_sibling == 0)
1859 this->node = this->node->parent;
1860 this->node = this->node->prev_sibling;
1861 }
1862 else
1863 {
1864 this->node = this->node->last_child;
1865 }
1866 return *this;
1867}
1868
1869template <class T, class tree_node_allocator>
1871{
1872 post_order_iterator copy = *this;
1873 ++(*this);
1874 return copy;
1875}
1876
1877template <class T, class tree_node_allocator>
1879{
1880 post_order_iterator copy = *this;
1881 --(*this);
1882 return copy;
1883}
1884
1885
1886template <class T, class tree_node_allocator>
1888{
1889 while (num > 0)
1890 {
1891 ++(*this);
1892 --num;
1893 }
1894 return (*this);
1895}
1896
1897template <class T, class tree_node_allocator>
1899{
1900 while (num > 0)
1901 {
1902 --(*this);
1903 --num;
1904 }
1905 return (*this);
1906}
1907
1908template <class T, class tree_node_allocator>
1910{
1911 assert(this->node != 0);
1912 while (this->node->first_child)
1913 this->node = this->node->first_child;
1914}
1915
1916
1917// Fixed depth iterator
1918
1919template <class T, class tree_node_allocator>
1921 : iterator_base()
1922{
1923 set_first_parent_();
1924}
1925
1926template <class T, class tree_node_allocator>
1928 : iterator_base(tn)
1929{
1930 set_first_parent_();
1931}
1932
1933template <class T, class tree_node_allocator>
1935 : iterator_base(other.node)
1936{
1937 set_first_parent_();
1938}
1939
1940template <class T, class tree_node_allocator>
1942 : iterator_base(other.node), first_parent_(other.parent_)
1943{
1944 find_leftmost_parent_();
1945}
1946
1947template <class T, class tree_node_allocator>
1949 : iterator_base(other.node), first_parent_(other.first_parent_)
1950{
1951}
1952
1953template <class T, class tree_node_allocator>
1955{
1956 return; // FIXME: we do not use first_parent_ yet, and it actually needs some serious reworking if
1957 // it is ever to work at the 'head' level.
1958 first_parent_ = 0;
1959 if (this->node == 0) return;
1960 if (this->node->parent != 0)
1961 first_parent_ = this->node->parent;
1962 if (first_parent_)
1963 find_leftmost_parent_();
1964}
1965
1966template <class T, class tree_node_allocator>
1968{
1969 return; // FIXME: see 'set_first_parent()'
1970 tree_node *tmppar = first_parent_;
1971 while (tmppar->prev_sibling)
1972 {
1973 tmppar = tmppar->prev_sibling;
1974 if (tmppar->first_child)
1975 first_parent_ = tmppar;
1976 }
1977}
1978
1979template <class T, class tree_node_allocator>
1981{
1982 assert(this->node != 0);
1983
1984 if (this->node->next_sibling)
1985 {
1986 this->node = this->node->next_sibling;
1987 }
1988 else
1989 {
1990 int relative_depth = 0;
1991upper:
1992 do
1993 {
1994 this->node = this->node->parent;
1995 if (this->node == 0) return *this;
1996 --relative_depth;
1997 }
1998 while (this->node->next_sibling == 0);
1999lower:
2000 this->node = this->node->next_sibling;
2001 while (this->node->first_child == 0)
2002 {
2003 if (this->node->next_sibling == 0)
2004 goto upper;
2005 this->node = this->node->next_sibling;
2006 if (this->node == 0) return *this;
2007 }
2008 while (relative_depth < 0 && this->node->first_child != 0)
2009 {
2010 this->node = this->node->first_child;
2011 ++relative_depth;
2012 }
2013 if (relative_depth < 0)
2014 {
2015 if (this->node->next_sibling == 0) goto upper;
2016 else goto lower;
2017 }
2018 }
2019 return *this;
2020
2021// if(this->node->next_sibling!=0) {
2022// this->node=this->node->next_sibling;
2023// assert(this->node!=0);
2024// if(this->node->parent==0 && this->node->next_sibling==0) // feet element
2025// this->node=0;
2026// }
2027// else {
2028// tree_node *par=this->node->parent;
2029// do {
2030// par=par->next_sibling;
2031// if(par==0) { // FIXME: need to keep track of this!
2032// this->node=0;
2033// return *this;
2034// }
2035// } while(par->first_child==0);
2036// this->node=par->first_child;
2037// }
2038 return *this;
2039}
2040
2041template <class T, class tree_node_allocator>
2043{
2044 assert(this->node != 0);
2045 if (this->node->prev_sibling != 0)
2046 {
2047 this->node = this->node->prev_sibling;
2048 assert(this->node != 0);
2049 if (this->node->parent == 0 && this->node->prev_sibling == 0) // head element
2050 this->node = 0;
2051 }
2052 else
2053 {
2054 tree_node *par = this->node->parent;
2055 do
2056 {
2057 par = par->prev_sibling;
2058 if (par == 0) // FIXME: need to keep track of this!
2059 {
2060 this->node = 0;
2061 return *this;
2062 }
2063 }
2064 while (par->last_child == 0);
2065 this->node = par->last_child;
2066 }
2067 return *this;
2068}
2069
2070template <class T, class tree_node_allocator>
2072{
2073 fixed_depth_iterator copy = *this;
2074 ++(*this);
2075 return copy;
2076}
2077
2078template <class T, class tree_node_allocator>
2080{
2081 fixed_depth_iterator copy = *this;
2082 --(*this);
2083 return copy;
2084}
2085
2086template <class T, class tree_node_allocator>
2088{
2089 while (num > 0)
2090 {
2091 --(*this);
2092 --(num);
2093 }
2094 return (*this);
2095}
2096
2097template <class T, class tree_node_allocator>
2099{
2100 while (num > 0)
2101 {
2102 ++(*this);
2103 --(num);
2104 }
2105 return *this;
2106}
2107
2108// FIXME: add the other members of fixed_depth_iterator.
2109
2110
2111// Sibling iterator
2112
2113template <class T, class tree_node_allocator>
2115 : iterator_base()
2116{
2117 set_parent_();
2118}
2119
2120template <class T, class tree_node_allocator>
2122 : iterator_base(tn)
2123{
2124 set_parent_();
2125}
2126
2127template <class T, class tree_node_allocator>
2129 : iterator_base(other.node)
2130{
2131 set_parent_();
2132}
2133
2134template <class T, class tree_node_allocator>
2136 : iterator_base(other), parent_(other.parent_)
2137{
2138}
2139
2140template <class T, class tree_node_allocator>
2142{
2143 parent_ = 0;
2144 if (this->node == 0) return;
2145 if (this->node->parent != 0)
2146 parent_ = this->node->parent;
2147}
2148
2149template <class T, class tree_node_allocator>
2151{
2152 if (this->node)
2153 this->node = this->node->next_sibling;
2154 return *this;
2155}
2156
2157template <class T, class tree_node_allocator>
2159{
2160 if (this->node) this->node = this->node->prev_sibling;
2161 else
2162 {
2163 assert(parent_);
2164 this->node = parent_->last_child;
2165 }
2166 return *this;
2167}
2168
2169template <class T, class tree_node_allocator>
2171{
2172 sibling_iterator copy = *this;
2173 ++(*this);
2174 return copy;
2175}
2176
2177template <class T, class tree_node_allocator>
2179{
2180 sibling_iterator copy = *this;
2181 --(*this);
2182 return copy;
2183}
2184
2185template <class T, class tree_node_allocator>
2187{
2188 while (num > 0)
2189 {
2190 ++(*this);
2191 --num;
2192 }
2193 return (*this);
2194}
2195
2196template <class T, class tree_node_allocator>
2198{
2199 while (num > 0)
2200 {
2201 --(*this);
2202 --num;
2203 }
2204 return (*this);
2205}
2206
2207template <class T, class tree_node_allocator>
2209{
2210 tree_node *tmp = parent_->first_child;
2211 return tmp;
2212}
2213
2214template <class T, class tree_node_allocator>
2216{
2217 return parent_->last_child;
2218}
2219
2220
2221#endif
2222
2223// Local variables:
2224// default-tab-width: 3
2225// End:
Iterator which traverses only the nodes at a given depth from the root.
Definition tree.hh:207
Comparator class for iterators (compares the actual node content, not pointer values).
Definition tree.hh:375
Base class for iterators, only pointers stored, no traversal logic.
Definition tree.hh:132
void skip_children()
When called, the next increment/decrement skips children of this node.
Definition tree.hh:1653
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
Definition tree.hh:1659
Depth-first iterator, first accessing the children, then the node itself.
Definition tree.hh:182
void descend_all()
Set iterator to the first child as deep as possible down the tree.
Definition tree.hh:1909
Depth-first iterator, first accessing the node, then its children.
Definition tree.hh:163
Iterator which traverses only the nodes which are siblings of each other.
Definition tree.hh:232
A node in the tree, combining links to other nodes as well as the actual data.
Definition tree.hh:97
Definition tree.hh:107
post_order_iterator begin_post() const
Return post-order iterator to the beginning of the tree.
Definition tree.hh:593
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
Definition tree.hh:531
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:1346
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:1554
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:1243
T value_type
Value of the data stored at a node.
Definition tree.hh:112
pre_order_iterator iterator
The default iterator type throughout the tree class.
Definition tree.hh:203
iter insert_after(iter position, const T &x)
Insert node as next sibling of node pointed to by position.
Definition tree.hh:890
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:1208
sibling_iterator insert(sibling_iterator position, const T &x)
Specialisation of previous member.
Definition tree.hh:857
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:1272
iter previous_sibling(iter) const
Return iterator to the previous sibling of a node.
Definition tree.hh:677
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:916
iter reparent(iter position, iter from)
Move all child nodes of 'from' to be children of 'position'.
Definition tree.hh:1148
int depth(const iterator_base &) const
Compute the depth to the root.
Definition tree.hh:1428
sibling_iterator end(const iterator_base &) const
Return sibling iterator to the end of the children of a given node.
Definition tree.hh:660
iter parent(iter) const
Return iterator to the parent of a node.
Definition tree.hh:669
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:1523
iter append_child(iter position, iter other_position)
Append the node (plus its children) at other_position as a child of position.
Definition tree.hh:798
post_order_iterator end_post() const
Return post-order iterator to the end of the tree.
Definition tree.hh:605
iter append_child(iter position)
Insert empty node as last child of node pointed to by position.
Definition tree.hh:742
iter next_sibling(iter) const
Return iterator to the next sibling of a node.
Definition tree.hh:687
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:1530
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:1509
void clear()
Erase all nodes of the tree.
Definition tree.hh:523
sibling_iterator begin(const iterator_base &) const
Return sibling iterator to the first child of given node.
Definition tree.hh:650
iter replace(iter position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
Definition tree.hh:936
iter move_after(iter target, iter source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
Definition tree.hh:1155
iter append_children(iter position, sibling_iterator from, sibling_iterator to)
Append the nodes in the from-to range (plus their children) as children of position.
Definition tree.hh:808
pre_order_iterator begin() const
Return iterator to the beginning of the tree.
Definition tree.hh:581
iter insert(iter position, const T &x)
Insert node as previous sibling of node pointed to by position.
Definition tree.hh:829
fixed_depth_iterator begin_fixed(const iterator_base &, unsigned int) const
Return fixed-depth iterator to the first node at a given depth.
Definition tree.hh:611
unsigned int number_of_children(const iterator_base &) const
Count the number of children of node at position.
Definition tree.hh:1442
fixed_depth_iterator end_fixed(const iterator_base &, unsigned int) const
Return fixed-depth iterator to end of the nodes at given depth.
Definition tree.hh:630
iter append_child(iter position, const T &x)
Insert node as last child of node pointed to by position.
Definition tree.hh:768
iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
Move nodes in range to be children of 'position'.
Definition tree.hh:1095
bool empty() const
Check if tree is empty.
Definition tree.hh:1421
void swap(sibling_iterator it)
Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
Definition tree.hh:1473
int size() const
Count the total number of nodes.
Definition tree.hh:1408
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty tree.
Definition tree.hh:821
iter flatten(iter position)
Move all children of node at 'position' to be siblings, returns position.
Definition tree.hh:1064
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:945
unsigned int number_of_siblings(const iterator_base &) const
Count the number of 'next' siblings of node at iterator.
Definition tree.hh:1458
iter erase(iter)
Erase element at position pointed to by iterator, return incremented iterator.
Definition tree.hh:550
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:1392
iter next_at_same_depth(iter) const
Return iterator to the next node at a given depth.
Definition tree.hh:697
pre_order_iterator end() const
Return iterator to the end of the tree.
Definition tree.hh:587
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:1015
iter move_before(iter target, iter source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
Definition tree.hh:1182
SGMLApplication::Position position
Definition messages.cpp:34
Definition tree.hh:72