//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MBN 07/06/89 -- Initial design
// Updated: MBN 08/15/89 -- Inherit from Generic and initial implementation
// Updated: MBN 09/19/89 -- Added conditional exception handling
// Updated: MBN 02/27/90 -- Added constructor that takes a pointer to node and
//                          the current_depth() member function
// Updated: MJF 03/12/90 -- Added group names to RAISE
//
// The  N_Tree  class  implements  N-ary  trees,  providing  the organizational
// structure for a tree  (collection) of nodes,  but  knowing nothing about the
// specific type of node  used. N_Tree is parameterized  over a node type and a
// data type, where the node specified  must have a data slot  of the same type
// Type as the N_Tree  class. Two node classes are  provided, but others  could
// also be written.  The  N_Node class implements  static-sized nodes for  some
// particular "N" number of sub-trees, and the D_Node class  implements dymamic
// sized nodes derived from the Vector class.
//
// Since the organization of a tree is important (as  with an expression tree),
// the user must supervise the construction  of  the tree by directing specific
// node and sub-tree assignment and layout.   No attempt  is made by the N_Tree
// class to balance or prune the tree.
//
// The N_Tree class supports the concept  of a  current  position and a current
// traversal mode. When  the traversal  mode  is  set, the current position  is
// invalidated.  The  first call   to advance the   current position causes  an
// internal dynamic cache of pointers to nodes to  be created ordered according
// to the traversal mode. Future current position  methods then act  based upon
// the information in  the cache.   Any method that  changes the tree structure
// invalidates the cache.
//
// There are two  public constructors. The  first takes a  reference  to a Node
// object and constructs an N_Tree object whose root is the supplied node.  The
// second takes a reference  to an existing  N_Tree  object and duplicates  its
// size and contents.  The N_Tree class has four private data slots.  The first
// contains a pointer to the root of the tree, the second maintains the current
// position,  the  third contains a pointer to  a  dynamic cache of pointers to
// nodes used  by  the current  position  methods, and  the   fourth contains a
// pointer to the default node comparison function.  In addition, there are two
// private methods.  The first is used to create the cache of pointers to nodes
// upon the first dispatch to  advance the current position,  and the second is
// the default node comparison function to be used  if the user  does not chose
// to provide one.
//
// All methods  in the  N_Tree class  support  the organization, structure, and
// traversal of a tree.  Methods to allow manipulation  of individual nodes and
// sub-trees is located in the node classes. N_Tree has methods to search for a
// sub-tree,  find a  node with a specific value,  and return a  pointer to the
// parent of the current  node. The reset, next, prev,  value, remove, and find
// methods provide a mechanism to  iterate  through the nodes  of a tree  based
// upon  the current position. The specific  traversal mechanism  for  use with
// this iteration can be set with  the set_traversal method,  and all nodes can
// be removed  from the tree   with  clear.  Finally,  methods  are provided to
// traverse the  tree in  either preorder, inorder,  or  postorder and apply  a
// user-specified function to each node.
//

#ifndef N_TREEH					// If no definition for class
#define N_TREEH

#ifndef GENERIC_H				// If no definition for class
#include <cool/Generic.h>				// include definition file
#endif

#ifndef STACKH					// If no definition for class
#include <cool/Stack.h>				// include definition file
#endif

#ifndef PAIRH					// If no definition for class
#include <cool/Pair.h>				// include definition file
#endif


#ifndef BASE_BINARY_TREEH
enum Left_Right {NONE, LEFT, RIGHT};
enum Traversal_Type {PREORDER, INORDER, POSTORDER,
		     PREORDER_REVERSE, INORDER_REVERSE, POSTORDER_REVERSE};
#endif


DECLARE Pair<long,int>;
typedef Pair<long,int> NT_Stack_Entry;
DECLARE Stack<Pair<long,int>>;
typedef Stack<Pair<long,int>> NT_Stack;

IMPLEMENT Pair<long,int>;
IMPLEMENT Stack<Pair<long,int>>;

#define N_Tree_state NT_State

// Simple class that bundles an iterator stack with the direction 
// of the traversal (forward or backward).  This is the current_position
// state that can be saved and restored 

class NT_State {				// State bundles Stack&Boolean
public:
  NT_Stack stack;
  Boolean forward;

  inline NT_State () {};			// Simple constructor
  inline NT_State (const NT_State& s) {		// Constructor with reference
    this->stack = s.stack;			
    this->forward = s.forward;
  };                                                  
  inline ~NT_State () {};			// Destructor
  inline NT_State& operator= (NT_State& s) {	// overload = operator
    this->stack = s.stack;			// Needs memberwise copy
    this->forward = s.forward;
    return *this;
  };                                                  
};

  
template <class Node, class Type, int nchild> N_Tree {
  typedef Boolean (*Node##_Apply_Function)(const Type&);	
  DECLARE Node<Type,nchild>;
}

template <class Node, class Type, int nchild>
class N_Tree<Node,Type,nchild> : public Generic {
private:
  Node##_##Type##_##nchild##_p root;		// Root of tree
  long number_nodes;				// Number of nodes in tree
  Traversal_Type t_mode;			// Retains traversal type
  NT_State state;				// Iterator state for N_Tree

  void do_count (Node<Type,nchild>*);		// Count nodes in tree
  Boolean next_internal (Traversal_Type);	// Moves current_position

  void value_error ();				// Raise exception
  
public:
  N_Tree<Node,Type,nchild> (Node<Type,nchild>*); // Simple constructor
  N_Tree<Node,Type,nchild> (Node<Type,nchild>&); // Simple constructor
  N_Tree<Node,Type,nchild> (const N_Tree<Node,Type,nchild>&);	// ref const.
  ~N_Tree<Node,Type,nchild> ();				// Destructor

  void clear ();				// Empty the tree
  inline long count ();				// Return number of nodes
  inline void reset ();				// Current position invalid
  inline Traversal_Type& traversal ();		// Set/Get the traversal mode
  inline Node##_##Type##_##nchild##_p& operator[] (int); // Set/Get pointers

  inline Boolean next ();			// Advance to next node
  Boolean prev ();			        // Backup to previous node
  Type& value ();			// Get value at current position
  Boolean find (const Type&);			// Search for item in tree
  inline NT_State& current_position();		// Get/Set Tree's curpos
  inline long current_depth () CONST;		// Depth of curpos in tree

  void preorder (Node##_Apply_Function);	// Preorder traversal
  void inorder (Node##_Apply_Function);		// Inorder traversal
  void postorder (Node##_Apply_Function);	// Postorder traversal

#ifdef __cplusplus
  inline operator Node##_##Type##_##nchild##_p () CONST;
#else
  inline Node##_##Type##_##nchild##_p operator Node##_##Type##_##nchild##_p ();
#endif
};

template <class Node, class Type, int nchild> N_Tree {
  IMPLEMENT Node<Type,nchild>;
}



// do_count -- Perform an preorder traversal of N-ary tree to count nodes
// Input:       Pointer to sub-tree node
// Output:       None

template <class Node, class Type, int nchild>
void N_Tree<Node,Type,nchild>::do_count (Node<Type,nchild>* t) {
  if (t != NULL) {				// If there is a subtree
    this->number_nodes++;			// Increment node count
    for (int i = 0; i < nchild; i++)		// For each pointer in vector
      this->do_count (t->sub_trees[i]);		// Traverse each subtree
  }
}


// ~N_Tree -- destructor (not inline because it's virtual)
// Input:    none
// Output:   none

template <class Node, class Type, int nchild>
N_Tree<Node,Type,nchild>::~N_Tree<Node,Type,nchild> () {}


// N_Tree -- Simple constructor that sets the root to the node provided
// Input:    Reference to node object
// Output:   N_Tree object created with root initialized

template <class Node, class Type, int nchild> 
N_Tree<Node,Type,nchild>::N_Tree<Node,Type,nchild> (Node<Type,nchild>& n) {
  this->root = &n;				// Point root to node
  this->t_mode = INORDER;			// Default traversal mode
  this->number_nodes = 1;			// Update node count
}


// N_Tree -- Simple constructor that sets the root to the node provided
// Input:    Pointer to node object
// Output:   N_Tree object created with root initialized

template <class Node, class Type, int nchild> 
N_Tree<Node,Type,nchild>::N_Tree<Node,Type,nchild> (Node<Type,nchild>* n) {
  this->root = n;				// Point root to node
  this->t_mode = INORDER;			// Default traversal mode
  this->number_nodes = 1;			// Update node count
}


// N_Tree -- Constructor that duplicates the size and values of another N_Tree
// Input:    Reference to N_Tree object
// Output:   N_Tree object duplicated

template <class Node, class Type, int nchild> 
N_Tree<Node,Type,nchild>::N_Tree<Node,Type,nchild> (const N_Tree<Node,Type,nchild>& n){
  this->root = n.root;				// Point root to node
  this->t_mode = INORDER;			// Default traversal mode
  this->number_nodes = 1;			// Update node count
}


// clear -- removes root and all subtrees
// input -- none
// output -- none

template <class Node, class Type, int nchild> 
void N_Tree<Node,Type,nchild>::clear () {
  delete this->root;
  this->root = NULL;
  this->number_nodes = 0;
  this->reset();
}



// Reset -- Initialize current position of Tree
// Input:   None
// Output:  None

template <class Node, class Type, int nchild> 
inline void N_Tree<Node,Type,nchild>::reset () {
  this->state.stack.clear();
}


// count -- Return number of nodes in tree
// Input:   None
// Output:  Number of nodes in tree

template <class Node, class Type, int nchild> 
inline long N_Tree<Node,Type,nchild>::count () {
  this->number_nodes = 0;			// Initialize count
  this->do_count (this->root);			// Count nodes in tree
  return this->number_nodes;			// Return node count
}


// set_traversal -- Set traversal mode
// Input:           Traversal type
// Output:          None

template <class Node, class Type, int nchild> 
inline Traversal_Type& N_Tree<Node,Type,nchild>::traversal () {
  return (this->t_mode);			// Traversal mode
}


// operator[] -- Overload the brackets operator to provide a mechanism to set
//               and/or get a sub-tree pointer of a node whose zero-relative
//               index is specified from left to right
// Input:        Zero-relative index into vector of sub-tree pointers
// Output:       Reference to a pointer value

template <class Node, class Type, int nchild> 
inline Node##_##Type##_##nchild##_p& N_Tree<Node,Type,nchild>::operator[] (int index) {
  return (this->root->sub_trees[index]);
}


// next -- Move current position to next node in tree. If no more nodes
//         return FALSE
// Input:  None
// Output: TRUE/FALSE

template <class Node, class Type, int nchild> 
inline Boolean N_Tree<Node,Type,nchild>::next () {
  return next_internal (this->t_mode);
}



// prev -- Move position to previous node in tree. If no more nodes
//         return FALSE 
// Input:  None
// Output: TRUE/FALSE

template <class Node, class Type, int nchild> 
Boolean N_Tree<Node,Type,nchild>::prev() {
  Traversal_Type reverse_mode;
  switch (this->t_mode) {
  case INORDER:
    reverse_mode = INORDER_REVERSE;
    break;
  case INORDER_REVERSE:
    reverse_mode = INORDER;
    break;
  case PREORDER:
    reverse_mode = PREORDER_REVERSE;
    break;
  case PREORDER_REVERSE:
    reverse_mode = PREORDER;
    break;
  case POSTORDER:
    reverse_mode = POSTORDER_REVERSE;
    break;
  case POSTORDER_REVERSE:
    reverse_mode = POSTORDER;
    break;
  }
  return this->next_internal (reverse_mode);
}
  
// Get the next node in the tree based on the Traversal Type.  This
// maintains a stack of parents in the tree for current position and
// knows how to move forward and backward for preorder, inorder, or
// postorder traversals. Changes here are most likely necessary in
// Base_BT.C next_internal also.

template <class Node, class Type, int nchild>
Boolean N_Tree<Node,Type,nchild>::next_internal (Traversal_Type ttype) {
  Node##_##Type##_##nchild##_p node, ptr1;
  Node##_##Type##_##nchild##_p last_node = NULL;
  NT_Stack_Entry stack_entry;
  int index;
  Boolean forward = TRUE;

  switch (ttype) {
  case INORDER_REVERSE:
  case PREORDER_REVERSE:			// Are we going backward?
  case POSTORDER_REVERSE:
    forward = FALSE;
    break;
  }
    
  if (state.stack.is_empty()) {			// If stack is empty
    node = this->root;				//  start with the root
    if (forward)				//  init starting subtree
      index = -1;				//    start at first subtree
    else					//    or
      index = node->num_subtrees();		//    start at last subtree
    state.stack.push (NT_Stack_Entry ((long)node,index));
    state.forward = forward;
    
  }
  else {					// Stack has some entries, so
    stack_entry = state.stack.top();		//  get top entry from stack
    node = (Node<Type,nchild>*)stack_entry.get_first();    //  load up node
    index = (int)stack_entry.get_second();	//  and subtree index
    last_node = node;				//  remember current position

    if (state.forward != forward) {		// Need to modify index
      if (forward)				//  if we've changed direction.
	index--;
      else
	index++;
    }
    state.forward = forward;			// Update direction.
  }

  if (forward) {				// Going left to right
    while (TRUE) {				// loop until next node found
      if (++index < node->num_subtrees()) {	// incremented index in range?
	if (node != last_node &&		// If we moved to new node &&
	    ((ttype == INORDER  && index == 1)  // Inorder after ltree or
	     ||(ttype == PREORDER && index == 0)// Preorder before ltree
	     ))
	  return TRUE;				// then this is next node

	state.stack.top().set_second(index);	// update stack with new index
	ptr1 = node->sub_trees[index];		// get node's next subtree
	if (ptr1) {				// When subtree exists
	  node = ptr1;				//   point node at subtree
	  index = -1;				//   init index for new node
	  state.stack.push (NT_Stack_Entry ((long)node, index)); 
	}
      }
      else {					// No more subtrees for node
	if (node != last_node &&		// If a new node
	    ttype == POSTORDER) {		//   and Postorder mode, 
	  return TRUE;				//   then this is next node
	}
	state.stack.pop();// pop this node from stack
	if (state.stack.is_empty())            // Stack empty?
	  return FALSE;				//   indicate we're at the end
        else {					// Stack not empty, so
	  stack_entry = state.stack.top();	//  update stack_entry object
	  node = (Node<Type,nchild>*)stack_entry.get_first(); //  load up node
	  index = stack_entry.get_second();	//  and subtree index
	}
      }
    }
  }

// This is essesentially the same code as above, but going right to
// left, giving reverse order capability
  else {                                        // Going right to left
    while (TRUE) {				// loop until next node found
      if (--index > -1) {			// decremented index in range?
	if (node != last_node &&		// If we moved to new node &&
	    ((ttype == INORDER_REVERSE &&	//  or Inorder_reverse node
	      index == 0) 			//  is ready to do left subtree
 	     || (ttype == POSTORDER_REVERSE &&	//  or Postorder_reverse is
	      index == (node->num_subtrees()-1))  // starting it's subtrees
	     ))
	  return TRUE;				// then this is next node
	state.stack.top().set_second(index);	// update stack with new index
	ptr1 = node->sub_trees[index];	        // get node's next subtree
	if (ptr1) {				// When subtree exists
	  node = ptr1;				//   point node at subtree
	  index = node->num_subtrees();		//   init index for new node
	  state.stack.push (NT_Stack_Entry ((long)node, index)); 
	}
      }
      else {					// No more subtrees for node
	if (node != last_node &&		// If a new node
        ttype == PREORDER_REVERSE) 	        //   and Preorder_reverse
	  return TRUE;				//   this is next node

	state.stack.pop();			// pop this node from stack
	if (state.stack.is_empty())		// Stack empty?
	  return FALSE;				//   indicate we're at the end
        else {					// Stack not empty, so
	  stack_entry = state.stack.top();	//  update stack_entry object
	  node = (Node<Type,nchild>*)stack_entry.get_first(); //  load up node
	  index = (int)stack_entry.get_second();	//  and subtree index
	}
      }
    }
  }
}


// value -- Return value of node at current position
// Input: None
// Output: Reference to value of node at current position

template <class Node, class Type, int nchild> 
Type& N_Tree<Node,Type,nchild>::value () { 
#if ERROR_CHECKING 
  if (this->state.stack.is_empty() )		// If no position established
    this->value_error ();			// Raise exception
#endif
  NT_Stack_Entry stack_entry = this->state.stack.top();
  return (((Node<Type,nchild>*)stack_entry.get_first())->get());
}


// find -- Search the tree for a particular value. If found, update the current
//         position marker.
// Input:  Reference of value to search for
// Output: TRUE/FALSE

template <class Node, class Type, int nchild> 
Boolean N_Tree<Node,Type,nchild>::find (const Type& value) {
  for (this->reset (); this->next (); ) 	// For each node in tree
    if (this->value() == value)			// If node found in tree
      return TRUE;				// Inidicate success
  return FALSE;					// Inidicate failure
}


// preorder -- Perform a preorder traversal of tree by setting traversal mode,
//             making node pointer cache, and applying function to each node
// Input:      Pointer to function to apply to each node
// Output:     None

template <class Node, class Type, int nchild> 
void N_Tree<Node,Type,nchild>::preorder (Node##_Apply_Function fn) {

  if (this->t_mode != PREORDER) 		// If incorrect traversal mode
    this->t_mode = PREORDER;			// Set preorder mode

  for (this->reset() ; this->next (); )		// For each preorder node
    (*fn)(this->value());			// Apply function
}


// inorder -- Perform an inorder traversal of tree by setting traversal mode,
//            making node pointer cache, and applying function to each node
// Input:     Pointer to function to apply to each node
// Output:    None

template <class Node, class Type, int nchild> 
void N_Tree<Node,Type,nchild>::inorder (Node##_Apply_Function fn) {
  if (this->t_mode != INORDER)  		// If incorrect traversal mode
    this->t_mode = INORDER;			// Set inorder mode

  for (this->reset() ; this->next (); )		// For each preorder node
    (*fn)(this->value());			// Apply function
}


// postorder -- Perform a postorder traversal of tree by setting traversal mode,
//              making node pointer cache, and applying function to each node
// Input:       Pointer to function to apply to each node
// Output:      None

template <class Node, class Type, int nchild> 
void N_Tree<Node,Type,nchild>::postorder (Node##_Apply_Function fn) {
  if (this->t_mode != POSTORDER) 		// If incorrect traversal mode
    this->t_mode = POSTORDER;			// Set postorder mode

  for (this->reset() ; this->next (); )		// For each preorder node
    (*fn)(this->value());			// Apply function
}

// current_position -- Get/Set iterator object for Tree
// Input:              None
// Output:             NT_State object of the Tree

template <class Node, class Type, int nchild>
NT_State& N_Tree<Node,Type,nchild>::current_position () {
  return this->state;
}


// current_depth -- Get current depth of current position in tree
// Input:           None
// Output:          Depth of current position node in tree

template <class Node, class Type, int nchild>
inline long N_Tree<Node,Type,nchild>::current_depth () CONST {
  return this->state.stack.length() - 1;
}


// value_error -- Raise exception for N_Tree::value()
// Input:         None
// Output:        None

template <class Node, class Type, int nchild> 
void N_Tree<Node,Type,nchild>::value_error () {
  RAISE (Error, SYM(N_Tree), SYM(Invalid_Cpos),
	 "N_Tree<%s,%s,%d>::value(): Invalid current position",
         #Type, #Node, nchild);
}

// operator Node -- Provide an accessor to the encapsulated Node object
// Input:           None
// Output:          Pointer to node object

#ifdef __cplusplus
template <class Node, class Type, int nchild> 
inline N_Tree<Node,Type,nchild>::operator Node##_##Type##_##nchild##_p () CONST
{
  return this->root;
}
#else
template <class Node, class Type, int nchild> 
inline Node##_##Type##_##nchild##_p N_Tree<Node,Type,nchild>::operator
   Node##_##Type##_##nchild##_p () 
{
  return this->root;
}
#endif

#endif						// End N_TREEH #if
