///////////////////////////////////////////////////////////////////////////
// Nodes.cpp - demonstrate how to define a template node class           //
// ver 1.1                                                               //
// Language:    Visual C++, 2008                                         //
// Platform:    Dell Precision T7400, Vista Ultimate, SP1                //
// Application: CSE382 - Algorithms and Data Structures Demo, Fall 2008  //
// Author:      Jim Fawcett, Syracuse University, CST 4-187,             //
//              (315) 443-3948, jfawcett@twcny.rr.com                    //
///////////////////////////////////////////////////////////////////////////

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

using namespace AbstractDataTypes;

#ifdef TEST_NODES

//----< this test function is how tree does depth first search >-----------

void WalkTree(MNode<std::string>* pMNode)
{
  std::cout << "\n  " << pMNode->ToString();
  pMNode->clearMarks();
  MNode<std::string>* pTemp;
  while(pTemp = pMNode->nextUnmarkedChild())
  {
    WalkTree(pTemp);
  }
}
//----< test stub demonstration >------------------------------------------

void main()
{
  std::cout << "\n  MNode<T> class demonstration";
  std::cout << "\n ==============================\n";

  std::cout << "\n  This demo uses a stack to order and link nodes, as they are created in";
  std::cout << "\n  depth-first order.  This builds a tree structure of nodes which is the";
  std::cout << "\n  product popped off the stack at the end.\n";

  std::cout << "\n  Note that this is exactly what happens when you assemble parts from";
  std::cout << "\n  XmlElementParts to build the internal tree for an XmlDocument instance.\n";
  
  std::cout << "\n  As the last step in parsing, you pull a fully formed parse tree (in linked";
  std::cout << "\n  nodes form) from the top of the stack on its final pop.  Now you just bind";
  std::cout << "\n  the top node to your tree root for subsequent processing.\n";

  std::stack<MNode<std::string>*> NodeStack;

  MNode<std::string> root("root");
  NodeStack.push(&root);                                          // &root on stack top
  
  MNode<std::string> child1("child1");
  NodeStack.top()->add(&child1);                                  // child1 added to root
  NodeStack.push(&child1);                                        // &child1 pushed to stack top

  MNode<std::string> grandchild11("grandchild11");
  NodeStack.top()->add(&grandchild11);                            // grandchild11 added to child1
  NodeStack.pop();                                                // stack popped to reveal &root

  MNode<std::string> child2("child2");
  NodeStack.top()->add(&child2);                                  // child2 added to root
  NodeStack.push(&child2);                                        // &child2 pushed to stack top

  MNode<std::string> grandchild21("grandchild21");
  NodeStack.top()->add(&grandchild21);                            // grandchild21 added to child2
  NodeStack.push(&grandchild21);                                  // &grandchild21 pushed to stack top

  MNode<std::string> greatgrandchild211("greatgrandchild211");
  NodeStack.top()->add(&greatgrandchild211);                      // greadgrandchild211 added to grandchild21
  NodeStack.pop();                                                // stack popped to reveal &child2

  MNode<std::string> grandchild22("grandchild22");
  NodeStack.top()->add(&grandchild22);                            // grandchild22 added to child2
  NodeStack.pop();                                                // stack popped to reveal &root

  MNode<std::string> child3("child3");
  NodeStack.top()->add(&child3);                                  // child3 added to root
  
  MNode<std::string>* pRoot = NodeStack.top();                    // &root popped from stack
  NodeStack.pop();

  WalkTree(pRoot);

  std::cout << "\n\n  removing first child";
  root.remove(&child1);

  WalkTree(&root);

  std::cout << "\n\n  root.ToString() = " << root.ToString().c_str();

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