NCBI C++ ToolKit
tree_msvc7.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /*
2 
3  $Id: tree_msvc7.hpp 99234 2023-03-01 16:28:17Z ucko $
4 
5  STL-like templated tree class.
6  Copyright (C) 2001 Kasper Peeters <k.peeters@damtp.cam.ac.uk>
7 
8  See
9 
10  http://www.damtp.cam.ac.uk/user/kp229/tree/
11 
12  for more information and documentation. See the Changelog file for
13  other credits.
14 
15  This program is free software; you can redistribute it and/or modify
16  it under the terms of the GNU General Public License as published by
17  the Free Software Foundation; version 2.
18 
19  This program is distributed in the hope that it will be useful,
20  but WITHOUT ANY WARRANTY; without even the implied warranty of
21  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  GNU General Public License for more details.
23 
24  You should have received a copy of the GNU General Public License
25  along with this program; if not, write to the Free Software
26  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27 
28  TODO: - 'Move' members are long overdue; will hopefully be incorporated in the
29  next release.
30  - Fixed depth iterators do not iterate over the entire range if there
31  are 'holes' in the tree.
32  - If a range uses const iter_base& as end iterator, things will
33  inevitably go wrong, because upcast from iter_base to a non-sibling_iter
34  is incorrect. This upcast should be removed (and then all illegal uses
35  as previously in 'equal' will be flagged by the compiler). This requires
36  new copy constructors though.
37  - There's a bug in replace(sibling_iterator, ...) when the ranges
38  sit next to each other. Turned up in append_child(iter,iter)
39  but has been avoided now.
40  - "std::operator<" does not work correctly on our iterators, and for some
41  reason a globally defined template operator< did not get picked up.
42  Using a comparison class now, but this should be investigated.
43 */
44 
45 #ifndef tree_hh_
46 #define tree_hh_
47 
48 #include <assert.h>
49 #include <memory>
50 #include <stdexcept>
51 #include <iterator>
52 #include <set>
53 
54 // HP-style construct/destroy have gone from the standard,
55 // so here is a copy.
56 
57 namespace kp {
58 
59 template <class T1, class T2>
60 inline void constructor(T1* p, T2& val)
61  {
62  new ((void *) p) T1(val);
63  }
64 
65 template <class T1>
66 inline void constructor(T1* p)
67  {
68  new ((void *) p) T1;
69  }
70 
71 template <class T1>
72 inline void destructor(T1* p)
73  {
74  p->~T1();
75  }
76 
77 }
78 
79 template<class T>
80 class NCBI_CDUTILS_EXPORT tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
81  public:
83  tree_node_<T> *first_child, *last_child;
84  tree_node_<T> *prev_sibling, *next_sibling;
86 };
87 
88 template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
90  protected:
91  public:
93  typedef T value_type;
94 
95  class iterator_base;
96  class pre_order_iterator;
97  class post_order_iterator;
98  class sibling_iterator;
99 
100  tree();
101  tree(const T&);
102  tree(const iterator_base&);
104  ~tree();
105  void operator=(const tree<T, tree_node_allocator>&);
106 
107 #ifdef __SGI_STL_PORT
108  class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
109 #else
111 #endif
112  public:
113  typedef T value_type;
114  typedef T* pointer;
115  typedef T& reference;
116  typedef size_t size_type;
117  typedef ptrdiff_t difference_type;
118  typedef std::bidirectional_iterator_tag iterator_category;
119 
120  iterator_base();
122 
123  T& operator*() const;
124  T* operator->() const;
125  bool operator==(const iterator_base&) const;
126  bool operator!=(const iterator_base&) const;
127 
128  void skip_children(); // do not iterate over children of this node
129  unsigned int number_of_children() const;
130 
131  sibling_iterator begin() const;
132  sibling_iterator end() const;
133  // ADDED BY VAHAN while conerting CDTRee2 from msvc6 to msvc7
134  bool is_valid() const { return node ? true : false ;}
135 
137  protected:
139  };
140 
142  public:
147 
148  pre_order_iterator& operator++();
150  pre_order_iterator operator++(int);
152  pre_order_iterator& operator+=(unsigned int);
153  pre_order_iterator& operator-=(unsigned int);
154  };
155 
157  public:
162 
163  post_order_iterator& operator++();
165  post_order_iterator operator++(int);
167  post_order_iterator& operator+=(unsigned int);
168  post_order_iterator& operator-=(unsigned int);
169 
170  void descend_all();
171  };
172 
174 
176  public:
182 
183  fixed_depth_iterator& operator++();
185  fixed_depth_iterator operator++(int);
187  fixed_depth_iterator& operator+=(unsigned int);
188  fixed_depth_iterator& operator-=(unsigned int);
189 
191  private:
192  void set_first_parent_();
193  void find_leftmost_parent_();
194  };
195 
197  public:
202 
203  sibling_iterator& operator++();
205  sibling_iterator operator++(int);
207  sibling_iterator& operator+=(unsigned int);
208  sibling_iterator& operator-=(unsigned int);
209 
210  tree_node *range_first() const;
211  tree_node *range_last() const;
213  private:
214  void set_parent_();
215  };
216 
217  // begin/end of tree
218  pre_order_iterator begin() const;
219  pre_order_iterator end() const;
220  post_order_iterator begin_post() const;
221  post_order_iterator end_post() const;
222  fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
223  fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
224  // begin/end of children of node
225  sibling_iterator begin(const iterator_base&) const;
226  sibling_iterator end(const iterator_base&) const;
227 
228  template<typename iter> iter parent(iter) const;
229  sibling_iterator previous_sibling(const iterator_base&) const;
230  sibling_iterator next_sibling(const iterator_base&) const;
231 
232  void clear();
233  // erase element at position pointed to by iterator, increment iterator
234  template<typename iter> iter erase(iter);
235  // erase all children of the node pointed to by iterator
236  void erase_children(const iterator_base&);
237 
238  // insert node as last child of node pointed to by position (first one inserts empty node)
239  template<typename iter> iter append_child(iter position);
240  template<typename iter> iter append_child(iter position, const T& x);
241  // the following two append nodes plus their children
242  template<typename iter> iter append_child(iter position, iter other_position);
243  template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
244 
245  // short-hand to insert topmost node in otherwise empty tree
246  pre_order_iterator set_head(const T& x);
247  // insert node as previous sibling of node pointed to by position
248  template<typename iter> iter insert(iter position, const T& x);
249  // specialisation: insert node as previous sibling of node pointed to by position
250  //pre_order_iterator insert(sibling_iterator position, const T& x);
251  sibling_iterator insert(sibling_iterator position, const T& x);
252  // insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
253  template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
254  // insert node as next sibling of node pointed to by position
255  template<typename iter> iter insert_after(iter position, const T& x);
256 
257  // replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
258  template<typename iter> iter replace(iter position, const T& x);
259  // replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
260  template<typename iter> iter replace(iter position, const iterator_base& from);
261  // replace string of siblings (plus their children) with copy of a new string (with children); see above
262  sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
263  sibling_iterator new_begin, sibling_iterator new_end);
264 
265  // move all children of node at 'position' to be siblings, returns position
266  template<typename iter> iter flatten(iter position);
267  // move nodes in range to be children of 'position'
268  template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
269  // ditto, the range being all children of the 'from' node
270  template<typename iter> iter reparent(iter position, iter from);
271 
272  // new style move members, moving nodes plus children to a different
273  template<typename iter> iter move_after(iter target, iter source);
274  template<typename iter> iter move_before(iter target, iter source);
275  template<typename iter> iter move_below(iter target, iter source);
276 
277  // merge with other tree, creating new branches and leaves only if they are not already present
279  bool duplicate_leaves=false);
280  // sort (std::sort only moves values of nodes, this one moves children as well)
281  void sort(sibling_iterator from, sibling_iterator to, bool deep=false);
282  template<class StrictWeakOrdering>
283  void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
284  // compare two ranges of nodes (compares nodes as well as tree structure)
285  template<typename iter>
286  bool equal(const iter& one, const iter& two, const iter& three) const;
287  template<typename iter, class BinaryPredicate>
288  bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
289  template<typename iter>
290  bool equal_subtree(const iter& one, const iter& two) const;
291  template<typename iter, class BinaryPredicate>
292  bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
293  // extract a new tree formed by the range of siblings plus all their children
294  tree subtree(sibling_iterator from, sibling_iterator to) const;
295  void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
296  // exchange the node (plus subtree) with its sibling node (do nothing if no sibling present)
297  void swap(sibling_iterator it);
298  // find a subtree
299 // template<class BinaryPredicate>
300 // iterator find_subtree(sibling_iterator, sibling_iterator, iterator from, iterator to, BinaryPredicate) const;
301 
302  // count the total number of nodes
303  int size() const;
304  // check if tree is empty
305  bool empty() const;
306  // compute the depth to the root
307  int depth(const iterator_base&) const;
308  // count the number of children of node at position
309  unsigned int number_of_children(const iterator_base&) const;
310  // count the number of 'next' siblings of node at iterator
311  unsigned int number_of_siblings(const iterator_base&) const;
312  // determine whether node at position is in the subtrees with root in the range
313  bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
314  const iterator_base& end) const;
315  // determine whether the iterator is an 'end' iterator and thus not actually
316  // pointing to a node
317  bool is_valid(const iterator_base&) const;
318 
319  // determine the index of a node in the range of siblings to which it belongs.
320  unsigned int index(sibling_iterator it) const;
321  // inverse of 'index': return the n-th child of the node at position
322  sibling_iterator child(const iterator_base& position, unsigned int) const;
323 
325  public:
327  const typename tree<T, tree_node_allocator>::iterator_base& two) const
328  {
329  return one.node < two.node;
330  }
331  };
332  tree_node *head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid
333 
334 // Return a new tree that is a restructuring of oldTree (*this) after
335 // re-rooting at the node 'newRoot'. Any properties of the nodes
336 // that depend on tree structure (e.g. branch length) are NOT
337 // adjusted. User will need to pre-process the nodes to deal
338 // with such node-specific issues.
339 
340 // Added by CJL: not part of distributed code
341  tree reroot(iterator newRoot) {
342 
343  tree newTree;
344  iterator attachNode, oldParent, z, zz;
345  int nChildren;
346  int nTopLevelNodes = number_of_siblings(begin());
347 
348  // start new tree at selected node
349  newTree = subtree(newRoot, next_sibling(newRoot));
350  attachNode = newTree.begin();
351  oldParent = parent(newRoot);
352  erase(newRoot);
353 
354  // climb old tree; attach old parent to its old child in the new tree
355  while(oldParent.is_valid()) {
356  z = parent(oldParent);
357  attachNode = newTree.reparent(attachNode, oldParent, next_sibling(oldParent));
358  oldParent = z;
359  }
360 
361  // Move over any sibling subtrees also attached to head as needed.
362  // Avoid spuriously creating an internal node corresp to 'root' of
363  // an old tree if not needed.
364 
365  if (nTopLevelNodes > 1) {
366  if (nTopLevelNodes > 2) {
367  attachNode = newTree.append_child(attachNode, value_type());
368  }
369  z = begin();
370  while (z.is_valid() && z != end()) {
371  zz = next_sibling(z);
372  newTree.reparent(attachNode, z, zz);
373  z = zz;
374 
375  }
376  }
377 
378  // If old root has only one child, remove it and reparent its children
379 
380  nChildren = newTree.number_of_children(attachNode);
381  if (nChildren <= 1) {
382  oldParent = newTree.parent(attachNode);
383  if (nChildren == 1) {
384  z = newTree.reparent(oldParent, attachNode.begin(), next_sibling(attachNode.begin()));
385  }
386  newTree.erase(attachNode);
387  }
388 
389  return newTree;
390  }
391 // End CJL addition
392 
393  private:
394  tree_node_allocator alloc_;
395  void head_initialise_();
396  void copy_(const tree<T, tree_node_allocator>& other);
397  template<class StrictWeakOrdering>
399  public:
400  bool operator()(const tree_node*, const tree_node *);
401  };
402 };
403 
404 //template <class T, class tree_node_allocator>
405 //class iterator_base_less {
406 // public:
407 // bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
408 // const typename tree<T, tree_node_allocator>::iterator_base& two) const
409 // {
410 // txtout << "operatorclass<" << one.node < two.node << std::endl;
411 // return one.node < two.node;
412 // }
413 //};
414 
415 //template <class T, class tree_node_allocator>
416 //bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
417 // const typename tree<T, tree_node_allocator>::iterator& two)
418 // {
419 // txtout << "operator< " << one.node < two.node << std::endl;
420 // if(one.node < two.node) return true;
421 // return false;
422 // }
423 
424 template <class T, class tree_node_allocator>
428  {
429  if(one.node > two.node) return true;
430  return false;
431  }
432 
433 
434 
435 // Tree
436 
437 template <class T, class tree_node_allocator>
439  {
440  head_initialise_();
441  }
442 
443 template <class T, class tree_node_allocator>
445  {
446  head_initialise_();
447  set_head(x);
448  }
449 
450 template <class T, class tree_node_allocator>
452  {
453  head_initialise_();
454  set_head((*other));
455  replace(begin(), other);
456  }
457 
458 template <class T, class tree_node_allocator>
460  {
461  clear();
462  alloc_.deallocate(head,1);
463  alloc_.deallocate(feet,1);
464  }
465 
466 template <class T, class tree_node_allocator>
468  {
469  head = (tree_node*) alloc_.allocate(1);
470  feet = (tree_node*) alloc_.allocate(1);
471 
472  head->parent=0;
473  head->first_child=0;
474  head->last_child=0;
475  head->prev_sibling=0; //head;
476  head->next_sibling=feet; //head;
477 
478  feet->parent=0;
479  feet->first_child=0;
480  feet->last_child=0;
481  feet->prev_sibling=head;
482  feet->next_sibling=0;
483  }
484 
485 template <class T, class tree_node_allocator>
487  {
488  copy_(other);
489  }
490 
491 template <class T, class tree_node_allocator>
493  {
494  head_initialise_();
495  copy_(other);
496  }
497 
498 template <class T, class tree_node_allocator>
500  {
501  clear();
502  pre_order_iterator it=other.begin(), to=begin();
503  while(it!=other.end()) {
504  to=insert(to, (*it));
505  it.skip_children();
506  ++it;
507  }
508  to=begin();
509  it=other.begin();
510  while(it!=other.end()) {
511  to=replace(to, it);
512  to.skip_children();
513  it.skip_children();
514  ++to;
515  ++it;
516  }
517  }
518 
519 template <class T, class tree_node_allocator>
521  {
522  if(head)
523  while(head->next_sibling!=feet)
524  erase(pre_order_iterator(head->next_sibling));
525  }
526 
527 template<class T, class tree_node_allocator>
529  {
530  tree_node *cur=it.node->first_child;
531  tree_node *prev=0;
532 
533  while(cur!=0) {
534  prev=cur;
535  cur=cur->next_sibling;
536  erase_children(pre_order_iterator(prev));
537  kp::destructor(&prev->data);
538  alloc_.deallocate(prev,1);
539  }
540  it.node->first_child=0;
541  it.node->last_child=0;
542  }
543 
544 template<class T, class tree_node_allocator>
545 template<class iter>
547  {
548  tree_node *cur=it.node;
549  assert(cur!=head);
550  iter ret=it;
551  ret.skip_children();
552  ++ret;
553  erase_children(it);
554  if(cur->prev_sibling==0) {
555  cur->parent->first_child=cur->next_sibling;
556  }
557  else {
558  cur->prev_sibling->next_sibling=cur->next_sibling;
559  }
560  if(cur->next_sibling==0) {
561  cur->parent->last_child=cur->prev_sibling;
562  }
563  else {
564  cur->next_sibling->prev_sibling=cur->prev_sibling;
565  }
566 
567  kp::destructor(&cur->data);
568  alloc_.deallocate(cur,1);
569  return ret;
570  }
571 
572 template <class T, class tree_node_allocator>
574  {
575  return pre_order_iterator(head->next_sibling);
576  }
577 
578 template <class T, class tree_node_allocator>
580  {
581  return pre_order_iterator(feet);
582  }
583 
584 template <class T, class tree_node_allocator>
586  {
587  tree_node *tmp=head->next_sibling;
588  if(tmp!=feet) {
589  while(tmp->first_child)
590  tmp=tmp->first_child;
591  }
592  return post_order_iterator(tmp);
593  }
594 
595 template <class T, class tree_node_allocator>
597  {
598  return post_order_iterator(feet);
599  }
600 
601 template <class T, class tree_node_allocator>
603  {
604  tree_node *tmp=pos.node;
605  unsigned int curdepth=0;
606  while(curdepth<dp) { // go down one level
607  while(tmp->first_child==0) {
608  tmp=tmp->next_sibling;
609  if(tmp==0)
610  throw std::range_error("tree: begin_fixed out of range");
611  }
612  tmp=tmp->first_child;
613  ++curdepth;
614  }
615  return tmp;
616  }
617 
618 template <class T, class tree_node_allocator>
620  {
621  assert(1==0); // FIXME: not correct yet
622  tree_node *tmp=pos.node;
623  unsigned int curdepth=1;
624  while(curdepth<dp) { // go down one level
625  while(tmp->first_child==0) {
626  tmp=tmp->next_sibling;
627  if(tmp==0)
628  throw std::range_error("tree: end_fixed out of range");
629  }
630  tmp=tmp->first_child;
631  ++curdepth;
632  }
633  return tmp;
634  }
635 
636 template <class T, class tree_node_allocator>
638  {
639  if(pos.node->first_child==0) {
640  return end(pos);
641  }
642  return pos.node->first_child;
643  }
644 
645 template <class T, class tree_node_allocator>
647  {
648  sibling_iterator ret(0);
649  ret.parent_=pos.node;
650  return ret;
651  }
652 
653 template <class T, class tree_node_allocator>
654 template <typename iter>
655 iter tree<T, tree_node_allocator>::parent(iter position) const
656  {
657  assert(position.node!=0);
658  return iter(position.node->parent);
659  }
660 
661 template <class T, class tree_node_allocator>
663  {
664  assert(position.node!=0);
665  return sibling_iterator(position.node->prev_sibling);
666  }
667 
668 template <class T, class tree_node_allocator>
670  {
671  assert(position.node!=0);
672  if(position.node->next_sibling==0)
673  return end(pre_order_iterator(position.node->parent));
674  else
675  return sibling_iterator(position.node->next_sibling);
676  }
677 
678 template <class T, class tree_node_allocator>
679 template <typename iter>
681  {
682  assert(position.node!=head);
683 
684  tree_node* tmp = (tree_node*) alloc_.allocate(1);
685  kp::constructor(&tmp->data);
686  tmp->first_child=0;
687  tmp->last_child=0;
688 
689  tmp->parent=position.node;
690  if(position.node->last_child!=0) {
691  position.node->last_child->next_sibling=tmp;
692  }
693  else {
694  position.node->first_child=tmp;
695  }
696  tmp->prev_sibling=position.node->last_child;
697  position.node->last_child=tmp;
698  tmp->next_sibling=0;
699  return tmp;
700  }
701 
702 template <class T, class tree_node_allocator>
703 template <class iter>
704 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
705  {
706  // If your program fails here you probably used 'append_child' to add the top
707  // node to an empty tree. From version 1.45 the top element should be added
708  // using 'insert'. See the documentation for further information, and sorry about
709  // the API change.
710  assert(position.node!=head);
711 
712  tree_node* tmp = (tree_node*) alloc_.allocate(1);
713  kp::constructor(&tmp->data, x);
714  tmp->first_child=0;
715  tmp->last_child=0;
716 
717  tmp->parent=position.node;
718  if(position.node->last_child!=0) {
719  position.node->last_child->next_sibling=tmp;
720  }
721  else {
722  position.node->first_child=tmp;
723  }
724  tmp->prev_sibling=position.node->last_child;
725  position.node->last_child=tmp;
726  tmp->next_sibling=0;
727  return tmp;
728  }
729 
730 template <class T, class tree_node_allocator>
731 template <class iter>
732 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
733  {
734  assert(position.node!=head);
735 
736  sibling_iterator aargh=append_child(position, value_type());
737  return replace(aargh, other);
738  }
739 
740 template <class T, class tree_node_allocator>
741 template <class iter>
743  {
744  iter ret=from;
745 
746  while(from!=to) {
747  insert_subtree(position.end(), from);
748  ++from;
749  }
750  return ret;
751  }
752 
753 template <class T, class tree_node_allocator>
755  {
756  assert(head->next_sibling==feet);
757  return insert(iterator(feet), x);
758  }
759 
760 template <class T, class tree_node_allocator>
761 template <class iter>
762 iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
763  {
764  if(position.node==0) {
765  position.node=feet; // Backward compatibility: when calling insert on a null node,
766  // insert before the feet.
767  }
768  tree_node* tmp = (tree_node*) alloc_.allocate(1);
769  kp::constructor(&tmp->data, x);
770  tmp->first_child=0;
771  tmp->last_child=0;
772 
773  tmp->parent=position.node->parent;
774  tmp->next_sibling=position.node;
775  tmp->prev_sibling=position.node->prev_sibling;
776  position.node->prev_sibling=tmp;
777 
778  if(tmp->prev_sibling==0)
779  tmp->parent->first_child=tmp;
780  else
781  tmp->prev_sibling->next_sibling=tmp;
782  return tmp;
783  }
784 
785 template <class T, class tree_node_allocator>
787  {
788  tree_node* tmp = (tree_node*) alloc_.allocate(1);
789  kp::constructor(&tmp->data, x);
790  tmp->first_child=0;
791  tmp->last_child=0;
792 
793  tmp->next_sibling=position.node;
794  if(position.node==0) { // iterator points to end of a subtree
795  tmp->parent=position.parent_;
796  tmp->prev_sibling=position.range_last();
797  tmp->parent->last_child=tmp;
798  }
799  else {
800  tmp->parent=position.node->parent;
801  tmp->prev_sibling=position.node->prev_sibling;
802  position.node->prev_sibling=tmp;
803  }
804 
805  if(tmp->prev_sibling==0)
806  tmp->parent->first_child=tmp;
807  else
808  tmp->prev_sibling->next_sibling=tmp;
809  return tmp;
810  }
811 
812 template <class T, class tree_node_allocator>
813 template <class iter>
814 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
815  {
816  tree_node* tmp = (tree_node*) alloc_.allocate(1);
817  kp::constructor(&tmp->data, x);
818  tmp->first_child=0;
819  tmp->last_child=0;
820 
821  tmp->parent=position.node->parent;
822  tmp->prev_sibling=position.node;
823  tmp->next_sibling=position.node->next_sibling;
824  position.node->next_sibling=tmp;
825 
826  if(tmp->next_sibling==0) {
827  if(tmp->parent) // when adding nodes at the head, there is no parent
828  tmp->parent->last_child=tmp;
829  }
830  else {
831  tmp->next_sibling->prev_sibling=tmp;
832  }
833  return tmp;
834  }
835 
836 template <class T, class tree_node_allocator>
837 template <class iter>
839  {
840  // insert dummy
841  iter it=insert(position, value_type());
842  // replace dummy with subtree
843  return replace(it, subtree);
844  }
845 
846 // template <class T, class tree_node_allocator>
847 // template <class iter>
848 // iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
849 // {
850 // // insert dummy
851 // iter it(insert(position, value_type()));
852 // // replace dummy with subtree
853 // return replace(it, subtree);
854 // }
855 
856 template <class T, class tree_node_allocator>
857 template <class iter>
858 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
859  {
860  kp::destructor(&position.node->data);
861  kp::constructor(&position.node->data, x);
862  return position;
863  }
864 
865 template <class T, class tree_node_allocator>
866 template <class iter>
867 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
868  {
869  assert(position.node!=head);
870  tree_node *current_from=from.node;
871  tree_node *start_from=from.node;
872  tree_node *current_to =position.node;
873 
874  // replace the node at position with head of the replacement tree at from
875  erase_children(position);
876  tree_node* tmp = (tree_node*) alloc_.allocate(1);
877  kp::constructor(&tmp->data, (*from));
878  tmp->first_child=0;
879  tmp->last_child=0;
880  if(current_to->prev_sibling==0) {
881  current_to->parent->first_child=tmp;
882  }
883  else {
884  current_to->prev_sibling->next_sibling=tmp;
885  }
886  tmp->prev_sibling=current_to->prev_sibling;
887  if(current_to->next_sibling==0) {
888  current_to->parent->last_child=tmp;
889  }
890  else {
891  current_to->next_sibling->prev_sibling=tmp;
892  }
893  tmp->next_sibling=current_to->next_sibling;
894  tmp->parent=current_to->parent;
895  kp::destructor(&current_to->data);
896  alloc_.deallocate(current_to,1);
897  current_to=tmp;
898 
899  // only at this stage can we fix 'last'
901 
902  pre_order_iterator toit=tmp;
903  // copy all children
904  do {
905  assert(current_from!=0);
906  if(current_from->first_child != 0) {
907  current_from=current_from->first_child;
908  toit=append_child(toit, current_from->data);
909  }
910  else {
911  while(current_from->next_sibling==0 && current_from!=start_from) {
912  current_from=current_from->parent;
913  toit=parent(toit);
914  assert(current_from!=0);
915  }
916  current_from=current_from->next_sibling;
917  if(current_from!=last) {
918  toit=append_child(parent(toit), current_from->data);
919  }
920  }
921  } while(current_from!=last);
922 
923  return current_to;
924  }
925 
926 template <class T, class tree_node_allocator>
928  sibling_iterator orig_begin,
929  sibling_iterator orig_end,
930  sibling_iterator new_begin,
931  sibling_iterator new_end)
932  {
933  tree_node *orig_first=orig_begin.node;
934  tree_node *new_first=new_begin.node;
935  tree_node *orig_last=orig_first;
936  while((++orig_begin)!=orig_end)
937  orig_last=orig_last->next_sibling;
938  tree_node *new_last=new_first;
939  while((++new_begin)!=new_end)
940  new_last=new_last->next_sibling;
941 
942  // insert all siblings in new_first..new_last before orig_first
943  bool first=true;
944  pre_order_iterator ret;
945  while(1==1) {
946  pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
947  if(first) {
948  ret=tt;
949  first=false;
950  }
951  if(new_first==new_last)
952  break;
953  new_first=new_first->next_sibling;
954  }
955 
956  // erase old range of siblings
957  bool last=false;
958  tree_node *next=orig_first;
959  while(1==1) {
960  if(next==orig_last)
961  last=true;
962  next=next->next_sibling;
963  erase((pre_order_iterator)orig_first);
964  if(last)
965  break;
966  orig_first=next;
967  }
968  return ret;
969  }
970 
971 template <class T, class tree_node_allocator>
972 template <typename iter>
974  {
975  if(position.node->first_child==0)
976  return position;
977 
978  tree_node *tmp=position.node->first_child;
979  while(tmp) {
980  tmp->parent=position.node->parent;
981  tmp=tmp->next_sibling;
982  }
983  if(position.node->next_sibling) {
984  position.node->last_child->next_sibling=position.node->next_sibling;
985  position.node->next_sibling->prev_sibling=position.node->last_child;
986  }
987  else {
988  position.node->parent->last_child=position.node->last_child;
989  }
990  position.node->next_sibling=position.node->first_child;
991  position.node->next_sibling->prev_sibling=position.node;
992  position.node->first_child=0;
993  position.node->last_child=0;
994 
995  return position;
996  }
997 
998 
999 template <class T, class tree_node_allocator>
1000 template <typename iter>
1002  {
1003  tree_node *first=begin.node;
1004  tree_node *last=first;
1005  if(begin==end) return begin;
1006  // determine last node
1007  while((++begin)!=end) {
1008  last=last->next_sibling;
1009  }
1010  // move subtree
1011  if(first->prev_sibling==0) {
1012  first->parent->first_child=last->next_sibling;
1013  }
1014  else {
1015  first->prev_sibling->next_sibling=last->next_sibling;
1016  }
1017  if(last->next_sibling==0) {
1018  last->parent->last_child=first->prev_sibling;
1019  }
1020  else {
1021  last->next_sibling->prev_sibling=first->prev_sibling;
1022  }
1023  if(position.node->first_child==0) {
1024  position.node->first_child=first;
1025  position.node->last_child=last;
1026  first->prev_sibling=0;
1027  }
1028  else {
1029  position.node->last_child->next_sibling=first;
1030  first->prev_sibling=position.node->last_child;
1031  position.node->last_child=last;
1032  }
1033  last->next_sibling=0;
1034 
1035  tree_node *pos=first;
1036  while(1==1) {
1037  pos->parent=position.node;
1038  if(pos==last) break;
1039  pos=pos->next_sibling;
1040  }
1041 
1042  return first;
1043  }
1044 
1045 template <class T, class tree_node_allocator>
1046 template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
1047  {
1048  if(from.node->first_child==0) return position;
1049  return reparent(position, from.node->first_child, end(from));
1050  }
1051 
1052 template <class T, class tree_node_allocator>
1053 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
1054  {
1055  tree_node *dst=target.node;
1056  tree_node *src=source.node;
1057  assert(dst);
1058  assert(src);
1059 
1060  if(dst==src) return source;
1061 
1062  // take src out of the tree
1063  if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1064  else src->parent->first_child=src->next_sibling;
1065  if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1066  else src->parent->last_child=src->prev_sibling;
1067 
1068  // connect it to the new point
1069  if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
1070  else dst->parent->first_child=src;
1071  src->prev_sibling=dst->prev_sibling;
1072  dst->prev_sibling=src;
1073  src->next_sibling=dst;
1074  src->parent=dst->parent;
1075  return src;
1076  }
1077 
1078 template <class T, class tree_node_allocator>
1080  sibling_iterator from1, sibling_iterator from2,
1081  bool duplicate_leaves)
1082  {
1083  sibling_iterator fnd;
1084  while(from1!=from2) {
1085  if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
1086  if(from1.begin()==from1.end()) { // full depth reached
1087  if(duplicate_leaves)
1088  append_child(parent(to1), (*from1));
1089  }
1090  else { // descend further
1091  merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1092  }
1093  }
1094  else { // element missing
1095  insert_subtree(to2, from1);
1096  }
1097  ++from1;
1098  }
1099  }
1100 
1101 template <class T, class tree_node_allocator>
1102 template <class StrictWeakOrdering>
1104  const tree_node *b)
1105  {
1106  static StrictWeakOrdering comp;
1107 
1108  return comp(a->data, b->data);
1109  }
1110 
1111 template <class T, class tree_node_allocator>
1113  {
1114  std::less<T> comp;
1115  sort(from, to, comp, deep);
1116  }
1117 
1118 template <class T, class tree_node_allocator>
1119 template <class StrictWeakOrdering>
1121  StrictWeakOrdering comp, bool deep)
1122  {
1123  if(from==to) return;
1124  // make list of sorted nodes
1125  // CHECK: if multiset stores equivalent nodes in the order in which they
1126  // are inserted, then this routine should be called 'stable_sort'.
1127  std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes;
1128  sibling_iterator it=from, it2=to;
1129  while(it != to) {
1130  nodes.insert(it.node);
1131  ++it;
1132  }
1133  // reassemble
1134  --it2;
1135 
1136  // prev and next are the nodes before and after the sorted range
1138  tree_node *next=it2.node->next_sibling;
1139  typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
1140  if(prev==0) {
1141  if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1142  (*nit)->parent->first_child=(*nit);
1143  }
1144  else prev->next_sibling=(*nit);
1145 
1146  --eit;
1147  while(nit!=eit) {
1148  (*nit)->prev_sibling=prev;
1149  if(prev)
1150  prev->next_sibling=(*nit);
1151  prev=(*nit);
1152  ++nit;
1153  }
1154  // prev now points to the last-but-one node in the sorted range
1155  if(prev)
1156  prev->next_sibling=(*eit);
1157 
1158  // eit points to the last node in the sorted range.
1159  (*eit)->next_sibling=next;
1160  (*eit)->prev_sibling=prev; // missed in the loop above
1161  if(next==0) {
1162  if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1163  (*eit)->parent->last_child=(*eit);
1164  }
1165  else next->prev_sibling=(*eit);
1166 
1167  if(deep) { // sort the children of each node too
1168  sibling_iterator bcs(*nodes.begin());
1169  sibling_iterator ecs(*eit);
1170  ++ecs;
1171  while(bcs!=ecs) {
1172  sort(begin(bcs), end(bcs), comp, deep);
1173  ++bcs;
1174  }
1175  }
1176  }
1177 
1178 template <class T, class tree_node_allocator>
1179 template <typename iter>
1180 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
1181  {
1182  std::equal_to<T> comp;
1183  return equal(one_, two, three_, comp);
1184  }
1185 
1186 template <class T, class tree_node_allocator>
1187 template <typename iter>
1188 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
1189  {
1190  std::equal_to<T> comp;
1191  return equal_subtree(one_, two_, comp);
1192  }
1193 
1194 template <class T, class tree_node_allocator>
1195 template <typename iter, class BinaryPredicate>
1196 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
1197  {
1198  pre_order_iterator one(one_), three(three_);
1199 
1200 // if(one==two && is_valid(three) && three.number_of_children()!=0)
1201 // return false;
1202  while(one!=two && is_valid(three)) {
1203  if(!fun(*one,*three))
1204  return false;
1205  if(one.number_of_children()!=three.number_of_children())
1206  return false;
1207  ++one;
1208  ++three;
1209  }
1210  return true;
1211  }
1212 
1213 template <class T, class tree_node_allocator>
1214 template <typename iter, class BinaryPredicate>
1215 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
1216  {
1217  pre_order_iterator one(one_), two(two_);
1218 
1219  if(!fun(*one,*two)) return false;
1220  if(number_of_children(one)!=number_of_children(two)) return false;
1221  return equal(begin(one),end(one),begin(two),fun);
1222  }
1223 
1224 template <class T, class tree_node_allocator>
1226  {
1227  tree tmp;
1228  tmp.set_head(value_type());
1229  tmp.replace(tmp.begin(), tmp.end(), from, to);
1230  return tmp;
1231  }
1232 
1233 template <class T, class tree_node_allocator>
1235  {
1236  tmp.set_head(value_type());
1237  tmp.replace(tmp.begin(), tmp.end(), from, to);
1238  }
1239 
1240 template <class T, class tree_node_allocator>
1242  {
1243  int i=0;
1244  pre_order_iterator it=begin(), eit=end();
1245  while(it!=eit) {
1246  ++i;
1247  ++it;
1248  }
1249  return i;
1250  }
1251 
1252 template <class T, class tree_node_allocator>
1254  {
1255  pre_order_iterator it=begin(), eit=end();
1256  return (it==eit);
1257  }
1258 
1259 template <class T, class tree_node_allocator>
1261  {
1262  tree_node* pos=it.node;
1263  assert(pos!=0);
1264  int ret=0;
1265  while(pos->parent!=0) {
1266  pos=pos->parent;
1267  ++ret;
1268  }
1269  return ret;
1270  }
1271 
1272 template <class T, class tree_node_allocator>
1274  {
1275  tree_node *pos=it.node->first_child;
1276  if(pos==0) return 0;
1277 
1278  unsigned int ret=1;
1279 // while(pos!=it.node->last_child) {
1280 // ++ret;
1281 // pos=pos->next_sibling;
1282 // }
1283  while((pos=pos->next_sibling))
1284  ++ret;
1285  return ret;
1286  }
1287 
1288 template <class T, class tree_node_allocator>
1290  {
1291  tree_node *pos=it.node;
1292  unsigned int ret=1;
1293  while(pos->next_sibling && pos->next_sibling!=head) {
1294  ++ret;
1295  pos=pos->next_sibling;
1296  }
1297  return ret;
1298  }
1299 
1300 template <class T, class tree_node_allocator>
1302  {
1303  tree_node *nxt=it.node->next_sibling;
1304  if(nxt) {
1305  if(it.node->prev_sibling)
1306  it.node->prev_sibling->next_sibling=nxt;
1307  else
1308  it.node->parent->first_child=nxt;
1309  nxt->prev_sibling=it.node->prev_sibling;
1310  tree_node *nxtnxt=nxt->next_sibling;
1311  if(nxtnxt)
1312  nxtnxt->prev_sibling=it.node;
1313  else
1314  it.node->parent->last_child=it.node;
1315  nxt->next_sibling=it.node;
1316  it.node->prev_sibling=nxt;
1317  it.node->next_sibling=nxtnxt;
1318  }
1319  }
1320 
1321 // template <class BinaryPredicate>
1322 // tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
1323 // sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
1324 // BinaryPredicate fun) const
1325 // {
1326 // assert(1==0); // this routine is not finished yet.
1327 // while(from!=to) {
1328 // if(fun(*subfrom, *from)) {
1329 //
1330 // }
1331 // }
1332 // return to;
1333 // }
1334 
1335 template <class T, class tree_node_allocator>
1337  const iterator_base& end) const
1338  {
1339  // FIXME: this should be optimised.
1340  pre_order_iterator tmp=begin;
1341  while(tmp!=end) {
1342  if(tmp==it) return true;
1343  ++tmp;
1344  }
1345  return false;
1346  }
1347 
1348 template <class T, class tree_node_allocator>
1350  {
1351  if(it.node==0 || it.node==feet) return false;
1352  else return true;
1353  }
1354 
1355 template <class T, class tree_node_allocator>
1357  {
1358  unsigned int ind=0;
1359  if(it.node->parent==0) {
1360  while(it.node->prev_sibling!=head) {
1361  it.node=it.node->prev_sibling;
1362  ++ind;
1363  }
1364  }
1365  else {
1366  while(it.node->prev_sibling!=0) {
1367  it.node=it.node->prev_sibling;
1368  ++ind;
1369  }
1370  }
1371  return ind;
1372  }
1373 
1374 
1375 template <class T, class tree_node_allocator>
1377  {
1379  while(num--) {
1380  assert(tmp!=0);
1381  tmp=tmp->next_sibling;
1382  }
1383  return tmp;
1384  }
1385 
1386 
1387 
1388 
1389 // Iterator base
1390 
1391 template <class T, class tree_node_allocator>
1393  : node(0), skip_current_children_(false)
1394  {
1395  }
1396 
1397 template <class T, class tree_node_allocator>
1399  : node(tn), skip_current_children_(false)
1400  {
1401  }
1402 
1403 template <class T, class tree_node_allocator>
1405  {
1406  return node->data;
1407  }
1408 
1409 template <class T, class tree_node_allocator>
1411  {
1412  return &(node->data);
1413  }
1414 
1415 template <class T, class tree_node_allocator>
1417  {
1418  if(other.node!=this->node) return true;
1419  else return false;
1420  }
1421 
1422 template <class T, class tree_node_allocator>
1424  {
1425  if(other.node==this->node) return true;
1426  else return false;
1427  }
1428 
1429 template <class T, class tree_node_allocator>
1431  {
1432  sibling_iterator ret(node->first_child);
1433  ret.parent_=this->node;
1434  return ret;
1435  }
1436 
1437 template <class T, class tree_node_allocator>
1439  {
1440  sibling_iterator ret(0);
1441  ret.parent_=node;
1442  return ret;
1443  }
1444 
1445 template <class T, class tree_node_allocator>
1447  {
1448  skip_current_children_=true;
1449  }
1450 
1451 template <class T, class tree_node_allocator>
1453  {
1454  tree_node *pos=node->first_child;
1455  if(pos==0) return 0;
1456 
1457  unsigned int ret=1;
1458  while(pos!=node->last_child) {
1459  ++ret;
1460  pos=pos->next_sibling;
1461  }
1462  return ret;
1463  }
1464 
1465 
1466 
1467 // Pre-order iterator
1468 
1469 template <class T, class tree_node_allocator>
1471  : iterator_base(0)
1472  {
1473  }
1474 
1475 template <class T, class tree_node_allocator>
1477  : iterator_base(tn)
1478  {
1479  }
1480 
1481 template <class T, class tree_node_allocator>
1483  : iterator_base(other.node)
1484  {
1485  }
1486 
1487 template <class T, class tree_node_allocator>
1489  : iterator_base(other.node)
1490  {
1491  if(this->node==0) {
1492  if(other.range_last()!=0)
1493  this->node=other.range_last();
1494  else
1495  this->node=other.parent_;
1496  this->skip_children();
1497  ++(*this);
1498  }
1499  }
1500 
1501 template <class T, class tree_node_allocator>
1503  {
1504  assert(this->node!=0);
1505  if(!this->skip_current_children_ && this->node->first_child != 0) {
1506  this->node=this->node->first_child;
1507  }
1508  else {
1509  this->skip_current_children_=false;
1510  while(this->node->next_sibling==0) {
1511  this->node=this->node->parent;
1512  if(this->node==0)
1513  return *this;
1514  }
1515  this->node=this->node->next_sibling;
1516  }
1517  return *this;
1518  }
1519 
1520 template <class T, class tree_node_allocator>
1522  {
1523  assert(this->node!=0);
1524  if(this->node->prev_sibling) {
1525  this->node=this->node->prev_sibling;
1526  while(this->node->last_child)
1527  this->node=this->node->last_child;
1528  }
1529  else {
1530  this->node=this->node->parent;
1531  if(this->node==0)
1532  return *this;
1533  }
1534  return *this;
1535 }
1536 
1537 template <class T, class tree_node_allocator>
1539  {
1540  pre_order_iterator copy = *this;
1541  ++(*this);
1542  return copy;
1543  }
1544 
1545 template <class T, class tree_node_allocator>
1547 {
1548  pre_order_iterator copy = *this;
1549  --(*this);
1550  return copy;
1551 }
1552 
1553 template <class T, class tree_node_allocator>
1555  {
1556  while(num>0) {
1557  ++(*this);
1558  --num;
1559  }
1560  return (*this);
1561  }
1562 
1563 template <class T, class tree_node_allocator>
1565  {
1566  while(num>0) {
1567  --(*this);
1568  --num;
1569  }
1570  return (*this);
1571  }
1572 
1573 
1574 
1575 // Post-order iterator
1576 
1577 template <class T, class tree_node_allocator>
1579  : iterator_base(0)
1580  {
1581  }
1582 
1583 template <class T, class tree_node_allocator>
1585  : iterator_base(tn)
1586  {
1587  }
1588 
1589 template <class T, class tree_node_allocator>
1591  : iterator_base(other.node)
1592  {
1593  }
1594 
1595 template <class T, class tree_node_allocator>
1597  : iterator_base(other.node)
1598  {
1599  if(this->node==0) {
1600  if(other.range_last()!=0)
1601  this->node=other.range_last();
1602  else
1603  this->node=other.parent_;
1604  this->skip_children();
1605  ++(*this);
1606  }
1607  }
1608 
1609 template <class T, class tree_node_allocator>
1611  {
1612  assert(this->node!=0);
1613  if(this->node->next_sibling==0)
1614  this->node=this->node->parent;
1615  else {
1616  this->node=this->node->next_sibling;
1617  if(this->skip_current_children_) {
1618  this->skip_current_children_=false;
1619  }
1620  else {
1621  while(this->node->first_child)
1622  this->node=this->node->first_child;
1623  }
1624  }
1625  return *this;
1626  }
1627 
1628 template <class T, class tree_node_allocator>
1630  {
1631  assert(this->node!=0);
1632  if(this->skip_current_children_ || this->node->last_child==0) {
1633  this->skip_current_children_=false;
1634  while(this->node->prev_sibling==0)
1635  this->node=this->node->parent;
1636  this->node=this->node->prev_sibling;
1637  }
1638  else {
1639  this->node=this->node->last_child;
1640  }
1641  return *this;
1642 }
1643 
1644 template <class T, class tree_node_allocator>
1646  {
1647  post_order_iterator copy = *this;
1648  ++(*this);
1649  return copy;
1650  }
1651 
1652 template <class T, class tree_node_allocator>
1654  {
1655  post_order_iterator copy = *this;
1656  --(*this);
1657  return copy;
1658  }
1659 
1660 
1661 template <class T, class tree_node_allocator>
1663  {
1664  while(num>0) {
1665  ++(*this);
1666  --num;
1667  }
1668  return (*this);
1669  }
1670 
1671 template <class T, class tree_node_allocator>
1673  {
1674  while(num>0) {
1675  --(*this);
1676  --num;
1677  }
1678  return (*this);
1679  }
1680 
1681 template <class T, class tree_node_allocator>
1683  {
1684  assert(this->node!=0);
1685  while(this->node->first_child)
1686  this->node=this->node->first_child;
1687  }
1688 
1689 
1690 // Fixed depth iterator
1691 
1692 template <class T, class tree_node_allocator>
1694  : iterator_base()
1695  {
1697  }
1698 
1699 template <class T, class tree_node_allocator>
1701  : iterator_base(tn)
1702  {
1704  }
1705 
1706 template <class T, class tree_node_allocator>
1708  : iterator_base(other.node)
1709  {
1711  }
1712 
1713 template <class T, class tree_node_allocator>
1715  : iterator_base(other.node), first_parent_(other.parent_)
1716  {
1718  }
1719 
1720 template <class T, class tree_node_allocator>
1722  : iterator_base(other.node), first_parent_(other.first_parent_)
1723  {
1724  }
1725 
1726 template <class T, class tree_node_allocator>
1728  {
1729  return; // FIXME: we do not use first_parent_ yet, and it actually needs some serious reworking if
1730  // it is ever to work at the 'head' level.
1731  first_parent_=0;
1732  if(this->node==0) return;
1733  if(this->node->parent!=0)
1734  first_parent_=this->node->parent;
1735  if(first_parent_)
1736  find_leftmost_parent_();
1737  }
1738 
1739 template <class T, class tree_node_allocator>
1741  {
1742  return; // FIXME: see 'set_first_parent()'
1743  tree_node *tmppar=first_parent_;
1744  while(tmppar->prev_sibling) {
1745  tmppar=tmppar->prev_sibling;
1746  if(tmppar->first_child)
1747  first_parent_=tmppar;
1748  }
1749  }
1750 
1751 template <class T, class tree_node_allocator>
1753  {
1754  assert(this->node!=0);
1755  if(this->node->next_sibling!=0) {
1756  this->node=this->node->next_sibling;
1757  assert(this->node!=0);
1758  if(this->node->parent==0 && this->node->next_sibling==0) // feet element
1759  this->node=0;
1760  }
1761  else {
1762  tree_node *par=this->node->parent;
1763  do {
1764  par=par->next_sibling;
1765  if(par==0) { // FIXME: need to keep track of this!
1766  this->node=0;
1767  return *this;
1768  }
1769  } while(par->first_child==0);
1770  this->node=par->first_child;
1771  }
1772  return *this;
1773  }
1774 
1775 template <class T, class tree_node_allocator>
1777  {
1778  assert(this->node!=0);
1779  if(this->node->prev_sibling!=0) {
1780  this->node=this->node->prev_sibling;
1781  assert(this->node!=0);
1782  if(this->node->parent==0 && this->node->prev_sibling==0) // head element
1783  this->node=0;
1784  }
1785  else {
1786  tree_node *par=this->node->parent;
1787  do {
1788  par=par->prev_sibling;
1789  if(par==0) { // FIXME: need to keep track of this!
1790  this->node=0;
1791  return *this;
1792  }
1793  } while(par->last_child==0);
1794  this->node=par->last_child;
1795  }
1796  return *this;
1797 }
1798 
1799 template <class T, class tree_node_allocator>
1801  {
1802  fixed_depth_iterator copy = *this;
1803  ++(*this);
1804  return copy;
1805  }
1806 
1807 template <class T, class tree_node_allocator>
1809 {
1810  fixed_depth_iterator copy = *this;
1811  --(*this);
1812  return copy;
1813 }
1814 
1815 template <class T, class tree_node_allocator>
1817  {
1818  while(num>0) {
1819  --(*this);
1820  --(num);
1821  }
1822  return (*this);
1823  }
1824 
1825 template <class T, class tree_node_allocator>
1827  {
1828  while(num>0) {
1829  ++(*this);
1830  --(num);
1831  }
1832  return *this;
1833  }
1834 
1835 // FIXME: add the other members of fixed_depth_iterator.
1836 
1837 
1838 // Sibling iterator
1839 
1840 template <class T, class tree_node_allocator>
1842  : iterator_base()
1843  {
1844  set_parent_();
1845  }
1846 
1847 template <class T, class tree_node_allocator>
1849  : iterator_base(tn)
1850  {
1851  set_parent_();
1852  }
1853 
1854 template <class T, class tree_node_allocator>
1856  : iterator_base(other.node)
1857  {
1858  set_parent_();
1859  }
1860 
1861 template <class T, class tree_node_allocator>
1863  : iterator_base(other), parent_(other.parent_)
1864  {
1865  }
1866 
1867 template <class T, class tree_node_allocator>
1869  {
1870  parent_=0;
1871  if(this->node==0) return;
1872  if(this->node->parent!=0)
1873  parent_=this->node->parent;
1874  }
1875 
1876 template <class T, class tree_node_allocator>
1878  {
1879  if(this->node)
1880  this->node=this->node->next_sibling;
1881  return *this;
1882  }
1883 
1884 template <class T, class tree_node_allocator>
1886  {
1887  if(this->node) this->node=this->node->prev_sibling;
1888  else {
1889  assert(parent_);
1890  this->node=parent_->last_child;
1891  }
1892  return *this;
1893 }
1894 
1895 template <class T, class tree_node_allocator>
1897  {
1898  sibling_iterator copy = *this;
1899  ++(*this);
1900  return copy;
1901  }
1902 
1903 template <class T, class tree_node_allocator>
1905  {
1906  sibling_iterator copy = *this;
1907  --(*this);
1908  return copy;
1909  }
1910 
1911 template <class T, class tree_node_allocator>
1913  {
1914  while(num>0) {
1915  ++(*this);
1916  --num;
1917  }
1918  return (*this);
1919  }
1920 
1921 template <class T, class tree_node_allocator>
1923  {
1924  while(num>0) {
1925  --(*this);
1926  --num;
1927  }
1928  return (*this);
1929  }
1930 
1931 template <class T, class tree_node_allocator>
1933  {
1934  tree_node *tmp=parent_->first_child;
1935  return tmp;
1936  }
1937 
1938 template <class T, class tree_node_allocator>
1940  {
1941  return parent_->last_child;
1942  }
1943 
1944 
1945 #endif
1946 
1947 // Local variables:
1948 // default-tab-width: 3
1949 // End:
bool operator!=(const _Ht_iterator< _Val, _Nonconst_traits< _Val >, _Key, _HF, _ExK, _EqK, _All > &__x, const _Ht_iterator< _Val, _Const_traits< _Val >, _Key, _HF, _ExK, _EqK, _All > &__y)
Definition: _hashtable.h:173
fixed_depth_iterator & operator--()
fixed_depth_iterator & operator+=(unsigned int)
fixed_depth_iterator & operator++()
fixed_depth_iterator & operator-=(unsigned int)
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_msvc7.hpp:326
bool is_valid() const
Definition: tree_msvc7.hpp:134
sibling_iterator end() const
bool operator!=(const iterator_base &) const
std::bidirectional_iterator_tag iterator_category
Definition: tree_msvc7.hpp:118
bool operator==(const iterator_base &) const
T * operator->() const
T & operator*() const
unsigned int number_of_children() const
sibling_iterator begin() const
ptrdiff_t difference_type
Definition: tree_msvc7.hpp:117
post_order_iterator & operator+=(unsigned int)
post_order_iterator & operator-=(unsigned int)
post_order_iterator & operator++()
post_order_iterator & operator--()
pre_order_iterator & operator++()
pre_order_iterator & operator--()
pre_order_iterator & operator+=(unsigned int)
pre_order_iterator & operator-=(unsigned int)
tree_node * range_first() const
sibling_iterator & operator--()
tree_node * range_last() const
sibling_iterator & operator++()
sibling_iterator & operator+=(unsigned int)
sibling_iterator & operator-=(unsigned int)
tree_node_< T > * next_sibling
Definition: tree_msvc7.hpp:84
tree_node_< T > * parent
Definition: tree_msvc7.hpp:82
tree_node_< T > * last_child
Definition: tree_msvc7.hpp:83
tree_node_< T > * first_child
Definition: tree_msvc7.hpp:83
tree_node_< T > * prev_sibling
Definition: tree_msvc7.hpp:84
post_order_iterator begin_post() const
Definition: tree_msvc7.hpp:585
void erase_children(const iterator_base &)
Definition: tree_msvc7.hpp:528
bool equal_subtree(const iter &one, const iter &two) const
bool equal(const iter &one, const iter &two, const iter &three) const
tree_node * head
Definition: tree_msvc7.hpp:332
sibling_iterator child(const iterator_base &position, unsigned int) const
void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, bool duplicate_leaves=false)
T value_type
Definition: tree_msvc7.hpp:93
pre_order_iterator iterator
Definition: tree_msvc7.hpp:173
iter insert_after(iter position, const T &x)
Definition: tree_msvc7.hpp:814
void copy_(const tree< T, tree_node_allocator > &other)
Definition: tree_msvc7.hpp:499
sibling_iterator previous_sibling(const iterator_base &) const
Definition: tree_msvc7.hpp:662
void sort(sibling_iterator from, sibling_iterator to, bool deep=false)
sibling_iterator next_sibling(const iterator_base &) const
Definition: tree_msvc7.hpp:669
void head_initialise_()
Definition: tree_msvc7.hpp:467
tree_node_< T > tree_node
Definition: tree_msvc7.hpp:92
iter insert_subtree(iter position, const iterator_base &subtree)
Definition: tree_msvc7.hpp:838
tree_node_allocator alloc_
Definition: tree_msvc7.hpp:394
int depth(const iterator_base &) const
iter parent(iter) const
Definition: tree_msvc7.hpp:655
bool is_valid(const iterator_base &) const
post_order_iterator end_post() const
Definition: tree_msvc7.hpp:596
void operator=(const tree< T, tree_node_allocator > &)
Definition: tree_msvc7.hpp:486
iter append_child(iter position)
Definition: tree_msvc7.hpp:680
tree reroot(iterator newRoot)
Definition: tree_msvc7.hpp:341
unsigned int index(sibling_iterator it) const
bool is_in_subtree(const iterator_base &position, const iterator_base &begin, const iterator_base &end) const
void clear()
Definition: tree_msvc7.hpp:520
iter replace(iter position, const T &x)
Definition: tree_msvc7.hpp:858
iter move_after(iter target, iter source)
iter append_children(iter position, sibling_iterator from, sibling_iterator to)
Definition: tree_msvc7.hpp:742
pre_order_iterator begin() const
Definition: tree_msvc7.hpp:573
iter insert(iter position, const T &x)
Definition: tree_msvc7.hpp:762
fixed_depth_iterator begin_fixed(const iterator_base &, unsigned int) const
Definition: tree_msvc7.hpp:602
unsigned int number_of_children(const iterator_base &) const
fixed_depth_iterator end_fixed(const iterator_base &, unsigned int) const
Definition: tree_msvc7.hpp:619
iter move_below(iter target, iter source)
iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
bool empty() const
void swap(sibling_iterator it)
int size() const
pre_order_iterator set_head(const T &x)
Definition: tree_msvc7.hpp:754
iter flatten(iter position)
Definition: tree_msvc7.hpp:973
unsigned int number_of_siblings(const iterator_base &) const
iter erase(iter)
Definition: tree_msvc7.hpp:546
tree subtree(sibling_iterator from, sibling_iterator to) const
pre_order_iterator end() const
Definition: tree_msvc7.hpp:579
iter move_before(iter target, iter source)
static bool is_valid(const char *num, int type, CONV_RESULT *cr)
#define head
Definition: ct_nlmzip_i.h:138
static unsigned char depth[2 *(256+1+29)+1]
#define T(s)
Definition: common.h:230
bool operator==(const CEquivRange &A, const CEquivRange &B)
#define true
Definition: bool.h:35
#define false
Definition: bool.h:36
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:51
static DLIST_TYPE *DLIST_NAME() prev(DLIST_LIST_TYPE *list, DLIST_TYPE *item)
Definition: dlist.tmpl.h:61
static DLIST_TYPE *DLIST_NAME() next(DLIST_LIST_TYPE *list, DLIST_TYPE *item)
Definition: dlist.tmpl.h:56
static char tmp[3200]
Definition: utf8.c:42
meTree * newTree()
Definition: graph.cpp:102
void swap(NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair1, NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair2)
Definition: ncbimisc.hpp:1508
CVect2< NCBI_PROMOTE(int,U) > operator*(int v1, const CVect2< U > &v2)
Definition: globals.hpp:371
#define NCBI_CDUTILS_EXPORT
Definition: ncbi_export.h:376
int i
yy_size_t n
CNcbiMatrix< T > & operator+=(CNcbiMatrix< T > &, const CNcbiMatrix< U > &)
global addition: matrix += matrix
Definition: matrix.hpp:570
CNcbiMatrix< T > & operator-=(CNcbiMatrix< T > &, const CNcbiMatrix< U > &)
global subtraction: matrix -= matrix
Definition: matrix.hpp:622
constexpr auto sort(_Init &&init)
constexpr bool empty(list< Ts... >) noexcept
void destructor(T1 *p)
Definition: tree_msvc7.hpp:72
void constructor(T1 *p, T2 &val)
Definition: tree_msvc7.hpp:60
double value_type
The numeric datatype used by the parser.
Definition: muParserDef.h:228
const struct ncbi::grid::netcache::search::fields::SIZE size
const CharType(& source)[N]
Definition: pointer.h:1149
unsigned int a
Definition: ncbi_localip.c:102
S & operator--(CNetRef< S > &r, int)
void flatten(size_t dimension_, const Int4 *const *scoreMatrix_, const double *const *prob_, size_t *dim_, Int4 **score_, double **p_, size_t dimension2_=0)
void copy(Njn::Matrix< S > *matrix_, const Njn::Matrix< T > &matrix0_)
Definition: njn_matrix.hpp:613
#define assert(x)
Definition: srv_diag.hpp:58
bool operator>(const typename tree< T, tree_node_allocator >::iterator_base &one, const typename tree< T, tree_node_allocator >::iterator_base &two)
Definition: tree_msvc7.hpp:426
Modified on Sun Apr 21 03:39:20 2024 by modify_doxy.py rev. 669887