Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

vgtl_tree.h

Go to the documentation of this file.
00001 // Tree implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2003 Hermann Schichl
00004 //
00005 // This file is part of the Vienna Graph Template Library.  This library
00006 // is free software; you can redistribute it and/or modify it under the
00007 // terms of the Library GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // Library GNU General Public License for more details.
00015 
00016 // As a special exception, you may use this file as part of a free software
00017 // library without restriction.  Specifically, if other files instantiate
00018 // templates or use macros or inline functions from this file, or you compile
00019 // this file and link it with other files to produce an executable, this
00020 // file does not by itself cause the resulting executable to be covered by
00021 // the Library GNU General Public License.  This exception does not however
00022 // invalidate any other reasons why the executable file might be covered by
00023 // the Library GNU General Public License.
00024 
00030 #ifndef __VGTL_TREE_H_
00031 #define __VGTL_TREE_H_
00032 
00033 #include <vector>
00034 #include <list>
00035 #include <multimap>
00036 #include <multiset>
00037 #include <algorithm>
00038 #include <iterator>
00039 #include <string>
00040 #include <utility>
00041 #include <g_data.h>
00042 
00044 #define _C_W_preorder   1
00045 
00046 #define _C_W_postorder  2
00047 
00049 typedef enum {cw_pre = _C_W_preorder, cw_post = _C_W_postorder,
00050               cw_pre_post = _C_W_preorder|_C_W_postorder} walker_type;
00051 
00052 #include <vgtl_helpers.h>
00053 #include <vgtl_intadapt.h>
00054 
00055 __VGTL_BEGIN_NAMESPACE
00056               
00058 
00062 template <class _Tp, class _Ctr, class _Iterator>
00063 class _Tree_node
00064 {
00065 private:
00066   typedef void* _Void_pointer;
00067   typedef _Iterator _Ctr_iterator;
00068   typedef _Tree_node<_Tp,_Ctr,_Iterator> _Self;
00069 
00070 public:
00072   _Tp _C_data;
00074   _Void_pointer _C_parent;
00076   _Ctr _C_children;
00077 
00079   _Tree_node() { _C_data();
00080                   __VGTL_TRY {
00081                     initialize();
00082                   }
00083                   __VGTL_UNWIND( );
00084                 }
00085 
00087   void initialize() {
00088       std::_Construct(&_C_children);
00089       _C_parent = NULL;
00090     }
00091   
00093   void get_rid_of() {
00094       std::_Destroy(&_C_children);
00095     }
00096 
00098   void clear_tree();
00100   void clear_children()
00101         { _C_children.erase(_C_children.begin(), _C_children.end()); }
00102 
00104   _Ctr_iterator get_childentry_iterator(_Void_pointer __p)
00105         { _Ctr_iterator __tmp;
00106           for(__tmp = _C_children.begin(); __tmp != _C_children.end(); ++__tmp)
00107             if(*__tmp == __p) break;
00108           return __tmp;
00109         }
00110 
00111 #ifdef __VGTL_MEMBER_TEMPLATES
00112 
00116   template <class _Output_Iterator>
00117   void add_all_children(_Output_Iterator fi, _Self* _parent);
00118 
00120   template <class Compare>
00121   void sort_children(_Ctr_iterator first, _Ctr_iterator last, Compare comp)
00122   {
00123     sort(first, last, _G_compare_adaptor<Compare, _Self>(comp));
00124   }
00125    
00127   template <class Compare>
00128   void sort_parents(_Ctr_iterator first, _Ctr_iterator last, Compare comp) {}
00129 #endif /* __VGTL_MEMBER_TEMPLATES */
00130 };
00131 
00133 
00137 template <class _Tp, class _Ctr, class _Iterator>
00138 class _ITree_node : public _Tree_node<_Tp,_Ctr,_Iterator>
00139 {
00140 private:
00141   typedef void* _Void_pointer;
00142   typedef _Iterator _Ctr_iterator;
00143   typedef _ITree_node<_Tp,_Ctr,_Iterator> _Self;
00144 
00145 public:
00147   ctree_data_hook _C_data_hook;
00148 
00150   _ITree_node() { _C_data();
00151                   __VGTL_TRY {
00152                     initialize();
00153                   }
00154                   __VGTL_UNWIND( );
00155                 }
00156 
00158   void initialize() {
00159       std::_Construct(&_C_children);
00160       _C_parent = NULL;
00161       _C_data_hook.f = 0;
00162     }
00163   
00165   void get_rid_of() {
00166       std::_Destroy(&_C_children);
00167       std::_Destroy(&_C_data_hook);
00168     }
00169 
00171   ctree_data_hook& data_hook() { return _C_data_hook; }
00172 
00173 };
00174 
00175 #ifdef __VGTL_MEMBER_TEMPLATES
00176 template <class _Tp, class _Ctr, class _Iterator>
00177 template <class _Output_Iterator>
00178 void 
00179 _Tree_node<_Tp,_Ctr,_Iterator>::
00180         add_all_children(_Output_Iterator fi, _Self* _parent)
00181 { _Ctr_iterator it;
00182   for(it = _C_children.begin();
00183       it != _C_children.end();
00184       ++it)
00185   {
00186     *fi++ = *it;
00187     (*((_Self*)*it))._C_parent = _parent;
00188   }
00189 };
00190 #endif /* __VGTL_MEMBER_TEMPLATES */
00191 
00192 // get rid of the subtree
00193 template <class _Tp, class _Ctr, class _Iterator>
00194 void
00195 _Tree_node<_Tp,_Ctr,_Iterator>::clear_tree()
00196 {
00197   _Ctr* chld = &this->_C_children;
00198   _Iterator it;
00199 
00200   for(it = chld->begin(); it != chld->end(); ++it)
00201     ((_Tree_node<_Tp,_Ctr,_Iterator>*)(*it))->clear_tree();
00202   this->_C_children.erase(this->_C_children.begin(), this->_C_children.end());
00203   this->_C_parent = NULL;
00204   
00205   std::_Destroy(&this->_C_data);
00206   get_rid_of();
00207 }
00208 
00209 // forward reference
00210 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00211           class _Node>
00212 class _Tree_iterator;
00213 
00215 
00219 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00220           class _Node>
00221 class _Tree_walker_base
00222 {
00223 public:
00224   typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node>    walker;
00225   typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node>  const_walker;
00226   typedef _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>    _Self;
00227   typedef _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>       _Itr;
00228 
00230 
00231   typedef _Tp value_type;
00232   typedef _Ptr pointer;
00233   typedef _Ref reference;
00235 private:
00236   typedef _Iterator _Ctr_iterator;
00237 
00238 public:
00240 
00241   typedef __one_iterator<void *> parents_iterator;
00242   typedef _Ctr_iterator children_iterator;
00243   typedef _Node node_type;
00244 
00245   typedef size_t size_type;
00246   typedef ptrdiff_t difference_type;
00248 
00249 public:
00251   _Node* _C_w_cur;
00252 
00253 public:
00255   _Tree_walker_base() {}
00256 
00258   _Tree_walker_base(_Node* __x) : _C_w_cur(__x) { }
00259 
00261   _Tree_walker_base(const walker& __x) : _C_w_cur(__x._C_w_cur) {}
00262 
00264   reference operator*() const { return (*_C_w_cur)._C_data; }
00265 
00266 #ifndef __SGI_STL_NO_ARROW_OPERATOR
00267 
00268   pointer operator->() const { return &(operator*()); }
00269 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
00270 
00271 public:
00273   _Self& operator=(const _Itr& __x) {
00274         _C_w_cur = __x._C_i_cur;
00275         return *this;
00276   }
00277 
00279   ctree_data_hook& data_hook() { return (*_C_w_cur)._C_data_hook; }
00281   ctree_data_hook& parent_data_hook()
00282         { return ((_Node*)(*_C_w_cur)._C_parent)->_C_data_hook; }
00283 
00285   const _Node* parent() { return (_Node*)(*_C_w_cur)._C_parent; }
00287   const _Node* node() { return _C_w_cur; }
00288 
00290   size_type n_children() { return _C_w_cur->_C_children.size(); }
00292   size_type n_parents() { return _C_w_cur->_C_parent ? 1 : 0; }
00293 
00295   bool is_leaf() { return _C_w_cur->_C_children.empty(); }
00297   bool is_root()
00298         { return parent() != NULL && (*parent())._C_parent == NULL; }
00299 
00301   bool is_ground() { return parent() == NULL; }
00303   bool is_sky() { return false; }
00304 
00306   children_iterator child_begin() { return _C_w_cur->_C_children.begin(); }
00308   children_iterator child_end() { return _C_w_cur->_C_children.end(); }
00309   
00311   parents_iterator parent_begin()
00312         { return parents_iterator(&_C_w_cur->_C_parent); }
00314   parents_iterator parent_end()
00315         { return parents_iterator(&_C_w_cur->_C_parent, false); }
00316   
00318   template <class _Function>
00319   _Function for_each_child(_Function __f)
00320     {
00321       return for_each(child_begin(), child_end(), __f);
00322     }
00324   template <class _Function>
00325   _Function for_each_parent(_Function __f)
00326     {
00327       return for_each(parent_begin(), parent_end(), __f);
00328     }
00329 
00331   template <class Compare>
00332   void sort_children(children_iterator first, children_iterator last,
00333                      Compare comp)
00334     { (*_C_w_cur).sort_children(first, last, comp); }
00335  
00337   template <class Compare>
00338   void sort_parents(parents_iterator first, parents_iterator last,
00339                     Compare comp) {}
00340  
00342   template <class Compare>
00343   void sort_children(Compare comp)
00344   { (*_C_w_cur).sort_children(child_begin(), child_end(), comp); }
00345  
00347   template <class Compare>
00348   void sort_parents(Compare comp) {}
00349 };
00350 
00352 
00357 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00358           class _Node>
00359 class _Tree_walker : public _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>
00360 {
00361 public:
00362   typedef _Tree_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node>              walker;
00363   typedef _Tree_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node>  const_walker;
00364   typedef _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>              _Self;
00365 
00366 public:
00368   struct {
00369     unsigned int order:2;
00370     unsigned int front_to_back:1;
00371     unsigned int depth_first:1;
00372   } _C_w_t;
00374   bool _C_w_in_preorder;
00376   std::vector<_Iterator> _C_w_cur_it;
00377 
00378 public:
00380   _Tree_walker() : _C_w_cur_it() {_C_w_cur_it.reserve(32); }
00381 
00382 private:
00384   void _find_start_node();
00386   void _find_end_node();
00388   void _find_next_preorder();
00390   void _find_next_postorder();
00392   void _find_next_any();
00394   void _find_prev_preorder();
00396   void _find_prev_postorder();
00398   void _find_prev_any();
00399 
00400 public:
00405   _Tree_walker(_Node* __x, int order = (_C_W_preorder|_C_W_postorder),
00406                 bool front_to_back = true, bool depth_first = true,
00407                 bool find_start = true)
00408         : _C_w_cur_it() {
00409           _C_w_cur = __x;
00410           _C_w_cur_it.reserve(32);
00411           _C_w_t.order = order;
00412           _C_w_t.front_to_back = front_to_back;
00413           _C_w_t.depth_first = depth_first;
00414           if(__x->_C_parent == NULL) // true top node
00415             _C_w_in_preorder = find_start;
00416           else if(find_start)
00417             _find_start_node();
00418           else
00419             _find_end_node(); }
00420 
00422   _Tree_walker(const walker& __x) : _C_w_in_preorder(__x._C_w_in_preorder),
00423                  _C_w_cur_it(__x._C_w_cur_it) {
00424                  _C_w_cur = __x._C_w_cur;
00425                  _C_w_t = __x._C_w_t;
00426                  }
00427 
00429 
00430   bool operator==(const _Self& __x) const 
00431         { return (_C_w_t.order == 0 && __x._C_w_t.order == 0) ||
00432                  (_C_w_cur == __x._C_w_cur &&
00433                  _C_w_in_preorder == __x._C_w_in_preorder &&
00434                  _C_w_t.order == __x._C_w_t.order &&
00435                  _C_w_t.front_to_back == __x._C_w_t.front_to_back &&
00436                  _C_w_t.depth_first == __x._C_w_t.depth_first &&
00437                  _C_w_cur_it == __x._C_w_cur_it); }
00438   bool operator!=(const _Self& __x) const 
00439         { return (_C_w_t.order != 0 || __x._C_w_t.order != 0) &&
00440                  (_C_w_cur != __x._C_w_cur ||
00441                  _C_w_in_preorder != __x._C_w_in_preorder ||
00442                  _C_w_t.order != __x._C_w_t.order ||
00443                  _C_w_t.front_to_back != __x._C_w_t.front_to_back ||
00444                  _C_w_t.depth_first != __x._C_w_t.depth_first ||
00445                  _C_w_cur_it != __x._C_w_cur_it); }
00447 
00448 public:
00450 
00451   _Self& operator++() {
00452     if(_C_w_t.depth_first)
00453     {
00454       if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00455       {
00456         _find_next_any();
00457       }
00458       else if(_C_w_t.order & _C_W_preorder)
00459       {
00460         _find_next_preorder();
00461       }
00462       else
00463       {
00464         _find_next_postorder();
00465       }
00466     }
00467     else
00468     {
00469       /**** NOT YET IMPLEMENTED ****/;
00470     }
00471     return *this;
00472   }
00473   _Self operator++(int) {
00474     _Self __tmp = *this;
00475     ++*this;
00476     return __tmp;
00477   }
00478 
00479   _Self& operator--() {
00480     if(_C_w_t.depth_first)
00481     {
00482       if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00483       {
00484         _find_prev_any();
00485       }
00486       else if(_C_w_t.order & _C_W_preorder)
00487       {
00488         _find_prev_preorder();
00489       }
00490       else
00491       {
00492         _find_prev_postorder();
00493       }
00494     }
00495     else
00496     {
00497       /**** NOT YET IMPLEMENTED ****/;
00498     }
00499     return *this;
00500   }
00501   _Self operator--(int) {
00502     _Self __tmp = *this;
00503     --*this;
00504     return __tmp;
00505   }
00507 
00509 
00510   _Self operator<<(const parents_iterator& __dummy) {
00511     _Self __tmp = *this;
00512     _Node *help = __tmp._C_w_cur._C_parent;
00513     if(help == NULL) // already at root node
00514     {
00515       __tmp._C_w_t.order = 0;
00516     }
00517     else
00518     {
00519       __tmp._C_w_cur = help;
00520       if(__tmp._C_w_t.order & _C_W_postorder)
00521         __tmp._C_w_in_preorder = false;
00522       if(!__tmp._C_w_cur_it.empty())
00523         pop_back(__tmp._C_w_cur_it);
00524     }
00525     return __tmp;
00526   }
00527   
00529 
00530   _Self operator>>(const children_iterator& __i) {
00531     _Self __tmp = *this;
00532     _Node *help = (_Node*) *__i;
00533     if(__tmp._C_w_t.order & _C_W_preorder)
00534       __tmp._C_w_in_preorder = true;
00535     __tmp._C_w_cur_it.push_back(__i);
00536     __tmp._C_w_cur = help;
00537     return __tmp;
00538   }
00539 
00541   _Self& operator<<=(const parents_iterator& __dummy) {
00542     _Node *help = _C_w_cur._C_parent;
00543     if(help == NULL) // already at root node
00544     {
00545       _C_w_t.order = 0;
00546     }
00547     else
00548     {
00549       _C_w_cur = help;
00550       if(_C_w_t.order & _C_W_postorder)
00551         _C_w_in_preorder = false;
00552       if(!_C_w_cur_it.empty())
00553         pop_back(_C_w_cur_it);
00554     }
00555     return *this;
00556   }
00557   
00559   _Self& operator>>=(const children_iterator& __i) {
00560     _Node *help = (_Node*) *__i;
00561     if(_C_w_t.order & _C_W_preorder)
00562       _C_w_in_preorder = true;
00563     push_back(_C_w_cur_it, __i);
00564     _C_w_cur = help;
00565     return *this;
00566   }
00567 
00569   _Self& operator~() {
00570     if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
00571       _C_w_in_preorder = !_C_w_in_preorder;
00572     return *this;
00573   }
00574 
00576   _Self& operator=(const _Itr& __x) {
00577         _C_w_cur = __x._C_i_cur;
00578         _C_w_cur_it = __x._C_i_cur_it;
00579         _C_w_t.order = _C_W_postorder;
00580         _C_w_t.depth_first = 1;
00581         _C_w_t.front_to_back = 1;
00582         return *this;
00583   }
00584   
00586   bool in_preorder() { return _C_w_in_preorder; }
00587 };
00588 
00589 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00590           class _Node>
00591 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_start_node()
00592 {
00593   if(_C_w_t.depth_first)
00594   {
00595     if(_C_w_t.order & _C_W_preorder)
00596     {
00597       _C_w_in_preorder = true;
00598     }
00599     else if(_C_w_t.order & _C_W_postorder)
00600     {
00601       _C_w_in_preorder = false;
00602       if(_C_w_t.front_to_back)
00603       {
00604         while(!_C_w_cur->_C_children.empty())
00605         {
00606           _Ctr_iterator help;
00607       
00608           help = _C_w_cur->_C_children.begin();
00609           _C_w_cur = (_Node*)*help;
00610           _C_w_cur_it.push_back(help);
00611         }
00612       }
00613       else
00614       {
00615         while(!_C_w_cur->_C_children.empty())
00616         {
00617           _Ctr_iterator help;
00618       
00619           help = _C_w_cur->_C_children.end();
00620           --help;
00621           _C_w_cur = (_Node*)*help;
00622           _C_w_cur_it.push_back(help);
00623         }
00624       }
00625     }
00626   }
00627   else
00628   {
00629     /**** NOT YET IMPLEMENTED ****/;
00630   }
00631 }
00632 
00633 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00634           class _Node>
00635 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_end_node()
00636 {
00637   if(_C_w_t.depth_first)
00638   {
00639     if(_C_w_t.order & _C_W_postorder)
00640     {
00641       _C_w_in_preorder = false;
00642       (&_C_w_cur_it)->~std::vector();
00643       _C_w_cur_it.reserve(32);
00644     }
00645     else if(_C_w_t.order & _C_W_postorder)
00646     {
00647       _C_w_in_preorder = true;
00648       if(_C_w_t.front_to_back)
00649       {
00650         while(!_C_w_cur->_C_children.empty())
00651         {
00652           _Ctr_iterator help;
00653       
00654           help = _C_w_cur->_C_children.begin();
00655           _C_w_cur = (_Node*)*help;
00656           _C_w_cur_it.push_back(help);
00657         }
00658       }
00659       else
00660       {
00661         while(!_C_w_cur->_C_children.empty())
00662         {
00663           _Ctr_iterator help;
00664       
00665           help = _C_w_cur->_C_children.end();
00666           --help;
00667           _C_w_cur = (_Node*)*help;
00668           _C_w_cur_it.push_back(help);
00669         }
00670       }
00671     }
00672   }
00673   else
00674   {
00675     /**** NOT YET IMPLEMENTED ****/;
00676   }
00677 }
00678 
00679 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00680           class _Node>
00681 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_preorder()
00682 {
00683   _Ctr_iterator help;
00684 
00685   if(_C_w_cur->_C_children.empty()) // this is a leaf -> go up
00686   {
00687     while(1)
00688     {
00689       if(_C_w_cur_it.empty()) // all done
00690       {
00691         if(_C_w_cur->_C_parent == NULL && _C_w_in_preorder)
00692           _C_w_in_preorder = false;
00693         else
00694           _C_w_t.order = 0;
00695         break;
00696       }
00697       help = _C_w_cur_it.back();
00698       _C_w_cur_it.pop_back();
00699       _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00700       if(_C_w_t.front_to_back)
00701       {
00702         ++help;
00703         if(help != _C_w_cur->_C_children.end())
00704         // go to next subtree
00705         {
00706           _C_w_cur_it.push_back(help);
00707           _C_w_cur = (_Node*)*help;
00708           break;
00709         }
00710       }
00711       else
00712       {
00713         if(help != _C_w_cur->_C_children.begin())
00714         // go to next subtree
00715         {
00716           --help;
00717           _C_w_cur_it.push_back(help);
00718           _C_w_cur = (_Node*)*help;
00719           break;
00720         }
00721       }
00722     }
00723   }
00724   else if(!_C_w_in_preorder)            // from end to through
00725     _C_w_t.order = 0;
00726   else // go down
00727   {
00728     if(_C_w_t.front_to_back)
00729       help = _C_w_cur->_C_children.begin();
00730     else
00731     {
00732       help = _C_w_cur->_C_children.end();
00733       help--;
00734     }
00735     _C_w_cur_it.push_back(help);
00736     _C_w_cur = (_Node*)*help;
00737   }
00738 }
00739 
00740 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00741           class _Node>
00742 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_postorder()
00743 {
00744   if(_C_w_in_preorder)
00745   {
00746     _C_w_in_preorder = false;
00747     _find_start_node();
00748   }
00749   else if(_C_w_cur_it.empty())
00750   {
00751     _C_w_t.order = 0;
00752   }
00753   else
00754   {
00755     _Ctr_iterator help = _C_w_cur_it.back();
00756     _C_w_cur_it.pop_back();
00757     if(_C_w_t.front_to_back)
00758     {
00759       ++help;
00760       if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00761       // go to next subtree
00762       {
00763         do
00764         {
00765           _C_w_cur_it.push_back(help);
00766           _C_w_cur = (_Node*)*help;
00767           help = _C_w_cur->_C_children.begin();
00768         } while(!_C_w_cur->_C_children.empty());
00769       }
00770       else // this was the last subtree -> hop one level up
00771       {
00772         _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00773       }
00774     }
00775     else
00776     {
00777       if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00778       // go to next subtree
00779       {
00780         do
00781         {
00782           --help;
00783           _C_w_cur_it.push_back(help);
00784           _C_w_cur = (_Node*)*help;
00785           help = _C_w_cur->_C_children.end();
00786         } while(!_C_w_cur->_C_children.empty());
00787       }
00788       else // this was the last subtree -> hop one level up
00789       {
00790         _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00791       }
00792     }
00793   }
00794 }
00795 
00796 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00797           class _Node>
00798 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_any() {
00799   if(_C_w_in_preorder) // step down
00800   {
00801     if(_C_w_cur->_C_children.empty()) // this is a leaf
00802       _C_w_in_preorder = false; // immediatly switch to post order
00803     else // step down
00804     {
00805       _Ctr_iterator help;
00806       if(_C_w_t.front_to_back)
00807         help = _C_w_cur->_C_children.begin();
00808       else
00809       {
00810         help = _C_w_cur->_C_children.end();
00811         --help;
00812       }
00813       _C_w_cur_it.push_back(help);
00814       _C_w_cur = (_Node*)*help;
00815     }
00816   }
00817   else
00818   {
00819     _Ctr_iterator help;
00820 
00821     if(!_C_w_cur_it.empty()) // we are somewhere down
00822     {
00823       help = _C_w_cur_it.back();
00824       _C_w_cur_it.pop_back();
00825       if(_C_w_t.front_to_back)
00826       {
00827         ++help;
00828         if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00829         // go to next subtree
00830         {
00831           _C_w_cur_it.push_back(help);
00832           _C_w_cur = (_Node*)*help;
00833           _C_w_in_preorder = true;
00834         }
00835         else // this was the last subtree
00836         {
00837           _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00838         }
00839       }
00840       else
00841       {
00842         if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00843         // go to next subtree
00844         {
00845           --help;
00846           _C_w_cur_it.push_back(help);
00847           _C_w_cur = (_Node*)*help;
00848           _C_w_in_preorder = true;
00849         }
00850         else // this was the last subtree
00851         {
00852           _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00853         }
00854       }
00855     }
00856     else // there is nothing left -> we have reached the end.
00857     {
00858       _C_w_t.order = 0;
00859     }
00860   }
00861 }
00862 
00863 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00864           class _Node>
00865 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_preorder()
00866 {
00867   if(!_C_w_in_preorder)
00868   {
00869     _C_w_t.order = _C_W_postorder;
00870     _C_w_t.front_to_back = !_C_w_t.front_to_back;
00871     _find_start_node();
00872     _C_w_in_preorder = true;
00873     _C_w_t.order = _C_W_preorder;
00874     _C_w_t.front_to_back = !_C_w_t.front_to_back;
00875   }
00876   else if(_C_w_cur_it.empty())
00877   {
00878     _C_w_t.order = 0;
00879   }
00880   else
00881   {
00882     _Ctr_iterator help = _C_w_cur_it.back();
00883     _C_w_cur_it.pop_back();
00884     if(!_C_w_t.front_to_back)
00885     {
00886       ++help;
00887       if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
00888       // go to next subtree
00889       {
00890         do
00891         {
00892           _C_w_cur_it.push_back(help);
00893           _C_w_cur = (_Node*)*help;
00894           help = _C_w_cur->_C_children.begin();
00895         } while(!_C_w_cur->_C_children.empty());
00896       }
00897       else // this was the last subtree -> hop one level up
00898       {
00899         _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00900       }
00901     }
00902     else
00903     {
00904       if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
00905       // go to next subtree
00906       {
00907         do
00908         {
00909           --help;
00910           _C_w_cur_it.push_back(help);
00911           _C_w_cur = (_Node*)*help;
00912           help = _C_w_cur->_C_children.end();
00913         } while(!_C_w_cur->_C_children.empty());
00914       }
00915       else // this was the last subtree -> hop one level up
00916       {
00917         _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00918       }
00919     }
00920   }
00921 }
00922 
00923 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00924           class _Node>
00925 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_postorder()
00926 {
00927   _Ctr_iterator help;
00928 
00929   if(_C_w_cur->_C_children.empty()) // this is a leaf -> go up
00930   {
00931     while(1)
00932     {
00933       if(_C_w_cur_it.empty()) // all done
00934       {
00935         if(_C_w_cur->_C_parent == NULL && !_C_w_in_preorder)
00936           _C_w_in_preorder = true;
00937         else
00938           _C_w_t.order = 0;
00939         break;
00940       }
00941       help = _C_w_cur_it.back();
00942       _C_w_cur_it.pop_back();
00943       _C_w_cur = (_Node*)_C_w_cur->_C_parent;
00944       if(!_C_w_t.front_to_back)
00945       {
00946         ++help;
00947         if(help != _C_w_cur->_C_children.end())
00948         // go to next subtree
00949         {
00950           _C_w_cur_it.push_back(help);
00951           _C_w_cur = (_Node*)*help;
00952           break;
00953         }
00954       }
00955       else
00956       {
00957         if(help != _C_w_cur->_C_children.begin())
00958         // go to next subtree
00959         {
00960           --help;
00961           _C_w_cur_it.push_back(help);
00962           _C_w_cur = (_Node*)*help;
00963           break;
00964         }
00965       }
00966     }
00967   }
00968   else if(_C_w_in_preorder)             // from end to through
00969     _C_w_t.order = 0;
00970   else // go down
00971   {
00972     if(!_C_w_t.front_to_back)
00973       help = _C_w_cur->_C_children.begin();
00974     else
00975     {
00976       help = _C_w_cur->_C_children.end();
00977       help--;
00978     }
00979     _C_w_cur_it.push_back(help);
00980     _C_w_cur = (_Node*)*help;
00981   }
00982 }
00983 
00984 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
00985           class _Node>
00986 void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_any()
00987 {
00988   if(!_C_w_in_preorder) // step down
00989   {
00990     if(_C_w_cur->_C_children.empty()) // this is a leaf
00991       _C_w_in_preorder = true; // immediatly switch to pre order
00992     else // step down
00993     {
00994       _Ctr_iterator help;
00995       if(!_C_w_t.front_to_back)
00996         help = _C_w_cur->_C_children.begin();
00997       else
00998       {
00999         help = _C_w_cur->_C_children.end();
01000         --help;
01001       }
01002       _C_w_cur_it.push_back(help);
01003       _C_w_cur = (_Node*)*help;
01004     }
01005   }
01006   else
01007   {
01008     _Ctr_iterator help;
01009 
01010     if(!_C_w_cur_it.empty()) // we are somewhere down
01011     {
01012       help = _C_w_cur_it.back();
01013       _C_w_cur_it.pop_back();
01014       if(!_C_w_t.front_to_back)
01015       {
01016         ++help;
01017         if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
01018         // go to next subtree
01019         {
01020           _C_w_cur_it.push_back(help);
01021           _C_w_cur = (_Node*)*help;
01022           _C_w_in_preorder = false;
01023         }
01024         else // this was the last subtree
01025         {
01026           _C_w_cur = (_Node*)_C_w_cur->_C_parent;
01027         }
01028       }
01029       else
01030       {
01031         if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
01032         // go to next subtree
01033         {
01034           --help;
01035           _C_w_cur_it.push_back(help);
01036           _C_w_cur = (_Node*)*help;
01037           _C_w_in_preorder = false;
01038         }
01039         else // this was the last subtree
01040         {
01041           _C_w_cur = (_Node*)_C_w_cur->_C_parent;
01042         }
01043       }
01044     }
01045     else // there is nothing left -> we have reached the end.
01046     {
01047       _C_w_t.order = 0;
01048     }
01049   }
01050 }
01051 
01053 
01058 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01059           class _Node>
01060 class _RTree_walker : public _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>
01061 {
01062 public:
01063   typedef _RTree_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node>             walker;
01064   typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node> const_walker;
01065   typedef _RTree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>             _Self;
01066 
01067 public:
01069   _RTree_walker() {}
01070 
01072   _RTree_walker(_Node* __x) { _C_w_cur = __x; }
01073 
01075   _RTree_walker(const walker& __x) { _C_w_cur = __x._C_w_cur; }
01076 
01077 public:
01079 
01080   bool operator==(const _Self& __x) const 
01081         { return _C_w_cur == __x._C_w_cur; }
01082   bool operator!=(const _Self& __x) const 
01083         { return _C_w_cur != __x._C_w_cur; }
01085 
01087 
01088   _Self operator<<(const parents_iterator& __dummy) {
01089     _Self __tmp = *this;
01090     _Node *help = __tmp._C_w_cur._C_parent;
01091     if(help != NULL) // already at root node
01092       __tmp._C_w_cur = help;
01093     return __tmp;
01094   }
01095   
01097 
01098   _Self operator>>(const children_iterator& __i) {
01099     _Self __tmp = *this;
01100     __tmp._C_w_cur = (_Node*) *__i;
01101     return __tmp;
01102   }
01103 
01105   _Self& operator<<=(const parents_iterator& __dummy) {
01106     _Node *help = _C_w_cur._C_parent;
01107     if(help != NULL) // already at root node
01108       _C_w_cur = help;
01109     return *this;
01110   }
01111   
01113   _Self& operator>>=(const children_iterator& __i) {
01114     _C_w_cur = (_Node*) *__i;
01115     return *this;
01116   }
01117   
01119   _Self& operator=(const _Itr& __x) {
01120         _C_w_cur = __x._C_i_cur;
01121         return *this;
01122   }
01123 
01125   _Self& operator=(const _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>& __x) 
01126   {
01127         _C_w_cur = __x._C_w_cur;
01128         return *this;
01129   }
01130 };
01131 
01133 
01138 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01139           class _Node>
01140 class _Tree_iterator
01141 {
01142 public:
01143   typedef _Tree_iterator<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node>             iterator;
01144   typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node> const_iterator;
01145   typedef _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>             _Self;
01146   typedef _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>               _Walk;
01147 
01149 
01150   typedef std::bidirectional_iterator_tag iterator_category;
01151   typedef _Tp value_type;
01152   typedef _Ptr pointer;
01153   typedef _Ref reference;
01154   typedef size_t size_type;
01155   typedef ptrdiff_t difference_type;
01157   typedef _Iterator _Ctr_iterator;
01158 
01159 protected:
01161   _Node* _C_i_cur;
01163   std::vector<_Ctr_iterator> _C_i_cur_it;
01164 
01165 public:
01167   _Tree_iterator() : _C_i_cur_it() {_C_i_cur_it.reserve(32);}
01169   _Tree_iterator(const iterator& __x) : _C_i_cur(__x._C_i_cur),
01170                                          _C_i_cur_it(__x._C_i_cur_it) {}
01172   _Tree_iterator(const _Node* __n, bool st = false) : _C_i_cur_it()
01173         { _C_i_cur = __n; if(st) find_start_node(); }
01174 
01176 
01177   bool operator==(const _Self& __x) const
01178         { return (_C_i_cur->_C_parent == NULL &&
01179                    __x._C_i_cur->_C_parent == NULL) ||
01180                  ( _C_i_cur == __x._C_i_cur &&
01181                    _C_i_cur_it == __x._C_i_cur_it);
01182         }
01183   bool operator!=(const _Self& __x) const
01184         { return (_C_i_cur->_C_parent != NULL ||
01185                    __x._C_i_cur->_C_parent != NULL) &&
01186                  ( _C_i_cur != __x._C_i_cur ||
01187                    _C_i_cur_it != __x._C_i_cur_it);
01188         }
01190 
01191   reference operator*() const { return (*_C_i_cur)._C_data; }
01192 
01193 #ifndef __SGI_STL_NO_ARROW_OPERATOR
01194 
01195   pointer operator->() const { return &(operator*()); }
01196 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
01197 
01198   ctree_data_hook& data_hook() { return (*_C_i_cur)._C_data_hook; }
01199 
01200 private:
01202   void find_start_node();
01204   void find_next_node();
01206   void find_prev_node();
01207   
01208 public:
01210   _Self& operator=(const _Walk& __x) {
01211         _C_i_cur = __x._C_w_cur;
01212         _C_i_cur_it.erase(_C_i_cur_it.begin(), _C_i_cur_it.end());
01213         // we have to find the next postorder node and
01214         // initialize the vector of iterators.
01215         find_start_node();
01216         return *this;
01217   }
01218 
01220 
01221   _Self& operator++() {
01222     find_next_node();
01223     return *this;
01224   }
01225   _Self operator++(int) {
01226     _Self __tmp = *this;
01227     ++*this;
01228     return __tmp;
01229   }
01230 
01231   _Self& operator--() {
01232     find_prev_node();
01233     return *this;
01234   }
01235   _Self operator--(int) {
01236     _Self __tmp = *this;
01237     --*this;
01238     return __tmp;
01239   }
01241 };
01242 
01243 #ifndef __VGTL_CLASS_PARTIAL_SPECIALIZATION
01244 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _I, class _N>
01245 inline std::bidirectional_iterator_tag
01246 iterator_category(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_I,_N>&)
01247 {
01248   return std::bidirectional_iterator_tag();
01249 }
01250 
01251 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _I, class _N>
01252 inline _Tp*
01253 value_type(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_I,_N>&)
01254 {
01255   return 0;
01256 }
01257 
01258 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _I, class _N>
01259 inline ptrdiff_t*
01260 distance_type(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_I,_N>&)
01261 {
01262   return 0;
01263 }
01264 
01265 #endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */
01266 
01267 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01268           class _Node>
01269 void
01270 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_start_node()
01271 {
01272   _Node* __s = _C_i_cur;
01273   _Ctr_iterator __help;
01274 
01275   while(__s->_C_parent != NULL)
01276   {
01277     __help = ((_Node*)__s->_C_parent)->get_childentry_iterator((void*)__s);
01278     _C_i_cur_it.insert(_C_i_cur_it.begin(), __help);
01279     __s = (_Node*)__s->_C_parent;
01280   }
01281   while(!_C_i_cur->_C_children.empty())
01282   {
01283     __help = _C_i_cur->_C_children.begin();
01284     _C_i_cur = (_Node*)*__help;
01285     _C_i_cur_it.push_back(__help);
01286   }
01287 }
01288 
01289 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01290           class _Node>
01291 void
01292 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_next_node()
01293 {
01294   if(_C_i_cur->_C_parent != NULL) // not yet through
01295   {
01296     _Ctr_iterator __help = _C_i_cur_it.back();
01297     _C_i_cur_it.pop_back();
01298     ++__help;
01299     if(__help != ((_Node*)_C_i_cur->_C_parent)->_C_children.end())
01300     { // go to next subtree
01301       do
01302       {
01303         _C_i_cur_it.push_back(__help);
01304         _C_i_cur = (_Node*)*__help;
01305         __help = _C_i_cur->_C_children.begin();
01306       } while(!_C_i_cur->_C_children.empty());
01307     }
01308     else // this was the last subtree -> hop one level up
01309     {
01310       _C_i_cur = (_Node*)_C_i_cur->_C_parent;
01311     }
01312   }
01313 }
01314 
01315 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
01316           class _Node>
01317 void
01318 _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_prev_node()
01319 {
01320   _Ctr_iterator help;
01321 
01322   if(_C_i_cur->_C_children.empty()) // this is a leaf -> go up
01323   {
01324     while(1)
01325     {
01326       if(_C_i_cur->_C_parent == NULL) // already through
01327         break;
01328       help = _C_i_cur_it.back();
01329       _C_i_cur_it.pop_back();
01330       _C_i_cur = (_Node*)_C_i_cur->_C_parent;
01331       if(help != _C_i_cur->_C_children.begin())
01332       { // go to prev subtree
01333         --help;
01334         _C_i_cur_it.push_back(help);
01335         _C_i_cur = (_Node*)*help;
01336         break;
01337       }
01338     }
01339   }
01340   else // go down
01341   {
01342     help = _C_i_cur->_C_children.end();
01343     --help;
01344     _C_i_cur_it.push_back(help);
01345     _C_i_cur = (_Node*)*help;
01346   }
01347 }
01348 
01349 #ifdef __VGTL_USE_STD_ALLOCATORS
01350 
01352 
01362 template <class _Tp, class _Ctr, class _I, class _Node, class _Allocator,
01363           bool _IsStatic>
01364 class _Tree_alloc_base {
01365 public:
01366   typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
01367           allocator_type;
01368   allocator_type get_allocator() const { return _Node_allocator; }
01369 
01370   _Tree_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
01371 
01372 protected:
01374   _Node* _C_get_node()
01375     { return _Node_allocator.allocate(1); }
01377   void _C_put_node(_Node* __p)
01378     { _Node_allocator.deallocate(__p, 1); }
01379 
01380 protected:
01381   typename std::_Alloc_traits<_Node, _Allocator>::allocator_type
01382            _Node_allocator;
01383 
01384 protected:
01386   _Node* _C_node;
01387 };
01388 
01390 
01400 template <class _Tp, class _Ctr, class _I, class _Node, class _Allocator>
01401 class _Tree_alloc_base<_Tp, _Ctr, _I, _Node, _Allocator, true> {
01402 public:
01403   typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
01404           allocator_type;
01405   allocator_type get_allocator() const { return allocator_type(); }
01406 
01407   _Tree_alloc_base(const allocator_type&) {}
01408 
01409 protected:
01410   typedef typename std::_Alloc_traits<_Node, _Allocator>::_Alloc_type
01411           _Alloc_type;
01413   _Node* _C_get_node()
01414     { return _Alloc_type::allocate(1); }
01416   void _C_put_node(_Node* __p)
01417     { _Alloc_type::deallocate(__p, 1); }
01418 
01419 protected:
01421   _Node* _C_node;
01422 };
01423 
01425 
01429 template <class _Tp, class _Ctr, class _I, class _Node, class _Alloc>
01430 class _Tree_base
01431   : public _Tree_alloc_base<_Tp, _Ctr, _I, _Node, _Alloc,
01432   std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
01433 {
01434 public:
01435   typedef _Tree_alloc_base<_Tp, _Ctr, _I, _Node, _Alloc,
01436   std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
01437           _Base;
01439   typedef typename _Base::allocator_type allocator_type;
01440 
01442   typedef _Ctr container_type;
01444   typedef _I children_iterator;
01446   typedef __one_iterator<void *> parents_iterator;
01447 
01449   _Tree_base(const allocator_type& __a) : _Base(__a) {
01450     _C_node = _C_get_node();
01451     __VGTL_TRY {
01452       _C_node->initialize();
01453     }
01454     __VGTL_UNWIND(_C_put_node(_C_node));
01455   }
01457   virtual ~_Tree_base() {
01458     clear();
01459     _C_put_node(_C_node);
01460   }
01461 
01463   void clear();
01465   void clear_children()
01466         { _C_node->clear_children(); }
01467 
01470   template <class _Output_Iterator>
01471   void add_all_children(_Output_Iterator fi, _Node* _parent);
01472 };
01473 #else /* __VGTL_USE_STD_ALLOCATORS */
01474 
01476 
01480 template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
01481 class _Tree_base
01482 {
01483 public:
01485   typedef _Alloc allocator_type;
01487   allocator_type get_allocator() const { return allocator_type(); }
01488   
01490   typedef _Ctr container_type;
01492   typedef _Iterator children_iterator;
01494   typedef __one_iterator<void *> parents_iterator;
01495 
01497   _Tree_base(const allocator_type&) {
01498     _C_node = _C_get_node();
01499     _C_node->initialize();
01500   }
01502   virtual ~_Tree_base() {
01503     clear();
01504     _C_put_node(_C_node);
01505   }
01506 
01508   void clear();
01509 
01510 protected:
01511   typedef simple_alloc<Node, _Alloc> _Alloc_type;
01513   _Node* _C_get_node()
01514     { return _Alloc_type::allocate(1); }
01516   void _C_put_node(_Node* __p)
01517     { _Alloc_type::deallocate(__p, 1); }
01518 
01519 protected:
01521   _Node* _C_node;
01522 
01524   void clear_children()
01525      { _C_node->clear_children(); }
01526 
01529   template <class _Output_Iterator>
01530   void add_all_children(_Output_Iterator fi, _Node* _parent);
01531 };
01532 
01533 #endif /* __VGTL_USE_STD_ALLOCATORS */
01534 
01535 template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
01536 template <class _Output_Iterator>
01537 inline void
01538 _Tree_base<_Tp,_Ctr,_Iterator,_Node,_Alloc>::add_all_children(
01539     _Output_Iterator fi, _Node* _parent)
01540 { _C_node->add_all_children(fi, _parent); };
01541 
01542 template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
01543 void
01544 _Tree_base<_Tp,_Ctr,_Iterator,_Node,_Alloc>::clear()
01545 {
01546   this->_C_node->clear_tree();
01547   this->_C_node->clear_children();
01548 }
01549 
01551 
01556 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Node,
01557           class _Alloc>
01558 class __Tree_t : public _Tree_base<_Tp, _Ctr, _Iterator, _Node, _Alloc>
01559 {
01560 public:
01561   typedef _Ctr  container_type;
01562   typedef _Iterator children_iterator;
01563   typedef __one_iterator<void *> parents_iterator;
01564   typedef _Inserter container_insert_arg;
01565 
01566 protected:
01567   typedef void* _Void_pointer;
01568   typedef _Tree_base<_Tp, container_type, children_iterator, _Node, _Alloc> _Base;
01569   typedef __Tree_t<_Tp,_Ctr,_Iterator,_Inserter,_Node,_Alloc> _Self;
01570 
01571 public:
01573 
01574   typedef _Tp                   value_type;
01575   typedef _Node                 node_type;
01576   typedef value_type*           pointer;
01577   typedef const value_type*     const_pointer;
01578   typedef value_type&           reference;
01579   typedef const value_type&     const_reference;
01580   typedef size_t                size_type;
01581   typedef ptrdiff_t             difference_type;
01583 
01584   typedef typename _Base::allocator_type allocator_type;
01586   allocator_type get_allocator() const { return _Base::get_allocator(); }
01587 
01588 public:
01590   typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
01592   typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;
01593 
01594 #ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION
01595 
01596   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
01598   typedef std::reverse_iterator<iterator>       reverse_iterator;
01599 #else /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */
01600 
01601   typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
01602                                          const_reference,difference_type>
01603           const_reverse_iterator;
01605   typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
01606                                          difference_type>
01607           reverse_iterator;
01608 #endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */
01609 
01611   typedef _RTree_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> walker;
01613   typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_walker;
01614 
01615 protected:
01616   typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> __walker_base;
01617   typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> __const_walker_base;
01618 
01619 protected:
01620 #ifdef __VGTL_HAS_NAMESPACES
01621   using _Base::_C_node;
01622   using _Base::_C_put_node;
01623   using _Base::_C_get_node;
01624 #endif /* __VGTL_HAS_NAMESPACES */
01625 
01626 protected:
01628   _Node* _C_create_node(const _Tp& __x)
01629   {
01630     _Node* __p = _C_get_node();
01631     __VGTL_TRY {
01632       __p->initialize();
01633       std::_Construct(&__p->_C_data, __x);
01634     }
01635     __VGTL_UNWIND(_C_put_node(__p));
01636     return __p;
01637   }
01638 
01640   _Node* _C_create_node()
01641   {
01642     _Node* __p = _C_get_node();
01643     __VGTL_TRY {
01644       __p->initialize();
01645       std::_Construct(&__p->_C_data);
01646     }
01647     __VGTL_UNWIND(_C_put_node(__p));
01648     return __p;
01649   }
01650 
01651 public:
01653   explicit __Tree_t(const allocator_type& __a = allocator_type()) : _Base(__a) {}
01654 
01656   bool empty() const { return _C_node->_C_children.empty(); }
01657 
01659   size_type max_size() const { return size_type(-1); }
01660 
01662   void swap(_Self& __x)
01663     { __STD::swap(_C_node, __x._C_node); }
01664 
01667   void insert_child(const __walker_base& __position, const _Tp& __x,
01668                              const container_insert_arg& __It) 
01669         { _Node* __tmp = _C_create_node(__x);
01670           __position._C_w_cur->_C_children.insert(__It,__tmp);
01671           __tmp->_C_parent = __position._C_w_cur;
01672         }
01675   void insert_child(const __walker_base& __position,
01676                              const container_insert_arg& __It) 
01677         { insert_child(__position, _Tp(), __It); }
01678 
01681   void insert_children(const __walker_base& __position, size_type __n,
01682                        const _Tp& __x, const children_iterator& __It)
01683         { _Node* __tmp;
01684           std::vector<_Node *> __Ctr;
01685           __Ctr.reserve(__n);
01686 
01687           for(int i=n; i>0; i--)
01688           {
01689             __tmp = _C_create_node(__x);
01690             __Ctr.insert(__Ctr.end(), __tmp);
01691             __tmp->_C_parent = __position._C_w_cur;
01692           }
01693           __position._C_w_cur->_C_children.insert(__It,
01694                         __Ctr.begin(), __Ctr.end());
01695         }
01696 
01701   void insert_subtree(const __walker_base& __position,
01702                       _Self& __subtree, const children_iterator& __It) 
01703         {
01704           __subtree.add_all_children(inserter(__position._C_w_cur->_C_children,
01705                 __It), __position._C_w_cur);
01706           __subtree.clear_children();
01707         }
01708   
01712   void erase(const __walker_base& __position)
01713         { _Node* __tmp = __position._C_w_cur;
01714           _Node* __parent = (_Node*)__tmp->_C_parent;
01715 
01716           if(__parent != NULL)
01717           { // cannot erase the (virtual!) root node
01718             children_iterator __ip = __parent->get_childentry_iterator(__tmp);
01719 
01720             if(!__tmp->_C_children.empty())
01721             {
01722               children_iterator __it = __tmp->_C_children.end();
01723 
01724               *__ip = *--__it;
01725               ((_Node*)*__it)->_C_parent = __parent;
01726               __tmp->_C_children.erase(__it);
01727               if(!__tmp->_C_children.empty())
01728               {
01729                 __tmp->add_all_children(inserter(__parent->_C_children, __ip),
01730                         __parent);
01731                 __tmp->clear_children();
01732               }
01733             }
01734             _C_put_node(__tmp);
01735           }
01736         }
01737 
01742   _Node* erase_tree(const __walker_base& __position)
01743         { _Node* __tmp = __position._C_w_cur;
01744           _Node* __parent = (_Node*)__tmp->_C_parent;
01745 
01746           if(__parent == NULL)
01747           { 
01748             this->_C_node = _C_create_node();
01749             return __tmp;
01750           }
01751           else
01752           {
01753             children_iterator __ip = __parent->get_childentry_iterator(__tmp);
01754 
01755             __parent->_C_children.erase(__ip);
01756             __parent = _C_create_node();
01757             __parent->_C_data = 0;
01758             __parent->_C_children.insert(__parent->_C_children.end(), __tmp);
01759             __tmp->_C_parent = __parent;
01760             return __parent;
01761           }
01762         }
01763 
01764 
01769   bool erase_child(const __walker_base& __position,
01770                    const children_iterator& __It)
01771         {
01772           _Node* __chld = (_Node*)*__It;
01773 
01774           if(!__chld->_C_children.empty())
01775           { return false; }
01776           else
01777           {
01778             __position->_C_w_cur->_C_children.erase(__It);
01779             _C_put_node(__chld);
01780             return true;
01781           }
01782         }
01783 
01789   _Node* erase_subtree(const __walker_base& __position,
01790                                 const children_iterator& __It)
01791         { _Node* __chld = (_Node*)*__It;
01792           _Node* __tmp = _C_create_node();
01793 
01794           __position->_C_w_cur->_C_children.erase(__It);
01795           __chld->_C_parent = __tmp;
01796           __tmp->_C_data = 0;
01797           __tmp->_C_children.insert(__tmp->_C_children.end(), __chld);
01798           return __tmp;
01799         }
01800   
01804   size_type depth(const walker& __position)
01805         { size_type __d=0;
01806           _Node* __x = __position._C_w_cur;
01807           while(__x != NULL)
01808           {
01809             __x = (_Node*)__x._C_parent;
01810             __d++;
01811           }
01812           return __d;
01813         }
01814 
01816   void clear() { _Base::clear(); }
01817 
01822   __Tree_t(size_type __n, const _Tp& __value,
01823         const allocator_type& __a = allocator_type()) : _Base(__a)
01824     { insert(root(), __n, __value); }
01829   explicit __Tree_t(size_type __n) : _Base(allocator_type())
01830     { insert(root(), __n, _Tp()); }
01831 
01832 private:
01834   _Node* copy_subtree(_Node* __x, _Node* __parent)
01835   { children_iterator cit;
01836 
01837     _Node* __h = _C_create_node();
01838     std::_Construct(&__h->_C_data, __x->_C_data);
01839     __h->_C_parent = (void*)__parent;
01840     for(cit = __x->_C_children.begin(); cit != __x->_C_children.end(); ++cit)
01841       __h->_C_children.insert(__h->_C_children.end(),
01842                         copy_subtree((_Node*)*cit, __h));
01843     return __h;
01844   }
01845 
01846 public:
01848   __Tree_t(const _Self& __x) : _Base(__x.get_allocator())
01849     { children_iterator cit;
01850       for(cit = __x._C_node->_C_children.begin();
01851           cit != __x._C_node->_C_children.end(); ++cit)
01852         this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
01853                 copy_subtree((_Node*)*cit, this->_C_node));
01854     }
01855 
01857   virtual ~__Tree_t() {}
01858 
01860   _Self& operator=(const _Self& __x);
01861 
01866   _Self& operator=(_Node* __x)
01867   {
01868     this->_C_node = __x;
01869     return *this;
01870   }
01871 
01872 #if 0
01873   friend bool operator== __VGTL_NULL_TMPL_ARGS (
01874     const __Tree_t& __x, const __Tree_t& __y);
01875 #endif
01876 }; 
01877 
01879 
01883 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
01884 class __Tree : public __Tree_t<_Tp, _Ctr, _Iterator, _Inserter,
01885                                _Tree_node<_Tp,_Ctr,_Iterator>, _Alloc>
01886 {
01887 protected:
01888   typedef void* _Void_pointer;
01889   typedef _Tree_node<_Tp, container_type, children_iterator> _Node;
01890   typedef __Tree_t<_Tp, container_type, children_iterator, _Inserter, _Node, _Alloc> _Base;
01891   typedef __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc> _Self;
01892 
01893 public:
01894   typedef _Node                 node_type;
01895 
01896 public:
01898   typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
01900   typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;
01901 
01902 #ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION
01903 
01904   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
01906   typedef std::reverse_iterator<iterator>       reverse_iterator;
01907 #else /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */
01908 
01909   typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
01910                                          const_reference,difference_type>
01911           const_reverse_iterator;
01913   typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
01914                                          difference_type>
01915           reverse_iterator;
01916 #endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */
01917 
01918 protected:
01919   typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> __walker_base;
01920   typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> __const_walker_base;
01921 
01922 protected:
01923 #ifdef __VGTL_HAS_NAMESPACES
01924   using _Base::_C_node;
01925   using _Base::_C_put_node;
01926   using _Base::_C_get_node;
01927 #endif /* __VGTL_HAS_NAMESPACES */
01928 
01929 public:
01931   explicit __Tree(const allocator_type& __a = allocator_type()) : _Base(__a) {}
01932 
01933   // preorder - postorder - pre and post,
01934   // depth-first - breadth first,
01935   // front-to-back - back-to-front
01936 
01938   walker ground()
01939     { walker __help(_C_node); return __help; }
01940 
01942   const_walker ground() const
01943     { const_walker __help(_C_node); return __help; }
01944 
01946   walker root(children_iterator __it)
01947     { walker __help = root();
01948       __help >>= __it;
01949       return __help; }
01951   const_walker root(children_iterator __it) const
01952     { const_walker __help = root();
01953       __help >>= __it;
01954       return __help; }
01956   walker root()
01957     { return root(_C_node->child_begin()); }
01959   const_walker root() const
01960     { return root(_C_node->child_begin()); }
01961 
01963   iterator begin()
01964     { iterator __help(_C_node, true);
01965       return __help; }
01967   iterator end()
01968     { iterator __help(_C_node);
01969       return __help; }
01970   
01972   const_iterator begin() const
01973     { const_iterator __help(_C_node, true);
01974       return __help; }
01976   const_iterator end() const
01977     { const_iterator __help(_C_node);
01978       return __help; }
01979   
01981   reverse_iterator rbegin()
01982         { return reverse_iterator(end()); }
01984   reverse_iterator rend()
01985         { return reverse_iterator(begin()); }
01986 
01988   const_reverse_iterator rbegin() const
01989         { return const_reverse_iterator(end()); }
01991   const_reverse_iterator rend() const
01992         { return const_reverse_iterator(begin()); }
01993 
01995   reference getroot() { return *ground(); }
01997   const_reference getroot() const { return *ground(); }
01998 
02003   __Tree(size_type __n, const _Tp& __value,
02004         const allocator_type& __a = allocator_type()) : _Base(__a)
02005     { insert(ground(), __n, __value); }
02010   explicit __Tree(size_type __n) : _Base(allocator_type())
02011     { insert(ground(), __n, _Tp()); }
02012 
02013 public:
02015   __Tree(const _Self& __x) : _Base(__x) {}
02016 
02018   virtual ~__Tree() {}
02019 
02021   _Self& operator=(const _Self& __x);
02022 
02027   _Self& operator=(_Node* __x)
02028   {
02029     this->_C_node = __x;
02030     return *this;
02031   }
02032 
02034   friend bool operator== __VGTL_NULL_TMPL_ARGS (
02035     const __Tree& __x, const __Tree& __y);
02036 }; 
02037 
02039 
02043 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02044 class __ITree : public __Tree_t<_Tp, _Ctr, _Iterator, _Inserter,
02045                                _ITree_node<_Tp,_Ctr,_Iterator>, _Alloc>
02046 {
02047 protected:
02048   typedef void* _Void_pointer;
02049   typedef _ITree_node<_Tp, container_type, children_iterator> _Node;
02050   typedef __Tree_t<_Tp,container_type,children_iterator,_Inserter,_Node,_Alloc> _Base;
02051   typedef __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc> _Self;
02052 
02053 public:
02054   typedef _Node                 node_type;
02055 
02057   typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
02059   typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;
02060 
02062   typedef _Tree_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator,_Node>  iterative_walker;
02064   typedef _Tree_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,_Node> const_iterative_walker;
02065 
02066 #ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION
02067 
02068   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
02070   typedef std::reverse_iterator<iterator>       reverse_iterator;
02071 #else /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */
02072 
02073   typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
02074                                          const_reference,difference_type>
02075           const_reverse_iterator;
02077   typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
02078                                          difference_type>
02079           reverse_iterator;
02080 #endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */
02081 
02082 protected:
02083 #ifdef __VGTL_HAS_NAMESPACES
02084   using _Base::_C_node;
02085   using _Base::_C_put_node;
02086   using _Base::_C_get_node;
02087 #endif /* __VGTL_HAS_NAMESPACES */
02088 
02089 public:
02091   explicit __ITree(const allocator_type& __a = allocator_type()) : _Base(__a) {}
02092 
02093   // preorder - postorder - pre and post,
02094   // depth-first - breadth first,
02095   // front-to-back - back-to-front
02096 
02098   iterative_walker root(walker_type wt = cw_pre_post,
02099                         bool front_to_back = true,
02100                         bool depth_first = true)
02101     { iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first);
02102       return __help; }
02103 
02105   const_iterative_walker root(walker_type wt =  cw_pre_post,
02106                               bool front_to_back = true,
02107                               bool depth_first = true) const
02108     { const_iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first);
02109       return __help; }
02110 
02112   iterative_walker through()
02113     { iterative_walker __help(_C_node, 0, 0, 0);
02114       return __help; }
02116   const_iterative_walker through() const
02117     { const_iterative_walker __help(_C_node, 0, 0, 0);
02118       return __help; }
02119 
02121   iterative_walker begin(walker_type wt = cw_pre_post,
02122                          bool front_to_back = true,
02123                          bool depth_first = true)
02124     { iterative_walker __help = root(wt, front_to_back, depth_first);
02125       ++__help;
02126       return __help; }
02128   const_iterative_walker begin(walker_type wt = cw_pre_post,
02129                                bool front_to_back = true,
02130                                bool depth_first = true) const
02131     { const_iterative_walker __help = root(wt, front_to_back, depth_first);
02132       ++__help;
02133       return __help; }
02134 
02136   iterative_walker end(walker_type wt = cw_pre_post,
02137                        bool front_to_back = true,
02138                        bool depth_first = true)
02139     { iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first, false); 
02140       return __help; }
02142   const_iterative_walker end(walker_type wt = cw_pre_post,
02143                              bool front_to_back = true,
02144                              bool depth_first = true) const
02145     { const_iterative_walker __help(_C_node, (int)wt, front_to_back,
02146                           depth_first, false); 
02147       return __help; }
02148 
02150   reverse_iterator rbegin()
02151         { return reverse_iterator(end()); }
02153   reverse_iterator rend()
02154         { return reverse_iterator(begin()); }
02155 
02157   const_reverse_iterator rbegin() const
02158         { return const_reverse_iterator(end()); }
02160   const_reverse_iterator rend() const
02161         { return const_reverse_iterator(begin()); }
02162 
02164   size_type size() const {
02165     size_type __result = 0;
02166     distance(begin(cw_pre), end(cw_pre), __result);
02167     return __result;
02168   }
02169 
02171   reference getroot() { return *root(cw_pre,true,true); }
02173   const_reference getroot() const { return *root(cw_pre,true,true); }
02174 
02176   size_type depth(const iterative_walker& __position)
02177         { return __position._C_w_cur_it.size(); }
02178   
02183   __ITree(size_type __n, const _Tp& __value,
02184         const allocator_type& __a = allocator_type()) : _Base(__a)
02185     { insert(root(), __n, __value); }
02190   explicit __ITree(size_type __n) : _Base(allocator_type())
02191     { insert(root(), __n, _Tp()); }
02192 
02193 public:
02195   __ITree(const _Self& __x) : _Base(__x) {}
02196 
02198   virtual ~__ITree() {}
02199 
02201   _Self& operator=(const _Self& __x);
02202 
02207   _Self& operator=(_Node* __x)
02208   {
02209     this->_C_node = __x;
02210     return *this;
02211   }
02212 
02214   friend bool operator== __VGTL_NULL_TMPL_ARGS (
02215     const __ITree& __x, const __ITree& __y);
02216 }; 
02217 
02218 // if no iterative walkers are available, comparing trees is more difficult
02219 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02220 inline bool operator==(const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
02221                        const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
02222 {
02223   typedef typename __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::const_walker const_walker;
02224   typedef typename __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::children_iterator children_iterator;
02225   const_walker __w1 = __x.ground();
02226   const_walker __w2 = __y.ground();
02227   children_iterator __it1, __it2;
02228 
02229   if(__w1->n_children() != __w2->n_children())
02230     return false;
02231   for(__it1 = __w1->child_begin(), __it2 = __w2->child_begin();
02232       __it1 != __w1->child_end(); ++__it1, ++__it2)
02233   {
02234     if(!compare_trees(__w1 >> __it1, __w2 >> __it2))
02235       return false;
02236   }
02237   return true;
02238 }
02239 
02240 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02241 inline bool operator==(const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
02242                        const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
02243 {
02244   typedef typename __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::const_iterative_walker const_walker;
02245   const_walker __w1 = __x.begin(cw_pre);
02246   const_walker __w2 = __y.begin(cw_pre);
02247   const_walker __e1 = __x.end(cw_pre);
02248   const_walker __e2 = __y.end(cw_pre);
02249   
02250   // compare values and tree structure with a pre-post-order walk
02251   for(; __w1 != __e1 && __w2 != __e2 ; ++__w1, ++__w2)
02252     if(__w1.in_preorder() != __w2.in_preorder() ||
02253        (__w1.in_preorder() && *__w1 != *__w2))
02254       return false;
02255   return __w1 == __e1 && __w2 == __e2;
02256 }
02257 
02258 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02259 inline bool operator<(const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
02260                        const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
02261 {
02262   return lexicographical_compare(__x.begin(), __x.end(),
02263                                  __y.begin(), __y.end());
02264 }
02265 
02266 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02267 inline bool operator<(const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
02268                        const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
02269 {
02270   return lexicographical_compare(__x.begin(cw_pre), __x.end(cw_pre),
02271                                  __y.begin(cw_pre), __y.end(cw_pre));
02272 }
02273 
02274 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02275 __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>&
02276 __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>::operator=(const __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>& __x)
02277 {
02278   children_iterator cit;
02279 
02280   if (this != &__x) {
02281     this->_C_node->clear_tree();
02282     this->_C_node->_C_children.erase(this->_C_node->_C_children.begin(),
02283                         this->_C_node->_C_children.end());
02284     for(cit = __x._C_node->_C_children.begin();
02285         cit != __x._C_node->_C_children.end(); ++cit)
02286       this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
02287                 copy_subtree((_Node*)*cit, this->_C_node));
02288     }
02289   return *this;
02290 }
02291 
02292 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
02293 __ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>&
02294 __ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>::operator=(const __ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>& __x)
02295 {
02296   children_iterator cit;
02297 
02298   if (this != &__x) {
02299     this->_C_node->clear_tree();
02300     this->_C_node->_C_children.erase(this->_C_node->_C_children.begin(),
02301                         this->_C_node->_C_children.end());
02302     for(cit = __x._C_node->_C_children.begin();
02303         cit != __x._C_node->_C_children.end(); ++cit)
02304       this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
02305                 copy_subtree((_Node*)*cit, this->_C_node));
02306     }
02307   return *this;
02308 }
02309 
02311 
02317 template <class _Tp,
02318           template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
02319           class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02320           class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02321 class ntree : public __ITree<_Tp, _SequenceCtr<void*, _PtrAlloc>,
02322                             typename _SequenceCtr<void*, _PtrAlloc>::iterator,
02323                             typename _SequenceCtr<void*, _PtrAlloc>::iterator,
02324                             _Alloc>
02325 {
02326 private:
02327   typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
02328 protected:
02329   typedef ntree<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
02330   
02331 public:
02335   void insert(const __walker_base& __position, const _Tp& __x)
02336         { _Node* __tmp = _C_create_node(__x);
02337           _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
02338           children_iterator __it;
02339 
02340           if(__parent == NULL) // this is the root node
02341           {
02342             __position._C_w_cur->add_all_children(
02343                         back_inserter(__tmp->_C_children), __tmp);
02344             __tmp->_C_parent = __position._C_w_cur;
02345             __position._C_w_cur->clear_children();
02346             __position._C_w_cur->_C_children.insert(
02347                             __position._C_w_cur->_C_children.end(), __tmp);
02348           }
02349           else
02350           {
02351             __it = __parent->get_childentry_iterator(__position._C_w_cur);
02352             *__it = __tmp;
02353             __tmp->clear_children();
02354             __tmp->_C_children.insert(__tmp->_C_children.end(),
02355                             __position._C_w_cur);
02356             __position._C_w_cur->_C_parent = __tmp;
02357             __tmp->_C_parent = __parent;
02358           }
02359         }
02363   void insert(const __walker_base& __position)
02364         { insert(__position, _Tp()); }
02365   
02368   void push_child(const __walker_base& __position, const _Tp& __x) 
02369         { insert_child(__position, __x,
02370                        __position._C_w_cur->_C_children.end()); }
02373   void push_child(const __walker_base& __position)
02374         { push_child(__position, _Tp()); }
02375 
02378   void push_children(const __walker_base& __position, size_type __n,
02379                               const _Tp& __x)
02380         { insert_children(__position, __n, __x,
02381                           __position._C_w_cur->_C_children.end()); }
02384   void push_children(const __walker_base& __position, size_type __n)
02385         { push_children(__position, n, _Tp()); }
02386 
02389   void unshift_child(const __walker_base& __position, const _Tp& __x) 
02390         { insert_child(__position, __x,
02391                        __position._C_w_cur->_C_children.begin()); }
02394   void unshift_child(const __walker_base& __position)
02395         { unshift_child(__position, _Tp()); }
02396 
02399   void unshift_children(const __walker_base& __position, size_type __n,
02400                               const _Tp& __x)
02401         { insert_children(__position, __n, __x,
02402                           __position._C_w_cur->_C_children.begin()); }
02405   void unshift_children(const __walker_base& __position, size_type __n)
02406         { unshift_children(__position, n, _Tp()); }
02407 
02412   void push_subtree(const __walker_base& __position, _Self& __subtree)
02413         {
02414           __subtree.add_all_children(back_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
02415           __subtree.clear_children();
02416         }
02417 
02422   void unshift_subtree(const __walker_base& __position, _Self& __subtree)
02423         {
02424           __subtree.add_all_children(front_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
02425           __subtree.clear_children();
02426         }
02427 
02432   bool pop_child(const __walker_base& __position)
02433         { if(__position._C_w_cur->_C_children.empty())
02434           { return false; }
02435           else
02436           {
02437             children_iterator __it = __position._C_w_cur->_C_children.end();
02438             return erase_child(__position, --__it);
02439           }
02440         }
02441 
02446   bool shift_child(const __walker_base& __position)
02447         { if(__position._C_w_cur->_C_children.empty())
02448           { return false; }
02449           else
02450           {
02451             children_iterator __it = __position._C_w_cur->_C_children.begin();
02452             return erase_child(__position, __it);
02453           }
02454         }
02455 
02460   _Node* pop_subtree(const __walker_base& __position)
02461         {
02462           if(__position._C_w_cur->_C_children.empty())
02463           { return NULL; }
02464           else
02465           {
02466             children_iterator __it = __position._C_w_cur->_C_children.end();
02467             return erase_subtree(__position, --__it);
02468           }
02469         }
02470 
02475   _Node* shift_subtree(const __walker_base& __position)
02476         {
02477           if(__position._C_w_cur->_C_children.empty())
02478           { return NULL; }
02479           else
02480           {
02481             children_iterator __it = __position._C_w_cur->_C_children.begin();
02482             return erase_subtree(__position, __it);
02483           }
02484         }
02485 
02490   _Self& operator=(_Node* __x)
02491   {
02492     this->_C_node = __x;
02493     return *this;
02494   }
02495 };
02496 
02498 
02504 template <class _Tp,
02505           template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
02506           class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02507           class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02508 class rntree : public __Tree<_Tp, _SequenceCtr<void*, _PtrAlloc>,
02509                             typename _SequenceCtr<void*, _PtrAlloc>::iterator,
02510                             typename _SequenceCtr<void*, _PtrAlloc>::iterator,
02511                             _Alloc>
02512 {
02513 private:
02514   typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
02515 protected:
02516   typedef rntree<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
02517   
02518 public:
02522   void insert(const __walker_base& __position, const _Tp& __x)
02523         { _Node* __tmp = _C_create_node(__x);
02524           _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
02525           children_iterator __it;
02526 
02527           if(__parent == NULL) // this is the root node
02528           {
02529             __position._C_w_cur->add_all_children(
02530                         back_inserter(__tmp->_C_children), __tmp);
02531             __tmp->_C_parent = __position._C_w_cur;
02532             __position._C_w_cur->clear_children();
02533             __position._C_w_cur->_C_children.insert(
02534                             __position._C_w_cur->_C_children.end(), __tmp);
02535           }
02536           else
02537           {
02538             __it = __parent->get_childentry_iterator(__position._C_w_cur);
02539             *__it = __tmp;
02540             __tmp->clear_children();
02541             __tmp->_C_children.insert(__tmp->_C_children.end(),
02542                             __position._C_w_cur);
02543             __position._C_w_cur->_C_parent = __tmp;
02544             __tmp->_C_parent = __parent;
02545           }
02546         }
02550   void insert(const __walker_base& __position)
02551         { insert(__position, _Tp()); }
02552   
02555   void push_child(const __walker_base& __position, const _Tp& __x) 
02556         { insert_child(__position, __x,
02557                        __position._C_w_cur->_C_children.end()); }
02560   void push_child(const __walker_base& __position)
02561         { push_child(__position, _Tp()); }
02562 
02565   void push_children(const __walker_base& __position, size_type __n,
02566                               const _Tp& __x)
02567         { insert_children(__position, __n, __x,
02568                           __position._C_w_cur->_C_children.end()); }
02571   void push_children(const __walker_base& __position, size_type __n)
02572         { push_children(__position, n, _Tp()); }
02573 
02576   void unshift_child(const __walker_base& __position, const _Tp& __x) 
02577         { insert_child(__position, __x,
02578                        __position._C_w_cur->_C_children.begin()); }
02581   void unshift_child(const __walker_base& __position)
02582         { unshift_child(__position, _Tp()); }
02583 
02586   void unshift_children(const __walker_base& __position, size_type __n,
02587                               const _Tp& __x)
02588         { insert_children(__position, __n, __x,
02589                           __position._C_w_cur->_C_children.begin()); }
02592   void unshift_children(const __walker_base& __position, size_type __n)
02593         { unshift_children(__position, n, _Tp()); }
02594 
02599   void push_subtree(const __walker_base& __position, _Self& __subtree)
02600         {
02601           __subtree.add_all_children(back_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
02602           __subtree.clear_children();
02603         }
02604 
02609   void unshift_subtree(const __walker_base& __position, _Self& __subtree)
02610         {
02611           __subtree.add_all_children(front_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
02612           __subtree.clear_children();
02613         }
02614 
02619   bool pop_child(const __walker_base& __position)
02620         { if(__position._C_w_cur->_C_children.empty())
02621           { return false; }
02622           else
02623           {
02624             children_iterator __it = __position._C_w_cur->_C_children.end();
02625             return erase_child(__position, --__it);
02626           }
02627         }
02628 
02633   bool shift_child(const __walker_base& __position)
02634         { if(__position._C_w_cur->_C_children.empty())
02635           { return false; }
02636           else
02637           {
02638             children_iterator __it = __position._C_w_cur->_C_children.begin();
02639             return erase_child(__position, __it);
02640           }
02641         }
02642 
02647   _Node* pop_subtree(const __walker_base& __position)
02648         {
02649           if(__position._C_w_cur->_C_children.empty())
02650           { return NULL; }
02651           else
02652           {
02653             children_iterator __it = __position._C_w_cur->_C_children.end();
02654             return erase_subtree(__position, --__it);
02655           }
02656         }
02657 
02662   _Node* shift_subtree(const __walker_base& __position)
02663         {
02664           if(__position._C_w_cur->_C_children.empty())
02665           { return NULL; }
02666           else
02667           {
02668             children_iterator __it = __position._C_w_cur->_C_children.begin();
02669             return erase_subtree(__position, __it);
02670           }
02671         }
02672 
02677   _Self& operator=(_Node* __x)
02678   {
02679     this->_C_node = __x;
02680     return *this;
02681   }
02682 };
02683 
02684 
02686 
02693 template <class _Tp,
02694           template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
02695           class _Key = string,
02696           class _Compare = less<_Key>,
02697           class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02698           class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02699 class atree : public __ITree<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
02700                             pair_adaptor<typename _AssocCtr<_Key, void*,
02701                                          _Compare, _PtrAlloc>::iterator>,
02702                             _Key, _Alloc>
02703 {
02704 protected:
02705   typedef atree<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
02706   
02707 public:
02712   _Self& operator=(_Node* __x)
02713   {
02714     this->_C_node = __x;
02715     return *this;
02716   }
02717 
02721   void insert(const __walker_base& __position, const _Tp& __x, const _Key& __k)
02722         { _Node* __tmp = _C_create_node(__x);
02723           _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
02724           children_iterator __it;
02725 
02726           if(__parent == NULL) // this is the root node
02727           {
02728             __position._C_w_cur->add_all_children(
02729                         inserter(__tmp->_C_children.end()), __tmp);
02730             __tmp->_C_parent = __position._C_w_cur;
02731             __position._C_w_cur->clear_children();
02732             __position._C_w_cur->_C_children.insert(__k, __tmp);
02733           }
02734           else
02735           {
02736             __it = __parent->get_childentry_iterator(__position._C_w_cur);
02737             *__it = __tmp;
02738             __tmp->clear_children();
02739             __tmp->_C_children.insert(__k, __position._C_w_cur);
02740             __position._C_w_cur->_C_parent = __tmp;
02741             __tmp->_C_parent = __parent;
02742           }
02743         }
02747   void insert(const __walker_base& __position, const _Key& __k)
02748         { insert(__position, _Tp(), __k); }
02749 
02750   
02751 };
02752 
02754 
02761 template <class _Key, class _Compare = less<_Key>,
02762           template <class __Key, class __Compare, class __AllocT> class _AssocCtr = std::multiset,
02763           class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02764           class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Key&) >
02765 class stree : public __ITree<_Key, _AssocCtr<_Key&, pointer_adaptor<_Compare>,
02766                                            _PtrAlloc>,
02767                             typename _AssocCtr<_Key&, pointer_adaptor<_Compare>,
02768                                                _PtrAlloc>::iterator,
02769                             _Key&, _Alloc>
02770 {
02771 protected:
02772   typedef stree<_Key,_Compare,_AssocCtr,_PtrAlloc,_Alloc> _Self;
02773   
02774 public:
02779   _Self& operator=(_Node* __x)
02780   {
02781     this->_C_node = __x;
02782     return *this;
02783   }
02784 };
02785 
02787 
02794 template <class _Tp,
02795           template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
02796           class _Key = string,
02797           class _Compare = less<_Key>,
02798           class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02799           class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02800 class ratree : public __Tree<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
02801                             pair_adaptor<typename _AssocCtr<_Key, void*,
02802                                          _Compare, _PtrAlloc>::iterator>,
02803                             _Key, _Alloc>
02804 {
02805 protected:
02806   typedef ratree<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
02807   
02808 public:
02813   _Self& operator=(_Node* __x)
02814   {
02815     this->_C_node = __x;
02816     return *this;
02817   }
02818 
02822   void insert(const __walker_base& __position, const _Tp& __x, const _Key& __k)
02823         { _Node* __tmp = _C_create_node(__x);
02824           _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
02825           children_iterator __it;
02826 
02827           if(__parent == NULL) // this is the root node
02828           {
02829             __position._C_w_cur->add_all_children(
02830                         inserter(__tmp->_C_children.end()), __tmp);
02831             __tmp->_C_parent = __position._C_w_cur;
02832             __position._C_w_cur->clear_children();
02833             __position._C_w_cur->_C_children.insert(__k, __tmp);
02834           }
02835           else
02836           {
02837             __it = __parent->get_childentry_iterator(__position._C_w_cur);
02838             *__it = __tmp;
02839             __tmp->clear_children();
02840             __tmp->_C_children.insert(__k, __position._C_w_cur);
02841             __position._C_w_cur->_C_parent = __tmp;
02842             __tmp->_C_parent = __parent;
02843           }
02844         }
02848   void insert(const __walker_base& __position, const _Key& __k)
02849         { insert(__position, _Tp(), __k); }
02850 
02851   
02852 };
02853 
02855 
02862 template <class _Key, class _Compare = less<_Key>,
02863           template <class __Key, class __Compare, class __AllocT> class _AssocCtr = std::multiset,
02864           class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02865           class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Key&) >
02866 class rstree : public __Tree<_Key, _AssocCtr<_Key&, pointer_adaptor<_Compare>,
02867                                            _PtrAlloc>,
02868                             typename _AssocCtr<_Key&, pointer_adaptor<_Compare>,
02869                                                _PtrAlloc>::iterator,
02870                             _Key&, _Alloc>
02871 {
02872 protected:
02873   typedef rstree<_Key,_Compare,_AssocCtr,_PtrAlloc,_Alloc> _Self;
02874   
02875 public:
02880   _Self& operator=(_Node* __x)
02881   {
02882     this->_C_node = __x;
02883     return *this;
02884   }
02885 };
02886 
02887 __VGTL_END_NAMESPACE
02888               
02889 #endif /* __VGTL_TREE_H_ */

Generated on Tue Nov 4 01:41:24 2003 for Vienna Graph Template Library by doxygen1.2.18