/////////////////////////////////////////////////////
// MT4Q4 - N-ary Tree with adjacency collection    //
//                                                 //
// Jim Fawcett, CSE687 - OOD Midterm, Spring 2013  //
/////////////////////////////////////////////////////

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include "../MTutility/MTutility.h"

template <typename T>
class Node {
public:
  typedef std::vector<Node<T>*> Children;
  Node(const T& t) : _t(t) {}
  void add(Node<T>* pChild) { _children.push_back(pChild); }
  Children& children() { return _children; }
  T& value() { return _t; }
private:
  Children _children;
  T _t;
};

template <typename T>
class Tree {
public:
  typedef void (*NodeProc)(Node<T>* pNode);
  Tree() {}
  ~Tree() 
  {
    // do this only if Tree creates nodes
    // for(auto pNode : _nodes) delete pNode; 
  }
  void makeRoot(Node<T>* pRoot) { _nodes.push_back(pRoot); }
  bool addNode(Node<T>* pParent, Node<T>* pChild);
  template<typename F>
  void dfs(Node<T>* node, F f);
private:
  Tree(const Tree<T>&);
  Tree<T>& operator=(const Tree<T>&);
  std::vector<Node<T>*> _nodes;  // could replace with pointer to root
};

template<typename T>
bool Tree<T>::addNode(Node<T>* pParent, Node<T>* pChild)
{
  std::vector<Node<T>*>::iterator iter 
    = std::find(_nodes.begin(), _nodes.end(), pParent);
  if(iter == _nodes.end())
  {
    std::cout << " can't find parent";
    return false;
  }
  (*iter)->add(pChild);
  _nodes.push_back(pChild);
  return true;
}

template<typename T>
template<typename F>
void Tree<T>::dfs(Node<T>* node, F f)
{
  f(node);
  for(auto& child : node->children())
    dfs(child, f);
}

template<typename T>
void show(Node<T>* pNode)
{
  std::cout << "\n  " << pNode->value() << " has " 
            << pNode->children().size() << " children ";
  for(auto node : pNode->children())
    std::cout << node->value() << " ";
}

int main()
{
  Title("MT4Q4 - N-Ary Tree");
  typedef Tree<std::string> sTree;
  sTree tree;
  typedef Node<std::string> sNode;
  sNode n0("n0");
  sNode n1("n1");
  sNode n2("n2");
  sNode n3("n3");
  sNode n4("n4");
  sNode n5("n5");
  tree.makeRoot(&n0);
  tree.addNode(&n0, &n1);
  tree.addNode(&n0, &n2);
  tree.addNode(&n1, &n3);
  tree.addNode(&n1, &n4);
  tree.addNode(&n2, &n5);
  tree.dfs(&n0, (sTree::NodeProc)show);
  class NoChild
  {
  public:
    void operator()(Node<std::string>* pNode)
    {
      if(pNode->children().size() == 0)
        noChildren.push_back(pNode);
    }
    std::vector<Node<std::string>*> noChildNodes() { return noChildren; }
  private:
    std::vector<Node<std::string>*> noChildren;
  };

  NoChild noChild;
  tree.dfs(&n0, std::ref(noChild));
  std::cout << "\n  Nodes with no children: ";
  for(auto node : noChild.noChildNodes())
    std::cout << node->value() << " ";

  std::cout << "\n\n";
}