// Node.h

#include <vector>

template <typename T, bool Delete>  // second argument is a policy
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
    if(Delete)
     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,Delete>* pNode) { children_.push_back(pNode); }
  bool& visited() { return visited_; }
  size_t size() { return children_.size(); }
  node<T,Delete>* 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<T,Delete>*> children_;
  bool visited_;
};
///////////////////////////////////////////////////
// class definition above is a complete answer
// for Midterm1, Question 6
// Policy is interesting, but not needed for
// correct complete answer

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

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