---

vgtl_algo.h

Go to the documentation of this file.

// Algorithm implementation -*- C++ -*-

// 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_ALGO_H
#define __VGTL_ALGO_H

#include <algorithm>
#include <vgtl_helpers.h>
#include <vgtl_gdata.h>

__VGTL_BEGIN_NAMESPACE

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1209
#endif


template <class _Iterator, class _Node>
class __Child_data_iterator
{
private:
  typedef __Child_data_iterator<_Iterator, _Node> _Self;

public:
  typedef typename std::iterator_traits<_Iterator>::iterator_category iterator_category;
  typedef typename std::iterator_traits<_Iterator>::difference_type difference_type;
  
public:

  typedef ctree_data_hook       value_type;
  typedef value_type*           pointer;
  typedef value_type&           reference;

  typedef _Iterator iterator_type;
protected:
  _Iterator current;

public:

  __Child_data_iterator() {}
  explicit __Child_data_iterator(iterator_type __x) : current(__x) {}

  __Child_data_iterator(const _Self& __x) : current(__x.current) {}

  iterator_type base() const { return current; }

  reference operator*() const {
    return (*((_Node*)*current)).data_hook();
  }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */


  bool operator== (const _Self& __x) const { return (*this).current == __x.current; }
  bool operator!= (const _Self& __x) const { return (*this).current != __x.current; }
  
  _Self& operator= (const iterator_type& it)
  {
    current = it;
    return *this;
  }
  

  _Self& operator++() {
    ++current;
    return *this;
  }
  _Self& operator++(int) {
    _Self __tmp = *this;
    ++current;
    return __tmp;
  }
  _Self& operator--() {
    --current;
    return *this;
  }
  _Self& operator--(int) {
    _Self __tmp = *this;
    --current;
    return __tmp;
  }
  //

  _Self operator+(difference_type __n) const {
    return _Self(current + __n);
  }
  _Self& operator+=(difference_type __n) {
    current += __n;
    return *this;
  }
  _Self operator-(difference_type __n) const {
    return _Self(current - __n);
  }
  _Self& operator-=(difference_type __n) {
    current -= __n;
    return *this;
  }
  reference operator[](difference_type __n) const { return *(*this + __n); }
};


template <class _Tree>
class child_data_iterator :
  public __Child_data_iterator<typename _Tree::children_iterator,
                               typename _Tree::node_type>
{
private:
  typedef child_data_iterator<_Tree>            _Self;
  typedef typename _Tree::children_iterator    _Iterator;
  typedef typename _Tree::node_type             _Node;

  typedef typename child_data_iterator<_Tree>::iterator_type iterator_type;

public:
  child_data_iterator() {}
  explicit child_data_iterator(iterator_type __x) { current = __x; }

  child_data_iterator(const _Self& __x) { current = __x.current; }
  
  _Self& operator= (const iterator_type& it)
  {
    current = it;
    return *this;
  }
};

template <class _IterativeWalker, class _Function>
_Function walk(_IterativeWalker __first, _IterativeWalker __last, _Function __f)
{
  typedef __Child_data_iterator<typename _IterativeWalker::children_iterator,
                                typename _IterativeWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
    __f(*__first, __first.data_hook(), __cit(__first.child_begin()),
        __cit(__first.child_end()));
  return __f;
}

template <class _PrePostWalker, class _Function>
_Function pre_post_walk(_PrePostWalker __first, _PrePostWalker __last,
                        _Function __f)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
    __f(*__first, __first.data_hook(), __cit(__first.child_begin()),
        __cit(__first.child_end()),
        __first.in_preorder());
  return __f;
}

template <class _PrePostWalker, class _Function1, class _Function2>
_Function2 pre_post_walk(_PrePostWalker __first, _PrePostWalker __last,
                        _Function1 __f1, _Function2 __f2)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
    __first.in_preorder() ? 
      __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end())) :
      __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end()));
  return __f2;
}

template <class _PrePostWalker, class _Function>
_Function var_walk(_PrePostWalker __first, _PrePostWalker __last,
                   _Function __f)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
    if(__f(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end()), __first.in_preorder()))
        ~__first;
  return __f;
}

template <class _PrePostWalker, class _Function1, class _Function2>
_Function2 var_walk(_PrePostWalker __first, _PrePostWalker __last,
                    _Function1 __f1, _Function2 __f2)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
    if(__first.in_preorder() ?
            __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
                 __cit(__first.child_end())): 
            __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
                 __cit(__first.child_end())))
        ~__first;
  return __f2;
}

template <class _PrePostWalker, class _Function, class _Predicate>
_Function walk_if(_PrePostWalker __first, _PrePostWalker __last,
                  _Function __f, _Predicate __pred)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
  {
    __f(*__first, __first.data_hook(), __cit(__first.child_begin()),
        __cit(__first.child_end()), __first.in_preorder());
    if(__pred(*__first))
        ~__first;
  }
  return __f;
}

template <class _PrePostWalker, class _Function1, class _Function2,
          class _Predicate>
_Function2 walk_if(_PrePostWalker __first, _PrePostWalker __last,
                   _Function1 __f1, _Function2 __f2, _Predicate __pred)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
  {
    __first.in_preorder() ? __f1(*__first, __first.data_hook(),
                                 __cit(__first.child_begin()),
                                 __cit(__first.child_end())) :
                            __f2(*__first, __first.data_hook(),
                                 __cit(__first.child_begin()),
                                 __cit(__first.child_end()));
    if(__pred(*__first))
      ~__first;
  }
  return __f2;
}

template <class _PrePostWalker, class _Function1, class _Function2,
          class _Predicate1, class _Predicate2>
_Function2 walk_if(_PrePostWalker __first, _PrePostWalker __last,
                   _Function1 __f1, _Function2 __f2, _Predicate1 __pred1,
                   _Predicate2 __pred2)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
  {
    if(__first.in_preorder())
    { 
      __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end()));
      if(__pred1(*__first))
        ~__first;
    }
    else
    {
      __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end()));
      if(__pred2(*__first))
        ~__first;
    }
  }
  return __f2;
}

template <class _PrePostWalker, class _Function1, class _Function2,
          class _Predicate>
_Function2 cached_walk_if(_PrePostWalker __first, _PrePostWalker __last,
                          _Function1 __f1, _Function2 __f2, _Predicate __pred)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
  {
    if(__first.in_preorder())
    {
      __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end()));
      if(__pred(*__first))
        ~__first;
    }
    else
      __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end()));
  }
  return __f2;
}

template <class _PrePostWalker, class _Function1, class _Function2,
          class _Predicate>
_Function2 multi_walk_if(_PrePostWalker __first, _PrePostWalker __last,
                         _Function1 __f1, _Function2 __f2, _Predicate __pred)
{
  typedef __Child_data_iterator<typename _PrePostWalker::children_iterator,
                                typename _PrePostWalker::node_type> __cit;
  for ( ; __first != __last; ++__first)
  {
    if(__first.in_preorder())
      __f1(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end()));
    else
    {
      __f2(*__first, __first.data_hook(), __cit(__first.child_begin()),
           __cit(__first.child_end()));
      if(__pred(*__first))
        ~__first;
    }
  }
  return __f2;
}

template <class _Walker, class _Function>
_Function walk_up(_Walker __w, _Function __f)
{
  while(!__w.is_root())
  {
    __f(*__w, __w.data_hook(), __w.parent_data_hook());
    __w <<= false;
  }
  return __f;
}

template <class _Walker, class _Function>
_Function var_walk_up(_Walker __w, _Function __f)
{
  while(!__w.is_root())
  {
    if(__f(*__w, __w.data_hook(), __w.parent_data_hook()))
      break;
    __w <<= false;
  }
  return __f;
}

template <class _Walker, class _Function, class _Predicate>
_Function walk_up_if(_Walker __w, _Function __f, _Predicate __p)
{
  while(!__w.is_root())
  {
    __f(*__w, __w.data_hook(), __w.parent_data_hook());
    if(__p(*__w, __w.data_hook()))
      break;
    __w <<= false;
  }
  return __f;
}

/* 
 * 
 * 
 * 
 * recursive walks start here
 * 
 * 
 * 
 */

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_preorder_walk(_Walker __w,
                                                        _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_preorder_walk(__w>>__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    __f.preorder(*__w);
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_preorder_walk(__w>>__it, __f));
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_preorder_walk(_Walker __w,
                                                        _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  __f.preorder(*__w);
  __e = __w.child_end();
  for(__it = __w.child_begin(); __it != __e; ++__it)
    __f.collect(*__w, _recursive_preorder_walk(__w>>__it, __f));
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_postorder_walk(_Walker __w,
                                                         _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __f.vinit();
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_postorder_walk(__w>>__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    __f.init();
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_postorder_walk(__w>>__it, __f));
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_postorder_walk(_Walker __w,
                                                         _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  __f.init();
  __e = __w.child_end();
  for(__it = __w.child_begin(); __it != __e; ++__it)
    __f.collect(*__w, _recursive_postorder_walk(__w>>__it, __f));
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_walk(_Walker __w, _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_walk(__w>>__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    __f.preorder(*__w);
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_walk(__w>>__it, __f));
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_walk(_Walker __w, _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  __f.preorder(*__w);
  __e = __w.child_end();
  for(__it = __w.child_begin(); __it != __e; ++__it)
    __f.collect(*__w, _recursive_walk(__w>>__it, __f));
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_preorder_walk_if(_Walker __w,
                                                           _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_preorder_walk_if(__w>>__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    if(__f.preorder(*__w))
    {
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_preorder_walk_if(__w>>__it, __f));
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_preorder_walk_if(_Walker __w,
                                                           _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  if(__f.preorder(*__w))
  {
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_preorder_walk_if(__w>>__it, __f));
  }
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value recursive_preorder_walk_if(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_preorder_walk_if(__w>>__it, __f, __p));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    __f.preorder(*__w);
    if(__p(*__w))
    {
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_preorder_walk_if(__w>>__it, __f, __p));
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value _recursive_preorder_walk_if(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  __f.preorder(*__w);
  if(__p(*__w))
  {
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_preorder_walk_if(__w>>__it, __f, __p));
  }
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value recursive_postorder_walk_if(_Walker __w,
                                        _Visitor __f, _Predicate __p)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __f.vinit();
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_postorder_walk_if(__w>>__it, __f, __p));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    __f.init();
    if(__p(*__w))
    {
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_postorder_walk_if(__w>>__it, __f, __p));
    }
    __f.postorder(*__w, __w.data_hook()); 
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value _recursive_postorder_walk_if(_Walker __w,
                                        _Visitor __f, _Predicate __p)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  __f.init();
  if(__p(*__w))
  {
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_postorder_walk_if(__w>>__it, __f, __p));
  }
  __f.postorder(*__w, __w.data_hook()); 
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_walk_if(_Walker __w, _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_walk_if(__w>>__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    while(1)
    {
      if(__f.preorder(*__w))
      {
        __e = __w.child_end();
        for(__it = __w.child_begin(); __it != __e; ++__it)
          __f.collect(*__w, _recursive_walk_if(__w>>__it, __f));
      }
      if(!__f.postorder(*__w))
        break;
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_walk_if(_Walker __w, _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  while(1)
  {
    if(__f.preorder(*__w))
    {
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_walk_if(__w>>__it, __f));
    }
    if(!__f.postorder(*__w))
      break;
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_cached_walk(_Walker __w, _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_cached_walk(__w>>__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    if(__f.preorder(*__w))
    {
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_cached_walk(__w>>__it, __f));
    }
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_cached_walk(_Walker __w,
                                                       _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  if(__f.preorder(*__w))
  {
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_cached_walk(__w>>__it, __f));
  }
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_multi_walk(_Walker __w, _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_mulit_walk(__w>>__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    while(1)
    {
      __f.preorder(*__w);
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_multi_walk(__w>>__it, __f));
      if(!__f.postorder(*__w))
        break;
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_multi_walk(_Walker __w, _Visitor __f)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  while(1)
  {
    __f.preorder(*__w);
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_multi_walk(__w>>__it, __f));
    if(!__f.postorder(*__w))
      break;
  }
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate1, class _Predicate2>
typename _Visitor::return_value recursive_walk_if(_Walker __w, _Visitor __f,
                                           _Predicate1 __p1, _Predicate2 __p2)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_walk_if(__w>>__it, __f, __p1, __p2));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    while(1)
    {
      __f.preorder(*__w);
      if(__p1(*__w))
      {
        __e = __w.child_end();
        for(__it = __w.child_begin(); __it != __e; ++__it)
          __f.collect(*__w, _recursive_walk_if(__w>>__it, __f, __p1, __p2));
      }
      __f.postorder(*__w);
      if(!__p2(*__w))
        break;
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate1, class _Predicate2>
typename _Visitor::return_value _recursive_walk_if(_Walker __w, _Visitor __f,
                                           _Predicate1 __p1, _Predicate2 __p2)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  while(1)
  {
    __f.preorder(*__w);
    if(__p1(*__w))
    {
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_walk_if(__w>>__it, __f, __p1, __p2));
    }
    __f.postorder(*__w);
    if(!__p2(*__w))
      break;
  }
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value recursive_cached_walk(_Walker __w, _Visitor __f,
                                                      _Predicate __p)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_cached_walk(__w>>__it, __f, __p));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    __f.preorder(*__w);
    if(__p(*__w))
    {
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_cached_walk(__w>>__it, __f, __p));
    }
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value _recursive_cached_walk(_Walker __w, _Visitor __f,
                                                      _Predicate __p)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  __f.preorder(*__w);
  if(__p(*__w))
  {
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_cached_walk(__w>>__it, __f, __p));
  }
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value recursive_multi_walk(_Walker __w, _Visitor __f,
                                                     _Predicate __p)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_multi_walk(__w>>__it, __f, __p));
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    while(1)
    {
      __f.preorder(*__w);
      __e = __w.child_end();
      for(__it = __w.child_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_multi_walk(__w>>__it, __f, __p));
      __f.postorder(*__w);
      if(!__p(*__w))
        break;
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value _recursive_multi_walk(_Walker __w, _Visitor __f,
                                                     _Predicate __p)
{
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  while(1)
  {
    __f.preorder(*__w);
    __e = __w.child_end();
    for(__it = __w.child_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_multi_walk(__w>>__it, __f, __p));
    __f.postorder(*__w);
    if(!__p(*__w))
      break;
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_preorder_walk_up(_Walker __w,
                                                           _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_preorder_walk_up(__w<<__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    __f.preorder(*__w);
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_preorder_walk_up(__w<<__it, __f));
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_preorder_walk_up(_Walker __w,
                                                           _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_ground())
    return __f.vvalue();
  __f.preorder(*__w);
  __e = __w.parent_end();
  for(__it = __w.parent_begin(); __it != __e; ++__it)
    __f.collect(*__w, _recursive_preorder_walk_up(__w<<__it, __f));
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_preorder_walk_up_if(_Walker __w,
                                                              _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_preorder_walk_up_if(__w<<__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    if(__f.preorder(*__w))
    {
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_preorder_walk_up_if(__w<<__it, __f));
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_preorder_walk_up_if(_Walker __w,
                                                              _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_ground())
    return __f.vvalue();
  if(__f.preorder(*__w))
  {
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_preorder_walk_up_if(__w<<__it, __f));
  }
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value recursive_preorder_walk_up_if(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_preorder_walk_up_if(__w<<__it, __f, __p));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    __f.preorder(*__w);
    if(__p(*__w))
    {
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_preorder_walk_up_if(__w<<__it, __f, __p));
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value _recursive_preorder_walk_up_if(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_ground())
    return __f.vvalue();
  __f.preorder(*__w);
  if(__p(*__w))
  {
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_preorder_walk_up_if(__w<<__it, __f, __p));
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_postorder_walk_up(_Walker __w,
                                                            _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_sky())
  {
    __f.vinit();
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_postorder_walk_up(__w<<__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    __f.init();
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_postorder_walk_up(__w<<__it, __f));
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_postorder_walk_up(_Walker __w,
                                                            _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_ground())
    return __f.vvalue();
  __f.init();
  __e = __w.parent_end();
  for(__it = __w.parent_begin(); __it != __e; ++__it)
    __f.collect(*__w, _recursive_postorder_walk_up(__w<<__it, __f));
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value recursive_postorder_walk_up_if(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_sky())
  {
    __f.vinit();
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_postorder_walk_up(__w<<__it, __f, __p));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    __f.init();
    if(__p(*__w))
    {
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_postorder_walk_up_if(__w<<__it, __f, __p));
    }
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value _recursive_postorder_walk_up_if(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_ground())
    return __f.vvalue();
  __f.init();
  if(__p(*__w))
  {
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_postorder_walk_up_if(__w<<__it, __f, __p));
  }
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_walk_up(_Walker __w, _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_walk_up(__w<<__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    __f.preorder(*__w);
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_walk_up(__w<<__it, __f));
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_walk_up(_Walker __w, _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_ground())
    return __f.vvalue();
  __f.preorder(*__w);
  __e = __w.parent_end();
  for(__it = __w.parent_begin(); __it != __e; ++__it)
    __f.collect(*__w, _recursive_walk_up(__w<<__it, __f));
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_walk_up_if(_Walker __w, _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_walk_up_if(__w<<__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    while(1)
    {
      if(__f.preorder(*__w))
      {
        __e = __w.parent_end();
        for(__it = __w.parent_begin(); __it != __e; ++__it)
          __f.collect(*__w, _recursive_walk_up_if(__w<<__it, __f));
      }
      if(!__f.postorder(*__w))
        break;
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_walk_up_if(_Walker __w, _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_ground())
    return __f.vvalue();
  while(1)
  {
    if(__f.preorder(*__w))
    {
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_walk_up_if(__w<<__it, __f));
    }
    if(!__f.postorder(*__w))
      break;
  }
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate1, class _Predicate2>
typename _Visitor::return_value recursive_walk_up_if(_Walker __w, _Visitor __f,
                                             _Predicate1 __p1, _Predicate2 __p2)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_walk_up_if(__w<<__it, __f, __p1, __p2));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    while(1)
    {
      __f.preorder(*__w);
      if(__p1(*__w))
      {
        __e = __w.parent_end();
        for(__it = __w.parent_begin(); __it != __e; ++__it)
          __f.collect(*__w, _recursive_walk_up_if(__w<<__it, __f, __p1, __p2));
      }
      __f.postorder(*__w);
      if(!__p2(*__w))
        break;
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate1, class _Predicate2>
typename _Visitor::return_value _recursive_walk_up_if(_Walker __w, _Visitor __f,
                                             _Predicate1 __p1, _Predicate2 __p2)
{
  typename _Walker::parents_iterator __it, __e;
  
  if(__w.is_ground())
    return __f.vvalue();
  while(1)
  {
    __f.preorder(*__w);
    if(__p1(*__w))
    {
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_walk_up_if(__w<<__it, __f, __p1, __p2));
    }
    __f.postorder(*__w);
    if(!__p2(*__w))
      break;
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_cached_walk_up(_Walker __w,
                                                         _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;

  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_cached_walk_up(__w<<__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    if(__f.preorder(*__w))
    {
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_cached_walk_up(__w<<__it, __f));
    }
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_cached_walk_up(_Walker __w,
                                                         _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;

  if(__w.is_ground())
    return __f.vvalue();
  if(__f.preorder(*__w))
  {
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_cached_walk_up(__w<<__it, __f));
  }
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_multi_walk_up(_Walker __w,
                                                        _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;

  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_multi_walk_up(__w<<__it, __f));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    while(1)
    {
      __f.preorder(*__w);
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_multi_walk_up(__w<<__it, __f));
      if(!__f.postorder(*__w))
        break;
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_multi_walk_up(_Walker __w,
                                                        _Visitor __f)
{
  typename _Walker::parents_iterator __it, __e;

  if(__w.is_ground())
    return __f.vvalue();
  while(1)
  {
    __f.preorder(*__w);
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_multi_walk_up(__w<<__it, __f));
    if(!__f.postorder(*__w))
      break;
  }
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value recursive_cached_walk_up(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::parents_iterator __it, __e;

  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_cached_walk_up(__w<<__it, __f, __p));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    __f.preorder(*__w);
    if(__p(*__w))
    {
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_cached_walk_up(__w<<__it, __f, __p));
    }
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value _recursive_cached_walk_up(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::parents_iterator __it, __e;

  if(__w.is_ground())
    return __f.vvalue();
  __f.preorder(*__w);
  if(__p(*__w))
  {
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_cached_walk_up(__w<<__it, __f, __p));
  }
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value recursive_multi_walk_up(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::parents_iterator __it, __e;
  

  if(__w.is_sky())
  {
    __e = __w.parent_end();
    __f.vinit();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.vcollect(_recursive_multi_walk_up(__w<<__it, __f, __p));
    return __f.vvalue();
  }
  else if(__w.is_ground())
    return __f.vvalue();
  else
  {
    while(1)
    {
      __f.preorder(*__w);
      __e = __w.parent_end();
      for(__it = __w.parent_begin(); __it != __e; ++__it)
        __f.collect(*__w, _recursive_multi_walk_up(__w<<__it, __f, __p));
      __f.postorder(*__w);
      if(!__p(*__w))
        break;
    }
    return __f.value();
  }
}

template <class _Walker, class _Visitor, class _Predicate>
typename _Visitor::return_value _recursive_multi_walk_up(_Walker __w,
                                                _Visitor __f, _Predicate __p)
{
  typename _Walker::parents_iterator __it, __e;
  

  if(__w.is_ground())
    return __f.vvalue();
  while(1)
  {
    __f.preorder(*__w);
    __e = __w.parent_end();
    for(__it = __w.parent_begin(); __it != __e; ++__it)
      __f.collect(*__w, _recursive_multi_walk_up(__w<<__it, __f));
    __f.postorder(*__w);
    if(!__p(*__w))
      break;
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value general_directed_walk(_Walker __w, _Visitor __f)
{
  _Walker __n;

  while(__f.analyze(__w))
  {
    __f.preorder(*__w);
    if(__f.walk_up())
      __n = __w<<__f.up();
    else
      __n = __w<<__f.down();
    __f.postorder(*__w);
    __w = __n;
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value general_directed_walk_down(_Walker __w,
                                                           _Visitor __f)
{
  _Walker __n;

  while(__f.analyze(__w))
  {
    __f.preorder(*__w);
    __n = __w<<__f.down();
    __f.postorder(*__w);
    __w = __n;
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value general_directed_walk_up(_Walker __w,
                                                         _Visitor __f)
{
  _Walker __n;

  while(__f.analyze(__w))
  {
    __f.preorder(*__w);
    __n = __w<<__f.up();
    __f.postorder(*__w);
    __w = __n;
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_general_directed_walk(_Walker __w,
                                                                _Visitor __f)
{
  __f.preorder(*__w);
  while(__f.analyze(__w))
  {
    if(__f.walk_up())
      __f.collect(*__w, recursive_general_directed_walk(__w<<__f.up(), __f),
                  true);
    else
      __f.collect(*__w, recursive_general_directed_walk(__w<<__f.down(), __f),
                  false);
  }
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_general_directed_walk_down(
                        _Walker __w, _Visitor __f)
{
  __f.preorder(*__w);
  while(__f.analyze(__w))
  {
    __f.collect(*__w, recursive_general_directed_walk_down(__w<<__f.down(), __f));
  }
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_general_directed_walk_up(_Walker __w,
                                                                   _Visitor __f)
{
  __f.preorder(*__w);
  while(__f.analyze(__w))
  {
    __f.collect(*__w, recursive_general_directed_walk_up(__w>>__f.up(), __f));
  }
  __f.postorder(*__w);
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value general_walk(_Walker __w, _Visitor __f)
{
  _Walker __n;

  while(__f.analyze(__w))
  {
    __f.preorder(*__w);
    __n = __w>>__f.next();
    __f.postorder(*__w);
    __w = __n;
  }
  return __f.value();
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_general_walk(_Walker __w,
                                                       _Visitor __f)
{
  __f.preorder(*__w);
  while(__f.analyze(__w))
    __f.collect(*__w, recursive_general_walk(__w>>__f.next(), __f));
  __f.postorder(*__w);
  return __f.value();
}

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1209
#endif

__VGTL_END_NAMESPACE

#endif /* __VGTL_ALGO_H */

// Local Variables:
// mode:C++
// End:

---