Main Page | Class Hierarchy | Data Structures | File List | Data Fields | Globals

tree.hh

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

Generated on Sun Jul 31 15:38:35 2005 for LibOFX by  doxygen 1.3.9.1