vgtl_graph.h

Go to the documentation of this file.

// Graph implementation -*- C++ -*-

// $Id: vgtl_graph.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_GRAPH_H_
#define __VGTL_GRAPH_H_

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

#include <vgtl_helpers.h>

__VGTL_BEGIN_NAMESPACE

#define _C_W_preorder   1
#define _C_W_postorder  2

WARNING: DO NOT USE THIS FILE -> NOT YET FINISHED!!!!!

// tree node
template <class _Tp, class _Ctr, class _Iterator>
class _Graph_node
{
private:
  typedef void* _Void_pointer;
  typedef _Iterator _Ctr_iterator;
  typedef _Graph_node<_Tp,_Ctr,_Iterator> _Self;

public:
  _Tp _C_data;
  _Ctr _C_neighbors;

  _Graph_node() { _C_data();
                  __VGTL_TRY {
                    construct(&_C_neighbors);
                  }
                  __VGTL_UNWIND( );
                }
  void clear_graph();
  void clear_neighbors()
        { _C_neighbors.erase(_C_neighbors.begin(), _C_neighbors.end()); }

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

#ifdef __VGTL_MEMBER_TEMPLATES
  template <class _Output_Iterator>
  void add_all_neighbors(_Output_Iterator fi, _Self* _nb);
#endif /* __VGTL_MEMBER_TEMPLATES */
};

#ifdef __VGTL_MEMBER_TEMPLATES
template <class _Tp, class _Ctr, class _Iterator>
template <class _Output_Iterator>
void 
_Graph_node<_Tp,_Ctr,_Iterator>::
        add_all_neighbors(_Output_Iterator fi, _Self* _nb)
{ _Ctr_iterator it;
  for(it = _C_neighbors.begin();
      it != _C_neighbors.end();
      ++it)
  {
    *fi++ = *it;
    ((_Self*)*it)->_C_neighbors.insert(((_Self*)*it)->_C_neighbors.end(),_nb);
  }
};
#endif /* __VGTL_MEMBER_TEMPLATES */

// get rid of the graph
template <class _Tp, class _Ctr, class _Iterator>
void
_Graph_node<_Tp,_Ctr,_Iterator>::clear_graph()
{
  // THIS IS NOT YET IMPLEMENTED
  destroy(&this->_C_data);
}

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

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

  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;
private:
  typedef _Graph_node<_Tp,_Ctr,_Iterator> _Node;
  typedef _Iterator _Ctr_iterator;

public:
  typedef _Ctr_iterator container_iterator;
  typedef _Node node_type;

  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

public:
  _Node* _C_w_cur;

public:
  _Graph_walker_base() {}

public:
  _Graph_walker_base(_Node* __x) : _C_w_cur(__x) { }

  _Graph_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=(_Itr __x) {
        _C_w_cur = __x._C_i_cur;
        return *this;
  }

  const _Node* node() { return _C_w_cur; }
  size_type n_neighbors() { return _C_w_cur->_C_neighbors.size(); }

  _Ctr_iterator neighbor_begin() { return _C_w_cur->_C_neighbors.begin(); }
  _Ctr_iterator neighbor_end() { return _C_w_cur->_C_neighbors.end(); }
  
template <class _Function>
  _Function for_each_neighbor(_Function __f)
    {
      return for_each(neighbor_begin(), neighbor_end(), __f);
    }
};

// CONTINUE HERE
template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
class _Graph_walker : public _Graph_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator>
{
public:
  typedef _Graph_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator>            walker;
  typedef _Graph_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator> const_walker;
  typedef _Graph_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>            _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;
  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<<(bool search_start) {
    _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);
      if(search_start)
        __tmp._find_start_node();
    }
    return __tmp;
  }
  
  _Self operator>>(_Ctr_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<<=(bool search_start) {
    _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);
      if(search_start)
        _find_start_node();
    }
    return *this;
  }
  
  _Self& operator>>=(_Ctr_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=(_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>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_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>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_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)->~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>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_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>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_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>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_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>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_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>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_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>
void _Tree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::_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 _RTree_walker : public _Tree_walker_base<_Tp,_Ref,_Ptr,_Ctr,_Iterator>
{
public:
  typedef _RTree_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator>             walker;
  typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator> const_walker;
  typedef _RTree_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator>             _Self;

public:
  _RTree_walker() {}

public:
  _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<<(bool search_start) {
    _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>>(_Ctr_iterator i) {
    _Self __tmp = *this;
    __tmp._C_w_cur = (_Node*) *i;
    return __tmp;
  }

  _Self& operator<<=(bool search_start) {
    _Node *help = _C_w_cur._C_parent;
    if(help != NULL) // already at root node
      _C_w_cur = help;
    return *this;
  }
  
  _Self& operator>>=(_Ctr_iterator i) {
    _C_w_cur = (_Node*) *i;
    return *this;
  }
  
  _Self& operator=(_Itr __x) {
        _C_w_cur = __x._C_i_cur;
        return *this;
  }

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

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

  typedef bidirectional_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;
  typedef _Tree_node<_Tp,_Ctr,_Iterator> _Node;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef _Iterator _Ctr_iterator;

protected:
  _Node* _C_i_cur;
  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) {}

  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=(_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>
inline bidirectional_iterator_tag
iterator_category(const _Tree_iterator<_Tp,_Ref,_Ptr,_Ctr>&)
{
  return bidirectional_iterator_tag();
}

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

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

#endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

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

  while(__s->_C_parent != NULL)
  {
    __help = ((_Node*)__s->_C_parent)->get_entry_iterator((void*)__s);
    _C_i_cur_it.push_front(__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>
void
_Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::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>
void
_Tree_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::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;
  }
}

// Base class that encapsulates details of allocators.  Three cases:
// an ordinary standard-conforming allocator, a standard-conforming
// allocator with no non-static data, and an SGI-style allocator.
// This complexity is necessary only because we're worrying about backward
// compatibility and because we want to avoid wasting storage on an
// allocator instance if it isn't necessary.
 
#ifdef __VGTL_USE_STD_ALLOCATORS

// Base for general standard-conforming allocators.

template <class _Tp, class _Ctr, class _TI, class _Allocator, bool _IsStatic>
class _Tree_alloc_base {
public:
  typedef typename _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:
  _Tree_node<_Tp,_Ctr,_TI>* _C_get_node()
    { return _Node_allocator.allocate(1); }
  void _C_put_node(_Tree_node<_Tp,_Ctr,_TI>* __p)
    { _Node_allocator.deallocate(__p, 1); }

protected:
  typename _Alloc_traits<_Tree_node<_Tp,_Ctr,_TI>, _Allocator>::allocator_type
           _Node_allocator;

protected:
  _Tree_node<_Tp,_Ctr,_TI>* _C_node;
};

// Specialization for instanceless allocators.

template <class _Tp, class _Ctr, class _TI, class _Allocator>
class _Tree_alloc_base<_Tp, _Ctr, _TI, _Allocator, true> {
public:
  typedef typename _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 _Alloc_traits<_Tree_node<_Tp,_Ctr,_TI>, _Allocator>::_Alloc_type
          _Alloc_type;
  _Tree_node<_Tp,_Ctr,_TI>* _C_get_node()
    { return _Alloc_type::allocate(1); }
  void _C_put_node(_Tree_node<_Tp,_Ctr,_TI>* __p)
    { _Alloc_type::deallocate(__p, 1); }

protected:
  _Tree_node<_Tp,_Ctr,_TI>* _C_node;
};

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

  typedef _Ctr container_type;
  typedef _TI container_iterator;

  _Tree_base(const allocator_type& __a) : _Base(__a) {
    _C_node = _C_get_node();
    __VGTL_TRY {
      construct(&_C_node->_C_children);
    }
    __VGTL_UNWIND(_C_put_node(_C_node));
    _C_node->_C_parent = NULL;
    _C_node->_C_data_hook.f = 0;
  }
  ~_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,
                        _Tree_node<_Tp,_Ctr,_TI>* _parent);
};
#else /* __VGTL_USE_STD_ALLOCATORS */

template <class _Tp, class _Ctr, class _Iterator, class _Alloc>
class _Tree_base
{
public:
  typedef _Alloc allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }
  
  typedef _Ctr container_type;
  typedef _Iterator container_iterator;

  _Tree_base(const allocator_type&) {
    _C_node = _C_get_node();
    _C_node->_C_children();
    _C_node->_C_parent = NULL;
  }
  ~_Tree_base() {
    clear();
    _C_put_node(_C_node);
  }

  void clear();

protected:
  typedef simple_alloc<_Tree_node<_Tp,_Ctr,_Iterator>, _Alloc> _Alloc_type;
  _Tree_node<_Tp,_Ctr,_Iterator>* _C_get_node()
    { return _Alloc_type::allocate(1); }
  void _C_put_node(_Tree_node<_Tp,_Ctr,_Iterator>* __p)
    { _Alloc_type::deallocate(__p, 1); }

protected:
  _Tree_node<_Tp,_Ctr,_Iterator>* _C_node;

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

  template <class _Output_Iterator>
  void add_all_children(_Output_Iterator fi,
                        _Tree_node<_Tp,_Ctr,_Iterator>* _parent);
};

#endif /* __VGTL_USE_STD_ALLOCATORS */

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

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

template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
class __Tree : public _Tree_base<_Tp, _Ctr, _Iterator, _Alloc>
{
public:
  typedef _Ctr  container_type;
  typedef _Iterator container_iterator;
  typedef _Inserter container_insert_arg;

protected:
  typedef void* _Void_pointer;
  typedef _Tree_base<_Tp, container_type, container_iterator, _Alloc> _Base;
  typedef _Tree_node<_Tp, container_type, container_iterator> _Node;
  typedef __Tree<_Tp,_Ctr,_Iterator,_Inserter,_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,container_iterator> iterator;
  typedef _Tree_iterator<_Tp,const _Tp&,const _Tp*,container_type,container_iterator> const_iterator;

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

  typedef _Tree_walker<_Tp,_Tp&,_Tp*,container_type,container_iterator>  walker;
  typedef _Tree_walker<_Tp,const _Tp&,const _Tp*,container_type,container_iterator> const_walker;

  typedef _RTree_walker<_Tp,_Tp&,_Tp*,container_type,container_iterator> recursive_walker;
  typedef _RTree_walker<_Tp,const _Tp&,const _Tp*,container_type,container_iterator> const_recursive_walker;

protected:
  typedef _Tree_walker_base<_Tp,_Tp&,_Tp*,container_type,container_iterator> __walker_base;
  typedef _Tree_walker_base<_Tp,const _Tp&,const _Tp*,container_type,container_iterator> __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 {
      construct(&__p->_C_data, __x);
      construct(&__p->_C_children);
    }
    __VGTL_UNWIND(_C_put_node(__p));
    __p->_C_data_hook.f = 0;
    __p->_C_parent = NULL;
    return __p;
  }

  _Node* _C_create_node()
  {
    _Node* __p = _C_get_node();
    __VGTL_TRY {
      construct(&__p->_C_data);
      construct(&__p->_C_children);
    }
    __VGTL_UNWIND(_C_put_node(__p));
    __p->_C_data_hook.f = 0;
    __p->_C_parent = NULL;
    return __p;
  }

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 root(walker_type wt = cw_pre_post,
               bool front_to_back = true,
               bool depth_first = true)
    { walker __help(_C_node, (int)wt, front_to_back, depth_first);
      return __help; }

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

  walker through()
    { walker __help(_C_node, 0, 0, 0);
      return __help; }
  const_walker through() const
    { const_walker __help(_C_node, 0, 0, 0);
      return __help; }

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

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

  /**** Iterators are implemented as postorder depthfirst front to back
  ***** walkers. begin(), end() are converted from the corresponding
  ***** walker functions
  iterator begin()             {}
  const_iterator begin() const {}

  iterator end()             {}
  const_iterator end() const {}
  ****/

  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()); }

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

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

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

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

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

  // add children anywhere
  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 container_iterator& __It)
        { _Node* __tmp;
          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());
        }

  // add complete subtrees
  void insert_subtree(const __walker_base& __position,
                        _Self& __subtree, const container_iterator& __It) 
        {
          __subtree.add_all_children(inserter(__position._C_w_cur->_C_children, __It), __position._C_w_cur);
          __subtree.clear_children();
        }
  
  // erase a node
  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
            container_iterator __ip = __parent->get_entry_iterator(__tmp);

            if(!__tmp->_C_children.empty())
            {
              container_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);
          }
        }

  // erase a complete subtree
  _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
          {
            container_iterator __ip = __parent->get_entry_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;
          }
        }


  // these work if and only if the child is a leaf.
  bool erase_child(const __walker_base& __position,
                   const container_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;
          }
        }

  // erase subtrees
  _Node* erase_subtree(const __walker_base& __position,
                                const container_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;
        }
  
  // other info on tree
  bool is_root() { return _C_node->_C_parent == NULL; }
  
  size_type depth(const walker& __position)
        { return __position._C_w_cur_it.size(); }

  size_type depth(const recursive_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(size_type __n, const _Tp& __value,
        const allocator_type& __a = allocator_type()) : _Base(__a)
    { insert(root(), __n, __value); }
  explicit __Tree(size_type __n) : _Base(allocator_type())
    { insert(root(), __n, _Tp()); }

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

    _Node* __h = _C_create_node();
    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(const _Self& __x) :
    _Base(__x.get_allocator())
    { container_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));
    }

  ~__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>
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;
  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(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)
{
  container_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 = vector,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class ntree : 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 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;
          container_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_entry_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()); }
  
  // add children at the end
  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()); }

  // add them at the beginning
  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()); }

  // insert subtrees at beginning and end, respectively
  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();
        }

  // remove leafs at the beginning, resp. end
  bool pop_child(const __walker_base& __position)
        { if(__position._C_w_cur->_C_children.empty())
          { return false; }
          else
          {
            container_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
          {
            container_iterator __it = __position._C_w_cur->_C_children.begin();
            return erase_child(__position, __it);
          }
        }

  // deattach subtrees at the beginning and the end, respectively
  _Node* pop_subtree(const __walker_base& __position)
        {
          if(__position._C_w_cur->_C_children.empty())
          { return NULL; }
          else
          {
            container_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
          {
            container_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 = multimap,
          class _Key = string,
          class _Compare = less<_Key>,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class atree : public __Tree<_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;
          container_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_entry_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 = multiset,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Key&) >
class stree : public __Tree<_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;
  }
};

__VGTL_END_NAMESPACE

#endif // __VGTL_GRAPH_H_ 

---