// Node.h

#include <vector>

template <typename T>
class node
{
public:
  node(size_t number, T t=0) : nodeNum_(number), value_(t), visited_(false) {}
  ~node()
  { 
    // Can't delete children unless you are sure they were created on heap
    // for(size_t i=0; i<children_.size(); ++i)
    //   delete children_[i];
  }
  size_t& number() { return nodeNum_; }
  T& value() { return value_; }
  void add(node<T>* pNode) { children_.push_back(pNode); }
  bool& visited() { return visited_; }
  size_t size() { return children_.size(); }
  node<T>* getNextUnmarkedChild()
  {
    for(size_t i=0; i<children_.size(); ++i)
      if(!children_[i]->visited())
        return children_[i];
    return 0;
  }
private:
  size_t nodeNum_;
  T value_;
  std::vector<node*> children_;
  bool visited_;
};

template <typename T>
struct IFunc
{
  virtual void operator()(node<T>* pNode, int level)=0;
};

template <typename T>
void DFS(node<T>* pNode, IFunc<T>& f)
{
  static int lev = 1;
  pNode->visited() = true;
  f(pNode, lev++);
  for(size_t i=0; i<pNode->size(); ++i)
  {
    node<T>* pChild = pNode->getNextUnmarkedChild();
    if(pChild)
    {
      DFS(pChild,f);
    }
  }
  --lev;
}