Tree walker

Some generic tree walking infrastructure...

// Some generic stack based tree walker.

template <class T>
class StackItem
{
public:
  typedef T Node;
  StackItem(Node *parent, Node *pre, Node *post)
    : m_parent(parent),
      m_pre(pre),
      m_post(post)
    {}
  Node *parent(void) { return m_parent; }
  Node *prev(void) { return m_pre; }
  Node *post(void) { return m_post; }
private:
  Node *m_parent;
  Node *m_pre;
  Node *m_post;
};

template <class T>
class StackManipulator
{
public:
  typedef StackItem<T> Item;
  typedef typename Item::Node Node;
  typedef typename Node::Iterator NodesIterator;
  typedef typename std::list<Item> Container;

  StackManipulator(Container *stack, T *first)
    : m_stack(stack) {
    m_stack->push_back(Item(0, first, 0));
  }
 
  void addChildrenToStack(Node *node)
    {
      ASSERT(node);
      for (NodesIterator i = node->begin();
           i != node->end(); i++)
        m_stack->push_back(Item(node, *i, 0));
    }
 
  void addToStack(Node *parent, Node *prev)
    { m_stack->push_back(Item(parent, 0, prev)); }

private:
  Container *m_stack;
};

class FilterBase
{
public:
  enum FilterType
  {
    PRE = 1,
    POST = 2,
    BOTH = 3
  };
   
  virtual ~FilterBase(void) {}
  virtual std::string name(void) const = 0;
  virtual enum FilterType type(void) const = 0;
};

template <class T>
class Filter : public FilterBase
{
public:
  virtual void pre(T *parent, T *node) {};
  virtual void post(T *parent, T *node) {};
};


template <class T>
void walk(T *first, Filter<T> *filter=0)
{
  // TODO: Apply more than one filter at the time.
  //     This method applies one filter at the time. Is it worth to do
  //     the walk only once for all the filters? Should increase locality
  //     as well...
  ASSERT(filter);
  ASSERT(first);
  typedef StackManipulator<T> Manipulator;
  typedef typename Manipulator::Container Stack;
  typedef typename Manipulator::Item Item;
  typedef typename Manipulator::Node Node;

  Stack stack;
  Manipulator manipulator(&stack, first);

  while (!stack.empty())
  {
    Item item = stack.back(); stack.pop_back();
    Node *node = item.prev();
    Node *parent = item.parent();
    if (node)
    {
      if ( filter->type() & FilterBase::PRE)
        filter->pre(parent, node);
      if ( filter->type() & FilterBase::POST)
        manipulator.addToStack(parent, node);
      manipulator.addChildrenToStack(node);
    }
    else
      filter->post(parent, item.post());
  }
}