• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

/builddir/build/BUILD/liborigin2/tree.hh

Go to the documentation of this file.
00001 
00002 //  STL-like templated tree class.
00003 //
00004 // Copyright (C) 2001-2009 Kasper Peeters <kasper.peeters@aei.mpg.de>
00005 // Distributed under the GNU General Public License version 3,
00006 // (eventually to be changed to the Boost Software License).
00007 
00024 #ifndef tree_hh_
00025 #define tree_hh_
00026 
00027 #include <cassert>
00028 #include <memory>
00029 #include <stdexcept>
00030 #include <iterator>
00031 #include <set>
00032 #include <queue>
00033 #include <algorithm>
00034 
00035 // HP-style construct/destroy have gone from the standard,
00036 // so here is a copy.
00037 
00038 namespace kp {
00039 
00040 template <class T1, class T2>
00041 void constructor(T1* p, T2& val) 
00042     {
00043     new ((void *) p) T1(val);
00044     }
00045 
00046 template <class T1>
00047 void constructor(T1* p) 
00048     {
00049     new ((void *) p) T1;
00050     }
00051 
00052 template <class T1>
00053 void destructor(T1* p)
00054     {
00055     p->~T1();
00056     }
00057 
00058 }
00059 
00061 template<class T>
00062 class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
00063     public:
00064         tree_node_<T> *parent;
00065        tree_node_<T> *first_child, *last_child;
00066         tree_node_<T> *prev_sibling, *next_sibling;
00067         T data;
00068 }; // __attribute__((packed));
00069 
00070 template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
00071 class tree {
00072     protected:
00073         typedef tree_node_<T> tree_node;
00074     public:
00076         typedef T value_type;
00077 
00078         class iterator_base;
00079         class pre_order_iterator;
00080         class post_order_iterator;
00081         class sibling_iterator;
00082       class leaf_iterator;
00083 
00084         tree();
00085         tree(const T&);
00086         tree(const iterator_base&);
00087         tree(const tree<T, tree_node_allocator>&);
00088         ~tree();
00089         void operator=(const tree<T, tree_node_allocator>&);
00090 
00092 #ifdef __SGI_STL_PORT
00093         class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
00094 #else
00095         class iterator_base {
00096 #endif
00097             public:
00098                 typedef T                               value_type;
00099                 typedef T*                              pointer;
00100                 typedef T&                              reference;
00101                 typedef size_t                          size_type;
00102                 typedef ptrdiff_t                       difference_type;
00103                 typedef std::bidirectional_iterator_tag iterator_category;
00104 
00105                 iterator_base();
00106                 iterator_base(tree_node *);
00107 
00108                 T&             operator*() const;
00109                 T*             operator->() const;
00110 
00112                 void         skip_children();
00113                 void         skip_children(bool skip);
00115                 unsigned int number_of_children() const;
00116 
00117                 sibling_iterator begin() const;
00118                 sibling_iterator end() const;
00119 
00120                 tree_node *node;
00121             protected:
00122                 bool skip_current_children_;
00123         };
00124 
00126         class pre_order_iterator : public iterator_base { 
00127             public:
00128                 pre_order_iterator();
00129                 pre_order_iterator(tree_node *);
00130                 pre_order_iterator(const iterator_base&);
00131                 pre_order_iterator(const sibling_iterator&);
00132 
00133                 bool    operator==(const pre_order_iterator&) const;
00134                 bool    operator!=(const pre_order_iterator&) const;
00135                 pre_order_iterator&  operator++();
00136                pre_order_iterator&  operator--();
00137                 pre_order_iterator   operator++(int);
00138                 pre_order_iterator   operator--(int);
00139                 pre_order_iterator&  operator+=(unsigned int);
00140                 pre_order_iterator&  operator-=(unsigned int);
00141         };
00142 
00144         class post_order_iterator : public iterator_base {
00145             public:
00146                 post_order_iterator();
00147                 post_order_iterator(tree_node *);
00148                 post_order_iterator(const iterator_base&);
00149                 post_order_iterator(const sibling_iterator&);
00150 
00151                 bool    operator==(const post_order_iterator&) const;
00152                 bool    operator!=(const post_order_iterator&) const;
00153                 post_order_iterator&  operator++();
00154                post_order_iterator&  operator--();
00155                 post_order_iterator   operator++(int);
00156                 post_order_iterator   operator--(int);
00157                 post_order_iterator&  operator+=(unsigned int);
00158                 post_order_iterator&  operator-=(unsigned int);
00159 
00161                 void descend_all();
00162         };
00163 
00165         class breadth_first_queued_iterator : public iterator_base {
00166             public:
00167                 breadth_first_queued_iterator();
00168                 breadth_first_queued_iterator(tree_node *);
00169                 breadth_first_queued_iterator(const iterator_base&);
00170 
00171                 bool    operator==(const breadth_first_queued_iterator&) const;
00172                 bool    operator!=(const breadth_first_queued_iterator&) const;
00173                 breadth_first_queued_iterator&  operator++();
00174                 breadth_first_queued_iterator   operator++(int);
00175                 breadth_first_queued_iterator&  operator+=(unsigned int);
00176 
00177             private:
00178                 std::queue<tree_node *> traversal_queue;
00179         };
00180 
00182         typedef pre_order_iterator            iterator;
00183         typedef breadth_first_queued_iterator breadth_first_iterator;
00184 
00186         class fixed_depth_iterator : public iterator_base {
00187             public:
00188                 fixed_depth_iterator();
00189                 fixed_depth_iterator(tree_node *);
00190                 fixed_depth_iterator(const iterator_base&);
00191                 fixed_depth_iterator(const sibling_iterator&);
00192                 fixed_depth_iterator(const fixed_depth_iterator&);
00193 
00194                 bool    operator==(const fixed_depth_iterator&) const;
00195                 bool    operator!=(const fixed_depth_iterator&) const;
00196                 fixed_depth_iterator&  operator++();
00197                fixed_depth_iterator&  operator--();
00198                 fixed_depth_iterator   operator++(int);
00199                 fixed_depth_iterator   operator--(int);
00200                 fixed_depth_iterator&  operator+=(unsigned int);
00201                 fixed_depth_iterator&  operator-=(unsigned int);
00202 
00203                 tree_node *top_node;
00204         };
00205 
00207         class sibling_iterator : public iterator_base {
00208             public:
00209                 sibling_iterator();
00210                 sibling_iterator(tree_node *);
00211                 sibling_iterator(const sibling_iterator&);
00212                 sibling_iterator(const iterator_base&);
00213 
00214                 bool    operator==(const sibling_iterator&) const;
00215                 bool    operator!=(const sibling_iterator&) const;
00216                 sibling_iterator&  operator++();
00217                 sibling_iterator&  operator--();
00218                 sibling_iterator   operator++(int);
00219                 sibling_iterator   operator--(int);
00220                 sibling_iterator&  operator+=(unsigned int);
00221                 sibling_iterator&  operator-=(unsigned int);
00222 
00223                 tree_node *range_first() const;
00224                 tree_node *range_last() const;
00225                 tree_node *parent_;
00226             private:
00227                 void set_parent_();
00228         };
00229 
00231       class leaf_iterator : public iterator_base {
00232          public:
00233             leaf_iterator();
00234             leaf_iterator(tree_node *, tree_node *top=0);
00235             leaf_iterator(const sibling_iterator&);
00236             leaf_iterator(const iterator_base&);
00237 
00238             bool    operator==(const leaf_iterator&) const;
00239             bool    operator!=(const leaf_iterator&) const;
00240             leaf_iterator&  operator++();
00241             leaf_iterator&  operator--();
00242             leaf_iterator   operator++(int);
00243             leaf_iterator   operator--(int);
00244             leaf_iterator&  operator+=(unsigned int);
00245             leaf_iterator&  operator-=(unsigned int);
00246             private:
00247                 tree_node *top_node;
00248       };
00249 
00251         inline pre_order_iterator   begin() const;
00253         inline pre_order_iterator   end() const;
00255         post_order_iterator  begin_post() const;
00257         post_order_iterator  end_post() const;
00259         fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
00261         fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
00263         breadth_first_queued_iterator begin_breadth_first() const;
00265         breadth_first_queued_iterator end_breadth_first() const;
00267         sibling_iterator     begin(const iterator_base&) const;
00269         sibling_iterator     end(const iterator_base&) const;
00271       leaf_iterator   begin_leaf() const;
00273       leaf_iterator   end_leaf() const;
00275       leaf_iterator   begin_leaf(const iterator_base& top) const;
00277       leaf_iterator   end_leaf(const iterator_base& top) const;
00278 
00280         template<typename   iter> static iter parent(iter);
00282         template<typename iter> iter previous_sibling(iter) const;
00284         template<typename iter> iter next_sibling(iter) const;
00286         template<typename iter> iter next_at_same_depth(iter) const;
00287 
00289         void     clear();
00291         template<typename iter> iter erase(iter);
00293         void     erase_children(const iterator_base&);
00294 
00296         template<typename iter> iter append_child(iter position); 
00297         template<typename iter> iter prepend_child(iter position); 
00299         template<typename iter> iter append_child(iter position, const T& x);
00300         template<typename iter> iter prepend_child(iter position, const T& x);
00302         template<typename iter> iter append_child(iter position, iter other_position);
00303         template<typename iter> iter prepend_child(iter position, iter other_position);
00305         template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
00306         template<typename iter> iter prepend_children(iter position, sibling_iterator from, sibling_iterator to);
00307 
00309         pre_order_iterator set_head(const T& x);
00311         template<typename iter> iter insert(iter position, const T& x);
00313         sibling_iterator insert(sibling_iterator position, const T& x);
00315         template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
00317         template<typename iter> iter insert_after(iter position, const T& x);
00319         template<typename iter> iter insert_subtree_after(iter position, const iterator_base& subtree);
00320 
00322         template<typename iter> iter replace(iter position, const T& x);
00324         template<typename iter> iter replace(iter position, const iterator_base& from);
00326         sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end, 
00327                                          sibling_iterator new_begin,  sibling_iterator new_end); 
00328 
00330         template<typename iter> iter flatten(iter position);
00332         template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
00334         template<typename iter> iter reparent(iter position, iter from);
00335 
00337         template<typename iter> iter wrap(iter position, const T& x);
00338 
00340         template<typename iter> iter move_after(iter target, iter source);
00342       template<typename iter> iter move_before(iter target, iter source);
00343       sibling_iterator move_before(sibling_iterator target, sibling_iterator source);
00345         template<typename iter> iter move_ontop(iter target, iter source);
00346 
00348         void     merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, 
00349                             bool duplicate_leaves=false);
00351         void     sort(sibling_iterator from, sibling_iterator to, bool deep=false);
00352         template<class StrictWeakOrdering>
00353         void     sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
00355         template<typename iter>
00356         bool     equal(const iter& one, const iter& two, const iter& three) const;
00357         template<typename iter, class BinaryPredicate>
00358         bool     equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
00359         template<typename iter>
00360         bool     equal_subtree(const iter& one, const iter& two) const;
00361         template<typename iter, class BinaryPredicate>
00362         bool     equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
00364         tree     subtree(sibling_iterator from, sibling_iterator to) const;
00365         void     subtree(tree&, sibling_iterator from, sibling_iterator to) const;
00367         void     swap(sibling_iterator it);
00369        void     swap(iterator, iterator);
00370         
00372         size_t   size() const;
00374         size_t   size(const iterator_base&) const;
00376         bool     empty() const;
00378         static int depth(const iterator_base&);
00379         static int depth(const iterator_base&, const iterator_base&);
00381         int      max_depth() const;
00383         int      max_depth(const iterator_base&) const;
00385         static unsigned int number_of_children(const iterator_base&);
00387         unsigned int number_of_siblings(const iterator_base&) const;
00389         bool     is_in_subtree(const iterator_base& position, const iterator_base& begin, 
00390                                       const iterator_base& end) const;
00392         bool     is_valid(const iterator_base&) const;
00393 
00395         unsigned int index(sibling_iterator it) const;
00397         static sibling_iterator child(const iterator_base& position, unsigned int);
00399         sibling_iterator sibling(const iterator_base& position, unsigned int);                  
00400         
00402         class iterator_base_less {
00403             public:
00404                 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
00405                                      const typename tree<T, tree_node_allocator>::iterator_base& two) const
00406                     {
00407                     return one.node < two.node;
00408                     }
00409         };
00410         tree_node *head, *feet;    // head/feet are always dummy; if an iterator points to them it is invalid
00411     private:
00412         tree_node_allocator alloc_;
00413         void head_initialise_();
00414         void copy_(const tree<T, tree_node_allocator>& other);
00415 
00417         template<class StrictWeakOrdering>
00418         class compare_nodes {
00419             public:
00420                 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
00421                 
00422                 bool operator()(const tree_node *a, const tree_node *b) 
00423                     {
00424                     return comp_(a->data, b->data);
00425                     }
00426             private:
00427                 StrictWeakOrdering comp_;
00428         };
00429 };
00430 
00431 //template <class T, class tree_node_allocator>
00432 //class iterator_base_less {
00433 //  public:
00434 //      bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
00435 //                        const typename tree<T, tree_node_allocator>::iterator_base& two) const
00436 //          {
00437 //          txtout << "operatorclass<" << one.node < two.node << std::endl;
00438 //          return one.node < two.node;
00439 //          }
00440 //};
00441 
00442 // template <class T, class tree_node_allocator>
00443 // bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
00444 //                  const typename tree<T, tree_node_allocator>::iterator& two)
00445 //  {
00446 //  txtout << "operator< " << one.node < two.node << std::endl;
00447 //  if(one.node < two.node) return true;
00448 //  return false;
00449 //  }
00450 // 
00451 // template <class T, class tree_node_allocator>
00452 // bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
00453 //                  const typename tree<T, tree_node_allocator>::iterator& two)
00454 //  {
00455 //  txtout << "operator== " << one.node == two.node << std::endl;
00456 //  if(one.node == two.node) return true;
00457 //  return false;
00458 //  }
00459 // 
00460 // template <class T, class tree_node_allocator>
00461 // bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
00462 //                  const typename tree<T, tree_node_allocator>::iterator_base& two)
00463 //  {
00464 //  txtout << "operator> " << one.node < two.node << std::endl;
00465 //  if(one.node > two.node) return true;
00466 //  return false;
00467 //  }
00468 
00469 
00470 
00471 // Tree
00472 
00473 template <class T, class tree_node_allocator>
00474 tree<T, tree_node_allocator>::tree() 
00475     {
00476     head_initialise_();
00477     }
00478 
00479 template <class T, class tree_node_allocator>
00480 tree<T, tree_node_allocator>::tree(const T& x) 
00481     {
00482     head_initialise_();
00483     set_head(x);
00484     }
00485 
00486 template <class T, class tree_node_allocator>
00487 tree<T, tree_node_allocator>::tree(const iterator_base& other)
00488     {
00489     head_initialise_();
00490     set_head((*other));
00491     replace(begin(), other);
00492     }
00493 
00494 template <class T, class tree_node_allocator>
00495 tree<T, tree_node_allocator>::~tree()
00496     {
00497     clear();
00498     alloc_.deallocate(head,1);
00499     alloc_.deallocate(feet,1);
00500     }
00501 
00502 template <class T, class tree_node_allocator>
00503 void tree<T, tree_node_allocator>::head_initialise_() 
00504    { 
00505    head = alloc_.allocate(1,0); // MSVC does not have default second argument 
00506     feet = alloc_.allocate(1,0);
00507 
00508    head->parent=0;
00509    head->first_child=0;
00510    head->last_child=0;
00511    head->prev_sibling=0; //head;
00512    head->next_sibling=feet; //head;
00513 
00514     feet->parent=0;
00515     feet->first_child=0;
00516     feet->last_child=0;
00517     feet->prev_sibling=head;
00518     feet->next_sibling=0;
00519    }
00520 
00521 template <class T, class tree_node_allocator>
00522 void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
00523     {
00524     copy_(other);
00525     }
00526 
00527 template <class T, class tree_node_allocator>
00528 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
00529     {
00530     head_initialise_();
00531     copy_(other);
00532     }
00533 
00534 template <class T, class tree_node_allocator>
00535 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other) 
00536     {
00537     clear();
00538     pre_order_iterator it=other.begin(), to=begin();
00539     while(it!=other.end()) {
00540         to=insert(to, (*it));
00541         it.skip_children();
00542         ++it;
00543         }
00544     to=begin();
00545     it=other.begin();
00546     while(it!=other.end()) {
00547         to=replace(to, it);
00548         to.skip_children();
00549         it.skip_children();
00550         ++to;
00551         ++it;
00552         }
00553     }
00554 
00555 template <class T, class tree_node_allocator>
00556 void tree<T, tree_node_allocator>::clear()
00557     {
00558     if(head)
00559         while(head->next_sibling!=feet)
00560             erase(pre_order_iterator(head->next_sibling));
00561     }
00562 
00563 template<class T, class tree_node_allocator> 
00564 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
00565     {
00566 //  std::cout << "erase_children " << it.node << std::endl;
00567     if(it.node==0) return;
00568 
00569     tree_node *cur=it.node->first_child;
00570     tree_node *prev=0;
00571 
00572     while(cur!=0) {
00573         prev=cur;
00574         cur=cur->next_sibling;
00575         erase_children(pre_order_iterator(prev));
00576         kp::destructor(&prev->data);
00577         alloc_.deallocate(prev,1);
00578         }
00579     it.node->first_child=0;
00580     it.node->last_child=0;
00581 //  std::cout << "exit" << std::endl;
00582     }
00583 
00584 template<class T, class tree_node_allocator> 
00585 template<class iter>
00586 iter tree<T, tree_node_allocator>::erase(iter it)
00587     {
00588     tree_node *cur=it.node;
00589     assert(cur!=head);
00590     iter ret=it;
00591     ret.skip_children();
00592     ++ret;
00593     erase_children(it);
00594     if(cur->prev_sibling==0) {
00595         cur->parent->first_child=cur->next_sibling;
00596         }
00597     else {
00598         cur->prev_sibling->next_sibling=cur->next_sibling;
00599         }
00600     if(cur->next_sibling==0) {
00601         cur->parent->last_child=cur->prev_sibling;
00602         }
00603     else {
00604         cur->next_sibling->prev_sibling=cur->prev_sibling;
00605         }
00606 
00607     kp::destructor(&cur->data);
00608    alloc_.deallocate(cur,1);
00609     return ret;
00610     }
00611 
00612 template <class T, class tree_node_allocator>
00613 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const
00614     {
00615     return pre_order_iterator(head->next_sibling);
00616     }
00617 
00618 template <class T, class tree_node_allocator>
00619 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const
00620     {
00621     return pre_order_iterator(feet);
00622     }
00623 
00624 template <class T, class tree_node_allocator>
00625 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first() const
00626     {
00627     return breadth_first_queued_iterator(head->next_sibling);
00628     }
00629 
00630 template <class T, class tree_node_allocator>
00631 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first() const
00632     {
00633     return breadth_first_queued_iterator();
00634     }
00635 
00636 template <class T, class tree_node_allocator>
00637 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const
00638     {
00639     tree_node *tmp=head->next_sibling;
00640     if(tmp!=feet) {
00641         while(tmp->first_child)
00642             tmp=tmp->first_child;
00643         }
00644     return post_order_iterator(tmp);
00645     }
00646 
00647 template <class T, class tree_node_allocator>
00648 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const
00649     {
00650     return post_order_iterator(feet);
00651     }
00652 
00653 template <class T, class tree_node_allocator>
00654 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const
00655     {
00656     typename tree<T, tree_node_allocator>::fixed_depth_iterator ret;
00657     ret.top_node=pos.node;
00658 
00659     tree_node *tmp=pos.node;
00660     unsigned int curdepth=0;
00661     while(curdepth<dp) { // go down one level
00662         while(tmp->first_child==0) {
00663             if(tmp->next_sibling==0) {
00664                 // try to walk up and then right again
00665                 do {
00666                     if(tmp==ret.top_node)
00667                        throw std::range_error("tree: begin_fixed out of range");
00668                     tmp=tmp->parent;
00669                if(tmp==0) 
00670                        throw std::range_error("tree: begin_fixed out of range");
00671                --curdepth;
00672                    } while(tmp->next_sibling==0);
00673                 }
00674             tmp=tmp->next_sibling;
00675             }
00676         tmp=tmp->first_child;
00677         ++curdepth;
00678         }
00679 
00680     ret.node=tmp;
00681     return ret;
00682     }
00683 
00684 template <class T, class tree_node_allocator>
00685 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
00686     {
00687     assert(1==0); // FIXME: not correct yet: use is_valid() as a temporary workaround 
00688     tree_node *tmp=pos.node;
00689     unsigned int curdepth=1;
00690     while(curdepth<dp) { // go down one level
00691         while(tmp->first_child==0) {
00692             tmp=tmp->next_sibling;
00693             if(tmp==0)
00694                 throw std::range_error("tree: end_fixed out of range");
00695             }
00696         tmp=tmp->first_child;
00697         ++curdepth;
00698         }
00699     return tmp;
00700     }
00701 
00702 template <class T, class tree_node_allocator>
00703 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const
00704     {
00705     assert(pos.node!=0);
00706     if(pos.node->first_child==0) {
00707         return end(pos);
00708         }
00709     return pos.node->first_child;
00710     }
00711 
00712 template <class T, class tree_node_allocator>
00713 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const
00714     {
00715     sibling_iterator ret(0);
00716     ret.parent_=pos.node;
00717     return ret;
00718     }
00719 
00720 template <class T, class tree_node_allocator>
00721 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf() const
00722    {
00723    tree_node *tmp=head->next_sibling;
00724    if(tmp!=feet) {
00725       while(tmp->first_child)
00726          tmp=tmp->first_child;
00727       }
00728    return leaf_iterator(tmp);
00729    }
00730 
00731 template <class T, class tree_node_allocator>
00732 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf() const
00733    {
00734    return leaf_iterator(feet);
00735    }
00736 
00737 template <class T, class tree_node_allocator>
00738 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf(const iterator_base& top) const
00739    {
00740     tree_node *tmp=top.node;
00741     while(tmp->first_child)
00742          tmp=tmp->first_child;
00743    return leaf_iterator(tmp, top.node);
00744    }
00745 
00746 template <class T, class tree_node_allocator>
00747 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf(const iterator_base& top) const
00748    {
00749    return leaf_iterator(top.node, top.node);
00750    }
00751 
00752 template <class T, class tree_node_allocator>
00753 template <typename iter>
00754 iter tree<T, tree_node_allocator>::parent(iter position) 
00755     {
00756     assert(position.node!=0);
00757     return iter(position.node->parent);
00758     }
00759 
00760 template <class T, class tree_node_allocator>
00761 template <typename iter>
00762 iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
00763     {
00764     assert(position.node!=0);
00765     iter ret(position);
00766     ret.node=position.node->prev_sibling;
00767     return ret;
00768     }
00769 
00770 template <class T, class tree_node_allocator>
00771 template <typename iter>
00772 iter tree<T, tree_node_allocator>::next_sibling(iter position) const
00773     {
00774     assert(position.node!=0);
00775     iter ret(position);
00776     ret.node=position.node->next_sibling;
00777     return ret;
00778     }
00779 
00780 template <class T, class tree_node_allocator>
00781 template <typename iter>
00782 iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
00783     {
00784     // We make use of a temporary fixed_depth iterator to implement this.
00785 
00786     typename tree<T, tree_node_allocator>::fixed_depth_iterator tmp(position.node);
00787 
00788     ++tmp;
00789     return iter(tmp);
00790 
00791 //  assert(position.node!=0);
00792 //  iter ret(position);
00793 //
00794 //  if(position.node->next_sibling) {
00795 //      ret.node=position.node->next_sibling;
00796 //      }
00797 //  else { 
00798 //      int relative_depth=0;
00799 //     upper:
00800 //      do {
00801 //          ret.node=ret.node->parent;
00802 //          if(ret.node==0) return ret;
00803 //          --relative_depth;
00804 //          } while(ret.node->next_sibling==0);
00805 //     lower:
00806 //      ret.node=ret.node->next_sibling;
00807 //      while(ret.node->first_child==0) {
00808 //          if(ret.node->next_sibling==0)
00809 //              goto upper;
00810 //          ret.node=ret.node->next_sibling;
00811 //          if(ret.node==0) return ret;
00812 //          }
00813 //      while(relative_depth<0 && ret.node->first_child!=0) {
00814 //          ret.node=ret.node->first_child;
00815 //          ++relative_depth;
00816 //          }
00817 //      if(relative_depth<0) {
00818 //          if(ret.node->next_sibling==0) goto upper;
00819 //          else                          goto lower;
00820 //          }
00821 //      }
00822 //  return ret;
00823     }
00824 
00825 template <class T, class tree_node_allocator>
00826 template <typename iter>
00827 iter tree<T, tree_node_allocator>::append_child(iter position)
00828     {
00829     assert(position.node!=head);
00830     assert(position.node);
00831 
00832     tree_node *tmp=alloc_.allocate(1,0);
00833     kp::constructor(&tmp->data);
00834     tmp->first_child=0;
00835     tmp->last_child=0;
00836 
00837     tmp->parent=position.node;
00838     if(position.node->last_child!=0) {
00839         position.node->last_child->next_sibling=tmp;
00840         }
00841     else {
00842         position.node->first_child=tmp;
00843         }
00844     tmp->prev_sibling=position.node->last_child;
00845     position.node->last_child=tmp;
00846     tmp->next_sibling=0;
00847     return tmp;
00848     }
00849 
00850 template <class T, class tree_node_allocator>
00851 template <typename iter>
00852 iter tree<T, tree_node_allocator>::prepend_child(iter position)
00853     {
00854     assert(position.node!=head);
00855     assert(position.node);
00856 
00857     tree_node *tmp=alloc_.allocate(1,0);
00858     kp::constructor(&tmp->data);
00859     tmp->first_child=0;
00860     tmp->last_child=0;
00861 
00862     tmp->parent=position.node;
00863     if(position.node->first_child!=0) {
00864         position.node->first_child->prev_sibling=tmp;
00865         }
00866     else {
00867         position.node->last_child=tmp;
00868         }
00869     tmp->next_sibling=position.node->first_child;
00870     position.node->prev_child=tmp;
00871     tmp->prev_sibling=0;
00872     return tmp;
00873     }
00874 
00875 template <class T, class tree_node_allocator>
00876 template <class iter>
00877 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
00878     {
00879     // If your program fails here you probably used 'append_child' to add the top
00880     // node to an empty tree. From version 1.45 the top element should be added
00881     // using 'insert'. See the documentation for further information, and sorry about
00882     // the API change.
00883     assert(position.node!=head);
00884     assert(position.node);
00885 
00886     tree_node* tmp = alloc_.allocate(1,0);
00887     kp::constructor(&tmp->data, x);
00888     tmp->first_child=0;
00889     tmp->last_child=0;
00890 
00891     tmp->parent=position.node;
00892     if(position.node->last_child!=0) {
00893         position.node->last_child->next_sibling=tmp;
00894         }
00895     else {
00896         position.node->first_child=tmp;
00897         }
00898     tmp->prev_sibling=position.node->last_child;
00899     position.node->last_child=tmp;
00900     tmp->next_sibling=0;
00901     return tmp;
00902     }
00903 
00904 template <class T, class tree_node_allocator>
00905 template <class iter>
00906 iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
00907     {
00908     assert(position.node!=head);
00909     assert(position.node);
00910 
00911     tree_node* tmp = alloc_.allocate(1,0);
00912     kp::constructor(&tmp->data, x);
00913     tmp->first_child=0;
00914     tmp->last_child=0;
00915 
00916     tmp->parent=position.node;
00917     if(position.node->first_child!=0) {
00918         position.node->first_child->prev_sibling=tmp;
00919         }
00920     else {
00921         position.node->last_child=tmp;
00922         }
00923     tmp->next_sibling=position.node->first_child;
00924     position.node->first_child=tmp;
00925     tmp->prev_sibling=0;
00926     return tmp;
00927     }
00928 
00929 template <class T, class tree_node_allocator>
00930 template <class iter>
00931 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
00932     {
00933     assert(position.node!=head);
00934     assert(position.node);
00935 
00936     sibling_iterator aargh=append_child(position, value_type());
00937     return replace(aargh, other);
00938     }
00939 
00940 template <class T, class tree_node_allocator>
00941 template <class iter>
00942 iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)
00943     {
00944     assert(position.node!=head);
00945     assert(position.node);
00946 
00947     sibling_iterator aargh=prepend_child(position, value_type());
00948     return replace(aargh, other);
00949     }
00950 
00951 template <class T, class tree_node_allocator>
00952 template <class iter>
00953 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
00954     {
00955     assert(position.node!=head);
00956     assert(position.node);
00957 
00958     iter ret=from;
00959 
00960     while(from!=to) {
00961         insert_subtree(position.end(), from);
00962         ++from;
00963         }
00964     return ret;
00965     }
00966 
00967 template <class T, class tree_node_allocator>
00968 template <class iter>
00969 iter tree<T, tree_node_allocator>::prepend_children(iter position, sibling_iterator from, sibling_iterator to)
00970     {
00971     assert(position.node!=head);
00972     assert(position.node);
00973 
00974     iter ret=from;
00975 
00976     while(from!=to) {
00977         insert_subtree(position.begin(), from);
00978         ++from;
00979         }
00980     return ret;
00981     }
00982 
00983 template <class T, class tree_node_allocator>
00984 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)
00985     {
00986     assert(head->next_sibling==feet);
00987     return insert(iterator(feet), x);
00988     }
00989 
00990 template <class T, class tree_node_allocator>
00991 template <class iter>
00992 iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
00993     {
00994     if(position.node==0) {
00995         position.node=feet; // Backward compatibility: when calling insert on a null node,
00996                             // insert before the feet.
00997         }
00998     tree_node* tmp = alloc_.allocate(1,0);
00999     kp::constructor(&tmp->data, x);
01000     tmp->first_child=0;
01001     tmp->last_child=0;
01002 
01003     tmp->parent=position.node->parent;
01004     tmp->next_sibling=position.node;
01005     tmp->prev_sibling=position.node->prev_sibling;
01006     position.node->prev_sibling=tmp;
01007 
01008     if(tmp->prev_sibling==0) {
01009         if(tmp->parent) // when inserting nodes at the head, there is no parent
01010             tmp->parent->first_child=tmp;
01011         }
01012     else
01013         tmp->prev_sibling->next_sibling=tmp;
01014     return tmp;
01015     }
01016 
01017 template <class T, class tree_node_allocator>
01018 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
01019     {
01020     tree_node* tmp = alloc_.allocate(1,0);
01021     kp::constructor(&tmp->data, x);
01022     tmp->first_child=0;
01023     tmp->last_child=0;
01024 
01025     tmp->next_sibling=position.node;
01026     if(position.node==0) { // iterator points to end of a subtree
01027         tmp->parent=position.parent_;
01028         tmp->prev_sibling=position.range_last();
01029         tmp->parent->last_child=tmp;
01030         }
01031     else {
01032         tmp->parent=position.node->parent;
01033         tmp->prev_sibling=position.node->prev_sibling;
01034         position.node->prev_sibling=tmp;
01035         }
01036 
01037     if(tmp->prev_sibling==0) {
01038         if(tmp->parent) // when inserting nodes at the head, there is no parent
01039             tmp->parent->first_child=tmp;
01040         }
01041     else
01042         tmp->prev_sibling->next_sibling=tmp;
01043     return tmp;
01044     }
01045 
01046 template <class T, class tree_node_allocator>
01047 template <class iter>
01048 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
01049     {
01050     tree_node* tmp = alloc_.allocate(1,0);
01051     kp::constructor(&tmp->data, x);
01052     tmp->first_child=0;
01053     tmp->last_child=0;
01054 
01055     tmp->parent=position.node->parent;
01056     tmp->prev_sibling=position.node;
01057     tmp->next_sibling=position.node->next_sibling;
01058     position.node->next_sibling=tmp;
01059 
01060     if(tmp->next_sibling==0) {
01061         if(tmp->parent) // when inserting nodes at the head, there is no parent
01062             tmp->parent->last_child=tmp;
01063         }
01064     else {
01065         tmp->next_sibling->prev_sibling=tmp;
01066         }
01067     return tmp;
01068     }
01069 
01070 template <class T, class tree_node_allocator>
01071 template <class iter>
01072 iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
01073     {
01074     // insert dummy
01075     iter it=insert(position, value_type());
01076     // replace dummy with subtree
01077     return replace(it, subtree);
01078     }
01079 
01080 template <class T, class tree_node_allocator>
01081 template <class iter>
01082 iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const iterator_base& subtree)
01083     {
01084     // insert dummy
01085     iter it=insert_after(position, value_type());
01086     // replace dummy with subtree
01087     return replace(it, subtree);
01088     }
01089 
01090 // template <class T, class tree_node_allocator>
01091 // template <class iter>
01092 // iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
01093 //  {
01094 //  // insert dummy
01095 //  iter it(insert(position, value_type()));
01096 //  // replace dummy with subtree
01097 //  return replace(it, subtree);
01098 //  }
01099 
01100 template <class T, class tree_node_allocator>
01101 template <class iter>
01102 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
01103     {
01104     kp::destructor(&position.node->data);
01105     kp::constructor(&position.node->data, x);
01106     return position;
01107     }
01108 
01109 template <class T, class tree_node_allocator>
01110 template <class iter>
01111 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
01112     {
01113     assert(position.node!=head);
01114     tree_node *current_from=from.node;
01115     tree_node *start_from=from.node;
01116     tree_node *current_to  =position.node;
01117 
01118     // replace the node at position with head of the replacement tree at from
01119 //  std::cout << "warning!" << position.node << std::endl;
01120     erase_children(position);   
01121 //  std::cout << "no warning!" << std::endl;
01122     tree_node* tmp = alloc_.allocate(1,0);
01123     kp::constructor(&tmp->data, (*from));
01124     tmp->first_child=0;
01125     tmp->last_child=0;
01126     if(current_to->prev_sibling==0) {
01127         if(current_to->parent!=0)
01128             current_to->parent->first_child=tmp;
01129         }
01130     else {
01131         current_to->prev_sibling->next_sibling=tmp;
01132         }
01133     tmp->prev_sibling=current_to->prev_sibling;
01134     if(current_to->next_sibling==0) {
01135         if(current_to->parent!=0)
01136             current_to->parent->last_child=tmp;
01137         }
01138     else {
01139         current_to->next_sibling->prev_sibling=tmp;
01140         }
01141     tmp->next_sibling=current_to->next_sibling;
01142     tmp->parent=current_to->parent;
01143     kp::destructor(&current_to->data);
01144     alloc_.deallocate(current_to,1);
01145     current_to=tmp;
01146     
01147     // only at this stage can we fix 'last'
01148     tree_node *last=from.node->next_sibling;
01149 
01150     pre_order_iterator toit=tmp;
01151     // copy all children
01152     do {
01153         assert(current_from!=0);
01154         if(current_from->first_child != 0) {
01155             current_from=current_from->first_child;
01156             toit=append_child(toit, current_from->data);
01157             }
01158         else {
01159             while(current_from->next_sibling==0 && current_from!=start_from) {
01160                 current_from=current_from->parent;
01161                 toit=parent(toit);
01162                 assert(current_from!=0);
01163                 }
01164             current_from=current_from->next_sibling;
01165             if(current_from!=last) {
01166                 toit=append_child(parent(toit), current_from->data);
01167                 }
01168             }
01169         } while(current_from!=last);
01170 
01171     return current_to;
01172     }
01173 
01174 template <class T, class tree_node_allocator>
01175 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
01176     sibling_iterator orig_begin, 
01177     sibling_iterator orig_end, 
01178     sibling_iterator new_begin, 
01179     sibling_iterator new_end)
01180     {
01181     tree_node *orig_first=orig_begin.node;
01182     tree_node *new_first=new_begin.node;
01183     tree_node *orig_last=orig_first;
01184     while((++orig_begin)!=orig_end)
01185         orig_last=orig_last->next_sibling;
01186     tree_node *new_last=new_first;
01187     while((++new_begin)!=new_end)
01188         new_last=new_last->next_sibling;
01189 
01190     // insert all siblings in new_first..new_last before orig_first
01191     bool first=true;
01192     pre_order_iterator ret;
01193     while(1==1) {
01194         pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
01195         if(first) {
01196             ret=tt;
01197             first=false;
01198             }
01199         if(new_first==new_last)
01200             break;
01201         new_first=new_first->next_sibling;
01202         }
01203 
01204     // erase old range of siblings
01205     bool last=false;
01206     tree_node *next=orig_first;
01207     while(1==1) {
01208         if(next==orig_last) 
01209             last=true;
01210         next=next->next_sibling;
01211         erase((pre_order_iterator)orig_first);
01212         if(last) 
01213             break;
01214         orig_first=next;
01215         }
01216     return ret;
01217     }
01218 
01219 template <class T, class tree_node_allocator>
01220 template <typename iter>
01221 iter tree<T, tree_node_allocator>::flatten(iter position)
01222     {
01223     if(position.node->first_child==0)
01224         return position;
01225 
01226     tree_node *tmp=position.node->first_child;
01227     while(tmp) {
01228         tmp->parent=position.node->parent;
01229         tmp=tmp->next_sibling;
01230         } 
01231     if(position.node->next_sibling) {
01232         position.node->last_child->next_sibling=position.node->next_sibling;
01233         position.node->next_sibling->prev_sibling=position.node->last_child;
01234         }
01235     else {
01236         position.node->parent->last_child=position.node->last_child;
01237         }
01238     position.node->next_sibling=position.node->first_child;
01239     position.node->next_sibling->prev_sibling=position.node;
01240     position.node->first_child=0;
01241     position.node->last_child=0;
01242 
01243     return position;
01244     }
01245 
01246 
01247 template <class T, class tree_node_allocator>
01248 template <typename iter>
01249 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
01250     {
01251     tree_node *first=begin.node;
01252     tree_node *last=first;
01253 
01254     assert(first!=position.node);
01255     
01256     if(begin==end) return begin;
01257     // determine last node
01258     while((++begin)!=end) {
01259         last=last->next_sibling;
01260         }
01261     // move subtree
01262     if(first->prev_sibling==0) {
01263         first->parent->first_child=last->next_sibling;
01264         }
01265     else {
01266         first->prev_sibling->next_sibling=last->next_sibling;
01267         }
01268     if(last->next_sibling==0) {
01269         last->parent->last_child=first->prev_sibling;
01270         }
01271     else {
01272         last->next_sibling->prev_sibling=first->prev_sibling;
01273         }
01274     if(position.node->first_child==0) {
01275         position.node->first_child=first;
01276         position.node->last_child=last;
01277         first->prev_sibling=0;
01278         }
01279     else {
01280         position.node->last_child->next_sibling=first;
01281         first->prev_sibling=position.node->last_child;
01282         position.node->last_child=last;
01283         }
01284     last->next_sibling=0;
01285 
01286     tree_node *pos=first;
01287    for(;;) {
01288         pos->parent=position.node;
01289         if(pos==last) break;
01290         pos=pos->next_sibling;
01291         }
01292 
01293     return first;
01294     }
01295 
01296 template <class T, class tree_node_allocator>
01297 template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
01298     {
01299     if(from.node->first_child==0) return position;
01300     return reparent(position, from.node->first_child, end(from));
01301     }
01302 
01303 template <class T, class tree_node_allocator>
01304 template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter position, const T& x)
01305     {
01306     assert(position.node!=0);
01307     sibling_iterator fr=position, to=position;
01308     ++to;
01309     iter ret = insert(position, x);
01310     reparent(ret, fr, to);
01311     return ret;
01312     }
01313 
01314 template <class T, class tree_node_allocator>
01315 template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
01316    {
01317    tree_node *dst=target.node;
01318    tree_node *src=source.node;
01319    assert(dst);
01320    assert(src);
01321 
01322    if(dst==src) return source;
01323     if(dst->next_sibling)
01324         if(dst->next_sibling==src) // already in the right spot
01325             return source;
01326 
01327    // take src out of the tree
01328    if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01329    else                     src->parent->first_child=src->next_sibling;
01330    if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01331    else                     src->parent->last_child=src->prev_sibling;
01332 
01333    // connect it to the new point
01334    if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
01335    else                     dst->parent->last_child=src;
01336    src->next_sibling=dst->next_sibling;
01337    dst->next_sibling=src;
01338    src->prev_sibling=dst;
01339    src->parent=dst->parent;
01340    return src;
01341    }
01342 
01343 template <class T, class tree_node_allocator>
01344 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
01345    {
01346    tree_node *dst=target.node;
01347    tree_node *src=source.node;
01348    assert(dst);
01349    assert(src);
01350 
01351    if(dst==src) return source;
01352     if(dst->prev_sibling)
01353         if(dst->prev_sibling==src) // already in the right spot
01354             return source;
01355 
01356    // take src out of the tree
01357    if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01358    else                     src->parent->first_child=src->next_sibling;
01359    if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01360    else                     src->parent->last_child=src->prev_sibling;
01361 
01362    // connect it to the new point
01363    if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
01364    else                     dst->parent->first_child=src;
01365    src->prev_sibling=dst->prev_sibling;
01366    dst->prev_sibling=src;
01367    src->next_sibling=dst;
01368    src->parent=dst->parent;
01369    return src;
01370    }
01371 
01372 // specialisation for sibling_iterators
01373 template <class T, class tree_node_allocator>
01374 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::move_before(sibling_iterator target, 
01375                                                                                                                       sibling_iterator source)
01376     {
01377     tree_node *dst=target.node;
01378     tree_node *src=source.node;
01379     tree_node *dst_prev_sibling;
01380     if(dst==0) { // must then be an end iterator
01381         dst_prev_sibling=target.parent_->last_child;
01382         assert(dst_prev_sibling);
01383         }
01384     else dst_prev_sibling=dst->prev_sibling;
01385     assert(src);
01386 
01387     if(dst==src) return source;
01388     if(dst_prev_sibling)
01389         if(dst_prev_sibling==src) // already in the right spot
01390             return source;
01391 
01392     // take src out of the tree
01393     if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01394     else                     src->parent->first_child=src->next_sibling;
01395     if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01396     else                     src->parent->last_child=src->prev_sibling;
01397 
01398     // connect it to the new point
01399     if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
01400     else                    target.parent_->first_child=src;
01401     src->prev_sibling=dst_prev_sibling;
01402     if(dst) {
01403         dst->prev_sibling=src;
01404         src->parent=dst->parent;
01405         }
01406     src->next_sibling=dst;
01407     return src;
01408     }
01409 
01410 template <class T, class tree_node_allocator>
01411 template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
01412     {
01413     tree_node *dst=target.node;
01414     tree_node *src=source.node;
01415     assert(dst);
01416     assert(src);
01417 
01418     if(dst==src) return source;
01419 
01420     // remember connection points
01421     tree_node *b_prev_sibling=dst->prev_sibling;
01422     tree_node *b_next_sibling=dst->next_sibling;
01423     tree_node *b_parent=dst->parent;
01424 
01425     // remove target
01426     erase(target);
01427 
01428     // take src out of the tree
01429     if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01430     else                     src->parent->first_child=src->next_sibling;
01431     if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01432     else                     src->parent->last_child=src->prev_sibling;
01433 
01434     // connect it to the new point
01435     if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
01436     else                  b_parent->first_child=src;
01437     if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
01438     else                  b_parent->last_child=src;
01439     src->prev_sibling=b_prev_sibling;
01440     src->next_sibling=b_next_sibling;
01441     src->parent=b_parent;
01442     return src;
01443     }
01444 
01445 template <class T, class tree_node_allocator>
01446 void tree<T, tree_node_allocator>::merge(sibling_iterator to1,   sibling_iterator to2,
01447                                                         sibling_iterator from1, sibling_iterator from2,
01448                                                         bool duplicate_leaves)
01449     {
01450     sibling_iterator fnd;
01451     while(from1!=from2) {
01452         if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
01453             if(from1.begin()==from1.end()) { // full depth reached
01454                 if(duplicate_leaves)
01455                     append_child(parent(to1), (*from1));
01456                 }
01457             else { // descend further
01458                 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
01459                 }
01460             }
01461         else { // element missing
01462             insert_subtree(to2, from1);
01463             }
01464         ++from1;
01465         }
01466     }
01467 
01468 
01469 template <class T, class tree_node_allocator>
01470 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
01471     {
01472     std::less<T> comp;
01473     sort(from, to, comp, deep);
01474     }
01475 
01476 template <class T, class tree_node_allocator>
01477 template <class StrictWeakOrdering>
01478 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, 
01479                                                      StrictWeakOrdering comp, bool deep)
01480     {
01481     if(from==to) return;
01482     // make list of sorted nodes
01483     // CHECK: if multiset stores equivalent nodes in the order in which they
01484     // are inserted, then this routine should be called 'stable_sort'.
01485     std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
01486     sibling_iterator it=from, it2=to;
01487     while(it != to) {
01488         nodes.insert(it.node);
01489         ++it;
01490         }
01491     // reassemble
01492     --it2;
01493 
01494     // prev and next are the nodes before and after the sorted range
01495     tree_node *prev=from.node->prev_sibling;
01496     tree_node *next=it2.node->next_sibling;
01497     typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
01498     if(prev==0) {
01499         if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
01500             (*nit)->parent->first_child=(*nit);
01501         }
01502     else prev->next_sibling=(*nit);
01503 
01504     --eit;
01505     while(nit!=eit) {
01506         (*nit)->prev_sibling=prev;
01507         if(prev)
01508             prev->next_sibling=(*nit);
01509         prev=(*nit);
01510         ++nit;
01511         }
01512     // prev now points to the last-but-one node in the sorted range
01513     if(prev)
01514         prev->next_sibling=(*eit);
01515 
01516     // eit points to the last node in the sorted range.
01517     (*eit)->next_sibling=next;
01518    (*eit)->prev_sibling=prev; // missed in the loop above
01519     if(next==0) {
01520         if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
01521             (*eit)->parent->last_child=(*eit);
01522         }
01523     else next->prev_sibling=(*eit);
01524 
01525     if(deep) {  // sort the children of each node too
01526         sibling_iterator bcs(*nodes.begin());
01527         sibling_iterator ecs(*eit);
01528         ++ecs;
01529         while(bcs!=ecs) {
01530             sort(begin(bcs), end(bcs), comp, deep);
01531             ++bcs;
01532             }
01533         }
01534     }
01535 
01536 template <class T, class tree_node_allocator>
01537 template <typename iter>
01538 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
01539     {
01540     std::equal_to<T> comp;
01541     return equal(one_, two, three_, comp);
01542     }
01543 
01544 template <class T, class tree_node_allocator>
01545 template <typename iter>
01546 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
01547     {
01548     std::equal_to<T> comp;
01549     return equal_subtree(one_, two_, comp);
01550     }
01551 
01552 template <class T, class tree_node_allocator>
01553 template <typename iter, class BinaryPredicate>
01554 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
01555     {
01556     pre_order_iterator one(one_), three(three_);
01557 
01558 //  if(one==two && is_valid(three) && three.number_of_children()!=0)
01559 //      return false;
01560     while(one!=two && is_valid(three)) {
01561         if(!fun(*one,*three))
01562             return false;
01563         if(one.number_of_children()!=three.number_of_children()) 
01564             return false;
01565         ++one;
01566         ++three;
01567         }
01568     return true;
01569     }
01570 
01571 template <class T, class tree_node_allocator>
01572 template <typename iter, class BinaryPredicate>
01573 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
01574     {
01575     pre_order_iterator one(one_), two(two_);
01576 
01577     if(!fun(*one,*two)) return false;
01578     if(number_of_children(one)!=number_of_children(two)) return false;
01579     return equal(begin(one),end(one),begin(two),fun);
01580     }
01581 
01582 template <class T, class tree_node_allocator>
01583 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
01584     {
01585     tree tmp;
01586     tmp.set_head(value_type());
01587     tmp.replace(tmp.begin(), tmp.end(), from, to);
01588     return tmp;
01589     }
01590 
01591 template <class T, class tree_node_allocator>
01592 void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
01593     {
01594     tmp.set_head(value_type());
01595     tmp.replace(tmp.begin(), tmp.end(), from, to);
01596     }
01597 
01598 template <class T, class tree_node_allocator>
01599 size_t tree<T, tree_node_allocator>::size() const
01600     {
01601     size_t i=0;
01602     pre_order_iterator it=begin(), eit=end();
01603     while(it!=eit) {
01604         ++i;
01605         ++it;
01606         }
01607     return i;
01608     }
01609 
01610 template <class T, class tree_node_allocator>
01611 size_t tree<T, tree_node_allocator>::size(const iterator_base& top) const
01612     {
01613     size_t i=0;
01614     pre_order_iterator it=top, eit=top;
01615     eit.skip_children();
01616     ++eit;
01617     while(it!=eit) {
01618         ++i;
01619         ++it;
01620         }
01621     return i;
01622     }
01623 
01624 template <class T, class tree_node_allocator>
01625 bool tree<T, tree_node_allocator>::empty() const
01626     {
01627     pre_order_iterator it=begin(), eit=end();
01628     return (it==eit);
01629     }
01630 
01631 template <class T, class tree_node_allocator>
01632 int tree<T, tree_node_allocator>::depth(const iterator_base& it) 
01633     {
01634     tree_node* pos=it.node;
01635     assert(pos!=0);
01636     int ret=0;
01637     while(pos->parent!=0) {
01638         pos=pos->parent;
01639         ++ret;
01640         }
01641     return ret;
01642     }
01643 
01644 template <class T, class tree_node_allocator>
01645 int tree<T, tree_node_allocator>::depth(const iterator_base& it, const iterator_base& root) 
01646     {
01647     tree_node* pos=it.node;
01648     assert(pos!=0);
01649     int ret=0;
01650     while(pos->parent!=0 && pos!=root.node) {
01651         pos=pos->parent;
01652         ++ret;
01653         }
01654     return ret;
01655     }
01656 
01657 template <class T, class tree_node_allocator>
01658 int tree<T, tree_node_allocator>::max_depth() const
01659     {
01660     int maxd=-1;
01661     for(tree_node *it = head->next_sibling; it!=feet; it=it->next_sibling)
01662         maxd=std::max(maxd, max_depth(it));
01663 
01664     return maxd;
01665     }
01666 
01667 
01668 template <class T, class tree_node_allocator>
01669 int tree<T, tree_node_allocator>::max_depth(const iterator_base& pos) const
01670     {
01671     tree_node *tmp=pos.node;
01672 
01673     if(tmp==0 || tmp==head || tmp==feet) return -1;
01674 
01675     int curdepth=0, maxdepth=0;
01676     while(true) { // try to walk the bottom of the tree
01677         while(tmp->first_child==0) {
01678             if(tmp==pos.node) return maxdepth;
01679             if(tmp->next_sibling==0) {
01680                 // try to walk up and then right again
01681                 do {
01682                     tmp=tmp->parent;
01683                if(tmp==0) return maxdepth;
01684                --curdepth;
01685                    } while(tmp->next_sibling==0);
01686                 }
01687          if(tmp==pos.node) return maxdepth;
01688             tmp=tmp->next_sibling;
01689             }
01690         tmp=tmp->first_child;
01691         ++curdepth;
01692         maxdepth=std::max(curdepth, maxdepth);
01693         } 
01694     }
01695 
01696 template <class T, class tree_node_allocator>
01697 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it) 
01698     {
01699     tree_node *pos=it.node->first_child;
01700     if(pos==0) return 0;
01701     
01702     unsigned int ret=1;
01703 //    while(pos!=it.node->last_child) {
01704 //        ++ret;
01705 //        pos=pos->next_sibling;
01706 //        }
01707     while((pos=pos->next_sibling))
01708         ++ret;
01709     return ret;
01710     }
01711 
01712 template <class T, class tree_node_allocator>
01713 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
01714     {
01715     tree_node *pos=it.node;
01716     unsigned int ret=0;
01717     // count forward
01718     while(pos->next_sibling && 
01719             pos->next_sibling!=head &&
01720             pos->next_sibling!=feet) {
01721         ++ret;
01722         pos=pos->next_sibling;
01723         }
01724     // count backward
01725     pos=it.node;
01726     while(pos->prev_sibling && 
01727             pos->prev_sibling!=head &&
01728             pos->prev_sibling!=feet) {
01729         ++ret;
01730         pos=pos->prev_sibling;
01731         }
01732     
01733     return ret;
01734     }
01735 
01736 template <class T, class tree_node_allocator>
01737 void tree<T, tree_node_allocator>::swap(sibling_iterator it)
01738     {
01739     tree_node *nxt=it.node->next_sibling;
01740     if(nxt) {
01741         if(it.node->prev_sibling)
01742             it.node->prev_sibling->next_sibling=nxt;
01743         else
01744             it.node->parent->first_child=nxt;
01745         nxt->prev_sibling=it.node->prev_sibling;
01746         tree_node *nxtnxt=nxt->next_sibling;
01747         if(nxtnxt)
01748             nxtnxt->prev_sibling=it.node;
01749         else
01750             it.node->parent->last_child=it.node;
01751         nxt->next_sibling=it.node;
01752         it.node->prev_sibling=nxt;
01753         it.node->next_sibling=nxtnxt;
01754         }
01755     }
01756 
01757 template <class T, class tree_node_allocator>
01758 void tree<T, tree_node_allocator>::swap(iterator one, iterator two)
01759     {
01760     // if one and two are adjacent siblings, use the sibling swap
01761     if(one.node->next_sibling==two.node) swap(one);
01762     else if(two.node->next_sibling==one.node) swap(two);
01763     else {
01764         tree_node *nxt1=one.node->next_sibling;
01765         tree_node *nxt2=two.node->next_sibling;
01766         tree_node *pre1=one.node->prev_sibling;
01767         tree_node *pre2=two.node->prev_sibling;
01768         tree_node *par1=one.node->parent;
01769         tree_node *par2=two.node->parent;
01770 
01771         // reconnect
01772         one.node->parent=par2;
01773         one.node->next_sibling=nxt2;
01774         if(nxt2) nxt2->prev_sibling=one.node;
01775         else     par2->last_child=one.node;
01776         one.node->prev_sibling=pre2;
01777         if(pre2) pre2->next_sibling=one.node;
01778         else     par2->first_child=one.node;    
01779 
01780         two.node->parent=par1;
01781         two.node->next_sibling=nxt1;
01782         if(nxt1) nxt1->prev_sibling=two.node;
01783         else     par1->last_child=two.node;
01784         two.node->prev_sibling=pre1;
01785         if(pre1) pre1->next_sibling=two.node;
01786         else     par1->first_child=two.node;
01787         }
01788     }
01789 
01790 // template <class BinaryPredicate>
01791 // tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
01792 //  sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to, 
01793 //  BinaryPredicate fun) const
01794 //  {
01795 //  assert(1==0); // this routine is not finished yet.
01796 //  while(from!=to) {
01797 //      if(fun(*subfrom, *from)) {
01798 //          
01799 //          }
01800 //      }
01801 //  return to;
01802 //  }
01803 
01804 template <class T, class tree_node_allocator>
01805 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin, 
01806                                                                  const iterator_base& end) const
01807     {
01808     // FIXME: this should be optimised.
01809     pre_order_iterator tmp=begin;
01810     while(tmp!=end) {
01811         if(tmp==it) return true;
01812         ++tmp;
01813         }
01814     return false;
01815     }
01816 
01817 template <class T, class tree_node_allocator>
01818 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
01819     {
01820     if(it.node==0 || it.node==feet || it.node==head) return false;
01821     else return true;
01822     }
01823 
01824 template <class T, class tree_node_allocator>
01825 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
01826     {
01827     unsigned int ind=0;
01828     if(it.node->parent==0) {
01829         while(it.node->prev_sibling!=head) {
01830             it.node=it.node->prev_sibling;
01831             ++ind;
01832             }
01833         }
01834     else {
01835         while(it.node->prev_sibling!=0) {
01836             it.node=it.node->prev_sibling;
01837             ++ind;
01838             }
01839         }
01840     return ind;
01841     }
01842 
01843 template <class T, class tree_node_allocator>
01844 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling(const iterator_base& it, unsigned int num)
01845    {
01846    tree_node *tmp;
01847    if(it.node->parent==0) {
01848       tmp=head->next_sibling;
01849       while(num) {
01850          tmp = tmp->next_sibling;
01851          --num;
01852          }
01853       }
01854    else {
01855       tmp=it.node->parent->first_child;
01856       while(num) {
01857          assert(tmp!=0);
01858          tmp = tmp->next_sibling;
01859          --num;
01860          }
01861       }
01862    return tmp;
01863    }
01864  
01865 
01866 template <class T, class tree_node_allocator>
01867 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num) 
01868     {
01869     tree_node *tmp=it.node->first_child;
01870     while(num--) {
01871         assert(tmp!=0);
01872         tmp=tmp->next_sibling;
01873         }
01874     return tmp;
01875     }
01876 
01877 
01878 
01879 
01880 // Iterator base
01881 
01882 template <class T, class tree_node_allocator>
01883 tree<T, tree_node_allocator>::iterator_base::iterator_base()
01884     : node(0), skip_current_children_(false)
01885     {
01886     }
01887 
01888 template <class T, class tree_node_allocator>
01889 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
01890     : node(tn), skip_current_children_(false)
01891     {
01892     }
01893 
01894 template <class T, class tree_node_allocator>
01895 T& tree<T, tree_node_allocator>::iterator_base::operator*() const
01896     {
01897     return node->data;
01898     }
01899 
01900 template <class T, class tree_node_allocator>
01901 T* tree<T, tree_node_allocator>::iterator_base::operator->() const
01902     {
01903     return &(node->data);
01904     }
01905 
01906 template <class T, class tree_node_allocator>
01907 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
01908     {
01909     if(other.node!=this->node) return true;
01910     else return false;
01911     }
01912 
01913 template <class T, class tree_node_allocator>
01914 bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
01915     {
01916     if(other.node==this->node) return true;
01917     else return false;
01918     }
01919 
01920 template <class T, class tree_node_allocator>
01921 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
01922     {
01923     if(other.node!=this->node) return true;
01924     else return false;
01925     }
01926 
01927 template <class T, class tree_node_allocator>
01928 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
01929     {
01930     if(other.node==this->node) return true;
01931     else return false;
01932     }
01933 
01934 template <class T, class tree_node_allocator>
01935 bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
01936     {
01937     if(other.node!=this->node) return true;
01938     else return false;
01939     }
01940 
01941 template <class T, class tree_node_allocator>
01942 bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
01943     {
01944     if(other.node==this->node) return true;
01945     else return false;
01946     }
01947 
01948 template <class T, class tree_node_allocator>
01949 bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_iterator& other) const
01950    {
01951    if(other.node!=this->node) return true;
01952    else return false;
01953    }
01954 
01955 template <class T, class tree_node_allocator>
01956 bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const leaf_iterator& other) const
01957    {
01958    if(other.node==this->node && other.top_node==this->top_node) return true;
01959    else return false;
01960    }
01961 
01962 template <class T, class tree_node_allocator>
01963 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const
01964     {
01965     if(node->first_child==0) 
01966         return end();
01967 
01968     sibling_iterator ret(node->first_child);
01969     ret.parent_=this->node;
01970     return ret;
01971     }
01972 
01973 template <class T, class tree_node_allocator>
01974 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const
01975     {
01976     sibling_iterator ret(0);
01977     ret.parent_=node;
01978     return ret;
01979     }
01980 
01981 template <class T, class tree_node_allocator>
01982 void tree<T, tree_node_allocator>::iterator_base::skip_children()
01983     {
01984     skip_current_children_=true;
01985     }
01986 
01987 template <class T, class tree_node_allocator>
01988 void tree<T, tree_node_allocator>::iterator_base::skip_children(bool skip)
01989    {
01990    skip_current_children_=skip;
01991    }
01992 
01993 template <class T, class tree_node_allocator>
01994 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
01995     {
01996     tree_node *pos=node->first_child;
01997     if(pos==0) return 0;
01998     
01999     unsigned int ret=1;
02000     while(pos!=node->last_child) {
02001         ++ret;
02002         pos=pos->next_sibling;
02003         }
02004     return ret;
02005     }
02006 
02007 
02008 
02009 // Pre-order iterator
02010 
02011 template <class T, class tree_node_allocator>
02012 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator() 
02013     : iterator_base(0)
02014     {
02015     }
02016 
02017 template <class T, class tree_node_allocator>
02018 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
02019     : iterator_base(tn)
02020     {
02021     }
02022 
02023 template <class T, class tree_node_allocator>
02024 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)
02025     : iterator_base(other.node)
02026     {
02027     }
02028 
02029 template <class T, class tree_node_allocator>
02030 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
02031     : iterator_base(other.node)
02032     {
02033     if(this->node==0) {
02034         if(other.range_last()!=0)
02035             this->node=other.range_last();
02036         else 
02037             this->node=other.parent_;
02038         this->skip_children();
02039         ++(*this);
02040         }
02041     }
02042 
02043 template <class T, class tree_node_allocator>
02044 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
02045     {
02046     assert(this->node!=0);
02047     if(!this->skip_current_children_ && this->node->first_child != 0) {
02048         this->node=this->node->first_child;
02049         }
02050     else {
02051         this->skip_current_children_=false;
02052         while(this->node->next_sibling==0) {
02053             this->node=this->node->parent;
02054             if(this->node==0)
02055                 return *this;
02056             }
02057         this->node=this->node->next_sibling;
02058         }
02059     return *this;
02060     }
02061 
02062 template <class T, class tree_node_allocator>
02063 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
02064     {
02065     assert(this->node!=0);
02066     if(this->node->prev_sibling) {
02067         this->node=this->node->prev_sibling;
02068         while(this->node->last_child)
02069             this->node=this->node->last_child;
02070         }
02071     else {
02072         this->node=this->node->parent;
02073         if(this->node==0)
02074             return *this;
02075         }
02076     return *this;
02077 }
02078 
02079 template <class T, class tree_node_allocator>
02080 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int)
02081     {
02082     pre_order_iterator copy = *this;
02083     ++(*this);
02084     return copy;
02085     }
02086 
02087 template <class T, class tree_node_allocator>
02088 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int)
02089 {
02090   pre_order_iterator copy = *this;
02091   --(*this);
02092   return copy;
02093 }
02094 
02095 template <class T, class tree_node_allocator>
02096 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
02097     {
02098     while(num>0) {
02099         ++(*this);
02100         --num;
02101         }
02102     return (*this);
02103     }
02104 
02105 template <class T, class tree_node_allocator>
02106 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
02107     {
02108     while(num>0) {
02109         --(*this);
02110         --num;
02111         }
02112     return (*this);
02113     }
02114 
02115 
02116 
02117 // Post-order iterator
02118 
02119 template <class T, class tree_node_allocator>
02120 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator() 
02121     : iterator_base(0)
02122     {
02123     }
02124 
02125 template <class T, class tree_node_allocator>
02126 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
02127     : iterator_base(tn)
02128     {
02129     }
02130 
02131 template <class T, class tree_node_allocator>
02132 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)
02133     : iterator_base(other.node)
02134     {
02135     }
02136 
02137 template <class T, class tree_node_allocator>
02138 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)
02139     : iterator_base(other.node)
02140     {
02141     if(this->node==0) {
02142         if(other.range_last()!=0)
02143             this->node=other.range_last();
02144         else 
02145             this->node=other.parent_;
02146         this->skip_children();
02147         ++(*this);
02148         }
02149     }
02150 
02151 template <class T, class tree_node_allocator>
02152 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
02153     {
02154     assert(this->node!=0);
02155     if(this->node->next_sibling==0) {
02156         this->node=this->node->parent;
02157         this->skip_current_children_=false;
02158         }
02159     else {
02160         this->node=this->node->next_sibling;
02161         if(this->skip_current_children_) {
02162             this->skip_current_children_=false;
02163             }
02164         else {
02165             while(this->node->first_child)
02166                 this->node=this->node->first_child;
02167             }
02168         }
02169     return *this;
02170     }
02171 
02172 template <class T, class tree_node_allocator>
02173 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
02174     {
02175     assert(this->node!=0);
02176     if(this->skip_current_children_ || this->node->last_child==0) {
02177         this->skip_current_children_=false;
02178         while(this->node->prev_sibling==0)
02179             this->node=this->node->parent;
02180         this->node=this->node->prev_sibling;
02181         }
02182     else {
02183         this->node=this->node->last_child;
02184         }
02185     return *this;
02186     }
02187 
02188 template <class T, class tree_node_allocator>
02189 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
02190     {
02191     post_order_iterator copy = *this;
02192     ++(*this);
02193     return copy;
02194     }
02195 
02196 template <class T, class tree_node_allocator>
02197 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
02198     {
02199     post_order_iterator copy = *this;
02200     --(*this);
02201     return copy;
02202     }
02203 
02204 
02205 template <class T, class tree_node_allocator>
02206 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
02207     {
02208     while(num>0) {
02209         ++(*this);
02210         --num;
02211         }
02212     return (*this);
02213     }
02214 
02215 template <class T, class tree_node_allocator>
02216 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
02217     {
02218     while(num>0) {
02219         --(*this);
02220         --num;
02221         }
02222     return (*this);
02223     }
02224 
02225 template <class T, class tree_node_allocator>
02226 void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
02227     {
02228     assert(this->node!=0);
02229     while(this->node->first_child)
02230         this->node=this->node->first_child;
02231     }
02232 
02233 
02234 // Breadth-first iterator
02235 
02236 template <class T, class tree_node_allocator>
02237 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()
02238     : iterator_base()
02239     {
02240     }
02241 
02242 template <class T, class tree_node_allocator>
02243 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node *tn)
02244     : iterator_base(tn)
02245     {
02246     traversal_queue.push(tn);
02247     }
02248 
02249 template <class T, class tree_node_allocator>
02250 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const iterator_base& other)
02251     : iterator_base(other.node)
02252     {
02253     traversal_queue.push(other.node);
02254     }
02255 
02256 template <class T, class tree_node_allocator>
02257 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=(const breadth_first_queued_iterator& other) const
02258     {
02259     if(other.node!=this->node) return true;
02260     else return false;
02261     }
02262 
02263 template <class T, class tree_node_allocator>
02264 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==(const breadth_first_queued_iterator& other) const
02265     {
02266     if(other.node==this->node) return true;
02267     else return false;
02268     }
02269 
02270 template <class T, class tree_node_allocator>
02271 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++()
02272     {
02273     assert(this->node!=0);
02274 
02275     // Add child nodes and pop current node
02276     sibling_iterator sib=this->begin();
02277     while(sib!=this->end()) {
02278         traversal_queue.push(sib.node);
02279         ++sib;
02280         }
02281     traversal_queue.pop();
02282     if(traversal_queue.size()>0)
02283         this->node=traversal_queue.front();
02284     else 
02285         this->node=0;
02286     return (*this);
02287     }
02288 
02289 template <class T, class tree_node_allocator>
02290 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++(int)
02291     {
02292     breadth_first_queued_iterator copy = *this;
02293     ++(*this);
02294     return copy;
02295     }
02296 
02297 template <class T, class tree_node_allocator>
02298 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num)
02299     {
02300     while(num>0) {
02301         ++(*this);
02302         --num;
02303         }
02304     return (*this);
02305     }
02306 
02307 
02308 
02309 // Fixed depth iterator
02310 
02311 template <class T, class tree_node_allocator>
02312 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
02313     : iterator_base()
02314     {
02315     }
02316 
02317 template <class T, class tree_node_allocator>
02318 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
02319     : iterator_base(tn), top_node(0)
02320     {
02321     }
02322 
02323 template <class T, class tree_node_allocator>
02324 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)
02325     : iterator_base(other.node), top_node(0)
02326     {
02327     }
02328 
02329 template <class T, class tree_node_allocator>
02330 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
02331     : iterator_base(other.node), top_node(0)
02332     {
02333     }
02334 
02335 template <class T, class tree_node_allocator>
02336 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)
02337     : iterator_base(other.node), top_node(other.top_node)
02338     {
02339     }
02340 
02341 template <class T, class tree_node_allocator>
02342 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==(const fixed_depth_iterator& other) const
02343     {
02344     if(other.node==this->node && other.top_node==top_node) return true;
02345     else return false;
02346     }
02347 
02348 template <class T, class tree_node_allocator>
02349 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=(const fixed_depth_iterator& other) const
02350     {
02351     if(other.node!=this->node || other.top_node!=top_node) return true;
02352     else return false;
02353     }
02354 
02355 template <class T, class tree_node_allocator>
02356 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
02357     {
02358     assert(this->node!=0);
02359 
02360     if(this->node->next_sibling) {
02361         this->node=this->node->next_sibling;
02362         }
02363     else { 
02364         int relative_depth=0;
02365        upper:
02366         do {
02367             if(this->node==this->top_node) {
02368                 this->node=0; // FIXME: return a proper fixed_depth end iterator once implemented
02369                 return *this;
02370                 }
02371             this->node=this->node->parent;
02372             if(this->node==0) return *this;
02373             --relative_depth;
02374             } while(this->node->next_sibling==0);
02375        lower:
02376         this->node=this->node->next_sibling;
02377         while(this->node->first_child==0) {
02378             if(this->node->next_sibling==0)
02379                 goto upper;
02380             this->node=this->node->next_sibling;
02381             if(this->node==0) return *this;
02382             }
02383         while(relative_depth<0 && this->node->first_child!=0) {
02384             this->node=this->node->first_child;
02385             ++relative_depth;
02386             }
02387         if(relative_depth<0) {
02388             if(this->node->next_sibling==0) goto upper;
02389             else                          goto lower;
02390             }
02391         }
02392     return *this;
02393     }
02394 
02395 template <class T, class tree_node_allocator>
02396 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
02397     {
02398     assert(this->node!=0);
02399 
02400     if(this->node->prev_sibling) {
02401         this->node=this->node->prev_sibling;
02402         }
02403     else { 
02404         int relative_depth=0;
02405        upper:
02406         do {
02407             if(this->node==this->top_node) {
02408                 this->node=0;
02409                 return *this;
02410                 }
02411             this->node=this->node->parent;
02412             if(this->node==0) return *this;
02413             --relative_depth;
02414             } while(this->node->prev_sibling==0);
02415        lower:
02416         this->node=this->node->prev_sibling;
02417         while(this->node->last_child==0) {
02418             if(this->node->prev_sibling==0)
02419                 goto upper;
02420             this->node=this->node->prev_sibling;
02421             if(this->node==0) return *this;
02422             }
02423         while(relative_depth<0 && this->node->last_child!=0) {
02424             this->node=this->node->last_child;
02425             ++relative_depth;
02426             }
02427         if(relative_depth<0) {
02428             if(this->node->prev_sibling==0) goto upper;
02429             else                            goto lower;
02430             }
02431         }
02432     return *this;
02433 
02434 //
02435 //
02436 //  assert(this->node!=0);
02437 //  if(this->node->prev_sibling!=0) {
02438 //      this->node=this->node->prev_sibling;
02439 //      assert(this->node!=0);
02440 //      if(this->node->parent==0 && this->node->prev_sibling==0) // head element
02441 //          this->node=0;
02442 //      }
02443 //  else {
02444 //      tree_node *par=this->node->parent;
02445 //      do {
02446 //          par=par->prev_sibling;
02447 //          if(par==0) { // FIXME: need to keep track of this!
02448 //              this->node=0;
02449 //              return *this;
02450 //              }
02451 //          } while(par->last_child==0);
02452 //      this->node=par->last_child;
02453 //      }
02454 //  return *this;
02455     }
02456 
02457 template <class T, class tree_node_allocator>
02458 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)
02459     {
02460     fixed_depth_iterator copy = *this;
02461     ++(*this);
02462     return copy;
02463     }
02464 
02465 template <class T, class tree_node_allocator>
02466 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)
02467    {
02468     fixed_depth_iterator copy = *this;
02469     --(*this);
02470     return copy;
02471     }
02472 
02473 template <class T, class tree_node_allocator>
02474 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
02475     {
02476     while(num>0) {
02477         --(*this);
02478         --(num);
02479         }
02480     return (*this);
02481     }
02482 
02483 template <class T, class tree_node_allocator>
02484 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
02485     {
02486     while(num>0) {
02487         ++(*this);
02488         --(num);
02489         }
02490     return *this;
02491     }
02492 
02493 
02494 // Sibling iterator
02495 
02496 template <class T, class tree_node_allocator>
02497 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator() 
02498     : iterator_base()
02499     {
02500     set_parent_();
02501     }
02502 
02503 template <class T, class tree_node_allocator>
02504 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
02505     : iterator_base(tn)
02506     {
02507     set_parent_();
02508     }
02509 
02510 template <class T, class tree_node_allocator>
02511 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)
02512     : iterator_base(other.node)
02513     {
02514     set_parent_();
02515     }
02516 
02517 template <class T, class tree_node_allocator>
02518 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)
02519     : iterator_base(other), parent_(other.parent_)
02520     {
02521     }
02522 
02523 template <class T, class tree_node_allocator>
02524 void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
02525     {
02526     parent_=0;
02527     if(this->node==0) return;
02528     if(this->node->parent!=0)
02529         parent_=this->node->parent;
02530     }
02531 
02532 template <class T, class tree_node_allocator>
02533 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
02534     {
02535     if(this->node)
02536         this->node=this->node->next_sibling;
02537     return *this;
02538     }
02539 
02540 template <class T, class tree_node_allocator>
02541 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
02542     {
02543     if(this->node) this->node=this->node->prev_sibling;
02544     else {
02545         assert(parent_);
02546         this->node=parent_->last_child;
02547         }
02548     return *this;
02549 }
02550 
02551 template <class T, class tree_node_allocator>
02552 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)
02553     {
02554     sibling_iterator copy = *this;
02555     ++(*this);
02556     return copy;
02557     }
02558 
02559 template <class T, class tree_node_allocator>
02560 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)
02561     {
02562     sibling_iterator copy = *this;
02563     --(*this);
02564     return copy;
02565     }
02566 
02567 template <class T, class tree_node_allocator>
02568 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
02569     {
02570     while(num>0) {
02571         ++(*this);
02572         --num;
02573         }
02574     return (*this);
02575     }
02576 
02577 template <class T, class tree_node_allocator>
02578 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
02579     {
02580     while(num>0) {
02581         --(*this);
02582         --num;
02583         }
02584     return (*this);
02585     }
02586 
02587 template <class T, class tree_node_allocator>
02588 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const
02589     {
02590     tree_node *tmp=parent_->first_child;
02591     return tmp;
02592     }
02593 
02594 template <class T, class tree_node_allocator>
02595 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const
02596     {
02597     return parent_->last_child;
02598     }
02599 
02600 // Leaf iterator
02601 
02602 template <class T, class tree_node_allocator>
02603 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator() 
02604    : iterator_base(0), top_node(0)
02605    {
02606    }
02607 
02608 template <class T, class tree_node_allocator>
02609 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn, tree_node *top)
02610    : iterator_base(tn), top_node(top)
02611    {
02612    }
02613 
02614 template <class T, class tree_node_allocator>
02615 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base &other)
02616    : iterator_base(other.node), top_node(0)
02617    {
02618    }
02619 
02620 template <class T, class tree_node_allocator>
02621 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const sibling_iterator& other)
02622    : iterator_base(other.node), top_node(0)
02623    {
02624    if(this->node==0) {
02625       if(other.range_last()!=0)
02626          this->node=other.range_last();
02627       else 
02628          this->node=other.parent_;
02629       ++(*this);
02630       }
02631    }
02632 
02633 template <class T, class tree_node_allocator>
02634 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator++()
02635    {
02636     assert(this->node!=0);
02637     if(this->node->first_child!=0) { // current node is no longer leaf (children got added)
02638          while(this->node->first_child) 
02639               this->node=this->node->first_child;
02640          }
02641     else {
02642          while(this->node->next_sibling==0) { 
02643               if (this->node->parent==0) return *this;
02644               this->node=this->node->parent;
02645               if (top_node != 0 && this->node==top_node) return *this;
02646               }
02647          this->node=this->node->next_sibling;
02648          while(this->node->first_child)
02649               this->node=this->node->first_child;
02650          }
02651     return *this;
02652    }
02653 
02654 template <class T, class tree_node_allocator>
02655 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator--()
02656    {
02657     assert(this->node!=0);
02658     while (this->node->prev_sibling==0) {
02659         if (this->node->parent==0) return *this;
02660         this->node=this->node->parent;
02661         if (top_node !=0 && this->node==top_node) return *this; 
02662         }
02663     this->node=this->node->prev_sibling;
02664     while(this->node->last_child)
02665         this->node=this->node->last_child;
02666     return *this;
02667     }
02668 
02669 template <class T, class tree_node_allocator>
02670 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator++(int)
02671    {
02672    leaf_iterator copy = *this;
02673    ++(*this);
02674    return copy;
02675    }
02676 
02677 template <class T, class tree_node_allocator>
02678 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator--(int)
02679    {
02680    leaf_iterator copy = *this;
02681    --(*this);
02682    return copy;
02683    }
02684 
02685 
02686 template <class T, class tree_node_allocator>
02687 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)
02688    {
02689    while(num>0) {
02690       ++(*this);
02691       --num;
02692       }
02693    return (*this);
02694    }
02695 
02696 template <class T, class tree_node_allocator>
02697 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)
02698    {
02699    while(num>0) {
02700       --(*this);
02701       --num;
02702       }
02703    return (*this);
02704    }
02705 
02706 #endif
02707 
02708 // Local variables:
02709 // default-tab-width: 3
02710 // End:

Generated on Fri Aug 12 2011 for liborigin2 by  doxygen 1.7.1