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

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 Thu Sep 30 2010 14:35:04 for Gnash by  doxygen 1.7.1