tree.hh

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

Generated on Mon Feb 9 21:22:00 2009 for LibOFX by  doxygen 1.5.0