LibOFX
tree.hh
00001 /*
00002 
00003    $Id: tree.hh,v 1.6 2006-07-20 04:41:16 benoitg Exp $
00004 
00005    STL-like templated tree class.
00006    Copyright (C) 2001-2005  Kasper Peeters <kasper.peeters@aei.mpg.de>.
00007 
00008 */
00009 
00026 /*
00027    This program is free software; you can redistribute it and/or modify
00028    it under the terms of the GNU General Public License as published by
00029    the Free Software Foundation; version 2.
00030 
00031    This program is distributed in the hope that it will be useful,
00032    but WITHOUT ANY WARRANTY; without even the implied warranty of
00033    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00034    GNU General Public License for more details.
00035 
00036    You should have received a copy of the GNU General Public License
00037    along with this program; if not, write to the Free Software
00038    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00039 */
00040 
00058 #ifndef tree_hh_
00059 #define tree_hh_
00060 
00061 #include <cassert>
00062 #include <memory>
00063 #include <stdexcept>
00064 #include <iterator>
00065 #include <set>
00066 
00067 // HP-style construct/destroy have gone from the standard,
00068 // so here is a copy.
00069 
00070 namespace kp
00071 {
00072 
00073 template <class T1, class T2>
00074 void constructor(T1* p, T2& val)
00075 {
00076   new ((void *) p) T1(val);
00077 }
00078 
00079 template <class T1>
00080 void constructor(T1* p)
00081 {
00082   new ((void *) p) T1;
00083 }
00084 
00085 template <class T1>
00086 void destructor(T1* p)
00087 {
00088   p->~T1();
00089 }
00090 
00091 };
00092 
00094 template<class T>
00095 class tree_node_   // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
00096 {
00097 public:
00098   tree_node_<T> *parent;
00099   tree_node_<T> *first_child, *last_child;
00100   tree_node_<T> *prev_sibling, *next_sibling;
00101   T data;
00102 }; // __attribute__((packed));
00103 
00104 template < class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
00105 class tree
00106 {
00107 protected:
00108   typedef tree_node_<T> tree_node;
00109 public:
00111   typedef T value_type;
00112 
00113   class iterator_base;
00114   class pre_order_iterator;
00115   class post_order_iterator;
00116   class sibling_iterator;
00117 
00118   tree();
00119   tree(const T&);
00120   tree(const iterator_base&);
00121   tree(const tree<T, tree_node_allocator>&);
00122   ~tree();
00123   void operator=(const tree<T, tree_node_allocator>&);
00124 
00126 #ifdef __SGI_STL_PORT
00127   class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t>
00128   {
00129 #else
00130   class iterator_base
00131   {
00132 #endif
00133   public:
00134     typedef T                               value_type;
00135     typedef T*                              pointer;
00136     typedef T&                              reference;
00137     typedef size_t                          size_type;
00138     typedef ptrdiff_t                       difference_type;
00139     typedef std::bidirectional_iterator_tag iterator_category;
00140 
00141     iterator_base();
00142     iterator_base(tree_node *);
00143 
00144     T&             operator*() const;
00145     T*             operator->() const;
00146 
00148     void         skip_children();
00150     unsigned int number_of_children() const;
00151 
00152     sibling_iterator begin() const;
00153     sibling_iterator end() const;
00154 
00155     tree_node *node;
00156   protected:
00157     bool skip_current_children_;
00158   };
00159 
00161   class pre_order_iterator : public iterator_base
00162   {
00163   public:
00164     pre_order_iterator();
00165     pre_order_iterator(tree_node *);
00166     pre_order_iterator(const iterator_base&);
00167     pre_order_iterator(const sibling_iterator&);
00168 
00169     bool    operator==(const pre_order_iterator&) const;
00170     bool    operator!=(const pre_order_iterator&) const;
00171     pre_order_iterator&  operator++();
00172     pre_order_iterator&  operator--();
00173     pre_order_iterator   operator++(int);
00174     pre_order_iterator   operator--(int);
00175     pre_order_iterator&  operator+=(unsigned int);
00176     pre_order_iterator&  operator-=(unsigned int);
00177   };
00178 
00180   class post_order_iterator : public iterator_base
00181   {
00182   public:
00183     post_order_iterator();
00184     post_order_iterator(tree_node *);
00185     post_order_iterator(const iterator_base&);
00186     post_order_iterator(const sibling_iterator&);
00187 
00188     bool    operator==(const post_order_iterator&) const;
00189     bool    operator!=(const post_order_iterator&) const;
00190     post_order_iterator&  operator++();
00191     post_order_iterator&  operator--();
00192     post_order_iterator   operator++(int);
00193     post_order_iterator   operator--(int);
00194     post_order_iterator&  operator+=(unsigned int);
00195     post_order_iterator&  operator-=(unsigned int);
00196 
00198     void descend_all();
00199   };
00200 
00202   typedef pre_order_iterator iterator;
00203 
00205   class fixed_depth_iterator : public iterator_base
00206   {
00207   public:
00208     fixed_depth_iterator();
00209     fixed_depth_iterator(tree_node *);
00210     fixed_depth_iterator(const iterator_base&);
00211     fixed_depth_iterator(const sibling_iterator&);
00212     fixed_depth_iterator(const fixed_depth_iterator&);
00213 
00214     bool    operator==(const fixed_depth_iterator&) const;
00215     bool    operator!=(const fixed_depth_iterator&) const;
00216     fixed_depth_iterator&  operator++();
00217     fixed_depth_iterator&  operator--();
00218     fixed_depth_iterator   operator++(int);
00219     fixed_depth_iterator   operator--(int);
00220     fixed_depth_iterator&  operator+=(unsigned int);
00221     fixed_depth_iterator&  operator-=(unsigned int);
00222 
00223     tree_node *first_parent_;
00224   private:
00225     void set_first_parent_();
00226     void find_leftmost_parent_();
00227   };
00228 
00230   class sibling_iterator : public iterator_base
00231   {
00232   public:
00233     sibling_iterator();
00234     sibling_iterator(tree_node *);
00235     sibling_iterator(const sibling_iterator&);
00236     sibling_iterator(const iterator_base&);
00237 
00238     bool    operator==(const sibling_iterator&) const;
00239     bool    operator!=(const sibling_iterator&) const;
00240     sibling_iterator&  operator++();
00241     sibling_iterator&  operator--();
00242     sibling_iterator   operator++(int);
00243     sibling_iterator   operator--(int);
00244     sibling_iterator&  operator+=(unsigned int);
00245     sibling_iterator&  operator-=(unsigned int);
00246 
00247     tree_node *range_first() const;
00248     tree_node *range_last() const;
00249     tree_node *parent_;
00250   private:
00251     void set_parent_();
00252   };
00253 
00255   inline pre_order_iterator   begin() const;
00257   inline pre_order_iterator   end() const;
00259   post_order_iterator  begin_post() const;
00261   post_order_iterator  end_post() const;
00263   fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
00265   fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
00267   sibling_iterator     begin(const iterator_base&) const;
00269   sibling_iterator     end(const iterator_base&) const;
00270 
00272   template<typename iter> iter parent(iter) const;
00274   template<typename iter> iter previous_sibling(iter) const;
00276   template<typename iter> iter next_sibling(iter) const;
00278   template<typename iter> iter next_at_same_depth(iter) const;
00279 
00281   void     clear();
00283   template<typename iter> iter erase(iter);
00285   void     erase_children(const iterator_base&);
00286 
00288   template<typename iter> iter append_child(iter position);
00290   template<typename iter> iter append_child(iter position, const T& x);
00292   template<typename iter> iter append_child(iter position, iter other_position);
00294   template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
00295 
00297   pre_order_iterator set_head(const T& x);
00299   template<typename iter> iter insert(iter position, const T& x);
00301   sibling_iterator insert(sibling_iterator position, const T& x);
00303   template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
00305   template<typename iter> iter insert_after(iter position, const T& x);
00306 
00308   template<typename iter> iter replace(iter position, const T& x);
00310   template<typename iter> iter replace(iter position, const iterator_base& from);
00312   sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
00313                            sibling_iterator new_begin,  sibling_iterator new_end);
00314 
00316   template<typename iter> iter flatten(iter position);
00318   template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
00320   template<typename iter> iter reparent(iter position, iter from);
00321 
00323   template<typename iter> iter move_after(iter target, iter source);
00325   template<typename iter> iter move_before(iter target, iter source);
00327   template<typename iter> iter move_ontop(iter target, iter source);
00328 
00330   void     merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
00331                  bool duplicate_leaves = false);
00333   void     sort(sibling_iterator from, sibling_iterator to, bool deep = false);
00334   template<class StrictWeakOrdering>
00335   void     sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep = false);
00337   template<typename iter>
00338   bool     equal(const iter& one, const iter& two, const iter& three) const;
00339   template<typename iter, class BinaryPredicate>
00340   bool     equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
00341   template<typename iter>
00342   bool     equal_subtree(const iter& one, const iter& two) const;
00343   template<typename iter, class BinaryPredicate>
00344   bool     equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
00346   tree     subtree(sibling_iterator from, sibling_iterator to) const;
00347   void     subtree(tree&, sibling_iterator from, sibling_iterator to) const;
00349   void     swap(sibling_iterator it);
00350 
00352   int      size() const;
00354   bool     empty() const;
00356   int      depth(const iterator_base&) const;
00358   unsigned int number_of_children(const iterator_base&) const;
00360   unsigned int number_of_siblings(const iterator_base&) const;
00362   bool     is_in_subtree(const iterator_base& position, const iterator_base& begin,
00363                          const iterator_base& end) const;
00365   bool     is_valid(const iterator_base&) const;
00366 
00368   unsigned int index(sibling_iterator it) const;
00370   sibling_iterator  child(const iterator_base& position, unsigned int) const;
00371 
00373   class iterator_base_less
00374   {
00375   public:
00376     bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
00377                     const typename tree<T, tree_node_allocator>::iterator_base& two) const
00378     {
00379       return one.node < two.node;
00380     }
00381   };
00382   tree_node *head, *feet;    // head/feet are always dummy; if an iterator points to them it is invalid
00383 private:
00384   tree_node_allocator alloc_;
00385   void head_initialise_();
00386   void copy_(const tree<T, tree_node_allocator>& other);
00387 
00389   template<class StrictWeakOrdering>
00390   class compare_nodes
00391   {
00392   public:
00393     compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
00394 
00395     bool operator()(const tree_node *a, const tree_node *b)
00396     {
00397       static StrictWeakOrdering comp;
00398       return comp(a->data, b->data);
00399     }
00400   private:
00401     StrictWeakOrdering comp_;
00402   };
00403 };
00404 
00405 //template <class T, class tree_node_allocator>
00406 //class iterator_base_less {
00407 // public:
00408 //    bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
00409 //                  const typename tree<T, tree_node_allocator>::iterator_base& two) const
00410 //       {
00411 //       txtout << "operatorclass<" << one.node < two.node << std::endl;
00412 //       return one.node < two.node;
00413 //       }
00414 //};
00415 
00416 //template <class T, class tree_node_allocator>
00417 //bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
00418 //             const typename tree<T, tree_node_allocator>::iterator& two)
00419 // {
00420 // txtout << "operator< " << one.node < two.node << std::endl;
00421 // if(one.node < two.node) return true;
00422 // return false;
00423 // }
00424 
00425 template <class T, class tree_node_allocator>
00426 bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
00427                const typename tree<T, tree_node_allocator>::iterator_base& two)
00428 {
00429   if (one.node > two.node) return true;
00430   return false;
00431 }
00432 
00433 
00434 
00435 // Tree
00436 
00437 template <class T, class tree_node_allocator>
00438 tree<T, tree_node_allocator>::tree()
00439 {
00440   head_initialise_();
00441 }
00442 
00443 template <class T, class tree_node_allocator>
00444 tree<T, tree_node_allocator>::tree(const T& x)
00445 {
00446   head_initialise_();
00447   set_head(x);
00448 }
00449 
00450 template <class T, class tree_node_allocator>
00451 tree<T, tree_node_allocator>::tree(const iterator_base& other)
00452 {
00453   head_initialise_();
00454   set_head((*other));
00455   replace(begin(), other);
00456 }
00457 
00458 template <class T, class tree_node_allocator>
00459 tree<T, tree_node_allocator>::~tree()
00460 {
00461   clear();
00462   alloc_.deallocate(head, 1);
00463   alloc_.deallocate(feet, 1);
00464 }
00465 
00466 template <class T, class tree_node_allocator>
00467 void tree<T, tree_node_allocator>::head_initialise_()
00468 {
00469   head = alloc_.allocate(1, 0); // MSVC does not have default second argument
00470   feet = alloc_.allocate(1, 0);
00471 
00472   head->parent = 0;
00473   head->first_child = 0;
00474   head->last_child = 0;
00475   head->prev_sibling = 0; //head;
00476   head->next_sibling = feet; //head;
00477 
00478   feet->parent = 0;
00479   feet->first_child = 0;
00480   feet->last_child = 0;
00481   feet->prev_sibling = head;
00482   feet->next_sibling = 0;
00483 }
00484 
00485 template <class T, class tree_node_allocator>
00486 void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
00487 {
00488   copy_(other);
00489 }
00490 
00491 template <class T, class tree_node_allocator>
00492 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
00493 {
00494   head_initialise_();
00495   copy_(other);
00496 }
00497 
00498 template <class T, class tree_node_allocator>
00499 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)
00500 {
00501   clear();
00502   pre_order_iterator it = other.begin(), to = begin();
00503   while (it != other.end())
00504   {
00505     to = insert(to, (*it));
00506     it.skip_children();
00507     ++it;
00508   }
00509   to = begin();
00510   it = other.begin();
00511   while (it != other.end())
00512   {
00513     to = replace(to, it);
00514     to.skip_children();
00515     it.skip_children();
00516     ++to;
00517     ++it;
00518   }
00519 }
00520 
00521 template <class T, class tree_node_allocator>
00522 void tree<T, tree_node_allocator>::clear()
00523 {
00524   if (head)
00525     while (head->next_sibling != feet)
00526       erase(pre_order_iterator(head->next_sibling));
00527 }
00528 
00529 template<class T, class tree_node_allocator>
00530 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
00531 {
00532   tree_node *cur = it.node->first_child;
00533   tree_node *prev = 0;
00534 
00535   while (cur != 0)
00536   {
00537     prev = cur;
00538     cur = cur->next_sibling;
00539     erase_children(pre_order_iterator(prev));
00540     kp::destructor(&prev->data);
00541     alloc_.deallocate(prev, 1);
00542   }
00543   it.node->first_child = 0;
00544   it.node->last_child = 0;
00545 }
00546 
00547 template<class T, class tree_node_allocator>
00548 template<class iter>
00549 iter tree<T, tree_node_allocator>::erase(iter it)
00550 {
00551   tree_node *cur = it.node;
00552   assert(cur != head);
00553   iter ret = it;
00554   ret.skip_children();
00555   ++ret;
00556   erase_children(it);
00557   if (cur->prev_sibling == 0)
00558   {
00559     cur->parent->first_child = cur->next_sibling;
00560   }
00561   else
00562   {
00563     cur->prev_sibling->next_sibling = cur->next_sibling;
00564   }
00565   if (cur->next_sibling == 0)
00566   {
00567     cur->parent->last_child = cur->prev_sibling;
00568   }
00569   else
00570   {
00571     cur->next_sibling->prev_sibling = cur->prev_sibling;
00572   }
00573 
00574   kp::destructor(&cur->data);
00575   alloc_.deallocate(cur, 1);
00576   return ret;
00577 }
00578 
00579 template <class T, class tree_node_allocator>
00580 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const
00581 {
00582   return pre_order_iterator(head->next_sibling);
00583 }
00584 
00585 template <class T, class tree_node_allocator>
00586 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const
00587 {
00588   return pre_order_iterator(feet);
00589 }
00590 
00591 template <class T, class tree_node_allocator>
00592 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const
00593 {
00594   tree_node *tmp = head->next_sibling;
00595   if (tmp != feet)
00596   {
00597     while (tmp->first_child)
00598       tmp = tmp->first_child;
00599   }
00600   return post_order_iterator(tmp);
00601 }
00602 
00603 template <class T, class tree_node_allocator>
00604 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const
00605 {
00606   return post_order_iterator(feet);
00607 }
00608 
00609 template <class T, class tree_node_allocator>
00610 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const
00611 {
00612   tree_node *tmp = pos.node;
00613   unsigned int curdepth = 0;
00614   while (curdepth < dp)   // go down one level
00615   {
00616     while (tmp->first_child == 0)
00617     {
00618       tmp = tmp->next_sibling;
00619       if (tmp == 0)
00620         throw std::range_error("tree: begin_fixed out of range");
00621     }
00622     tmp = tmp->first_child;
00623     ++curdepth;
00624   }
00625   return tmp;
00626 }
00627 
00628 template <class T, class tree_node_allocator>
00629 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
00630 {
00631   assert(1 == 0); // FIXME: not correct yet
00632   tree_node *tmp = pos.node;
00633   unsigned int curdepth = 1;
00634   while (curdepth < dp)   // go down one level
00635   {
00636     while (tmp->first_child == 0)
00637     {
00638       tmp = tmp->next_sibling;
00639       if (tmp == 0)
00640         throw std::range_error("tree: end_fixed out of range");
00641     }
00642     tmp = tmp->first_child;
00643     ++curdepth;
00644   }
00645   return tmp;
00646 }
00647 
00648 template <class T, class tree_node_allocator>
00649 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const
00650 {
00651   if (pos.node->first_child == 0)
00652   {
00653     return end(pos);
00654   }
00655   return pos.node->first_child;
00656 }
00657 
00658 template <class T, class tree_node_allocator>
00659 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const
00660 {
00661   sibling_iterator ret(0);
00662   ret.parent_ = pos.node;
00663   return ret;
00664 }
00665 
00666 template <class T, class tree_node_allocator>
00667 template <typename iter>
00668 iter tree<T, tree_node_allocator>::parent(iter position) const
00669 {
00670   assert(position.node != 0);
00671   return iter(position.node->parent);
00672 }
00673 
00674 template <class T, class tree_node_allocator>
00675 template <typename iter>
00676 iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
00677 {
00678   assert(position.node != 0);
00679   iter ret(position);
00680   ret.node = position.node->prev_sibling;
00681   return ret;
00682 }
00683 
00684 template <class T, class tree_node_allocator>
00685 template <typename iter>
00686 iter tree<T, tree_node_allocator>::next_sibling(iter position) const
00687 {
00688   assert(position.node != 0);
00689   iter ret(position);
00690   ret.node = position.node->next_sibling;
00691   return ret;
00692 }
00693 
00694 template <class T, class tree_node_allocator>
00695 template <typename iter>
00696 iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
00697 {
00698   assert(position.node != 0);
00699   iter ret(position);
00700 
00701   if (position.node->next_sibling)
00702   {
00703     ret.node = position.node->next_sibling;
00704   }
00705   else
00706   {
00707     int relative_depth = 0;
00708 upper:
00709     do
00710     {
00711       ret.node = ret.node->parent;
00712       if (ret.node == 0) return ret;
00713       --relative_depth;
00714     }
00715     while (ret.node->next_sibling == 0);
00716 lower:
00717     ret.node = ret.node->next_sibling;
00718     while (ret.node->first_child == 0)
00719     {
00720       if (ret.node->next_sibling == 0)
00721         goto upper;
00722       ret.node = ret.node->next_sibling;
00723       if (ret.node == 0) return ret;
00724     }
00725     while (relative_depth < 0 && ret.node->first_child != 0)
00726     {
00727       ret.node = ret.node->first_child;
00728       ++relative_depth;
00729     }
00730     if (relative_depth < 0)
00731     {
00732       if (ret.node->next_sibling == 0) goto upper;
00733       else                          goto lower;
00734     }
00735   }
00736   return ret;
00737 }
00738 
00739 template <class T, class tree_node_allocator>
00740 template <typename iter>
00741 iter tree<T, tree_node_allocator>::append_child(iter position)
00742 {
00743   assert(position.node != head);
00744 
00745   tree_node* tmp = alloc_.allocate(1, 0);
00746   kp::constructor(&tmp->data);
00747   tmp->first_child = 0;
00748   tmp->last_child = 0;
00749 
00750   tmp->parent = position.node;
00751   if (position.node->last_child != 0)
00752   {
00753     position.node->last_child->next_sibling = tmp;
00754   }
00755   else
00756   {
00757     position.node->first_child = tmp;
00758   }
00759   tmp->prev_sibling = position.node->last_child;
00760   position.node->last_child = tmp;
00761   tmp->next_sibling = 0;
00762   return tmp;
00763 }
00764 
00765 template <class T, class tree_node_allocator>
00766 template <class iter>
00767 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
00768 {
00769   // If your program fails here you probably used 'append_child' to add the top
00770   // node to an empty tree. From version 1.45 the top element should be added
00771   // using 'insert'. See the documentation for further information, and sorry about
00772   // the API change.
00773   assert(position.node != head);
00774 
00775   tree_node* tmp = alloc_.allocate(1, 0);
00776   kp::constructor(&tmp->data, x);
00777   tmp->first_child = 0;
00778   tmp->last_child = 0;
00779 
00780   tmp->parent = position.node;
00781   if (position.node->last_child != 0)
00782   {
00783     position.node->last_child->next_sibling = tmp;
00784   }
00785   else
00786   {
00787     position.node->first_child = tmp;
00788   }
00789   tmp->prev_sibling = position.node->last_child;
00790   position.node->last_child = tmp;
00791   tmp->next_sibling = 0;
00792   return tmp;
00793 }
00794 
00795 template <class T, class tree_node_allocator>
00796 template <class iter>
00797 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
00798 {
00799   assert(position.node != head);
00800 
00801   sibling_iterator aargh = append_child(position, value_type());
00802   return replace(aargh, other);
00803 }
00804 
00805 template <class T, class tree_node_allocator>
00806 template <class iter>
00807 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
00808 {
00809   iter ret = from;
00810 
00811   while (from != to)
00812   {
00813     insert_subtree(position.end(), from);
00814     ++from;
00815   }
00816   return ret;
00817 }
00818 
00819 template <class T, class tree_node_allocator>
00820 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)
00821 {
00822   assert(head->next_sibling == feet);
00823   return insert(iterator(feet), x);
00824 }
00825 
00826 template <class T, class tree_node_allocator>
00827 template <class iter>
00828 iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
00829 {
00830   if (position.node == 0)
00831   {
00832     position.node = feet; // Backward compatibility: when calling insert on a null node,
00833     // insert before the feet.
00834   }
00835   tree_node* tmp = alloc_.allocate(1, 0);
00836   kp::constructor(&tmp->data, x);
00837   tmp->first_child = 0;
00838   tmp->last_child = 0;
00839 
00840   tmp->parent = position.node->parent;
00841   tmp->next_sibling = position.node;
00842   tmp->prev_sibling = position.node->prev_sibling;
00843   position.node->prev_sibling = tmp;
00844 
00845   if (tmp->prev_sibling == 0)
00846   {
00847     if (tmp->parent) // when inserting nodes at the head, there is no parent
00848       tmp->parent->first_child = tmp;
00849   }
00850   else
00851     tmp->prev_sibling->next_sibling = tmp;
00852   return tmp;
00853 }
00854 
00855 template <class T, class tree_node_allocator>
00856 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
00857 {
00858   tree_node* tmp = alloc_.allocate(1, 0);
00859   kp::constructor(&tmp->data, x);
00860   tmp->first_child = 0;
00861   tmp->last_child = 0;
00862 
00863   tmp->next_sibling = position.node;
00864   if (position.node == 0)   // iterator points to end of a subtree
00865   {
00866     tmp->parent = position.parent_;
00867     tmp->prev_sibling = position.range_last();
00868     tmp->parent->last_child = tmp;
00869   }
00870   else
00871   {
00872     tmp->parent = position.node->parent;
00873     tmp->prev_sibling = position.node->prev_sibling;
00874     position.node->prev_sibling = tmp;
00875   }
00876 
00877   if (tmp->prev_sibling == 0)
00878   {
00879     if (tmp->parent) // when inserting nodes at the head, there is no parent
00880       tmp->parent->first_child = tmp;
00881   }
00882   else
00883     tmp->prev_sibling->next_sibling = tmp;
00884   return tmp;
00885 }
00886 
00887 template <class T, class tree_node_allocator>
00888 template <class iter>
00889 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
00890 {
00891   tree_node* tmp = alloc_.allocate(1, 0);
00892   kp::constructor(&tmp->data, x);
00893   tmp->first_child = 0;
00894   tmp->last_child = 0;
00895 
00896   tmp->parent = position.node->parent;
00897   tmp->prev_sibling = position.node;
00898   tmp->next_sibling = position.node->next_sibling;
00899   position.node->next_sibling = tmp;
00900 
00901   if (tmp->next_sibling == 0)
00902   {
00903     if (tmp->parent) // when inserting nodes at the head, there is no parent
00904       tmp->parent->last_child = tmp;
00905   }
00906   else
00907   {
00908     tmp->next_sibling->prev_sibling = tmp;
00909   }
00910   return tmp;
00911 }
00912 
00913 template <class T, class tree_node_allocator>
00914 template <class iter>
00915 iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
00916 {
00917   // insert dummy
00918   iter it = insert(position, value_type());
00919   // replace dummy with subtree
00920   return replace(it, subtree);
00921 }
00922 
00923 // template <class T, class tree_node_allocator>
00924 // template <class iter>
00925 // iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
00926 //    {
00927 //    // insert dummy
00928 //    iter it(insert(position, value_type()));
00929 //    // replace dummy with subtree
00930 //    return replace(it, subtree);
00931 //    }
00932 
00933 template <class T, class tree_node_allocator>
00934 template <class iter>
00935 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
00936 {
00937   kp::destructor(&position.node->data);
00938   kp::constructor(&position.node->data, x);
00939   return position;
00940 }
00941 
00942 template <class T, class tree_node_allocator>
00943 template <class iter>
00944 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
00945 {
00946   assert(position.node != head);
00947   tree_node *current_from = from.node;
00948   tree_node *start_from = from.node;
00949   tree_node *current_to  = position.node;
00950 
00951   // replace the node at position with head of the replacement tree at from
00952   erase_children(position);
00953   tree_node* tmp = alloc_.allocate(1, 0);
00954   kp::constructor(&tmp->data, (*from));
00955   tmp->first_child = 0;
00956   tmp->last_child = 0;
00957   if (current_to->prev_sibling == 0)
00958   {
00959     current_to->parent->first_child = tmp;
00960   }
00961   else
00962   {
00963     current_to->prev_sibling->next_sibling = tmp;
00964   }
00965   tmp->prev_sibling = current_to->prev_sibling;
00966   if (current_to->next_sibling == 0)
00967   {
00968     current_to->parent->last_child = tmp;
00969   }
00970   else
00971   {
00972     current_to->next_sibling->prev_sibling = tmp;
00973   }
00974   tmp->next_sibling = current_to->next_sibling;
00975   tmp->parent = current_to->parent;
00976   kp::destructor(&current_to->data);
00977   alloc_.deallocate(current_to, 1);
00978   current_to = tmp;
00979 
00980   // only at this stage can we fix 'last'
00981   tree_node *last = from.node->next_sibling;
00982 
00983   pre_order_iterator toit = tmp;
00984   // copy all children
00985   do
00986   {
00987     assert(current_from != 0);
00988     if (current_from->first_child != 0)
00989     {
00990       current_from = current_from->first_child;
00991       toit = append_child(toit, current_from->data);
00992     }
00993     else
00994     {
00995       while (current_from->next_sibling == 0 && current_from != start_from)
00996       {
00997         current_from = current_from->parent;
00998         toit = parent(toit);
00999         assert(current_from != 0);
01000       }
01001       current_from = current_from->next_sibling;
01002       if (current_from != last)
01003       {
01004         toit = append_child(parent(toit), current_from->data);
01005       }
01006     }
01007   }
01008   while (current_from != last);
01009 
01010   return current_to;
01011 }
01012 
01013 template <class T, class tree_node_allocator>
01014 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
01015   sibling_iterator orig_begin,
01016   sibling_iterator orig_end,
01017   sibling_iterator new_begin,
01018   sibling_iterator new_end)
01019 {
01020   tree_node *orig_first = orig_begin.node;
01021   tree_node *new_first = new_begin.node;
01022   tree_node *orig_last = orig_first;
01023   while ((++orig_begin) != orig_end)
01024     orig_last = orig_last->next_sibling;
01025   tree_node *new_last = new_first;
01026   while ((++new_begin) != new_end)
01027     new_last = new_last->next_sibling;
01028 
01029   // insert all siblings in new_first..new_last before orig_first
01030   bool first = true;
01031   pre_order_iterator ret;
01032   while (1 == 1)
01033   {
01034     pre_order_iterator tt = insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
01035     if (first)
01036     {
01037       ret = tt;
01038       first = false;
01039     }
01040     if (new_first == new_last)
01041       break;
01042     new_first = new_first->next_sibling;
01043   }
01044 
01045   // erase old range of siblings
01046   bool last = false;
01047   tree_node *next = orig_first;
01048   while (1 == 1)
01049   {
01050     if (next == orig_last)
01051       last = true;
01052     next = next->next_sibling;
01053     erase((pre_order_iterator)orig_first);
01054     if (last)
01055       break;
01056     orig_first = next;
01057   }
01058   return ret;
01059 }
01060 
01061 template <class T, class tree_node_allocator>
01062 template <typename iter>
01063 iter tree<T, tree_node_allocator>::flatten(iter position)
01064 {
01065   if (position.node->first_child == 0)
01066     return position;
01067 
01068   tree_node *tmp = position.node->first_child;
01069   while (tmp)
01070   {
01071     tmp->parent = position.node->parent;
01072     tmp = tmp->next_sibling;
01073   }
01074   if (position.node->next_sibling)
01075   {
01076     position.node->last_child->next_sibling = position.node->next_sibling;
01077     position.node->next_sibling->prev_sibling = position.node->last_child;
01078   }
01079   else
01080   {
01081     position.node->parent->last_child = position.node->last_child;
01082   }
01083   position.node->next_sibling = position.node->first_child;
01084   position.node->next_sibling->prev_sibling = position.node;
01085   position.node->first_child = 0;
01086   position.node->last_child = 0;
01087 
01088   return position;
01089 }
01090 
01091 
01092 template <class T, class tree_node_allocator>
01093 template <typename iter>
01094 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
01095 {
01096   tree_node *first = begin.node;
01097   tree_node *last = first;
01098   if (begin == end) return begin;
01099   // determine last node
01100   while ((++begin) != end)
01101   {
01102     last = last->next_sibling;
01103   }
01104   // move subtree
01105   if (first->prev_sibling == 0)
01106   {
01107     first->parent->first_child = last->next_sibling;
01108   }
01109   else
01110   {
01111     first->prev_sibling->next_sibling = last->next_sibling;
01112   }
01113   if (last->next_sibling == 0)
01114   {
01115     last->parent->last_child = first->prev_sibling;
01116   }
01117   else
01118   {
01119     last->next_sibling->prev_sibling = first->prev_sibling;
01120   }
01121   if (position.node->first_child == 0)
01122   {
01123     position.node->first_child = first;
01124     position.node->last_child = last;
01125     first->prev_sibling = 0;
01126   }
01127   else
01128   {
01129     position.node->last_child->next_sibling = first;
01130     first->prev_sibling = position.node->last_child;
01131     position.node->last_child = last;
01132   }
01133   last->next_sibling = 0;
01134 
01135   tree_node *pos = first;
01136   while (1 == 1)
01137   {
01138     pos->parent = position.node;
01139     if (pos == last) break;
01140     pos = pos->next_sibling;
01141   }
01142 
01143   return first;
01144 }
01145 
01146 template <class T, class tree_node_allocator>
01147 template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
01148 {
01149   if (from.node->first_child == 0) return position;
01150   return reparent(position, from.node->first_child, end(from));
01151 }
01152 
01153 template <class T, class tree_node_allocator>
01154 template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
01155 {
01156   tree_node *dst = target.node;
01157   tree_node *src = source.node;
01158   assert(dst);
01159   assert(src);
01160 
01161   if (dst == src) return source;
01162 
01163   // take src out of the tree
01164   if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
01165   else                     src->parent->first_child = src->next_sibling;
01166   if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
01167   else                     src->parent->last_child = src->prev_sibling;
01168 
01169   // connect it to the new point
01170   if (dst->next_sibling != 0) dst->next_sibling->prev_sibling = src;
01171   else                     dst->parent->last_child = src;
01172   src->next_sibling = dst->next_sibling;
01173   dst->next_sibling = src;
01174   src->prev_sibling = dst;
01175   src->parent = dst->parent;
01176   return src;
01177 }
01178 
01179 
01180 template <class T, class tree_node_allocator>
01181 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
01182 {
01183   tree_node *dst = target.node;
01184   tree_node *src = source.node;
01185   assert(dst);
01186   assert(src);
01187 
01188   if (dst == src) return source;
01189 
01190   // take src out of the tree
01191   if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
01192   else                     src->parent->first_child = src->next_sibling;
01193   if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
01194   else                     src->parent->last_child = src->prev_sibling;
01195 
01196   // connect it to the new point
01197   if (dst->prev_sibling != 0) dst->prev_sibling->next_sibling = src;
01198   else                     dst->parent->first_child = src;
01199   src->prev_sibling = dst->prev_sibling;
01200   dst->prev_sibling = src;
01201   src->next_sibling = dst;
01202   src->parent = dst->parent;
01203   return src;
01204 }
01205 
01206 template <class T, class tree_node_allocator>
01207 template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
01208 {
01209   tree_node *dst = target.node;
01210   tree_node *src = source.node;
01211   assert(dst);
01212   assert(src);
01213 
01214   if (dst == src) return source;
01215 
01216   // remember connection points
01217   tree_node *b_prev_sibling = dst->prev_sibling;
01218   tree_node *b_next_sibling = dst->next_sibling;
01219   tree_node *b_parent = dst->parent;
01220 
01221   // remove target
01222   erase(target);
01223 
01224   // take src out of the tree
01225   if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
01226   else                     src->parent->first_child = src->next_sibling;
01227   if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
01228   else                     src->parent->last_child = src->prev_sibling;
01229 
01230   // connect it to the new point
01231   if (b_prev_sibling != 0) b_prev_sibling->next_sibling = src;
01232   else                  b_parent->first_child = src;
01233   if (b_next_sibling != 0) b_next_sibling->prev_sibling = src;
01234   else                  b_parent->last_child = src;
01235   src->prev_sibling = b_prev_sibling;
01236   src->next_sibling = b_next_sibling;
01237   src->parent = b_parent;
01238   return src;
01239 }
01240 
01241 template <class T, class tree_node_allocator>
01242 void tree<T, tree_node_allocator>::merge(sibling_iterator to1,   sibling_iterator to2,
01243     sibling_iterator from1, sibling_iterator from2,
01244     bool duplicate_leaves)
01245 {
01246   sibling_iterator fnd;
01247   while (from1 != from2)
01248   {
01249     if ((fnd = std::find(to1, to2, (*from1))) != to2)   // element found
01250     {
01251       if (from1.begin() == from1.end())   // full depth reached
01252       {
01253         if (duplicate_leaves)
01254           append_child(parent(to1), (*from1));
01255       }
01256       else     // descend further
01257       {
01258         merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
01259       }
01260     }
01261     else     // element missing
01262     {
01263       insert_subtree(to2, from1);
01264     }
01265     ++from1;
01266   }
01267 }
01268 
01269 
01270 template <class T, class tree_node_allocator>
01271 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
01272 {
01273   std::less<T> comp;
01274   sort(from, to, comp, deep);
01275 }
01276 
01277 template <class T, class tree_node_allocator>
01278 template <class StrictWeakOrdering>
01279 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
01280                                         StrictWeakOrdering comp, bool deep)
01281 {
01282   if (from == to) return;
01283   // make list of sorted nodes
01284   // CHECK: if multiset stores equivalent nodes in the order in which they
01285   // are inserted, then this routine should be called 'stable_sort'.
01286   std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
01287   sibling_iterator it = from, it2 = to;
01288   while (it != to)
01289   {
01290     nodes.insert(it.node);
01291     ++it;
01292   }
01293   // reassemble
01294   --it2;
01295 
01296   // prev and next are the nodes before and after the sorted range
01297   tree_node *prev = from.node->prev_sibling;
01298   tree_node *next = it2.node->next_sibling;
01299   typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit = nodes.begin(), eit = nodes.end();
01300   if (prev == 0)
01301   {
01302     if ((*nit)->parent != 0) // to catch "sorting the head" situations, when there is no parent
01303       (*nit)->parent->first_child = (*nit);
01304   }
01305   else prev->next_sibling = (*nit);
01306 
01307   --eit;
01308   while (nit != eit)
01309   {
01310     (*nit)->prev_sibling = prev;
01311     if (prev)
01312       prev->next_sibling = (*nit);
01313     prev = (*nit);
01314     ++nit;
01315   }
01316   // prev now points to the last-but-one node in the sorted range
01317   if (prev)
01318     prev->next_sibling = (*eit);
01319 
01320   // eit points to the last node in the sorted range.
01321   (*eit)->next_sibling = next;
01322   (*eit)->prev_sibling = prev; // missed in the loop above
01323   if (next == 0)
01324   {
01325     if ((*eit)->parent != 0) // to catch "sorting the head" situations, when there is no parent
01326       (*eit)->parent->last_child = (*eit);
01327   }
01328   else next->prev_sibling = (*eit);
01329 
01330   if (deep)   // sort the children of each node too
01331   {
01332     sibling_iterator bcs(*nodes.begin());
01333     sibling_iterator ecs(*eit);
01334     ++ecs;
01335     while (bcs != ecs)
01336     {
01337       sort(begin(bcs), end(bcs), comp, deep);
01338       ++bcs;
01339     }
01340   }
01341 }
01342 
01343 template <class T, class tree_node_allocator>
01344 template <typename iter>
01345 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
01346 {
01347   std::equal_to<T> comp;
01348   return equal(one_, two, three_, comp);
01349 }
01350 
01351 template <class T, class tree_node_allocator>
01352 template <typename iter>
01353 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
01354 {
01355   std::equal_to<T> comp;
01356   return equal_subtree(one_, two_, comp);
01357 }
01358 
01359 template <class T, class tree_node_allocator>
01360 template <typename iter, class BinaryPredicate>
01361 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
01362 {
01363   pre_order_iterator one(one_), three(three_);
01364 
01365 // if(one==two && is_valid(three) && three.number_of_children()!=0)
01366 //    return false;
01367   while (one != two && is_valid(three))
01368   {
01369     if (!fun(*one, *three))
01370       return false;
01371     if (one.number_of_children() != three.number_of_children())
01372       return false;
01373     ++one;
01374     ++three;
01375   }
01376   return true;
01377 }
01378 
01379 template <class T, class tree_node_allocator>
01380 template <typename iter, class BinaryPredicate>
01381 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
01382 {
01383   pre_order_iterator one(one_), two(two_);
01384 
01385   if (!fun(*one, *two)) return false;
01386   if (number_of_children(one) != number_of_children(two)) return false;
01387   return equal(begin(one), end(one), begin(two), fun);
01388 }
01389 
01390 template <class T, class tree_node_allocator>
01391 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
01392 {
01393   tree tmp;
01394   tmp.set_head(value_type());
01395   tmp.replace(tmp.begin(), tmp.end(), from, to);
01396   return tmp;
01397 }
01398 
01399 template <class T, class tree_node_allocator>
01400 void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
01401 {
01402   tmp.set_head(value_type());
01403   tmp.replace(tmp.begin(), tmp.end(), from, to);
01404 }
01405 
01406 template <class T, class tree_node_allocator>
01407 int tree<T, tree_node_allocator>::size() const
01408 {
01409   int i = 0;
01410   pre_order_iterator it = begin(), eit = end();
01411   while (it != eit)
01412   {
01413     ++i;
01414     ++it;
01415   }
01416   return i;
01417 }
01418 
01419 template <class T, class tree_node_allocator>
01420 bool tree<T, tree_node_allocator>::empty() const
01421 {
01422   pre_order_iterator it = begin(), eit = end();
01423   return (it == eit);
01424 }
01425 
01426 template <class T, class tree_node_allocator>
01427 int tree<T, tree_node_allocator>::depth(const iterator_base& it) const
01428 {
01429   tree_node* pos = it.node;
01430   assert(pos != 0);
01431   int ret = 0;
01432   while (pos->parent != 0)
01433   {
01434     pos = pos->parent;
01435     ++ret;
01436   }
01437   return ret;
01438 }
01439 
01440 template <class T, class tree_node_allocator>
01441 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it) const
01442 {
01443   tree_node *pos = it.node->first_child;
01444   if (pos == 0) return 0;
01445 
01446   unsigned int ret = 1;
01447 //   while(pos!=it.node->last_child) {
01448 //      ++ret;
01449 //      pos=pos->next_sibling;
01450 //      }
01451   while ((pos = pos->next_sibling))
01452     ++ret;
01453   return ret;
01454 }
01455 
01456 template <class T, class tree_node_allocator>
01457 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
01458 {
01459   tree_node *pos = it.node;
01460   unsigned int ret = 0;
01461   while (pos->next_sibling &&
01462          pos->next_sibling != head &&
01463          pos->next_sibling != feet)
01464   {
01465     ++ret;
01466     pos = pos->next_sibling;
01467   }
01468   return ret;
01469 }
01470 
01471 template <class T, class tree_node_allocator>
01472 void tree<T, tree_node_allocator>::swap(sibling_iterator it)
01473 {
01474   tree_node *nxt = it.node->next_sibling;
01475   if (nxt)
01476   {
01477     if (it.node->prev_sibling)
01478       it.node->prev_sibling->next_sibling = nxt;
01479     else
01480       it.node->parent->first_child = nxt;
01481     nxt->prev_sibling = it.node->prev_sibling;
01482     tree_node *nxtnxt = nxt->next_sibling;
01483     if (nxtnxt)
01484       nxtnxt->prev_sibling = it.node;
01485     else
01486       it.node->parent->last_child = it.node;
01487     nxt->next_sibling = it.node;
01488     it.node->prev_sibling = nxt;
01489     it.node->next_sibling = nxtnxt;
01490   }
01491 }
01492 
01493 // template <class BinaryPredicate>
01494 // tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
01495 //    sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
01496 //    BinaryPredicate fun) const
01497 //    {
01498 //    assert(1==0); // this routine is not finished yet.
01499 //    while(from!=to) {
01500 //       if(fun(*subfrom, *from)) {
01501 //
01502 //          }
01503 //       }
01504 //    return to;
01505 //    }
01506 
01507 template <class T, class tree_node_allocator>
01508 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,
01509     const iterator_base& end) const
01510 {
01511   // FIXME: this should be optimised.
01512   pre_order_iterator tmp = begin;
01513   while (tmp != end)
01514   {
01515     if (tmp == it) return true;
01516     ++tmp;
01517   }
01518   return false;
01519 }
01520 
01521 template <class T, class tree_node_allocator>
01522 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
01523 {
01524   if (it.node == 0 || it.node == feet) return false;
01525   else return true;
01526 }
01527 
01528 template <class T, class tree_node_allocator>
01529 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
01530 {
01531   unsigned int ind = 0;
01532   if (it.node->parent == 0)
01533   {
01534     while (it.node->prev_sibling != head)
01535     {
01536       it.node = it.node->prev_sibling;
01537       ++ind;
01538     }
01539   }
01540   else
01541   {
01542     while (it.node->prev_sibling != 0)
01543     {
01544       it.node = it.node->prev_sibling;
01545       ++ind;
01546     }
01547   }
01548   return ind;
01549 }
01550 
01551 
01552 template <class T, class tree_node_allocator>
01553 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num) const
01554 {
01555   tree_node *tmp = it.node->first_child;
01556   while (num--)
01557   {
01558     assert(tmp != 0);
01559     tmp = tmp->next_sibling;
01560   }
01561   return tmp;
01562 }
01563 
01564 
01565 
01566 
01567 // Iterator base
01568 
01569 template <class T, class tree_node_allocator>
01570 tree<T, tree_node_allocator>::iterator_base::iterator_base()
01571   : node(0), skip_current_children_(false)
01572 {
01573 }
01574 
01575 template <class T, class tree_node_allocator>
01576 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
01577   : node(tn), skip_current_children_(false)
01578 {
01579 }
01580 
01581 template <class T, class tree_node_allocator>
01582 T& tree<T, tree_node_allocator>::iterator_base::operator*() const
01583 {
01584   return node->data;
01585 }
01586 
01587 template <class T, class tree_node_allocator>
01588 T* tree<T, tree_node_allocator>::iterator_base::operator->() const
01589 {
01590   return &(node->data);
01591 }
01592 
01593 template <class T, class tree_node_allocator>
01594 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
01595 {
01596   if (other.node != this->node) return true;
01597   else return false;
01598 }
01599 
01600 template <class T, class tree_node_allocator>
01601 bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
01602 {
01603   if (other.node == this->node) return true;
01604   else return false;
01605 }
01606 
01607 template <class T, class tree_node_allocator>
01608 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
01609 {
01610   if (other.node != this->node) return true;
01611   else return false;
01612 }
01613 
01614 template <class T, class tree_node_allocator>
01615 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
01616 {
01617   if (other.node == this->node) return true;
01618   else return false;
01619 }
01620 
01621 template <class T, class tree_node_allocator>
01622 bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
01623 {
01624   if (other.node != this->node) return true;
01625   else return false;
01626 }
01627 
01628 template <class T, class tree_node_allocator>
01629 bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
01630 {
01631   if (other.node == this->node) return true;
01632   else return false;
01633 }
01634 
01635 template <class T, class tree_node_allocator>
01636 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const
01637 {
01638   sibling_iterator ret(node->first_child);
01639   ret.parent_ = this->node;
01640   return ret;
01641 }
01642 
01643 template <class T, class tree_node_allocator>
01644 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const
01645 {
01646   sibling_iterator ret(0);
01647   ret.parent_ = node;
01648   return ret;
01649 }
01650 
01651 template <class T, class tree_node_allocator>
01652 void tree<T, tree_node_allocator>::iterator_base::skip_children()
01653 {
01654   skip_current_children_ = true;
01655 }
01656 
01657 template <class T, class tree_node_allocator>
01658 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
01659 {
01660   tree_node *pos = node->first_child;
01661   if (pos == 0) return 0;
01662 
01663   unsigned int ret = 1;
01664   while (pos != node->last_child)
01665   {
01666     ++ret;
01667     pos = pos->next_sibling;
01668   }
01669   return ret;
01670 }
01671 
01672 
01673 
01674 // Pre-order iterator
01675 
01676 template <class T, class tree_node_allocator>
01677 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
01678   : iterator_base(0)
01679 {
01680 }
01681 
01682 template <class T, class tree_node_allocator>
01683 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
01684   : iterator_base(tn)
01685 {
01686 }
01687 
01688 template <class T, class tree_node_allocator>
01689 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)
01690   : iterator_base(other.node)
01691 {
01692 }
01693 
01694 template <class T, class tree_node_allocator>
01695 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
01696   : iterator_base(other.node)
01697 {
01698   if (this->node == 0)
01699   {
01700     if (other.range_last() != 0)
01701       this->node = other.range_last();
01702     else
01703       this->node = other.parent_;
01704     this->skip_children();
01705     ++(*this);
01706   }
01707 }
01708 
01709 template <class T, class tree_node_allocator>
01710 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
01711 {
01712   assert(this->node != 0);
01713   if (!this->skip_current_children_ && this->node->first_child != 0)
01714   {
01715     this->node = this->node->first_child;
01716   }
01717   else
01718   {
01719     this->skip_current_children_ = false;
01720     while (this->node->next_sibling == 0)
01721     {
01722       this->node = this->node->parent;
01723       if (this->node == 0)
01724         return *this;
01725     }
01726     this->node = this->node->next_sibling;
01727   }
01728   return *this;
01729 }
01730 
01731 template <class T, class tree_node_allocator>
01732 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
01733 {
01734   assert(this->node != 0);
01735   if (this->node->prev_sibling)
01736   {
01737     this->node = this->node->prev_sibling;
01738     while (this->node->last_child)
01739       this->node = this->node->last_child;
01740   }
01741   else
01742   {
01743     this->node = this->node->parent;
01744     if (this->node == 0)
01745       return *this;
01746   }
01747   return *this;
01748 }
01749 
01750 template <class T, class tree_node_allocator>
01751 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int n)
01752 {
01753   pre_order_iterator copy = *this;
01754   ++(*this);
01755   return copy;
01756 }
01757 
01758 template <class T, class tree_node_allocator>
01759 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int n)
01760 {
01761   pre_order_iterator copy = *this;
01762   --(*this);
01763   return copy;
01764 }
01765 
01766 template <class T, class tree_node_allocator>
01767 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
01768 {
01769   while (num > 0)
01770   {
01771     ++(*this);
01772     --num;
01773   }
01774   return (*this);
01775 }
01776 
01777 template <class T, class tree_node_allocator>
01778 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
01779 {
01780   while (num > 0)
01781   {
01782     --(*this);
01783     --num;
01784   }
01785   return (*this);
01786 }
01787 
01788 
01789 
01790 // Post-order iterator
01791 
01792 template <class T, class tree_node_allocator>
01793 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
01794   : iterator_base(0)
01795 {
01796 }
01797 
01798 template <class T, class tree_node_allocator>
01799 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
01800   : iterator_base(tn)
01801 {
01802 }
01803 
01804 template <class T, class tree_node_allocator>
01805 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)
01806   : iterator_base(other.node)
01807 {
01808 }
01809 
01810 template <class T, class tree_node_allocator>
01811 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)
01812   : iterator_base(other.node)
01813 {
01814   if (this->node == 0)
01815   {
01816     if (other.range_last() != 0)
01817       this->node = other.range_last();
01818     else
01819       this->node = other.parent_;
01820     this->skip_children();
01821     ++(*this);
01822   }
01823 }
01824 
01825 template <class T, class tree_node_allocator>
01826 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
01827 {
01828   assert(this->node != 0);
01829   if (this->node->next_sibling == 0)
01830   {
01831     this->node = this->node->parent;
01832     this->skip_current_children_ = false;
01833   }
01834   else
01835   {
01836     this->node = this->node->next_sibling;
01837     if (this->skip_current_children_)
01838     {
01839       this->skip_current_children_ = false;
01840     }
01841     else
01842     {
01843       while (this->node->first_child)
01844         this->node = this->node->first_child;
01845     }
01846   }
01847   return *this;
01848 }
01849 
01850 template <class T, class tree_node_allocator>
01851 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
01852 {
01853   assert(this->node != 0);
01854   if (this->skip_current_children_ || this->node->last_child == 0)
01855   {
01856     this->skip_current_children_ = false;
01857     while (this->node->prev_sibling == 0)
01858       this->node = this->node->parent;
01859     this->node = this->node->prev_sibling;
01860   }
01861   else
01862   {
01863     this->node = this->node->last_child;
01864   }
01865   return *this;
01866 }
01867 
01868 template <class T, class tree_node_allocator>
01869 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
01870 {
01871   post_order_iterator copy = *this;
01872   ++(*this);
01873   return copy;
01874 }
01875 
01876 template <class T, class tree_node_allocator>
01877 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
01878 {
01879   post_order_iterator copy = *this;
01880   --(*this);
01881   return copy;
01882 }
01883 
01884 
01885 template <class T, class tree_node_allocator>
01886 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
01887 {
01888   while (num > 0)
01889   {
01890     ++(*this);
01891     --num;
01892   }
01893   return (*this);
01894 }
01895 
01896 template <class T, class tree_node_allocator>
01897 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
01898 {
01899   while (num > 0)
01900   {
01901     --(*this);
01902     --num;
01903   }
01904   return (*this);
01905 }
01906 
01907 template <class T, class tree_node_allocator>
01908 void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
01909 {
01910   assert(this->node != 0);
01911   while (this->node->first_child)
01912     this->node = this->node->first_child;
01913 }
01914 
01915 
01916 // Fixed depth iterator
01917 
01918 template <class T, class tree_node_allocator>
01919 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
01920   : iterator_base()
01921 {
01922   set_first_parent_();
01923 }
01924 
01925 template <class T, class tree_node_allocator>
01926 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
01927   : iterator_base(tn)
01928 {
01929   set_first_parent_();
01930 }
01931 
01932 template <class T, class tree_node_allocator>
01933 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)
01934   : iterator_base(other.node)
01935 {
01936   set_first_parent_();
01937 }
01938 
01939 template <class T, class tree_node_allocator>
01940 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
01941   : iterator_base(other.node), first_parent_(other.parent_)
01942 {
01943   find_leftmost_parent_();
01944 }
01945 
01946 template <class T, class tree_node_allocator>
01947 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)
01948   : iterator_base(other.node), first_parent_(other.first_parent_)
01949 {
01950 }
01951 
01952 template <class T, class tree_node_allocator>
01953 void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
01954 {
01955   return; // FIXME: we do not use first_parent_ yet, and it actually needs some serious reworking if
01956   // it is ever to work at the 'head' level.
01957   first_parent_ = 0;
01958   if (this->node == 0) return;
01959   if (this->node->parent != 0)
01960     first_parent_ = this->node->parent;
01961   if (first_parent_)
01962     find_leftmost_parent_();
01963 }
01964 
01965 template <class T, class tree_node_allocator>
01966 void tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()
01967 {
01968   return; // FIXME: see 'set_first_parent()'
01969   tree_node *tmppar = first_parent_;
01970   while (tmppar->prev_sibling)
01971   {
01972     tmppar = tmppar->prev_sibling;
01973     if (tmppar->first_child)
01974       first_parent_ = tmppar;
01975   }
01976 }
01977 
01978 template <class T, class tree_node_allocator>
01979 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
01980 {
01981   assert(this->node != 0);
01982 
01983   if (this->node->next_sibling)
01984   {
01985     this->node = this->node->next_sibling;
01986   }
01987   else
01988   {
01989     int relative_depth = 0;
01990 upper:
01991     do
01992     {
01993       this->node = this->node->parent;
01994       if (this->node == 0) return *this;
01995       --relative_depth;
01996     }
01997     while (this->node->next_sibling == 0);
01998 lower:
01999     this->node = this->node->next_sibling;
02000     while (this->node->first_child == 0)
02001     {
02002       if (this->node->next_sibling == 0)
02003         goto upper;
02004       this->node = this->node->next_sibling;
02005       if (this->node == 0) return *this;
02006     }
02007     while (relative_depth < 0 && this->node->first_child != 0)
02008     {
02009       this->node = this->node->first_child;
02010       ++relative_depth;
02011     }
02012     if (relative_depth < 0)
02013     {
02014       if (this->node->next_sibling == 0) goto upper;
02015       else                          goto lower;
02016     }
02017   }
02018   return *this;
02019 
02020 // if(this->node->next_sibling!=0) {
02021 //    this->node=this->node->next_sibling;
02022 //    assert(this->node!=0);
02023 //    if(this->node->parent==0 && this->node->next_sibling==0) // feet element
02024 //       this->node=0;
02025 //    }
02026 // else {
02027 //    tree_node *par=this->node->parent;
02028 //    do {
02029 //       par=par->next_sibling;
02030 //       if(par==0) { // FIXME: need to keep track of this!
02031 //          this->node=0;
02032 //          return *this;
02033 //          }
02034 //       } while(par->first_child==0);
02035 //    this->node=par->first_child;
02036 //    }
02037   return *this;
02038 }
02039 
02040 template <class T, class tree_node_allocator>
02041 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
02042 {
02043   assert(this->node != 0);
02044   if (this->node->prev_sibling != 0)
02045   {
02046     this->node = this->node->prev_sibling;
02047     assert(this->node != 0);
02048     if (this->node->parent == 0 && this->node->prev_sibling == 0) // head element
02049       this->node = 0;
02050   }
02051   else
02052   {
02053     tree_node *par = this->node->parent;
02054     do
02055     {
02056       par = par->prev_sibling;
02057       if (par == 0)   // FIXME: need to keep track of this!
02058       {
02059         this->node = 0;
02060         return *this;
02061       }
02062     }
02063     while (par->last_child == 0);
02064     this->node = par->last_child;
02065   }
02066   return *this;
02067 }
02068 
02069 template <class T, class tree_node_allocator>
02070 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)
02071 {
02072   fixed_depth_iterator copy = *this;
02073   ++(*this);
02074   return copy;
02075 }
02076 
02077 template <class T, class tree_node_allocator>
02078 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)
02079 {
02080   fixed_depth_iterator copy = *this;
02081   --(*this);
02082   return copy;
02083 }
02084 
02085 template <class T, class tree_node_allocator>
02086 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
02087 {
02088   while (num > 0)
02089   {
02090     --(*this);
02091     --(num);
02092   }
02093   return (*this);
02094 }
02095 
02096 template <class T, class tree_node_allocator>
02097 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
02098 {
02099   while (num > 0)
02100   {
02101     ++(*this);
02102     --(num);
02103   }
02104   return *this;
02105 }
02106 
02107 // FIXME: add the other members of fixed_depth_iterator.
02108 
02109 
02110 // Sibling iterator
02111 
02112 template <class T, class tree_node_allocator>
02113 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
02114   : iterator_base()
02115 {
02116   set_parent_();
02117 }
02118 
02119 template <class T, class tree_node_allocator>
02120 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
02121   : iterator_base(tn)
02122 {
02123   set_parent_();
02124 }
02125 
02126 template <class T, class tree_node_allocator>
02127 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)
02128   : iterator_base(other.node)
02129 {
02130   set_parent_();
02131 }
02132 
02133 template <class T, class tree_node_allocator>
02134 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)
02135   : iterator_base(other), parent_(other.parent_)
02136 {
02137 }
02138 
02139 template <class T, class tree_node_allocator>
02140 void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
02141 {
02142   parent_ = 0;
02143   if (this->node == 0) return;
02144   if (this->node->parent != 0)
02145     parent_ = this->node->parent;
02146 }
02147 
02148 template <class T, class tree_node_allocator>
02149 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
02150 {
02151   if (this->node)
02152     this->node = this->node->next_sibling;
02153   return *this;
02154 }
02155 
02156 template <class T, class tree_node_allocator>
02157 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
02158 {
02159   if (this->node) this->node = this->node->prev_sibling;
02160   else
02161   {
02162     assert(parent_);
02163     this->node = parent_->last_child;
02164   }
02165   return *this;
02166 }
02167 
02168 template <class T, class tree_node_allocator>
02169 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)
02170 {
02171   sibling_iterator copy = *this;
02172   ++(*this);
02173   return copy;
02174 }
02175 
02176 template <class T, class tree_node_allocator>
02177 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)
02178 {
02179   sibling_iterator copy = *this;
02180   --(*this);
02181   return copy;
02182 }
02183 
02184 template <class T, class tree_node_allocator>
02185 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
02186 {
02187   while (num > 0)
02188   {
02189     ++(*this);
02190     --num;
02191   }
02192   return (*this);
02193 }
02194 
02195 template <class T, class tree_node_allocator>
02196 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
02197 {
02198   while (num > 0)
02199   {
02200     --(*this);
02201     --num;
02202   }
02203   return (*this);
02204 }
02205 
02206 template <class T, class tree_node_allocator>
02207 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const
02208 {
02209   tree_node *tmp = parent_->first_child;
02210   return tmp;
02211 }
02212 
02213 template <class T, class tree_node_allocator>
02214 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const
02215 {
02216   return parent_->last_child;
02217 }
02218 
02219 
02220 #endif
02221 
02222 // Local variables:
02223 // default-tab-width: 3
02224 // End: