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 
71 namespace kp
72 {
73 
74 template <class T1, class T2>
75 void constructor(T1* p, T2& val)
76 {
77  new ((void *) p) T1(val);
78 }
79 
80 template <class T1>
81 void constructor(T1* p)
82 {
83  new ((void *) p) T1;
84 }
85 
86 template <class T1>
87 void destructor(T1* p)
88 {
89  p->~T1();
90 }
91 
92 }
93 
95 template<class T>
96 class tree_node_ // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
97 {
98 public:
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 
105 template < class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
106 class tree
107 {
108 protected:
109  typedef tree_node_<T> tree_node;
110 public:
112  typedef T value_type;
113 
114  class iterator_base;
115  class pre_order_iterator;
116  class post_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 
142  iterator_base();
144 
145  T& operator*() const;
146  T* operator->() const;
147 
149  void skip_children();
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 
203  typedef pre_order_iterator iterator;
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;
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);
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);
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 
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;
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
384 private:
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 
426 template <class T, class tree_node_allocator>
427 bool 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 
438 template <class T, class tree_node_allocator>
440 {
441  head_initialise_();
442 }
443 
444 template <class T, class tree_node_allocator>
446 {
447  head_initialise_();
448  set_head(x);
449 }
450 
451 template <class T, class tree_node_allocator>
452 tree<T, tree_node_allocator>::tree(const iterator_base& other)
453 {
454  head_initialise_();
455  set_head((*other));
456  replace(begin(), other);
457 }
458 
459 template <class T, class tree_node_allocator>
461 {
462  clear();
463  alloc_.deallocate(head, 1);
464  alloc_.deallocate(feet, 1);
465 }
466 
467 template <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 
486 template <class T, class tree_node_allocator>
488 {
489  copy_(other);
490 }
491 
492 template <class T, class tree_node_allocator>
494 {
495  head_initialise_();
496  copy_(other);
497 }
498 
499 template <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 
522 template <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 
530 template<class T, class tree_node_allocator>
531 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
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;
540  erase_children(pre_order_iterator(prev));
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 
548 template<class T, class tree_node_allocator>
549 template<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 
580 template <class T, class tree_node_allocator>
582 {
583  return pre_order_iterator(head->next_sibling);
584 }
585 
586 template <class T, class tree_node_allocator>
588 {
589  return pre_order_iterator(feet);
590 }
591 
592 template <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 
604 template <class T, class tree_node_allocator>
606 {
607  return post_order_iterator(feet);
608 }
609 
610 template <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 
629 template <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 
649 template <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 
659 template <class T, class tree_node_allocator>
661 {
662  sibling_iterator ret(0);
663  ret.parent_ = pos.node;
664  return ret;
665 }
666 
667 template <class T, class tree_node_allocator>
668 template <typename iter>
670 {
671  assert(position.node != 0);
672  return iter(position.node->parent);
673 }
674 
675 template <class T, class tree_node_allocator>
676 template <typename iter>
678 {
679  assert(position.node != 0);
680  iter ret(position);
681  ret.node = position.node->prev_sibling;
682  return ret;
683 }
684 
685 template <class T, class tree_node_allocator>
686 template <typename iter>
688 {
689  assert(position.node != 0);
690  iter ret(position);
691  ret.node = position.node->next_sibling;
692  return ret;
693 }
694 
695 template <class T, class tree_node_allocator>
696 template <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;
709 upper:
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);
717 lower:
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 
740 template <class T, class tree_node_allocator>
741 template <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 
766 template <class T, class tree_node_allocator>
767 template <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 
796 template <class T, class tree_node_allocator>
797 template <class iter>
799 {
800  assert(position.node != head);
801 
802  sibling_iterator aargh = append_child(position, value_type());
803  return replace(aargh, other);
804 }
805 
806 template <class T, class tree_node_allocator>
807 template <class iter>
808 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
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 
820 template <class T, class tree_node_allocator>
822 {
823  assert(head->next_sibling == feet);
824  return insert(iterator(feet), x);
825 }
826 
827 template <class T, class tree_node_allocator>
828 template <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 
856 template <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 
888 template <class T, class tree_node_allocator>
889 template <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 
914 template <class T, class tree_node_allocator>
915 template <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 
934 template <class T, class tree_node_allocator>
935 template <class iter>
937 {
938  kp::destructor(&position.node->data);
939  kp::constructor(&position.node->data, x);
940  return position;
941 }
942 
943 template <class T, class tree_node_allocator>
944 template <class iter>
945 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
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 
1014 template <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;
1032  pre_order_iterator ret;
1033  while (1 == 1)
1034  {
1035  pre_order_iterator tt = insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
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 
1062 template <class T, class tree_node_allocator>
1063 template <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 
1093 template <class T, class tree_node_allocator>
1094 template <typename iter>
1095 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
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 
1147 template <class T, class tree_node_allocator>
1148 template <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 
1154 template <class T, class tree_node_allocator>
1155 template <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 
1181 template <class T, class tree_node_allocator>
1182 template <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 
1207 template <class T, class tree_node_allocator>
1208 template <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 
1242 template <class T, class tree_node_allocator>
1243 void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,
1244  sibling_iterator from1, sibling_iterator from2,
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 
1271 template <class T, class tree_node_allocator>
1272 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
1273 {
1274  std::less<T> comp;
1275  sort(from, to, comp, deep);
1276 }
1277 
1278 template <class T, class tree_node_allocator>
1279 template <class StrictWeakOrdering>
1280 void 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 
1344 template <class T, class tree_node_allocator>
1345 template <typename iter>
1346 bool 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 
1352 template <class T, class tree_node_allocator>
1353 template <typename iter>
1354 bool 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 
1360 template <class T, class tree_node_allocator>
1361 template <typename iter, class BinaryPredicate>
1362 bool 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 
1380 template <class T, class tree_node_allocator>
1381 template <typename iter, class BinaryPredicate>
1382 bool 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 
1391 template <class T, class tree_node_allocator>
1392 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
1393 {
1394  tree tmp;
1395  tmp.set_head(value_type());
1396  tmp.replace(tmp.begin(), tmp.end(), from, to);
1397  return tmp;
1398 }
1399 
1400 template <class T, class tree_node_allocator>
1401 void 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 
1407 template <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 
1420 template <class T, class tree_node_allocator>
1422 {
1423  pre_order_iterator it = begin(), eit = end();
1424  return (it == eit);
1425 }
1426 
1427 template <class T, class tree_node_allocator>
1428 int tree<T, tree_node_allocator>::depth(const iterator_base& it) const
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 
1441 template <class T, class tree_node_allocator>
1442 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it) const
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 
1457 template <class T, class tree_node_allocator>
1458 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
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 
1472 template <class T, class tree_node_allocator>
1473 void tree<T, tree_node_allocator>::swap(sibling_iterator it)
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 
1508 template <class T, class tree_node_allocator>
1509 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,
1510  const iterator_base& end) const
1511 {
1512  // FIXME: this should be optimised.
1513  pre_order_iterator tmp = begin;
1514  while (tmp != end)
1515  {
1516  if (tmp == it) return true;
1517  ++tmp;
1518  }
1519  return false;
1520 }
1521 
1522 template <class T, class tree_node_allocator>
1523 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
1524 {
1525  if (it.node == 0 || it.node == feet) return false;
1526  else return true;
1527 }
1528 
1529 template <class T, class tree_node_allocator>
1530 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
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 
1553 template <class T, class tree_node_allocator>
1554 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num) const
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 
1570 template <class T, class tree_node_allocator>
1572  : node(0), skip_current_children_(false)
1573 {
1574 }
1575 
1576 template <class T, class tree_node_allocator>
1578  : node(tn), skip_current_children_(false)
1579 {
1580 }
1581 
1582 template <class T, class tree_node_allocator>
1584 {
1585  return node->data;
1586 }
1587 
1588 template <class T, class tree_node_allocator>
1590 {
1591  return &(node->data);
1592 }
1593 
1594 template <class T, class tree_node_allocator>
1595 bool 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 
1601 template <class T, class tree_node_allocator>
1602 bool 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 
1608 template <class T, class tree_node_allocator>
1609 bool 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 
1615 template <class T, class tree_node_allocator>
1616 bool 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 
1622 template <class T, class tree_node_allocator>
1623 bool 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 
1629 template <class T, class tree_node_allocator>
1630 bool 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 
1636 template <class T, class tree_node_allocator>
1638 {
1639  sibling_iterator ret(node->first_child);
1640  ret.parent_ = this->node;
1641  return ret;
1642 }
1643 
1644 template <class T, class tree_node_allocator>
1646 {
1647  sibling_iterator ret(0);
1648  ret.parent_ = node;
1649  return ret;
1650 }
1651 
1652 template <class T, class tree_node_allocator>
1654 {
1655  skip_current_children_ = true;
1656 }
1657 
1658 template <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 
1677 template <class T, class tree_node_allocator>
1679  : iterator_base(0)
1680 {
1681 }
1682 
1683 template <class T, class tree_node_allocator>
1685  : iterator_base(tn)
1686 {
1687 }
1688 
1689 template <class T, class tree_node_allocator>
1691  : iterator_base(other.node)
1692 {
1693 }
1694 
1695 template <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 
1710 template <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 
1732 template <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 
1751 template <class T, class tree_node_allocator>
1753 {
1754  pre_order_iterator copy = *this;
1755  ++(*this);
1756  return copy;
1757 }
1758 
1759 template <class T, class tree_node_allocator>
1761 {
1762  pre_order_iterator copy = *this;
1763  --(*this);
1764  return copy;
1765 }
1766 
1767 template <class T, class tree_node_allocator>
1769 {
1770  while (num > 0)
1771  {
1772  ++(*this);
1773  --num;
1774  }
1775  return (*this);
1776 }
1777 
1778 template <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 
1793 template <class T, class tree_node_allocator>
1795  : iterator_base(0)
1796 {
1797 }
1798 
1799 template <class T, class tree_node_allocator>
1801  : iterator_base(tn)
1802 {
1803 }
1804 
1805 template <class T, class tree_node_allocator>
1807  : iterator_base(other.node)
1808 {
1809 }
1810 
1811 template <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 
1826 template <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 
1851 template <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 
1869 template <class T, class tree_node_allocator>
1871 {
1872  post_order_iterator copy = *this;
1873  ++(*this);
1874  return copy;
1875 }
1876 
1877 template <class T, class tree_node_allocator>
1879 {
1880  post_order_iterator copy = *this;
1881  --(*this);
1882  return copy;
1883 }
1884 
1885 
1886 template <class T, class tree_node_allocator>
1888 {
1889  while (num > 0)
1890  {
1891  ++(*this);
1892  --num;
1893  }
1894  return (*this);
1895 }
1896 
1897 template <class T, class tree_node_allocator>
1899 {
1900  while (num > 0)
1901  {
1902  --(*this);
1903  --num;
1904  }
1905  return (*this);
1906 }
1907 
1908 template <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 
1919 template <class T, class tree_node_allocator>
1921  : iterator_base()
1922 {
1923  set_first_parent_();
1924 }
1925 
1926 template <class T, class tree_node_allocator>
1928  : iterator_base(tn)
1929 {
1930  set_first_parent_();
1931 }
1932 
1933 template <class T, class tree_node_allocator>
1935  : iterator_base(other.node)
1936 {
1937  set_first_parent_();
1938 }
1939 
1940 template <class T, class tree_node_allocator>
1942  : iterator_base(other.node), first_parent_(other.parent_)
1943 {
1944  find_leftmost_parent_();
1945 }
1946 
1947 template <class T, class tree_node_allocator>
1949  : iterator_base(other.node), first_parent_(other.first_parent_)
1950 {
1951 }
1952 
1953 template <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 
1966 template <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 
1979 template <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;
1991 upper:
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);
1999 lower:
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 
2041 template <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 
2070 template <class T, class tree_node_allocator>
2072 {
2073  fixed_depth_iterator copy = *this;
2074  ++(*this);
2075  return copy;
2076 }
2077 
2078 template <class T, class tree_node_allocator>
2080 {
2081  fixed_depth_iterator copy = *this;
2082  --(*this);
2083  return copy;
2084 }
2085 
2086 template <class T, class tree_node_allocator>
2088 {
2089  while (num > 0)
2090  {
2091  --(*this);
2092  --(num);
2093  }
2094  return (*this);
2095 }
2096 
2097 template <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 
2113 template <class T, class tree_node_allocator>
2115  : iterator_base()
2116 {
2117  set_parent_();
2118 }
2119 
2120 template <class T, class tree_node_allocator>
2122  : iterator_base(tn)
2123 {
2124  set_parent_();
2125 }
2126 
2127 template <class T, class tree_node_allocator>
2129  : iterator_base(other.node)
2130 {
2131  set_parent_();
2132 }
2133 
2134 template <class T, class tree_node_allocator>
2136  : iterator_base(other), parent_(other.parent_)
2137 {
2138 }
2139 
2140 template <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 
2149 template <class T, class tree_node_allocator>
2151 {
2152  if (this->node)
2153  this->node = this->node->next_sibling;
2154  return *this;
2155 }
2156 
2157 template <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 
2169 template <class T, class tree_node_allocator>
2171 {
2172  sibling_iterator copy = *this;
2173  ++(*this);
2174  return copy;
2175 }
2176 
2177 template <class T, class tree_node_allocator>
2179 {
2180  sibling_iterator copy = *this;
2181  --(*this);
2182  return copy;
2183 }
2184 
2185 template <class T, class tree_node_allocator>
2187 {
2188  while (num > 0)
2189  {
2190  ++(*this);
2191  --num;
2192  }
2193  return (*this);
2194 }
2195 
2196 template <class T, class tree_node_allocator>
2198 {
2199  while (num > 0)
2200  {
2201  --(*this);
2202  --num;
2203  }
2204  return (*this);
2205 }
2206 
2207 template <class T, class tree_node_allocator>
2209 {
2210  tree_node *tmp = parent_->first_child;
2211  return tmp;
2212 }
2213 
2214 template <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:
tree::iterator_base
Base class for iterators, only pointers stored, no traversal logic.
Definition: tree.hh:131
tree::sort
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
OFX
@ OFX
Definition: inc/libofx.h:140
tree::swap
void swap(sibling_iterator it)
Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
Definition: tree.hh:1473
tree::move_after
iter move_after(iter target, iter source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
Definition: tree.hh:1155
tree::iterator
pre_order_iterator iterator
The default iterator type throughout the tree class.
Definition: tree.hh:203
tree::begin_fixed
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
tree::move_before
iter move_before(iter target, iter source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
Definition: tree.hh:1182
tree::reparent
iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
Move nodes in range to be children of 'position'.
Definition: tree.hh:1095
tree::parent
iter parent(iter) const
Return iterator to the parent of a node.
Definition: tree.hh:669
tree::set_head
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty tree.
Definition: tree.hh:821
tree::sibling_iterator
Iterator which traverses only the nodes which are siblings of each other.
Definition: tree.hh:231
tree::erase
iter erase(iter)
Erase element at position pointed to by iterator, return incremented iterator.
Definition: tree.hh:550
tree::pre_order_iterator
Depth-first iterator, first accessing the node, then its children.
Definition: tree.hh:162
tree::empty
bool empty() const
Check if tree is empty.
Definition: tree.hh:1421
tree::begin
pre_order_iterator begin() const
Return iterator to the beginning of the tree.
Definition: tree.hh:581
tree::end
pre_order_iterator end() const
Return iterator to the end of the tree.
Definition: tree.hh:587
tree::equal
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
tree::append_children
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
tree::is_in_subtree
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
tree::replace
iter replace(iter position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
Definition: tree.hh:936
tree::iterator_base::number_of_children
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
Definition: tree.hh:1659
tree::erase_children
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
Definition: tree.hh:531
tree::append_child
iter append_child(iter position)
Insert empty node as last child of node pointed to by position.
Definition: tree.hh:742
tree::insert_after
iter insert_after(iter position, const T &x)
Insert node as next sibling of node pointed to by position.
Definition: tree.hh:890
tree_node_
A node in the tree, combining links to other nodes as well as the actual data.
Definition: tree.hh:96
tree::next_sibling
iter next_sibling(iter) const
Return iterator to the next sibling of a node.
Definition: tree.hh:687
tree::post_order_iterator
Depth-first iterator, first accessing the children, then the node itself.
Definition: tree.hh:181
tree::insert_subtree
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
tree::begin_post
post_order_iterator begin_post() const
Return post-order iterator to the beginning of the tree.
Definition: tree.hh:593
tree::iterator_base::skip_children
void skip_children()
When called, the next increment/decrement skips children of this node.
Definition: tree.hh:1653
tree::merge
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
tree::post_order_iterator::descend_all
void descend_all()
Set iterator to the first child as deep as possible down the tree.
Definition: tree.hh:1909
tree::insert
iter insert(iter position, const T &x)
Insert node as previous sibling of node pointed to by position.
Definition: tree.hh:829
position
SGMLApplication::Position position
Definition: messages.cpp:34
tree::next_at_same_depth
iter next_at_same_depth(iter) const
Return iterator to the next node at a given depth.
Definition: tree.hh:697
tree::iterator_base_less
Comparator class for iterators (compares the actual node content, not pointer values).
Definition: tree.hh:374
tree::move_ontop
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
tree::size
int size() const
Count the total number of nodes.
Definition: tree.hh:1408
tree::child
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
tree::is_valid
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
tree::previous_sibling
iter previous_sibling(iter) const
Return iterator to the previous sibling of a node.
Definition: tree.hh:677
kp
Definition: tree.hh:71
tree::clear
void clear()
Erase all nodes of the tree.
Definition: tree.hh:523
tree::number_of_children
unsigned int number_of_children(const iterator_base &) const
Count the number of children of node at position.
Definition: tree.hh:1442
tree::subtree
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
tree::end_post
post_order_iterator end_post() const
Return post-order iterator to the end of the tree.
Definition: tree.hh:605
tree::depth
int depth(const iterator_base &) const
Compute the depth to the root.
Definition: tree.hh:1428
tree::number_of_siblings
unsigned int number_of_siblings(const iterator_base &) const
Count the number of 'next' siblings of node at iterator.
Definition: tree.hh:1458
tree::fixed_depth_iterator
Iterator which traverses only the nodes at a given depth from the root.
Definition: tree.hh:206
tree::value_type
T value_type
Value of the data stored at a node.
Definition: tree.hh:112
tree
Definition: tree.hh:106
tree::end_fixed
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
tree::index
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
tree::flatten
iter flatten(iter position)
Move all children of node at 'position' to be siblings, returns position.
Definition: tree.hh:1064