vgtl_tree.h

Go to the documentation of this file.

// Tree implementation -*- C++ -*-

// $Id: vgtl_tree.h 347 2008-02-06 15:20:01Z schilly $
// Copyright (C) 2001-2003 Hermann Schichl
//
// This file is part of the Vienna Graph Template Library.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#ifndef __VGTL_TREE_H_
#define __VGTL_TREE_H_

#include <vector>
#include <list>
#include <multimap>
#include <multiset>
#include <algorithm>
#include <iterator>
#include <string>
#include <utility>
#include <g_data.h>

#define _C_W_preorder   1

#define _C_W_postorder  2

typedef enum {cw_pre = _C_W_preorder, cw_post = _C_W_postorder,
              cw_pre_post = _C_W_preorder|_C_W_postorder} walker_type;

#include <vgtl_helpers.h>
#include <vgtl_intadapt.h>

__VGTL_BEGIN_NAMESPACE
              

template <class _Tp, class _Ctr, class _Iterator>
class _Tree_node
{
private:
  typedef void* _Void_pointer;
  typedef _Iterator _Ctr_iterator;
  typedef _Tree_node<_Tp,_Ctr,_Iterator> _Self;

public:
  _Tp _C_data;
  _Void_pointer _C_parent;
  _Ctr _C_children;

  _Tree_node() { _C_data();
                  __VGTL_TRY {
                    initialize();
                  }
                  __VGTL_UNWIND( );
                }

  void initialize() {
      std::_Construct(&_C_children);
      _C_parent = NULL;
    }
  
  void get_rid_of() {
      std::_Destroy(&_C_children);
    }

  void clear_tree();
  void clear_children()
        { _C_children.erase(_C_children.begin(), _C_children.end()); }

  _Ctr_iterator get_childentry_iterator(_Void_pointer __p)
        { _Ctr_iterator __tmp;
          for(__tmp = _C_children.begin(); __tmp != _C_children.end(); ++__tmp)
            if(*__tmp == __p) break;
          return __tmp;
        }

#ifdef __VGTL_MEMBER_TEMPLATES

  template <class _Output_Iterator>
  void add_all_children(_Output_Iterator fi, _Self* _parent);

  template <class Compare>
  void sort_children(_Ctr_iterator first, _Ctr_iterator last, Compare comp)
  {
    sort(first, last, _G_compare_adaptor<Compare, _Self>(comp));
  }
   
  template <class Compare>
  void sort_parents(_Ctr_iterator first, _Ctr_iterator last, Compare comp) {}
#endif /* __VGTL_MEMBER_TEMPLATES */
};


template <class _Tp, class _Ctr, class _Iterator>
class _ITree_node : public _Tree_node<_Tp,_Ctr,_Iterator>
{
private:
  typedef void* _Void_pointer;
  typedef _Iterator _Ctr_iterator;
  typedef _ITree_node<_Tp,_Ctr,_Iterator> _Self;

public:
  ctree_data_hook _C_data_hook;

  _ITree_node() { _C_data();
                  __VGTL_TRY {
                    initialize();
                  }
                  __VGTL_UNWIND( );
                }

  void initialize() {
      std::_Construct(&_C_children);
      _C_parent = NULL;
      _C_data_hook.f = 0;
    }
  
  void get_rid_of() {
      std::_Destroy(&_C_children);
      std::_Destroy(&_C_data_hook);
    }

  ctree_data_hook& data_hook() { return _C_data_hook; }

};

#ifdef __VGTL_MEMBER_TEMPLATES
template <class _Tp, class _Ctr, class _Iterator>
template <class _Output_Iterator>
void 
_Tree_node<_Tp,_Ctr,_Iterator>::
        add_all_children(_Output_Iterator fi, _Self* _parent)
{ _Ctr_iterator it;
  for(it = _C_children.begin();
      it != _C_children.end();
      ++it)
  {
    *fi++ = *it;
    (*((_Self*)*it))._C_parent = _parent;
  }
};
#endif /* __VGTL_MEMBER_TEMPLATES */

// get rid of the subtree
template <class _Tp, class _Ctr, class _Iterator>
void
_Tree_node<_Tp,_Ctr,_Iterator>::clear_tree()
{
  _Ctr* chld = &this->_C_children;
  _Iterator it;

  for(it = chld->begin(); it != chld->end(); ++it)
    ((_Tree_node<_Tp,_Ctr,_Iterator>*)(*it))->clear_tree();
  this->_C_children.erase(this->_C_children.begin(), this->_C_children.end());
  this->_C_parent = NULL;
  
  std::_Destroy(&this->_C_data);
  get_rid_of();
}

// forward reference
template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
class _Tree_iterator;


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
class _Tree_walker_base
{
public:
  typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node>    walker;
  typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node>  const_walker;
  typedef _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>    _Self;
  typedef _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>       _Itr;


  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;
private:
  typedef _Iterator _Ctr_iterator;

public:

  typedef __one_iterator<void *> parents_iterator;
  typedef _Ctr_iterator children_iterator;
  typedef _Node node_type;

  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

public:
  _Node* _C_w_cur;

public:
  _Tree_walker_base() {}

  _Tree_walker_base(_Node* __x) : _C_w_cur(__x) { }

  _Tree_walker_base(const walker& __x) : _C_w_cur(__x._C_w_cur) {}

  reference operator*() const { return (*_C_w_cur)._C_data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR

  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

public:
  _Self& operator=(const _Itr& __x) {
        _C_w_cur = __x._C_i_cur;
        return *this;
  }

  ctree_data_hook& data_hook() { return (*_C_w_cur)._C_data_hook; }
  ctree_data_hook& parent_data_hook()
        { return ((_Node*)(*_C_w_cur)._C_parent)->_C_data_hook; }

  const _Node* parent() { return (_Node*)(*_C_w_cur)._C_parent; }
  const _Node* node() { return _C_w_cur; }

  size_type n_children() { return _C_w_cur->_C_children.size(); }
  size_type n_parents() { return _C_w_cur->_C_parent ? 1 : 0; }

  bool is_leaf() { return _C_w_cur->_C_children.empty(); }
  bool is_root()
        { return parent() != NULL && (*parent())._C_parent == NULL; }

  bool is_ground() { return parent() == NULL; }
  bool is_sky() { return false; }

  children_iterator child_begin() { return _C_w_cur->_C_children.begin(); }
  children_iterator child_end() { return _C_w_cur->_C_children.end(); }
  
  parents_iterator parent_begin()
        { return parents_iterator(&_C_w_cur->_C_parent); }
  parents_iterator parent_end()
        { return parents_iterator(&_C_w_cur->_C_parent, false); }
  
  template <class _Function>
  _Function for_each_child(_Function __f)
    {
      return for_each(child_begin(), child_end(), __f);
    }
  template <class _Function>
  _Function for_each_parent(_Function __f)
    {
      return for_each(parent_begin(), parent_end(), __f);
    }

  template <class Compare>
  void sort_children(children_iterator first, children_iterator last,
                     Compare comp)
    { (*_C_w_cur).sort_children(first, last, comp); }
 
  template <class Compare>
  void sort_parents(parents_iterator first, parents_iterator last,
                    Compare comp) {}
 
  template <class Compare>
  void sort_children(Compare comp)
  { (*_C_w_cur).sort_children(child_begin(), child_end(), comp); }
 
  template <class Compare>
  void sort_parents(Compare comp) {}
};


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
class _Tree_walker : public _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>
{
public:
  typedef _Tree_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node>              walker;
  typedef _Tree_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node>  const_walker;
  typedef _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>              _Self;

public:
  struct {
    unsigned int order:2;
    unsigned int front_to_back:1;
    unsigned int depth_first:1;
  } _C_w_t;
  bool _C_w_in_preorder;
  std::vector<_Iterator> _C_w_cur_it;

public:
  _Tree_walker() : _C_w_cur_it() {_C_w_cur_it.reserve(32); }

private:
  void _find_start_node();
  void _find_end_node();
  void _find_next_preorder();
  void _find_next_postorder();
  void _find_next_any();
  void _find_prev_preorder();
  void _find_prev_postorder();
  void _find_prev_any();

public:
  _Tree_walker(_Node* __x, int order = (_C_W_preorder|_C_W_postorder),
                bool front_to_back = true, bool depth_first = true,
                bool find_start = true)
        : _C_w_cur_it() {
          _C_w_cur = __x;
          _C_w_cur_it.reserve(32);
          _C_w_t.order = order;
          _C_w_t.front_to_back = front_to_back;
          _C_w_t.depth_first = depth_first;
          if(__x->_C_parent == NULL) // true top node
            _C_w_in_preorder = find_start;
          else if(find_start)
            _find_start_node();
          else
            _find_end_node(); }

  _Tree_walker(const walker& __x) : _C_w_in_preorder(__x._C_w_in_preorder),
                 _C_w_cur_it(__x._C_w_cur_it) {
                 _C_w_cur = __x._C_w_cur;
                 _C_w_t = __x._C_w_t;
                 }


  bool operator==(const _Self& __x) const 
        { return (_C_w_t.order == 0 && __x._C_w_t.order == 0) ||
                 (_C_w_cur == __x._C_w_cur &&
                 _C_w_in_preorder == __x._C_w_in_preorder &&
                 _C_w_t.order == __x._C_w_t.order &&
                 _C_w_t.front_to_back == __x._C_w_t.front_to_back &&
                 _C_w_t.depth_first == __x._C_w_t.depth_first &&
                 _C_w_cur_it == __x._C_w_cur_it); }
  bool operator!=(const _Self& __x) const 
        { return (_C_w_t.order != 0 || __x._C_w_t.order != 0) &&
                 (_C_w_cur != __x._C_w_cur ||
                 _C_w_in_preorder != __x._C_w_in_preorder ||
                 _C_w_t.order != __x._C_w_t.order ||
                 _C_w_t.front_to_back != __x._C_w_t.front_to_back ||
                 _C_w_t.depth_first != __x._C_w_t.depth_first ||
                 _C_w_cur_it != __x._C_w_cur_it); }

public:

  _Self& operator++() {
    if(_C_w_t.depth_first)
    {
      if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
      {
        _find_next_any();
      }
      else if(_C_w_t.order & _C_W_preorder)
      {
        _find_next_preorder();
      }
      else
      {
        _find_next_postorder();
      }
    }
    else
    {
      /**** NOT YET IMPLEMENTED ****/;
    }
    return *this;
  }
  _Self operator++(int) {
    _Self __tmp = *this;
    ++*this;
    return __tmp;
  }

  _Self& operator--() {
    if(_C_w_t.depth_first)
    {
      if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
      {
        _find_prev_any();
      }
      else if(_C_w_t.order & _C_W_preorder)
      {
        _find_prev_preorder();
      }
      else
      {
        _find_prev_postorder();
      }
    }
    else
    {
      /**** NOT YET IMPLEMENTED ****/;
    }
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    --*this;
    return __tmp;
  }


  _Self operator<<(const parents_iterator& __dummy) {
    _Self __tmp = *this;
    _Node *help = __tmp._C_w_cur._C_parent;
    if(help == NULL) // already at root node
    {
      __tmp._C_w_t.order = 0;
    }
    else
    {
      __tmp._C_w_cur = help;
      if(__tmp._C_w_t.order & _C_W_postorder)
        __tmp._C_w_in_preorder = false;
      if(!__tmp._C_w_cur_it.empty())
        pop_back(__tmp._C_w_cur_it);
    }
    return __tmp;
  }
  

  _Self operator>>(const children_iterator& __i) {
    _Self __tmp = *this;
    _Node *help = (_Node*) *__i;
    if(__tmp._C_w_t.order & _C_W_preorder)
      __tmp._C_w_in_preorder = true;
    __tmp._C_w_cur_it.push_back(__i);
    __tmp._C_w_cur = help;
    return __tmp;
  }

  _Self& operator<<=(const parents_iterator& __dummy) {
    _Node *help = _C_w_cur._C_parent;
    if(help == NULL) // already at root node
    {
      _C_w_t.order = 0;
    }
    else
    {
      _C_w_cur = help;
      if(_C_w_t.order & _C_W_postorder)
        _C_w_in_preorder = false;
      if(!_C_w_cur_it.empty())
        pop_back(_C_w_cur_it);
    }
    return *this;
  }
  
  _Self& operator>>=(const children_iterator& __i) {
    _Node *help = (_Node*) *__i;
    if(_C_w_t.order & _C_W_preorder)
      _C_w_in_preorder = true;
    push_back(_C_w_cur_it, __i);
    _C_w_cur = help;
    return *this;
  }

  _Self& operator~() {
    if(_C_w_t.order == (_C_W_preorder | _C_W_postorder))
      _C_w_in_preorder = !_C_w_in_preorder;
    return *this;
  }

  _Self& operator=(const _Itr& __x) {
        _C_w_cur = __x._C_i_cur;
        _C_w_cur_it = __x._C_i_cur_it;
        _C_w_t.order = _C_W_postorder;
        _C_w_t.depth_first = 1;
        _C_w_t.front_to_back = 1;
        return *this;
  }
  
  bool in_preorder() { return _C_w_in_preorder; }
};

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_start_node()
{
  if(_C_w_t.depth_first)
  {
    if(_C_w_t.order & _C_W_preorder)
    {
      _C_w_in_preorder = true;
    }
    else if(_C_w_t.order & _C_W_postorder)
    {
      _C_w_in_preorder = false;
      if(_C_w_t.front_to_back)
      {
        while(!_C_w_cur->_C_children.empty())
        {
          _Ctr_iterator help;
      
          help = _C_w_cur->_C_children.begin();
          _C_w_cur = (_Node*)*help;
          _C_w_cur_it.push_back(help);
        }
      }
      else
      {
        while(!_C_w_cur->_C_children.empty())
        {
          _Ctr_iterator help;
      
          help = _C_w_cur->_C_children.end();
          --help;
          _C_w_cur = (_Node*)*help;
          _C_w_cur_it.push_back(help);
        }
      }
    }
  }
  else
  {
    /**** NOT YET IMPLEMENTED ****/;
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_end_node()
{
  if(_C_w_t.depth_first)
  {
    if(_C_w_t.order & _C_W_postorder)
    {
      _C_w_in_preorder = false;
      (&_C_w_cur_it)->~std::vector();
      _C_w_cur_it.reserve(32);
    }
    else if(_C_w_t.order & _C_W_postorder)
    {
      _C_w_in_preorder = true;
      if(_C_w_t.front_to_back)
      {
        while(!_C_w_cur->_C_children.empty())
        {
          _Ctr_iterator help;
      
          help = _C_w_cur->_C_children.begin();
          _C_w_cur = (_Node*)*help;
          _C_w_cur_it.push_back(help);
        }
      }
      else
      {
        while(!_C_w_cur->_C_children.empty())
        {
          _Ctr_iterator help;
      
          help = _C_w_cur->_C_children.end();
          --help;
          _C_w_cur = (_Node*)*help;
          _C_w_cur_it.push_back(help);
        }
      }
    }
  }
  else
  {
    /**** NOT YET IMPLEMENTED ****/;
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_preorder()
{
  _Ctr_iterator help;

  if(_C_w_cur->_C_children.empty()) // this is a leaf -> go up
  {
    while(1)
    {
      if(_C_w_cur_it.empty()) // all done
      {
        if(_C_w_cur->_C_parent == NULL && _C_w_in_preorder)
          _C_w_in_preorder = false;
        else
          _C_w_t.order = 0;
        break;
      }
      help = _C_w_cur_it.back();
      _C_w_cur_it.pop_back();
      _C_w_cur = (_Node*)_C_w_cur->_C_parent;
      if(_C_w_t.front_to_back)
      {
        ++help;
        if(help != _C_w_cur->_C_children.end())
        // go to next subtree
        {
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          break;
        }
      }
      else
      {
        if(help != _C_w_cur->_C_children.begin())
        // go to next subtree
        {
          --help;
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          break;
        }
      }
    }
  }
  else if(!_C_w_in_preorder)            // from end to through
    _C_w_t.order = 0;
  else // go down
  {
    if(_C_w_t.front_to_back)
      help = _C_w_cur->_C_children.begin();
    else
    {
      help = _C_w_cur->_C_children.end();
      help--;
    }
    _C_w_cur_it.push_back(help);
    _C_w_cur = (_Node*)*help;
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_postorder()
{
  if(_C_w_in_preorder)
  {
    _C_w_in_preorder = false;
    _find_start_node();
  }
  else if(_C_w_cur_it.empty())
  {
    _C_w_t.order = 0;
  }
  else
  {
    _Ctr_iterator help = _C_w_cur_it.back();
    _C_w_cur_it.pop_back();
    if(_C_w_t.front_to_back)
    {
      ++help;
      if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
      // go to next subtree
      {
        do
        {
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          help = _C_w_cur->_C_children.begin();
        } while(!_C_w_cur->_C_children.empty());
      }
      else // this was the last subtree -> hop one level up
      {
        _C_w_cur = (_Node*)_C_w_cur->_C_parent;
      }
    }
    else
    {
      if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
      // go to next subtree
      {
        do
        {
          --help;
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          help = _C_w_cur->_C_children.end();
        } while(!_C_w_cur->_C_children.empty());
      }
      else // this was the last subtree -> hop one level up
      {
        _C_w_cur = (_Node*)_C_w_cur->_C_parent;
      }
    }
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_next_any() {
  if(_C_w_in_preorder) // step down
  {
    if(_C_w_cur->_C_children.empty()) // this is a leaf
      _C_w_in_preorder = false; // immediatly switch to post order
    else // step down
    {
      _Ctr_iterator help;
      if(_C_w_t.front_to_back)
        help = _C_w_cur->_C_children.begin();
      else
      {
        help = _C_w_cur->_C_children.end();
        --help;
      }
      _C_w_cur_it.push_back(help);
      _C_w_cur = (_Node*)*help;
    }
  }
  else
  {
    _Ctr_iterator help;

    if(!_C_w_cur_it.empty()) // we are somewhere down
    {
      help = _C_w_cur_it.back();
      _C_w_cur_it.pop_back();
      if(_C_w_t.front_to_back)
      {
        ++help;
        if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
        // go to next subtree
        {
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          _C_w_in_preorder = true;
        }
        else // this was the last subtree
        {
          _C_w_cur = (_Node*)_C_w_cur->_C_parent;
        }
      }
      else
      {
        if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
        // go to next subtree
        {
          --help;
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          _C_w_in_preorder = true;
        }
        else // this was the last subtree
        {
          _C_w_cur = (_Node*)_C_w_cur->_C_parent;
        }
      }
    }
    else // there is nothing left -> we have reached the end.
    {
      _C_w_t.order = 0;
    }
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_preorder()
{
  if(!_C_w_in_preorder)
  {
    _C_w_t.order = _C_W_postorder;
    _C_w_t.front_to_back = !_C_w_t.front_to_back;
    _find_start_node();
    _C_w_in_preorder = true;
    _C_w_t.order = _C_W_preorder;
    _C_w_t.front_to_back = !_C_w_t.front_to_back;
  }
  else if(_C_w_cur_it.empty())
  {
    _C_w_t.order = 0;
  }
  else
  {
    _Ctr_iterator help = _C_w_cur_it.back();
    _C_w_cur_it.pop_back();
    if(!_C_w_t.front_to_back)
    {
      ++help;
      if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
      // go to next subtree
      {
        do
        {
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          help = _C_w_cur->_C_children.begin();
        } while(!_C_w_cur->_C_children.empty());
      }
      else // this was the last subtree -> hop one level up
      {
        _C_w_cur = (_Node*)_C_w_cur->_C_parent;
      }
    }
    else
    {
      if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
      // go to next subtree
      {
        do
        {
          --help;
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          help = _C_w_cur->_C_children.end();
        } while(!_C_w_cur->_C_children.empty());
      }
      else // this was the last subtree -> hop one level up
      {
        _C_w_cur = (_Node*)_C_w_cur->_C_parent;
      }
    }
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_postorder()
{
  _Ctr_iterator help;

  if(_C_w_cur->_C_children.empty()) // this is a leaf -> go up
  {
    while(1)
    {
      if(_C_w_cur_it.empty()) // all done
      {
        if(_C_w_cur->_C_parent == NULL && !_C_w_in_preorder)
          _C_w_in_preorder = true;
        else
          _C_w_t.order = 0;
        break;
      }
      help = _C_w_cur_it.back();
      _C_w_cur_it.pop_back();
      _C_w_cur = (_Node*)_C_w_cur->_C_parent;
      if(!_C_w_t.front_to_back)
      {
        ++help;
        if(help != _C_w_cur->_C_children.end())
        // go to next subtree
        {
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          break;
        }
      }
      else
      {
        if(help != _C_w_cur->_C_children.begin())
        // go to next subtree
        {
          --help;
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          break;
        }
      }
    }
  }
  else if(_C_w_in_preorder)             // from end to through
    _C_w_t.order = 0;
  else // go down
  {
    if(!_C_w_t.front_to_back)
      help = _C_w_cur->_C_children.begin();
    else
    {
      help = _C_w_cur->_C_children.end();
      help--;
    }
    _C_w_cur_it.push_back(help);
    _C_w_cur = (_Node*)*help;
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::_find_prev_any()
{
  if(!_C_w_in_preorder) // step down
  {
    if(_C_w_cur->_C_children.empty()) // this is a leaf
      _C_w_in_preorder = true; // immediatly switch to pre order
    else // step down
    {
      _Ctr_iterator help;
      if(!_C_w_t.front_to_back)
        help = _C_w_cur->_C_children.begin();
      else
      {
        help = _C_w_cur->_C_children.end();
        --help;
      }
      _C_w_cur_it.push_back(help);
      _C_w_cur = (_Node*)*help;
    }
  }
  else
  {
    _Ctr_iterator help;

    if(!_C_w_cur_it.empty()) // we are somewhere down
    {
      help = _C_w_cur_it.back();
      _C_w_cur_it.pop_back();
      if(!_C_w_t.front_to_back)
      {
        ++help;
        if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.end())
        // go to next subtree
        {
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          _C_w_in_preorder = false;
        }
        else // this was the last subtree
        {
          _C_w_cur = (_Node*)_C_w_cur->_C_parent;
        }
      }
      else
      {
        if(help != ((_Node*)_C_w_cur->_C_parent)->_C_children.begin())
        // go to next subtree
        {
          --help;
          _C_w_cur_it.push_back(help);
          _C_w_cur = (_Node*)*help;
          _C_w_in_preorder = false;
        }
        else // this was the last subtree
        {
          _C_w_cur = (_Node*)_C_w_cur->_C_parent;
        }
      }
    }
    else // there is nothing left -> we have reached the end.
    {
      _C_w_t.order = 0;
    }
  }
}


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
class _RTree_walker : public _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>
{
public:
  typedef _RTree_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node>             walker;
  typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node> const_walker;
  typedef _RTree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>             _Self;

public:
  _RTree_walker() {}

  _RTree_walker(_Node* __x) { _C_w_cur = __x; }

  _RTree_walker(const walker& __x) { _C_w_cur = __x._C_w_cur; }

public:

  bool operator==(const _Self& __x) const 
        { return _C_w_cur == __x._C_w_cur; }
  bool operator!=(const _Self& __x) const 
        { return _C_w_cur != __x._C_w_cur; }


  _Self operator<<(const parents_iterator& __dummy) {
    _Self __tmp = *this;
    _Node *help = __tmp._C_w_cur._C_parent;
    if(help != NULL) // already at root node
      __tmp._C_w_cur = help;
    return __tmp;
  }
  

  _Self operator>>(const children_iterator& __i) {
    _Self __tmp = *this;
    __tmp._C_w_cur = (_Node*) *__i;
    return __tmp;
  }

  _Self& operator<<=(const parents_iterator& __dummy) {
    _Node *help = _C_w_cur._C_parent;
    if(help != NULL) // already at root node
      _C_w_cur = help;
    return *this;
  }
  
  _Self& operator>>=(const children_iterator& __i) {
    _C_w_cur = (_Node*) *__i;
    return *this;
  }
  
  _Self& operator=(const _Itr& __x) {
        _C_w_cur = __x._C_i_cur;
        return *this;
  }

  _Self& operator=(const _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>& __x) 
  {
        _C_w_cur = __x._C_w_cur;
        return *this;
  }
};


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
class _Tree_iterator
{
public:
  typedef _Tree_iterator<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_Node>             iterator;
  typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_Node> const_iterator;
  typedef _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>             _Self;
  typedef _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>               _Walk;


  typedef std::bidirectional_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef _Iterator _Ctr_iterator;

protected:
  _Node* _C_i_cur;
  std::vector<_Ctr_iterator> _C_i_cur_it;

public:
  _Tree_iterator() : _C_i_cur_it() {_C_i_cur_it.reserve(32);}
  _Tree_iterator(const iterator& __x) : _C_i_cur(__x._C_i_cur),
                                         _C_i_cur_it(__x._C_i_cur_it) {}
  _Tree_iterator(const _Node* __n, bool st = false) : _C_i_cur_it()
        { _C_i_cur = __n; if(st) find_start_node(); }


  bool operator==(const _Self& __x) const
        { return (_C_i_cur->_C_parent == NULL &&
                   __x._C_i_cur->_C_parent == NULL) ||
                 ( _C_i_cur == __x._C_i_cur &&
                   _C_i_cur_it == __x._C_i_cur_it);
        }
  bool operator!=(const _Self& __x) const
        { return (_C_i_cur->_C_parent != NULL ||
                   __x._C_i_cur->_C_parent != NULL) &&
                 ( _C_i_cur != __x._C_i_cur ||
                   _C_i_cur_it != __x._C_i_cur_it);
        }

  reference operator*() const { return (*_C_i_cur)._C_data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR

  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  ctree_data_hook& data_hook() { return (*_C_i_cur)._C_data_hook; }

private:
  void find_start_node();
  void find_next_node();
  void find_prev_node();
  
public:
  _Self& operator=(const _Walk& __x) {
        _C_i_cur = __x._C_w_cur;
        _C_i_cur_it.erase(_C_i_cur_it.begin(), _C_i_cur_it.end());
        // we have to find the next postorder node and
        // initialize the vector of iterators.
        find_start_node();
        return *this;
  }


  _Self& operator++() {
    find_next_node();
    return *this;
  }
  _Self operator++(int) {
    _Self __tmp = *this;
    ++*this;
    return __tmp;
  }

  _Self& operator--() {
    find_prev_node();
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    --*this;
    return __tmp;
  }
};

#ifndef __VGTL_CLASS_PARTIAL_SPECIALIZATION
template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _TI, class _TN>
inline std::bidirectional_iterator_tag
iterator_category(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_TI,_TN>&)
{
  return std::bidirectional_iterator_tag();
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _TI, class _TN>
inline _Tp*
value_type(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_TI,_TN>&)
{
  return 0;
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _TI, class _TN>
inline ptrdiff_t*
distance_type(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_TI,_TN>&)
{
  return 0;
}

#endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void
_Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_start_node()
{
  _Node* __s = _C_i_cur;
  _Ctr_iterator __help;

  while(__s->_C_parent != NULL)
  {
    __help = ((_Node*)__s->_C_parent)->get_childentry_iterator((void*)__s);
    _C_i_cur_it.insert(_C_i_cur_it.begin(), __help);
    __s = (_Node*)__s->_C_parent;
  }
  while(!_C_i_cur->_C_children.empty())
  {
    __help = _C_i_cur->_C_children.begin();
    _C_i_cur = (_Node*)*__help;
    _C_i_cur_it.push_back(__help);
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void
_Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_next_node()
{
  if(_C_i_cur->_C_parent != NULL) // not yet through
  {
    _Ctr_iterator __help = _C_i_cur_it.back();
    _C_i_cur_it.pop_back();
    ++__help;
    if(__help != ((_Node*)_C_i_cur->_C_parent)->_C_children.end())
    { // go to next subtree
      do
      {
        _C_i_cur_it.push_back(__help);
        _C_i_cur = (_Node*)*__help;
        __help = _C_i_cur->_C_children.begin();
      } while(!_C_i_cur->_C_children.empty());
    }
    else // this was the last subtree -> hop one level up
    {
      _C_i_cur = (_Node*)_C_i_cur->_C_parent;
    }
  }
}

template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _Node>
void
_Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_Node>::find_prev_node()
{
  _Ctr_iterator help;

  if(_C_i_cur->_C_children.empty()) // this is a leaf -> go up
  {
    while(1)
    {
      if(_C_i_cur->_C_parent == NULL) // already through
        break;
      help = _C_i_cur_it.back();
      _C_i_cur_it.pop_back();
      _C_i_cur = (_Node*)_C_i_cur->_C_parent;
      if(help != _C_i_cur->_C_children.begin())
      { // go to prev subtree
        --help;
        _C_i_cur_it.push_back(help);
        _C_i_cur = (_Node*)*help;
        break;
      }
    }
  }
  else // go down
  {
    help = _C_i_cur->_C_children.end();
    --help;
    _C_i_cur_it.push_back(help);
    _C_i_cur = (_Node*)*help;
  }
}

#ifdef __VGTL_USE_STD_ALLOCATORS


template <class _Tp, class _Ctr, class _TI, class _Node, class _Allocator,
          bool _IsStatic>
class _Tree_alloc_base {
public:
  typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return _Node_allocator; }

  _Tree_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}

protected:
  _Node* _C_get_node()
    { return _Node_allocator.allocate(1); }
  void _C_put_node(_Node* __p)
    { _Node_allocator.deallocate(__p, 1); }

protected:
  typename std::_Alloc_traits<_Node, _Allocator>::allocator_type
           _Node_allocator;

protected:
  _Node* _C_node;
};


template <class _Tp, class _Ctr, class _TI, class _Node, class _Allocator>
class _Tree_alloc_base<_Tp, _Ctr, _TI, _Node, _Allocator, true> {
public:
  typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }

  _Tree_alloc_base(const allocator_type&) {}

protected:
  typedef typename std::_Alloc_traits<_Node, _Allocator>::_Alloc_type
          _Alloc_type;
  _Node* _C_get_node()
    { return _Alloc_type::allocate(1); }
  void _C_put_node(_Node* __p)
    { _Alloc_type::deallocate(__p, 1); }

protected:
  _Node* _C_node;
};


template <class _Tp, class _Ctr, class _TI, class _Node, class _Alloc>
class _Tree_base
  : public _Tree_alloc_base<_Tp, _Ctr, _TI, _Node, _Alloc,
  std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
public:
  typedef _Tree_alloc_base<_Tp, _Ctr, _TI, _Node, _Alloc,
  std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
          _Base;
  typedef typename _Base::allocator_type allocator_type;

  typedef _Ctr container_type;
  typedef _TI children_iterator;
  typedef __one_iterator<void *> parents_iterator;

  _Tree_base(const allocator_type& __a) : _Base(__a) {
    _C_node = _C_get_node();
    __VGTL_TRY {
      _C_node->initialize();
    }
    __VGTL_UNWIND(_C_put_node(_C_node));
  }
  virtual ~_Tree_base() {
    clear();
    _C_put_node(_C_node);
  }

  void clear();
  void clear_children()
        { _C_node->clear_children(); }

  template <class _Output_Iterator>
  void add_all_children(_Output_Iterator fi, _Node* _parent);
};
#else /* __VGTL_USE_STD_ALLOCATORS */


template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
class _Tree_base
{
public:
  typedef _Alloc allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }
  
  typedef _Ctr container_type;
  typedef _Iterator children_iterator;
  typedef __one_iterator<void *> parents_iterator;

  _Tree_base(const allocator_type&) {
    _C_node = _C_get_node();
    _C_node->initialize();
  }
  virtual ~_Tree_base() {
    clear();
    _C_put_node(_C_node);
  }

  void clear();

protected:
  typedef simple_alloc<Node, _Alloc> _Alloc_type;
  _Node* _C_get_node()
    { return _Alloc_type::allocate(1); }
  void _C_put_node(_Node* __p)
    { _Alloc_type::deallocate(__p, 1); }

protected:
  _Node* _C_node;

  void clear_children()
     { _C_node->clear_children(); }

  template <class _Output_Iterator>
  void add_all_children(_Output_Iterator fi, _Node* _parent);
};

#endif /* __VGTL_USE_STD_ALLOCATORS */

template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
template <class _Output_Iterator>
inline void
_Tree_base<_Tp,_Ctr,_Iterator,_Node,_Alloc>::add_all_children(
    _Output_Iterator fi, _Node* _parent)
{ _C_node->add_all_children(fi, _parent); };

template <class _Tp, class _Ctr, class _Iterator, class _Node, class _Alloc>
void
_Tree_base<_Tp,_Ctr,_Iterator,_Node,_Alloc>::clear()
{
  this->_C_node->clear_tree();
  this->_C_node->clear_children();
}


template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Node,
          class _Alloc>
class __Tree_t : public _Tree_base<_Tp, _Ctr, _Iterator, _Node, _Alloc>
{
public:
  typedef _Ctr  container_type;
  typedef _Iterator children_iterator;
  typedef __one_iterator<void *> parents_iterator;
  typedef _Inserter container_insert_arg;

protected:
  typedef void* _Void_pointer;
  typedef _Tree_base<_Tp, container_type, children_iterator, _Node, _Alloc> _Base;
  typedef __Tree_t<_Tp,_Ctr,_Iterator,_Inserter,_Node,_Alloc> _Self;

public:

  typedef _Tp                   value_type;
  typedef _Node                 node_type;
  typedef value_type*           pointer;
  typedef const value_type*     const_pointer;
  typedef value_type&           reference;
  typedef const value_type&     const_reference;
  typedef size_t                size_type;
  typedef ptrdiff_t             difference_type;

  typedef typename _Base::allocator_type allocator_type;
  allocator_type get_allocator() const { return _Base::get_allocator(); }

public:
  typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
  typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;

#ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION

  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef std::reverse_iterator<iterator>       reverse_iterator;
#else /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

  typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
                                         const_reference,difference_type>
          const_reverse_iterator;
  typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
                                         difference_type>
          reverse_iterator;
#endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

  typedef _RTree_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> walker;
  typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_walker;

protected:
  typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> __walker_base;
  typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> __const_walker_base;

protected:
#ifdef __VGTL_HAS_NAMESPACES
  using _Base::_C_node;
  using _Base::_C_put_node;
  using _Base::_C_get_node;
#endif /* __VGTL_HAS_NAMESPACES */

protected:
  _Node* _C_create_node(const _Tp& __x)
  {
    _Node* __p = _C_get_node();
    __VGTL_TRY {
      __p->initialize();
      std::_Construct(&__p->_C_data, __x);
    }
    __VGTL_UNWIND(_C_put_node(__p));
    return __p;
  }

  _Node* _C_create_node()
  {
    _Node* __p = _C_get_node();
    __VGTL_TRY {
      __p->initialize();
      std::_Construct(&__p->_C_data);
    }
    __VGTL_UNWIND(_C_put_node(__p));
    return __p;
  }

public:
  explicit __Tree_t(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  bool empty() const { return _C_node->_C_children.empty(); }

  size_type max_size() const { return size_type(-1); }

  void swap(_Self& __x)
    { __STD::swap(_C_node, __x._C_node); }

  void insert_child(const __walker_base& __position, const _Tp& __x,
                             const container_insert_arg& __It) 
        { _Node* __tmp = _C_create_node(__x);
          __position._C_w_cur->_C_children.insert(__It,__tmp);
          __tmp->_C_parent = __position._C_w_cur;
        }
  void insert_child(const __walker_base& __position,
                             const container_insert_arg& __It) 
        { insert_child(__position, _Tp(), __It); }

  void insert_children(const __walker_base& __position, size_type __n,
                       const _Tp& __x, const children_iterator& __It)
        { _Node* __tmp;
          std::vector<_Node *> __Ctr;
          __Ctr.reserve(__n);

          for(int i=n; i>0; i--)
          {
            __tmp = _C_create_node(__x);
            __Ctr.insert(__Ctr.end(), __tmp);
            __tmp->_C_parent = __position._C_w_cur;
          }
          __position._C_w_cur->_C_children.insert(__It,
                        __Ctr.begin(), __Ctr.end());
        }

  void insert_subtree(const __walker_base& __position,
                      _Self& __subtree, const children_iterator& __It) 
        {
          __subtree.add_all_children(inserter(__position._C_w_cur->_C_children,
                __It), __position._C_w_cur);
          __subtree.clear_children();
        }
  
  void erase(const __walker_base& __position)
        { _Node* __tmp = __position._C_w_cur;
          _Node* __parent = (_Node*)__tmp->_C_parent;

          if(__parent != NULL)
          { // cannot erase the (virtual!) root node
            children_iterator __ip = __parent->get_childentry_iterator(__tmp);

            if(!__tmp->_C_children.empty())
            {
              children_iterator __it = __tmp->_C_children.end();

              *__ip = *--__it;
              ((_Node*)*__it)->_C_parent = __parent;
              __tmp->_C_children.erase(__it);
              if(!__tmp->_C_children.empty())
              {
                __tmp->add_all_children(inserter(__parent->_C_children, __ip),
                        __parent);
                __tmp->clear_children();
              }
            }
            _C_put_node(__tmp);
          }
        }

  _Node* erase_tree(const __walker_base& __position)
        { _Node* __tmp = __position._C_w_cur;
          _Node* __parent = (_Node*)__tmp->_C_parent;

          if(__parent == NULL)
          { 
            this->_C_node = _C_create_node();
            return __tmp;
          }
          else
          {
            children_iterator __ip = __parent->get_childentry_iterator(__tmp);

            __parent->_C_children.erase(__ip);
            __parent = _C_create_node();
            __parent->_C_data = 0;
            __parent->_C_children.insert(__parent->_C_children.end(), __tmp);
            __tmp->_C_parent = __parent;
            return __parent;
          }
        }


  bool erase_child(const __walker_base& __position,
                   const children_iterator& __It)
        {
          _Node* __chld = (_Node*)*__It;

          if(!__chld->_C_children.empty())
          { return false; }
          else
          {
            __position->_C_w_cur->_C_children.erase(__It);
            _C_put_node(__chld);
            return true;
          }
        }

  _Node* erase_subtree(const __walker_base& __position,
                                const children_iterator& __It)
        { _Node* __chld = (_Node*)*__It;
          _Node* __tmp = _C_create_node();

          __position->_C_w_cur->_C_children.erase(__It);
          __chld->_C_parent = __tmp;
          __tmp->_C_data = 0;
          __tmp->_C_children.insert(__tmp->_C_children.end(), __chld);
          return __tmp;
        }
  
  size_type depth(const walker& __position)
        { size_type __d=0;
          _Node* __x = __position._C_w_cur;
          while(__x != NULL)
          {
            __x = (_Node*)__x._C_parent;
            __d++;
          }
          return __d;
        }

  void clear() { _Base::clear(); }

  __Tree_t(size_type __n, const _Tp& __value,
        const allocator_type& __a = allocator_type()) : _Base(__a)
    { insert(root(), __n, __value); }
  explicit __Tree_t(size_type __n) : _Base(allocator_type())
    { insert(root(), __n, _Tp()); }

private:
  _Node* copy_subtree(_Node* __x, _Node* __parent)
  { children_iterator cit;

    _Node* __h = _C_create_node();
    std::_Construct(&__h->_C_data, __x->_C_data);
    __h->_C_parent = (void*)__parent;
    for(cit = __x->_C_children.begin(); cit != __x->_C_children.end(); ++cit)
      __h->_C_children.insert(__h->_C_children.end(),
                        copy_subtree((_Node*)*cit, __h));
    return __h;
  }

public:
  __Tree_t(const _Self& __x) : _Base(__x.get_allocator())
    { children_iterator cit;
      for(cit = __x._C_node->_C_children.begin();
          cit != __x._C_node->_C_children.end(); ++cit)
        this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
                copy_subtree((_Node*)*cit, this->_C_node));
    }

  virtual ~__Tree_t() {}

  _Self& operator=(const _Self& __x);

  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }

#if 0
  friend bool operator== __VGTL_NULL_TMPL_ARGS (
    const __Tree_t& __x, const __Tree_t& __y);
#endif
}; 


template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
class __Tree : public __Tree_t<_Tp, _Ctr, _Iterator, _Inserter,
                               _Tree_node<_Tp,_Ctr,_Iterator>, _Alloc>
{
protected:
  typedef void* _Void_pointer;
  typedef _Tree_node<_Tp, container_type, children_iterator> _Node;
  typedef __Tree_t<_Tp, container_type, children_iterator, _Inserter, _Node, _Alloc> _Base;
  typedef __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc> _Self;

public:
  typedef _Node                 node_type;

public:
  typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
  typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;

#ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION

  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef std::reverse_iterator<iterator>       reverse_iterator;
#else /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

  typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
                                         const_reference,difference_type>
          const_reverse_iterator;
  typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
                                         difference_type>
          reverse_iterator;
#endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

protected:
  typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> __walker_base;
  typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> __const_walker_base;

protected:
#ifdef __VGTL_HAS_NAMESPACES
  using _Base::_C_node;
  using _Base::_C_put_node;
  using _Base::_C_get_node;
#endif /* __VGTL_HAS_NAMESPACES */

public:
  explicit __Tree(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  // preorder - postorder - pre and post,
  // depth-first - breadth first,
  // front-to-back - back-to-front

  walker ground()
    { walker __help(_C_node); return __help; }

  const_walker ground() const
    { const_walker __help(_C_node); return __help; }

  walker root(children_iterator __it)
    { walker __help = root();
      __help >>= __it;
      return __help; }
  const_walker root(children_iterator __it) const
    { const_walker __help = root();
      __help >>= __it;
      return __help; }
  walker root()
    { return root(_C_node->child_begin()); }
  const_walker root() const
    { return root(_C_node->child_begin()); }

  iterator begin()
    { iterator __help(_C_node, true);
      return __help; }
  iterator end()
    { iterator __help(_C_node);
      return __help; }
  
  const_iterator begin() const
    { const_iterator __help(_C_node, true);
      return __help; }
  const_iterator end() const
    { const_iterator __help(_C_node);
      return __help; }
  
  reverse_iterator rbegin()
        { return reverse_iterator(end()); }
  reverse_iterator rend()
        { return reverse_iterator(begin()); }

  const_reverse_iterator rbegin() const
        { return const_reverse_iterator(end()); }
  const_reverse_iterator rend() const
        { return const_reverse_iterator(begin()); }

  reference getroot() { return *ground(); }
  const_reference getroot() const { return *ground(); }

  __Tree(size_type __n, const _Tp& __value,
        const allocator_type& __a = allocator_type()) : _Base(__a)
    { insert(ground(), __n, __value); }
  explicit __Tree(size_type __n) : _Base(allocator_type())
    { insert(ground(), __n, _Tp()); }

public:
  __Tree(const _Self& __x) : _Base(__x) {}

  virtual ~__Tree() {}

  _Self& operator=(const _Self& __x);

  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }

  friend bool operator== __VGTL_NULL_TMPL_ARGS (
    const __Tree& __x, const __Tree& __y);
}; 


template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
class __ITree : public __Tree_t<_Tp, _Ctr, _Iterator, _Inserter,
                               _ITree_node<_Tp,_Ctr,_Iterator>, _Alloc>
{
protected:
  typedef void* _Void_pointer;
  typedef _ITree_node<_Tp, container_type, children_iterator> _Node;
  typedef __Tree_t<_Tp,container_type,children_iterator,_Inserter,_Node,_Alloc> _Base;
  typedef __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc> _Self;

public:
  typedef _Node                 node_type;

  typedef _Tree_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,node_type> iterator;
  typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,node_type> const_iterator;

  typedef _Tree_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator,_Node>  iterative_walker;
  typedef _Tree_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,_Node> const_iterative_walker;

#ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION

  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef std::reverse_iterator<iterator>       reverse_iterator;
#else /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

  typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
                                         const_reference,difference_type>
          const_reverse_iterator;
  typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
                                         difference_type>
          reverse_iterator;
#endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

protected:
#ifdef __VGTL_HAS_NAMESPACES
  using _Base::_C_node;
  using _Base::_C_put_node;
  using _Base::_C_get_node;
#endif /* __VGTL_HAS_NAMESPACES */

public:
  explicit __ITree(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  // preorder - postorder - pre and post,
  // depth-first - breadth first,
  // front-to-back - back-to-front

  iterative_walker root(walker_type wt = cw_pre_post,
                        bool front_to_back = true,
                        bool depth_first = true)
    { iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first);
      return __help; }

  const_iterative_walker root(walker_type wt =  cw_pre_post,
                              bool front_to_back = true,
                              bool depth_first = true) const
    { const_iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first);
      return __help; }

  iterative_walker through()
    { iterative_walker __help(_C_node, 0, 0, 0);
      return __help; }
  const_iterative_walker through() const
    { const_iterative_walker __help(_C_node, 0, 0, 0);
      return __help; }

  iterative_walker begin(walker_type wt = cw_pre_post,
                         bool front_to_back = true,
                         bool depth_first = true)
    { iterative_walker __help = root(wt, front_to_back, depth_first);
      ++__help;
      return __help; }
  const_iterative_walker begin(walker_type wt = cw_pre_post,
                               bool front_to_back = true,
                               bool depth_first = true) const
    { const_iterative_walker __help = root(wt, front_to_back, depth_first);
      ++__help;
      return __help; }

  iterative_walker end(walker_type wt = cw_pre_post,
                       bool front_to_back = true,
                       bool depth_first = true)
    { iterative_walker __help(_C_node, (int)wt, front_to_back, depth_first, false); 
      return __help; }
  const_iterative_walker end(walker_type wt = cw_pre_post,
                             bool front_to_back = true,
                             bool depth_first = true) const
    { const_iterative_walker __help(_C_node, (int)wt, front_to_back,
                          depth_first, false); 
      return __help; }

  reverse_iterator rbegin()
        { return reverse_iterator(end()); }
  reverse_iterator rend()
        { return reverse_iterator(begin()); }

  const_reverse_iterator rbegin() const
        { return const_reverse_iterator(end()); }
  const_reverse_iterator rend() const
        { return const_reverse_iterator(begin()); }

  size_type size() const {
    size_type __result = 0;
    distance(begin(cw_pre), end(cw_pre), __result);
    return __result;
  }

  reference getroot() { return *root(cw_pre,true,true); }
  const_reference getroot() const { return *root(cw_pre,true,true); }

  size_type depth(const iterative_walker& __position)
        { return __position._C_w_cur_it.size(); }
  
  __ITree(size_type __n, const _Tp& __value,
        const allocator_type& __a = allocator_type()) : _Base(__a)
    { insert(root(), __n, __value); }
  explicit __ITree(size_type __n) : _Base(allocator_type())
    { insert(root(), __n, _Tp()); }

public:
  __ITree(const _Self& __x) : _Base(__x) {}

  virtual ~__ITree() {}

  _Self& operator=(const _Self& __x);

  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }

  friend bool operator== __VGTL_NULL_TMPL_ARGS (
    const __ITree& __x, const __ITree& __y);
}; 

// if no iterative walkers are available, comparing trees is more difficult
template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
inline bool operator==(const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
                       const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
{
  typedef typename __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::const_walker const_walker;
  typedef typename __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::children_iterator children_iterator;
  const_walker __w1 = __x.ground();
  const_walker __w2 = __y.ground();
  children_iterator __it1, __it2;

  if(__w1->n_children() != __w2->n_children())
    return false;
  for(__it1 = __w1->child_begin(), __it2 = __w2->child_begin();
      __it1 != __w1->child_end(); ++__it1, ++__it2)
  {
    if(!compare_trees(__w1 >> __it1, __w2 >> __it2))
      return false;
  }
  return true;
}

template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
inline bool operator==(const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
                       const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
{
  typedef typename __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::const_iterative_walker const_walker;
  const_walker __w1 = __x.begin(cw_pre);
  const_walker __w2 = __y.begin(cw_pre);
  const_walker __e1 = __x.end(cw_pre);
  const_walker __e2 = __y.end(cw_pre);
  
  // compare values and tree structure with a pre-post-order walk
  for(; __w1 != __e1 && __w2 != __e2 ; ++__w1, ++__w2)
    if(__w1.in_preorder() != __w2.in_preorder() ||
       (__w1.in_preorder() && *__w1 != *__w2))
      return false;
  return __w1 == __e1 && __w2 == __e2;
}

template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
inline bool operator<(const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
                       const __Tree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
{
  return lexicographical_compare(__x.begin(), __x.end(),
                                 __y.begin(), __y.end());
}

template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
inline bool operator<(const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
                       const __ITree<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
{
  return lexicographical_compare(__x.begin(cw_pre), __x.end(cw_pre),
                                 __y.begin(cw_pre), __y.end(cw_pre));
}

template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
__Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>&
__Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>::operator=(const __Tree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>& __x)
{
  children_iterator cit;

  if (this != &__x) {
    this->_C_node->clear_tree();
    this->_C_node->_C_children.erase(this->_C_node->_C_children.begin(),
                        this->_C_node->_C_children.end());
    for(cit = __x._C_node->_C_children.begin();
        cit != __x._C_node->_C_children.end(); ++cit)
      this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
                copy_subtree((_Node*)*cit, this->_C_node));
    }
  return *this;
}

template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
__ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>&
__ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>::operator=(const __ITree<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>& __x)
{
  children_iterator cit;

  if (this != &__x) {
    this->_C_node->clear_tree();
    this->_C_node->_C_children.erase(this->_C_node->_C_children.begin(),
                        this->_C_node->_C_children.end());
    for(cit = __x._C_node->_C_children.begin();
        cit != __x._C_node->_C_children.end(); ++cit)
      this->_C_node->_C_children.insert(this->_C_node->_C_children.end(),
                copy_subtree((_Node*)*cit, this->_C_node));
    }
  return *this;
}


template <class _Tp,
          template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class ntree : public __ITree<_Tp, _SequenceCtr<void*, _PtrAlloc>,
                            typename _SequenceCtr<void*, _PtrAlloc>::iterator,
                            typename _SequenceCtr<void*, _PtrAlloc>::iterator,
                            _Alloc>
{
private:
  typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
protected:
  typedef ntree<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
  
public:
  void insert(const __walker_base& __position, const _Tp& __x)
        { _Node* __tmp = _C_create_node(__x);
          _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
          children_iterator __it;

          if(__parent == NULL) // this is the root node
          {
            __position._C_w_cur->add_all_children(
                        back_inserter(__tmp->_C_children), __tmp);
            __tmp->_C_parent = __position._C_w_cur;
            __position._C_w_cur->clear_children();
            __position._C_w_cur->_C_children.insert(
                            __position._C_w_cur->_C_children.end(), __tmp);
          }
          else
          {
            __it = __parent->get_childentry_iterator(__position._C_w_cur);
            *__it = __tmp;
            __tmp->clear_children();
            __tmp->_C_children.insert(__tmp->_C_children.end(),
                            __position._C_w_cur);
            __position._C_w_cur->_C_parent = __tmp;
            __tmp->_C_parent = __parent;
          }
        }
  void insert(const __walker_base& __position)
        { insert(__position, _Tp()); }
  
  void push_child(const __walker_base& __position, const _Tp& __x) 
        { insert_child(__position, __x,
                       __position._C_w_cur->_C_children.end()); }
  void push_child(const __walker_base& __position)
        { push_child(__position, _Tp()); }

  void push_children(const __walker_base& __position, size_type __n,
                              const _Tp& __x)
        { insert_children(__position, __n, __x,
                          __position._C_w_cur->_C_children.end()); }
  void push_children(const __walker_base& __position, size_type __n)
        { push_children(__position, n, _Tp()); }

  void unshift_child(const __walker_base& __position, const _Tp& __x) 
        { insert_child(__position, __x,
                       __position._C_w_cur->_C_children.begin()); }
  void unshift_child(const __walker_base& __position)
        { unshift_child(__position, _Tp()); }

  void unshift_children(const __walker_base& __position, size_type __n,
                              const _Tp& __x)
        { insert_children(__position, __n, __x,
                          __position._C_w_cur->_C_children.begin()); }
  void unshift_children(const __walker_base& __position, size_type __n)
        { unshift_children(__position, n, _Tp()); }

  void push_subtree(const __walker_base& __position, _Self& __subtree)
        {
          __subtree.add_all_children(back_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
          __subtree.clear_children();
        }

  void unshift_subtree(const __walker_base& __position, _Self& __subtree)
        {
          __subtree.add_all_children(front_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
          __subtree.clear_children();
        }

  bool pop_child(const __walker_base& __position)
        { if(__position._C_w_cur->_C_children.empty())
          { return false; }
          else
          {
            children_iterator __it = __position._C_w_cur->_C_children.end();
            return erase_child(__position, --__it);
          }
        }

  bool shift_child(const __walker_base& __position)
        { if(__position._C_w_cur->_C_children.empty())
          { return false; }
          else
          {
            children_iterator __it = __position._C_w_cur->_C_children.begin();
            return erase_child(__position, __it);
          }
        }

  _Node* pop_subtree(const __walker_base& __position)
        {
          if(__position._C_w_cur->_C_children.empty())
          { return NULL; }
          else
          {
            children_iterator __it = __position._C_w_cur->_C_children.end();
            return erase_subtree(__position, --__it);
          }
        }

  _Node* shift_subtree(const __walker_base& __position)
        {
          if(__position._C_w_cur->_C_children.empty())
          { return NULL; }
          else
          {
            children_iterator __it = __position._C_w_cur->_C_children.begin();
            return erase_subtree(__position, __it);
          }
        }

  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }
};


template <class _Tp,
          template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class rntree : public __Tree<_Tp, _SequenceCtr<void*, _PtrAlloc>,
                            typename _SequenceCtr<void*, _PtrAlloc>::iterator,
                            typename _SequenceCtr<void*, _PtrAlloc>::iterator,
                            _Alloc>
{
private:
  typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
protected:
  typedef rntree<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
  
public:
  void insert(const __walker_base& __position, const _Tp& __x)
        { _Node* __tmp = _C_create_node(__x);
          _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
          children_iterator __it;

          if(__parent == NULL) // this is the root node
          {
            __position._C_w_cur->add_all_children(
                        back_inserter(__tmp->_C_children), __tmp);
            __tmp->_C_parent = __position._C_w_cur;
            __position._C_w_cur->clear_children();
            __position._C_w_cur->_C_children.insert(
                            __position._C_w_cur->_C_children.end(), __tmp);
          }
          else
          {
            __it = __parent->get_childentry_iterator(__position._C_w_cur);
            *__it = __tmp;
            __tmp->clear_children();
            __tmp->_C_children.insert(__tmp->_C_children.end(),
                            __position._C_w_cur);
            __position._C_w_cur->_C_parent = __tmp;
            __tmp->_C_parent = __parent;
          }
        }
  void insert(const __walker_base& __position)
        { insert(__position, _Tp()); }
  
  void push_child(const __walker_base& __position, const _Tp& __x) 
        { insert_child(__position, __x,
                       __position._C_w_cur->_C_children.end()); }
  void push_child(const __walker_base& __position)
        { push_child(__position, _Tp()); }

  void push_children(const __walker_base& __position, size_type __n,
                              const _Tp& __x)
        { insert_children(__position, __n, __x,
                          __position._C_w_cur->_C_children.end()); }
  void push_children(const __walker_base& __position, size_type __n)
        { push_children(__position, n, _Tp()); }

  void unshift_child(const __walker_base& __position, const _Tp& __x) 
        { insert_child(__position, __x,
                       __position._C_w_cur->_C_children.begin()); }
  void unshift_child(const __walker_base& __position)
        { unshift_child(__position, _Tp()); }

  void unshift_children(const __walker_base& __position, size_type __n,
                              const _Tp& __x)
        { insert_children(__position, __n, __x,
                          __position._C_w_cur->_C_children.begin()); }
  void unshift_children(const __walker_base& __position, size_type __n)
        { unshift_children(__position, n, _Tp()); }

  void push_subtree(const __walker_base& __position, _Self& __subtree)
        {
          __subtree.add_all_children(back_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
          __subtree.clear_children();
        }

  void unshift_subtree(const __walker_base& __position, _Self& __subtree)
        {
          __subtree.add_all_children(front_inserter(__position._C_w_cur->_C_children), __position._C_w_cur);
          __subtree.clear_children();
        }

  bool pop_child(const __walker_base& __position)
        { if(__position._C_w_cur->_C_children.empty())
          { return false; }
          else
          {
            children_iterator __it = __position._C_w_cur->_C_children.end();
            return erase_child(__position, --__it);
          }
        }

  bool shift_child(const __walker_base& __position)
        { if(__position._C_w_cur->_C_children.empty())
          { return false; }
          else
          {
            children_iterator __it = __position._C_w_cur->_C_children.begin();
            return erase_child(__position, __it);
          }
        }

  _Node* pop_subtree(const __walker_base& __position)
        {
          if(__position._C_w_cur->_C_children.empty())
          { return NULL; }
          else
          {
            children_iterator __it = __position._C_w_cur->_C_children.end();
            return erase_subtree(__position, --__it);
          }
        }

  _Node* shift_subtree(const __walker_base& __position)
        {
          if(__position._C_w_cur->_C_children.empty())
          { return NULL; }
          else
          {
            children_iterator __it = __position._C_w_cur->_C_children.begin();
            return erase_subtree(__position, __it);
          }
        }

  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }
};



template <class _Tp,
          template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
          class _Key = string,
          class _Compare = less<_Key>,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class atree : public __ITree<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
                            pair_adaptor<typename _AssocCtr<_Key, void*,
                                         _Compare, _PtrAlloc>::iterator>,
                            _Key, _Alloc>
{
protected:
  typedef atree<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
  
public:
  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }

  void insert(const __walker_base& __position, const _Tp& __x, const _Key& __k)
        { _Node* __tmp = _C_create_node(__x);
          _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
          children_iterator __it;

          if(__parent == NULL) // this is the root node
          {
            __position._C_w_cur->add_all_children(
                        inserter(__tmp->_C_children.end()), __tmp);
            __tmp->_C_parent = __position._C_w_cur;
            __position._C_w_cur->clear_children();
            __position._C_w_cur->_C_children.insert(__k, __tmp);
          }
          else
          {
            __it = __parent->get_childentry_iterator(__position._C_w_cur);
            *__it = __tmp;
            __tmp->clear_children();
            __tmp->_C_children.insert(__k, __position._C_w_cur);
            __position._C_w_cur->_C_parent = __tmp;
            __tmp->_C_parent = __parent;
          }
        }
  void insert(const __walker_base& __position, const _Key& __k)
        { insert(__position, _Tp(), __k); }

  
};


template <class _Key, class _Compare = less<_Key>,
          template <class __Key, class __Compare, class __AllocT> class _AssocCtr = std::multiset,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Key&) >
class stree : public __ITree<_Key, _AssocCtr<_Key&, pointer_adaptor<_Compare>,
                                           _PtrAlloc>,
                            typename _AssocCtr<_Key&, pointer_adaptor<_Compare>,
                                               _PtrAlloc>::iterator,
                            _Key&, _Alloc>
{
protected:
  typedef stree<_Key,_Compare,_AssocCtr,_PtrAlloc,_Alloc> _Self;
  
public:
  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }
};


template <class _Tp,
          template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
          class _Key = string,
          class _Compare = less<_Key>,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class ratree : public __Tree<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
                            pair_adaptor<typename _AssocCtr<_Key, void*,
                                         _Compare, _PtrAlloc>::iterator>,
                            _Key, _Alloc>
{
protected:
  typedef ratree<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
  
public:
  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }

  void insert(const __walker_base& __position, const _Tp& __x, const _Key& __k)
        { _Node* __tmp = _C_create_node(__x);
          _Node* __parent = (_Node*)__position._C_w_cur->_C_parent;
          children_iterator __it;

          if(__parent == NULL) // this is the root node
          {
            __position._C_w_cur->add_all_children(
                        inserter(__tmp->_C_children.end()), __tmp);
            __tmp->_C_parent = __position._C_w_cur;
            __position._C_w_cur->clear_children();
            __position._C_w_cur->_C_children.insert(__k, __tmp);
          }
          else
          {
            __it = __parent->get_childentry_iterator(__position._C_w_cur);
            *__it = __tmp;
            __tmp->clear_children();
            __tmp->_C_children.insert(__k, __position._C_w_cur);
            __position._C_w_cur->_C_parent = __tmp;
            __tmp->_C_parent = __parent;
          }
        }
  void insert(const __walker_base& __position, const _Key& __k)
        { insert(__position, _Tp(), __k); }

  
};


template <class _Key, class _Compare = less<_Key>,
          template <class __Key, class __Compare, class __AllocT> class _AssocCtr = std::multiset,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Key&) >
class rstree : public __Tree<_Key, _AssocCtr<_Key&, pointer_adaptor<_Compare>,
                                           _PtrAlloc>,
                            typename _AssocCtr<_Key&, pointer_adaptor<_Compare>,
                                               _PtrAlloc>::iterator,
                            _Key&, _Alloc>
{
protected:
  typedef rstree<_Key,_Compare,_AssocCtr,_PtrAlloc,_Alloc> _Self;
  
public:
  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }
};

__VGTL_END_NAMESPACE
              
#endif /* __VGTL_TREE_H_ */

---