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