//
// 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 06/28/89 -- Initial design
// Updated: MBN 07/19/89 -- Derived from Base_Binary_Node class
// Updated: DKM 11/05/89 -- Added accessors to avl_balance
// Updated: MJF 06/30/90 -- Added base class name to constructor initializer
//
// The Binary_Node<Type> class implements parameterized nodes for binary trees.
// This class  is privately  derived from the  Binary_Node class  that contains
// left and right subtree  pointers.   The Binary_Node<Type> class adds  a data
// slot of  the required type  in the private section.    The Binary_Node<Type>
// class is  intended for the sole  use of  the  Binary_Tree<Type>  class.  All
// constructors and protected and the Binary_Tree<Type> class is  declared as a
// friend class.
//
// There are three protected constructors  for the Binary_Node<Type>class.  The
// first takes no arguments  and initializes the two subtree  pointers  to NULL
// via the Binary_Node constructor.  The second takes an  argument of type Type
// and initializes the data slot to that value.  The third takes a reference to
// another Binary_Node<Type> 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 Binary_Node<Type> to another via the overloaded operator=.
//

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

#ifndef BASE_BINARY_NODEH			// If no definition for class
#include <cool/Base_BN.h>				// Include useful defintions
#endif	

template <class Type> Binary_Node {
  class Binary_Tree<Type>;			// Forward reference class
}

template <class Type>
class Binary_Node<Type> : public Binary_Node {
private:
  friend class Binary_Tree<Type>;		// Binary_Tree class is friend
  Type data;					// Slot to hold data value

protected:
  inline int get_avl_balance () CONST;		// Return avl balance
  inline void set_avl_balance (int);		// Set avl balance
public:  
  Binary_Node<Type> ();				// Simple constructor
  Binary_Node<Type> (const Type&);		// Constructor with data value
  Binary_Node<Type> (const Binary_Node<Type>&);	// Constructor with reference
  ~Binary_Node<Type> ();			// Destructor
  inline void set (Type&);		       // Set node data to value
  inline Type& get () CONST;		       // Get node data value
  inline void set_ltree (Binary_Node<Type>*);  // Accessor to set ltree pointer
  inline Binary_Node<Type>* get_ltree () CONST;// Accessor to get ltree pointer
  inline void set_rtree (Binary_Node<Type>*);  // Accessor to set rtree pointer
  inline Binary_Node<Type>* get_rtree () CONST;// Accessor to get rtree pointer
  inline Boolean is_leaf () CONST;	       // TRUE if node has no children
  
  Binary_Node<Type>& operator= (const Binary_Node<Type>&); // Assignment 
};

// Binary_Node -- Simple constructor to initialize a node object
// Input:         None
// Output:        None

template <class Type>
Binary_Node<Type>::Binary_Node<Type> () {
}


// Binary_Node -- Constructor to initialize a node object and assign a value
//                to the data slot
// Input:         Data slot value
// Output:        None

template <class Type>
Binary_Node<Type>::Binary_Node<Type> (const Type& value) {
  this->data = value;				// Assign data value
}

// Binary_Node -- Constructor to assign values to the subtree pointers and a 
//                value to the data slot
// Input:         Reference to Binary_Node object
// Output:        None

template <class Type>
Binary_Node<Type>::Binary_Node<Type> (const Binary_Node<Type>& bn)
#ifdef __cplusplus
 : Binary_Node(bn)
#else
 : (bn)
#endif
{
  this->data = bn.data;				// Assign data value
}


// ~Binary_Node -- Destructor for the Binary_Node class
// Input:          None
// Output:         None

template <class Type>
Binary_Node<Type>::~Binary_Node<Type> () {
}

// get_avl_balance -- Return the value of the avl_balance slot for node
// Input: None
// Output: int value of avl balance.  Must be -1, 0, or 1.

template <class Type>
inline int Binary_Node<Type>::get_avl_balance () CONST {
  return this->avl_balance;
}

// set_avl_balance -- Set the value of the avl_balance slot for node
// Input: Int of -1 0 or 1
// Output: Void

template <class Type>
inline void Binary_Node<Type>::set_avl_balance (int val) {
  this->avl_balance = val;
}

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

template <class Type>
inline void Binary_Node<Type>::set (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>
inline Type& Binary_Node<Type>::get () CONST {
  return (this->data);				// Return data slot value
}


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

template <class Type>
inline Boolean Binary_Node<Type>::is_leaf () CONST {
  return (Binary_Node::is_leaf ());
}


// set_ltree -- Accessor to set left subtree pointer in base class
// Input:       Binary_Node pointer
// Output:      None

template <class Type>
inline void Binary_Node<Type>::set_ltree (Binary_Node<Type>* bn) {
  this->ltree = (Binary_Node<Type>*)bn;
}


// set_rtree -- Accessor to set right subtree pointer in base class
// Input:       Binary_Node pointer
// Output:      None

template <class Type>
inline void Binary_Node<Type>::set_rtree (Binary_Node<Type>* bn) {
  this->rtree = (Binary_Node<Type>*)bn;
}


// get_ltree -- Accessor to get left subtree pointer in base class
// Input:       None
// Output:      Binary_Node pointer

template <class Type>
inline Binary_Node<Type>* Binary_Node<Type>::get_ltree () CONST {
  return (Binary_Node<Type>*)this->ltree;
}


// get_rtree -- Accessor to get right subtree pointer in base class
// Input:       None
// Output:      Binary_Node pointer

template <class Type>
inline Binary_Node<Type>* Binary_Node<Type>::get_rtree () CONST {
  return (Binary_Node<Type>*)this->rtree;
}


// operator= -- Overload assignment for Binary_Node to assign the subtree
//              pointers and a value to the data slot
// Input:       Reference to Binary_Node object
// Output:      Reference to Binary_Node object

template <class Type>
Binary_Node<Type>& Binary_Node<Type>::operator= (const Binary_Node<Type>& bn) {
  this->data = bn.data;				// Assign data value
  Binary_Node::operator= (bn);			// Assign subtrees in base node
  return *this;					// Return updated object
}

#endif						// End BINARY_NODEH #if
