///////////////////////////////////////////////////////////
// MT2Q1.h
//   - Here, instead of graph class, used simpler
//     node class to illustrate idea

#include <vector>

template <typename T> class node;

template <typename T>
struct IFunc
{
  typedef void(IFunc<T>::*callback)(typename node<T>* pNode);
  virtual void nodeOp(node<T>* pNode) = 0;  // pointer to node callback handler
  virtual void edgeOp(node<T>* pNode) = 0;  // pointer to child callback handler
  virtual void operator()(node<T>* pNode, int level)=0;
};

template <typename T>
class node
{
public:
  node(size_t number, T t=0) : nodeNum_(number), value_(t), visited_(false), pFunc_(0) {}
  ~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;
  }
  void doNodeOp() { if(pFunc_) pFunc_->nodeOp(this); }
  void doEdgeOp() { if(pFunc_) pFunc_->edgeOp(this); }
  void Register(IFunc<T>* pFunc)
  {
    pFunc_ = pFunc;
  }
private:
  size_t nodeNum_;
  T value_;
  std::vector<node*> children_;
  bool visited_;
  IFunc<T>* pFunc_;
};

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