#ifndef TREE_H
#define TREE_H
///////////////////////////////////////////////////////////////////////////
// Tree.h    -  demonstrates how to define a template m-ary tree class   //
// ver 1.2                                                               //
// Language:    Visual C++, 2008                                         //
// Platform:    Dell Precision T7400, Vista Ultimate, SP1                //
// Application: CSE687 - Demo for Project #1, Spring 2009                //
// Author:      Jim Fawcett, Syracuse University, CST 4-187,             //
//              (315) 443-3948, jfawcett@twcny.rr.com                    //
///////////////////////////////////////////////////////////////////////////
/*
 * Module Operations:
 * ==================
 * Provides a template Tree class that holds a finite number of nodes and
 * and supports visitation of each node, using depth first search.  
 * 
 * Build Process:
 * ==============
 * cl /D:TEST_TREE Tree.cpp Nodes.cpp
 * 
 * Maintenance History:
 * ====================
 * ver 1.2 : 29 Jan 10
 * - added some comments below and in code
 * ver 1.1 : 27 Jan 10
 * - added private declarations for copy and assignment
 *   to prevent compiler from generating incorrect versions
 * ver 1.0 : 23 Jan 09
 * - first release
 */
/*
 * Notes:
 * - Tree destructor is not deleting nodes because the test stub is creating
 *   on the stack, e.g., local to main.  If you create nodes on the heap
 *   then you should delete all the contents pointed to by the nodes vector.
 * - This simple tree depends on user to assemble the linked structure, as
 *   done in the test stub.  Since you will get a fully linked tree from the
 *   XmlParser stack in Project #1, this tree can just accept that structure.
 */

#include <iostream>
#include "Nodes.h"

namespace AbstractDataTypes
{
  template <typename T>
  class Operation
  {
  public:
    virtual ~Operation() {}
    virtual void operator()(MNode<T>* pNode)
    {
      std::cout << "\n  " << pNode->value();
    }
  };

  template <typename T>
  class Tree
  {
  public:
    Tree(Operation<T>* pOper=new Operation<T>());
    ~Tree();
    void setOperation(Operation<T>* pOper);
    void add(MNode<T>* pMNode);
    bool remove(MNode<T>* pMNode);
    void clearMarks();
    void walk(MNode<T>* pStart);
  private:
    Tree(const Tree& tree);
    Tree& operator=(const Tree& tree);
    MNode<T>* pRoot;               // not used yet
    std::vector<MNode<T>*> nodes;  // used to unmark
    Operation<T>* pOper_;
  };

  template <typename T>
  Tree<T>::Tree(Operation<T>* pOper) : pOper_(pOper) {}

  template <typename T>
  Tree<T>::~Tree() 
  { 
    delete pOper_;

  // Do this only if you create nodes on heap
  // for(size_t i=0; i<nodes.size(); ++i)
  //   delete nodes[i];
  }

  template <typename T>
  void Tree<T>::setOperation(Operation<T>* pOper)
  {
    delete pOper_;
    pOper_ = pOper;
  }

  template <typename T>
  void Tree<T>::add(MNode<T>* pMNode)
  {
    nodes.push_back(pMNode);
  }

  template <typename T>
  bool Tree<T>::remove(MNode<T>* pMNode)
  {
    std::vector< MNode<T>* >::iterator iter;
    for(iter=nodes.begin(); iter!=nodes.end(); ++iter)
    {
      if(*iter == pMNode)
      {
        nodes.erase(iter);
        return true;
      }
    }
    return false;
  }

  template <typename T>
  void Tree<T>::clearMarks()
  {
    for(size_t i=0; i<nodes.size(); ++i)
      nodes[i]->isMarked() = false;
  }

  template <typename T>
  void Tree<T>::walk(MNode<T>* pStart)
  {
    (*pOper_)(pStart);
    MNode<T>* pTemp;
    for(size_t i=0; i<nodes.size(); ++i)
    {
      pTemp = pStart->nextUnmarkedChild();
      if(pTemp == 0)
        return;
      pTemp->isMarked() = true;
      walk(pTemp);
    }
  }
}
#endif