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