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