//
// 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/05/89 -- Initial design
// Updated: MBN 08/10/89 -- Initial implementation
// Updated: MBN 08/11/89 -- Inherit from Generic
// Updated: MBN 09/19/89 -- Added conditional exception handling
// Updated: MBN 12/21/89 -- Added optional argument to set_compare method
// Updated: MBN 02/27/90 -- Added operator= for pointer argument
// Updated: MJF 03/12/90 -- Added group names to RAISE
//
// The N_Node<Type,nchild>  class implements parameterized   nodes of a  static
// size  for N-ary trees.   This node class  is parameterized for both the type
// and some "N", the number of  subtrees each node  may have.  The constructors
// for  the  N_Node<Type,nchild> class are  declared  in the public  section to
// allow the user to create nodes and control  the building and structure of an
// N-ary  tree where  the   ordering can have  a specific   meaning, as with an
// expression tree.
//
// The  private data section contains  just two slots.  The  first is  a static
// sized vector of "N" pointers to N_Node objects, one for  each subtree.   The
// second is  a data  slot  of type Type  to hold the  value  of the data item.
// There are three  public constructors for the  N-Node class.  The first takes
// no arguments and initializes the pointer and data slots to NULL.  The second
// takes an argument of type Type and initializes the data  slot to that value.
// The  third takes a  reference to  another  N-Node object  and duplicates its
// values.
//
// Methods are provided to set and get the node data value, determine if a node
// is a leaf or the root of some subtree,  and implement member-wise assignment
// from one  N-Node to another via  the overloaded operator=. In  addition, the
// brackets operator is overloaded to  provided  a mechanism to efficiently get
// and set individual  subtree pointers in  a specific node,  thus allowing the
// user to   control  the  orgranization  and  structure   of a tree.  Finally,
// insertion, and removal  methods to allow the  user to control  placement and
// ordering of sub-trees of a node are available.
//

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

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

template <class Type, int nchild> N_Node {
  class N_Node<Type,nchild>;			// Forward reference class
  class N_Tree<N_Node,Type,nchild>;		// Forward reference class
  typedef Boolean (*Type ## _N_Node_Compare)(const Type&, const Type&);
  typedef N_Node<Type,nchild>* N_Node_##Type##_##nchild##_p; // Pointer to class
}

template <class Type, int nchild>
class N_Node<Type,nchild> : public Generic {
private:
  N_Node_##Type##_##nchild##_p sub_trees[nchild]; // Vector of subtree pointers
  Type data;					// Slot to hold data value
  static Type ## _N_Node_Compare compare_s;	// Compare function for class

  void index_error (int);			// Raise exception
  void before_error (int);			// Raise exception
  void after_error (int);			// Raise exception

  friend class N_Tree<N_Node,Type,nchild>;	// Friend class to access data
  friend int Type ## _default_N_Node_compare (const Type&, const Type&);

public:
  N_Node<Type,nchild> ();			// Simple constructor
  N_Node<Type,nchild> (const Type&);		// Constructor with data value
  N_Node<Type,nchild> (N_Node<Type,nchild>&);	// Constructor with reference

  ~N_Node<Type,nchild> ();			// Destructor
  inline void set (const Type&);		// Set node data to value
  inline Type& get ();				// Get node data value
  Boolean is_leaf () CONST;			// TRUE if node has no children
  inline N_Node_##Type##_##nchild##_p& operator[] (int); // Set/Get pointers
  inline int num_subtrees () CONST;		 // Number of subtree slots
  
  inline void set_compare (Type ## _N_Node_Compare = NULL); // Set compare
  inline Boolean operator== (const Type&) CONST;     // Overload operator==
  inline Boolean operator!= (const Type&) CONST;     // Overload operator!=
  inline Boolean operator< (const Type&) CONST;	     // Overload operator<
  inline Boolean operator> (const Type&) CONST;	     // Overload operator>
  inline Boolean operator<= (const Type&) CONST;     // Overload operator<=
  inline Boolean operator>= (const Type&) CONST;     // Overload operator>=

  N_Node<Type,nchild>& operator= (N_Node<Type,nchild>&); // Assignment
  inline N_Node<Type,nchild>& operator= (N_Node<Type,nchild>*); 
  Boolean insert_before (N_Node<Type,nchild>&, int);	 // Insert subtree
  Boolean insert_after (N_Node<Type,nchild>&, int);	 // Insert subtree
};


// default_N_Node_compare -- Default node comparison function utilizing builtin
//                           less than, equal, and greater than operators
// Input:                    Reference to two Type data values
// Output:                   -1, 0, or 1 if less than, equal to, or greater than

template <class Type, int nchild> N_Node {
  int Type ## _default_N_Node_compare (const Type& v1, const Type& v2) {
    if (v1 == v2)				// If data items equal
      return 0;					// Return zero
    if (v1 < v2)				// If this less than data
      return -1;				// Return negative one
    return 1;					// Else return positive one
  }
}


// N_Node -- Simple constructor that allocates enough storage for a vector of
//           pointers to N_Node objects
// Input:    None
// Output:   None

template <class Type, int nchild> 
N_Node<Type,nchild>::N_Node<Type,nchild> () {
  for (int i = 0; i < nchild; i++)		// For each pointer in vector
    this->sub_trees[i] = NULL;			// Insure NULL pointer value
  if (this->compare_s == NULL)			// If no compare function
    this->compare_s = &Type##_default_N_Node_compare; // Default
}


// N_Node -- Simple constructor that allocates enough storage for a vector of
//           pointers to N_Node objects and assigns an initial data value
// Input:    Data slot value
// Output:   None

template <class Type, int nchild> 
N_Node<Type,nchild>::N_Node<Type,nchild> (const Type& value) {
  this->data = value;				// Copy initial data value
  for (int i = 0; i < nchild; i++)		// For each pointer in vector
    this->sub_trees[i] = NULL;			// Insure NULL pointer value
  if (this->compare_s == NULL)			// If no compare function
    this->compare_s = &Type##_default_N_Node_compare; // Default
}


// N_Node -- Constructor that duplicates the values of another N_Node object
// Input:    Reference to N_Node
// Output:   None

template <class Type, int nchild> 
N_Node<Type,nchild>::N_Node<Type,nchild> (N_Node<Type,nchild>& n) {
  this->set(n.get());				// Copy data value
  for (int i = 0; i < nchild; i++)		// For each pointer in vector
    this->sub_trees[i] = n.sub_trees[i];	// Copy value
  this->compare_s = n.compare_s;		// Set compare method
}


// ~N_Node -- Destructor for the N_Node<Type,nchild> class
// Input:     None
// Output:    None

template <class Type, int nchild> 
N_Node<Type,nchild>::~N_Node<Type,nchild> () {
  for (int i = 0; i < nchild; i++)		// For each pointer in vector
    delete this->sub_trees[i];			// Invoke destructor
}

// num_subtrees -- Returns number of slots available for subtrees in node
// Input:          None
// Output:         int length of the allocated array for Nodes

template <class Type, int nchild>
inline int N_Node<Type,nchild>::num_subtrees () CONST {
  return nchild;
}

// set -- Set value of data slot in node
// Input: Reference to data slot value
// Output: None

template <class Type, int nchild> 
inline void N_Node<Type,nchild>::set (const Type& value) {
  this->data = value;				// Set data slot value
}


// get -- Get value of data slot in node
// Input: None
// Output: Reference to data slot value

template <class Type, int nchild> 
inline Type& N_Node<Type,nchild>::get () {
  return (this->data);				// Return data slot value
}


// set_compare -- Specify the comparison function to be used in logical tests
//                of node data values
// Input:         Pointer to a compare function
// Output:        None

template <class Type, int nchild> 
inline void N_Node<Type,nchild>::set_compare (Type ## _N_Node_Compare c) {
  if (c == NULL)
    this->compare_s = &Type##_default_N_Node_compare; // Default equality
  else
    this->compare_s = c;			// Else use one provided
}


// operator== -- Overload the equality operator to use the compare function
// Input:        Constant reference to Type value
// Output:       TRUE/FALSE

template <class Type, int nchild> 
inline Boolean N_Node<Type,nchild>::operator== (const Type& value) CONST {
  return ((((*this->compare_s)(this->data,value)) == 0) ? TRUE : FALSE);
}


// operator!= -- Overload the inequality operator to use the compare function
// Input:        Constant reference to Type value
// Output:       TRUE/FALSE

template <class Type, int nchild> 
inline Boolean N_Node<Type,nchild>::operator!= (const Type& value) CONST {
  return ((((*this->compare_s)(this->data,value)) == 0) ? FALSE : TRUE);
}


// operator< -- Overload the less than operator to use the compare function
// Input:       Constant reference to Type value
// Output:      TRUE/FALSE

template <class Type, int nchild> 
inline Boolean N_Node<Type,nchild>::operator< (const Type& value) CONST {
  return ((((*this->compare_s)(this->data,value)) < 0) ? TRUE : FALSE);
}


// operator> -- Overload the greater than operator to use the compare function
// Input:       Constant reference to Type value
// Output:      TRUE/FALSE

template <class Type, int nchild> 
inline Boolean N_Node<Type,nchild>::operator> (const Type& value) CONST {
  return ((((*this->compare_s)(this->data,value)) > 0) ? TRUE : FALSE);
}


// operator<= -- Overload the less than or equal operator to use the compare
//               function
// Input:        Constant reference to Type value
// Output:       TRUE/FALSE

template <class Type, int nchild> 
inline Boolean N_Node<Type,nchild>::operator<= (const Type& value) CONST {
  return ((((*this->compare_s)(this->data,value)) > 0) ? FALSE : TRUE);
}


// operator>= -- Overload the greater than or equal operator to use the compare
//               function
// Input:        Constant reference to Type value
// Output:       TRUE/FALSE

template <class Type, int nchild> 
inline Boolean N_Node<Type,nchild>::operator>= (const Type& value) CONST {
  return ((((*this->compare_s)(this->data,value)) < 0) ? FALSE : TRUE);
}


// is_leaf -- Determine if node has any children
// Input:     None
// Output:    TRUE if no children, else FALSE

template <class Type, int nchild> 
Boolean N_Node<Type,nchild>::is_leaf () CONST {
  for (int i = 0; i < nchild; i++)
    if (this->sub_trees[i])
      return (FALSE);
  return TRUE;
}


// 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 Type, int nchild> 
inline N_Node_##Type##_##nchild##_p& N_Node<Type,nchild>::operator[] (int index) {
#if ERROR_CHECKING
  if (index >= nchild)				// If index out of range
    this->index_error (index);			// Raise exception
#endif
  return (this->sub_trees[index]);
}


// operator= -- Overload the assignment operator to copy all values from one
//              node object to another. This routine could potentially result
//              in a complete deep copy, since for each valid sub_tree pointer,
//              a new node is allocated and its sub_tree pointers copied.
// Input:       Reference to N_Node
// Output:      Rererence to updated N_Node

template <class Type, int nchild> 
N_Node<Type,nchild>& N_Node<Type,nchild>::operator= (N_Node<Type,nchild>& n) {
  for (int i = 0; i < nchild; i++) {		// For each pointer in vector
    N_Node<Type,nchild>* temp;			// Temporary node pointer
    if (n.sub_trees[i]) {			// If valid sub_tree pointer
      temp = new N_Node<Type,nchild> (*(n.sub_trees[i])); // Duplicate node
      this->sub_trees[i] = temp;		// Point to subtree
    }
    else
      this->sub_trees[i] = NULL;		// Else NULL pointer
  }
  this->set(n.get());				// Copy data value
  return *this;					// Return reference
}


// operator= -- Overload the assignment operator to copy all values from one
//              node object to another. This routine could potentially result
//              in a complete deep copy, since for each valid sub_tree pointer,
//              a new node is allocated and its sub_tree pointers copied.
// Input:       Pointer to N_Node
// Output:      Rererence to updated N_Node

template <class Type, int nchild> 
inline N_Node<Type,nchild>& N_Node<Type,nchild>::operator= (N_Node<Type,nchild>* n) {
  return this->operator=(*n);
}


// insert_before -- Insert sub-tree pointer to child before the specified
//                  zero-relative sub-tree index (numbered from left to right)
// Input:           Pointer to child node, zero-relative index
// Output:          TRUE/FALSE

template <class Type, int nchild> 
Boolean N_Node<Type,nchild>::insert_before (N_Node<Type,nchild>& n, int index) {
#if ERROR_CHECKING
  if (index < 0 || index >= nchild) {		// If index out of range
    this->before_error (index);			// Raise exception
    return FALSE;				// Return failure status
  }
#endif
  for (int i = nchild-1; i > index; i--)	// For each pointer after index
    this->sub_trees[i] = this->sub_trees[i-1];	// Move up one in vector
  this->sub_trees[i] = &n;			// Pointer to new sub-tree
  return TRUE;					// Return success status
}


// insert_after -- Insert sub-tree pointer to child after the specified
//                 zero-relative sub-tree index (numbered from left to right)
// Input:          Pointer to child node, zero-relative index
// Output:         TRUE/FALSE

template <class Type, int nchild> 
Boolean N_Node<Type,nchild>::insert_after (N_Node<Type,nchild>& n, int index) {
#if ERROR_CHECKING
  if (index < 0 || index >= nchild) {		// If index out of range
    this->after_error (index);			// Raise exception
    return FALSE;				// Return failure status
  }
#endif
  for (int i = nchild-1; i > index+1; i--) 	// For each pointer after index
    this->sub_trees[i] = this->sub_trees[i-1];	// Move up one in vector
  this->sub_trees[i] = &n;			// Pointer to new sub-tree
  return TRUE;					// Return success status
}


// index_error -- Raise exception for N_Node::operator[]
// Input:         Invalid index
// Output:        None

template <class Type, int nchild> 
void N_Node<Type,nchild>::index_error (int n) {
  RAISE (Error, SYM(N_Node), SYM(Out_Of_Range),
	 "N_Node<%s,%d>::operator[]: Index %d out of range", #Type,
	 nchild, n);
}


// before_error -- Raise exception for N_Node::insert_before()
// Input:          Invalid index
// Output:         None

template <class Type, int nchild> 
void N_Node<Type,nchild>::before_error (int n) {
  RAISE (Error, SYM(N_Node), SYM(Out_Of_Range),
	 "N_Node<%s,%d>::insert_before(): Index %d out of range", #Type,
	 nchild, n);
}


// after_error -- Raise exception for N_Node::insert_after()
// Input:         Invalid index
// Output:        None

template <class Type, int nchild> 
void N_Node<Type,nchild>::after_error (int n) {
  RAISE (Error, SYM(N_Node), SYM(Out_Of_Range),
	"N_Node<%s,%d>::insert_after: Index %d out of range", #Type,
	 nchild, n);
}

#endif						// End N_NODEH #if


