/* iterators.h
 *
 * Defines and implements the two tree iterators BreadthFirstIterator and PostOrderIterator.
 *
 */

// BEGIN breadthDefn
template <class NodeData>
class BreadthFirstIterator 
{
private:
  TreeNode<NodeData> *root;
  unsigned int degree;
  queue<TreeNode<NodeData> *> Q;
  
public:
  BreadthFirstIterator(TreeNode<NodeData> *inRoot, unsigned int inDegree);
  void Reset();
  bool isDone();
  TreeNode<NodeData> *operator*();
  void operator++();
};
// END breadthDefn

// BEGIN postDefn
template <class NodeData>
class PostOrderIterator 
{
private:
  TreeNode<NodeData> *root;
  unsigned int degree;
  stack<TreeNode<NodeData> *> S;
  stack<int> curDegrees;
  TFunctor *visitListener;
  
public:
  PostOrderIterator(TreeNode<NodeData> *inRoot, unsigned int inDegree, TFunctor *inVisitListener);
  void registerVisitListener(TFunctor *inVisitListener);
  void Reset();
  bool isDone();
  TreeNode<NodeData> *operator*();
  void operator++();
  void dump();
};
// END postDefn

/********************** BreadthFirstIterator *********************************/

// BEGIN breadthConst
template <class NodeData>
BreadthFirstIterator<NodeData>::BreadthFirstIterator(TreeNode<NodeData> *inRoot, unsigned int inDegree)
{
  degree = inDegree;
  root = inRoot;
  Q.push(root);
}
// END breadthConst

// BEGIN breadthReset
template <class NodeData>
void BreadthFirstIterator<NodeData>::Reset()
{
  while(!Q.empty())
    Q.pop();
  
  Q.push(root);
}
// END breadthReset

// BEGIN breadthDone
template <class NodeData>
bool BreadthFirstIterator<NodeData>::isDone()
{
  return Q.empty();
}
// END breadthDone

// BEGIN breadthDref
template <class NodeData>
TreeNode<NodeData> *BreadthFirstIterator<NodeData>::operator *()
{
  return Q.front();
}
// END breadthDref

// BEGIN breadthIncr
template <class NodeData>
void BreadthFirstIterator<NodeData>::operator++()
{
  TreeNode<NodeData> *head, *child;
  
  head = Q.front();
  Q.pop();

  if(head->children.size() == degree)
    for(unsigned int curDegree = 0; curDegree < degree; curDegree++)
      {
	child = head->children[curDegree];
	Q.push(child);
      }
}
// END breadthIncr

/********************** PostOrderIterator *********************************/
// BEGIN postConst
template <class NodeData>
PostOrderIterator<NodeData>::PostOrderIterator(TreeNode<NodeData> *inRoot, unsigned int inDegree, 
					       TFunctor *inVisitListener)
{
  degree = inDegree;
  root = inRoot;

  visitListener = inVisitListener;  

  Reset();
}
// END postConst

// BEGIN postRegister
template <class NodeData>
void PostOrderIterator<NodeData>::registerVisitListener(TFunctor *inVisitListener)
{
  visitListener = inVisitListener;
}
// END postRegister

// BEGIN postReset
template <class NodeData>
void PostOrderIterator<NodeData>::Reset()
{
  TreeNode<NodeData> *walker;

  while(!curDegrees.empty())
    curDegrees.pop();
  
  while(!S.empty())
    S.pop();

  for(walker = root; walker->children.size() == degree; 
      walker = walker->children[0])
    {
      if(visitListener)
	(*visitListener)(walker);

      S.push(walker);
      curDegrees.push(0);
    }

  if(visitListener)
    (*visitListener)(walker);
  
  curDegrees.push(0);
  S.push(walker);
}
// END postReset

// BEGIN postDone
template <class NodeData>
bool PostOrderIterator<NodeData>::isDone()
{
  return S.empty();
}
// END postDone

// BEGIN postDref
template <class NodeData>
TreeNode<NodeData> *PostOrderIterator<NodeData>::operator *()
{
  return S.top();
}
// END postDref

// BEGIN postIncr
/* This code is quite complicated, as it generally is expressed
 * as a recursive function.
 * 
 * We need two stacks: one for the objects themselves
 *                     another to keep track of which child we've visited
 */
template <class NodeData>
void PostOrderIterator<NodeData>::operator++()
{
  TreeNode<NodeData> *top, *walker;
  unsigned int curDegree;

  curDegrees.pop();  
  S.pop();

  if(S.empty())
    return;
  
  top = S.top();

  curDegree = curDegrees.top();

  if(top->children.size() != degree)
    return;
  
  curDegree++;

  if(curDegree < degree)
    {
      curDegrees.pop();
      curDegrees.push(curDegree);
      
      for(walker = top->children[curDegree]; 
	  walker->children.size() == degree; walker = walker->children[0])
	{
	  if(visitListener)
	    (*visitListener)(walker);

	  S.push(walker);
	  curDegrees.push(0);
	}
      
      if(visitListener)
	(*visitListener)(walker);

      S.push(walker);
      curDegrees.push(0);
    }
}
// END postIncr

template <class NodeData>
void PostOrderIterator<NodeData>::dump()
{
  printf("S size is %d\n", S.size());
  
  while(!S.empty())
    {
      printf("%f\n", (S.top())->value);
      S.pop();
    }
  
  printf("curDegrees size is %d\n", curDegrees.size());

  while(!curDegrees.empty())
    {
      printf("%d\n", curDegrees.top());
      curDegrees.pop();
    }
  
  exit(0);
}

