//
// 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 and implementation
// Updated: MBN 09/15/89 -- Added conditional exception handling
// Updated: DKM 11/05/89 -- Replaced cache traversal with stack traversal
//                          Also added support for AVL balancing
// Updated: LGO 12/04/89 -- operator<< not inline
// Updated: MBN 12/21/89 -- Added optional argument to set_compare method
// Updated: MBN 02/20/90 -- Cut operators <, >, <=, >=; fixed operators ==, !=
// Updated: MJF 06/30/90 -- Added base class name to constructor initializer
//
// The Binary_Tree<Type> class is publicly derived  from the  Binary_Tree class
// and  implements simple, dynamic, sorted sequences.   Users requiring  a data
// structure for  unsorted  sequences whose structure  and organization is more
// under the control  of the programmer  are refered  to the N_Tree class.  The
// Binary_Tree<Type>  class  is  a   friend   of the  Binary Node  class,  also
// parameterized over the  same Type.  There is no  attempt made  to balance or
// prune the tree.  Nodes  are added to  a particular sub-tree at the direction
// of  the colating function.  As a  result, a tree parameterized  for integers
// and that  uses the default integer  comparison operators whose  elements are
// added in increasing order would result  in a lopsided  tree.  Likewise after
// many items have been added and removed.
//
// The Binary_Tree<Type> class supports  the concept of  a current position  as
// the tree is  traversed via  next, prev,  and find.   method that changes the
// tree structure invalidates the current position state
//
// The  Binary_Tree<Type>  class supports   the concept of  a current position.
// Once  the  current position is  initialized, the first  call  to advance the
// current position causes an internal dynamic cache of pointers to nodes to be
// created.  This cache is created by  an inorder traversal  of the tree. Other
// current  position  advance and  decrement 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  no arguments and simply
// allocates initial storage for a  Binary_Tree<Type> object.  The second takes
// a reference to an existing Binary_Tree<Type> object  and duplicates its size
// and contents.  The Binary_Tree<Type> 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.
//
// Methods are available to put, remove, and find a node in a tree.  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.  In addition,
// all nodes can  be  removed from the  tree with  the clear method.  A balance
// method is provided to allow  the user to shake the  tree at some appropriate
// time in  order  to balance  the  left and  right  sub-trees.  This  might be
// particularly useful in the case of static binary  trees, where the structure
// becomes fixed and the impetus for fast, efficient searches is high. Finally,
// the  equality, inequality,  less   than,  and greater  than    operators are
// overloaded to provide node comparison functionality.
//

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

#ifndef BASE_BINARY_TREEH			// If no definition for class
#include <cool/Base_BT.h>			// Include definition file
#endif

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

template <class Type> Binary_Tree {
  #define DECLARE_Binary_Tree_##Type
  typedef int (*Type##_Tree_Compare)(const Type&, const Type&);
  DECLARE Binary_Node<Type>;
}


template <class Type>
class Binary_Tree<Type> : public Binary_Tree {
private:
  Type##_Tree_Compare compare;			// Compare function
  Binary_Node<Type>* baltree (long);		// Build balanced subtree
  Binary_Node<Type>* copy_tree (Binary_Node<Type>*);
  friend void Type##_print_tree (const Binary_Node<Type>*, ostream&);
  friend int Type##_default_node_compare (const Type&, const Type&);

protected:
  Boolean put_internal    (const Type&, Boolean avl=NULL);// adds a node
  Boolean remove_internal (const Type&, Boolean avl=NULL);// removes a node

public:
  Binary_Tree<Type> ();				// Simple constructor
  Binary_Tree<Type> (const Binary_Tree<Type>&);	// Constructor with reference
  ~Binary_Tree<Type> ();			// Destructor

  Boolean find (const Type&);			// Find value in tree

  friend ostream& operator<< (ostream&, const Binary_Tree<Type>&);
  friend ostream& operator<< (ostream&, const Binary_Tree<Type>*);

  Type& value ();				// Return value at current pos
  Binary_Node<Type>* get_root () CONST;		// Return root node
  Binary_Node<Type>* node ();			// Return current node
  inline Boolean remove ();			// Remove node at current pos
  inline Boolean put (const Type&);		// Add value to tree 
  inline Boolean remove (const Type&);		// Remove value from tree
  Binary_Tree<Type>& operator= (Binary_Tree<Type>&); // Assignment operator
  void balance ();				// Balance the tree

  inline void set_compare (Type##_Tree_Compare = NULL); // Set compare function
  Boolean operator== (Binary_Tree<Type>&);		// Overload equality
  inline Boolean operator!= (Binary_Tree<Type>&);	// Overload not equal
};

template <class Type> Binary_Tree {
ONCE_ONLY(IMPLEMENT_Binary_Tree_##Type) {
  IMPLEMENT Binary_Node<Type>;
}}


// default_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> Binary_Tree {
  int Type##_default_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
  }
}

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

template <class Type>
Binary_Tree<Type>::Binary_Tree<Type> () {
  this->compare = &Type##_default_node_compare; // Pointer to compare function
}



// Binary_Tree -- Constructor to initialize a Binary_Tree object to have the
//                same size and values as some other Binary_Tree object
// Input:         Reference to Binary_Tree
// Output:        None

template <class Type>
Binary_Tree<Type>::Binary_Tree<Type> (const Binary_Tree<Type>& b)
#ifdef __cplusplus
 : Binary_Tree(b)
#else 
 : (b)
#endif
{
  this->compare = b.compare;			// Pointer to compare function
  this->number_nodes = b.number_nodes;
  this->root = this->copy_tree ((Binary_Node<Type>*)b.root);
  this->current_position () = b.current_position ();
}



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

template <class Type>
Binary_Tree<Type>::~Binary_Tree<Type> () {
  delete (Binary_Node<Type>*)this->root;
}

// copy_tree -- Copies this node and it's subtrees

template <class Type>
Binary_Node<Type>* Binary_Tree<Type>::copy_tree (Binary_Node<Type> *n) {
  if (n == NULL)				
    return n;
  Binary_Node<Type> *new_n = new Binary_Node<Type>; // Allocate a new node
  new_n->set_ltree (copy_tree (n->get_ltree() ));   // Copy the left tree
  new_n->set_rtree (copy_tree (n->get_rtree() ));   // and the right tree
  new_n->set (n->get());			    // copy the value
  new_n->set_avl_balance (n->get_avl_balance());    // copy avl balance
  return new_n;					    // Return copied node.
}


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

template <class Type>
Type& Binary_Tree<Type>::value () {
#if ERROR_CHECKING
 if (this->state.stack.is_empty() ) 	        // If invalid current position
   this->value_error (#Type);			// Raise exception
#endif
  Stack_Entry stack_entry = this->state.stack.top(); // get top stack
  return (((Binary_Node<Type>*)stack_entry.get_first())->get()); // Return value
}

// get_root -- return node that roots this tree
// Input:      None
// Output:     Pointer to Binary_Node of type Type.

template <class Type>
Binary_Node<Type>* Binary_Tree<Type>::get_root () CONST {
  return (Binary_Node<Type>*)Binary_Tree::get_root ();
}

// node -- return node pointed to by the current position
// Input:      None
// Output:     Pointer to Binary_Node of type Type.

template <class Type>
Binary_Node<Type>* Binary_Tree<Type>::node () {
  return (Binary_Node<Type>*)Binary_Tree::node ();
}

// put -- Add a value to the sorted binary tree if it is not already there
// Input: Reference to value to add to tree
// Output: TRUE if item added, FALSE otherwise

template <class Type>
inline Boolean Binary_Tree<Type>::put (const Type& value) {
  return this->put_internal (value);
}

template <class Type>
Boolean Binary_Tree<Type>::put_internal
                            (const Type& value, Boolean avl) {

  if (this->root == NULL) {			// If this is the first node
    this->root = new Binary_Node<Type> (value);	// Add new node and value
    this->number_nodes++;			// Update node count
    return TRUE;				// Indicate success
  }
  Binary_Node<Type>* ptr = (Binary_Node<Type>*)this->root; // Start at root
  BT_Stack stack;				// Stack for AVL balancing
  while (TRUE) {				// Until we find location
    int pos = (*this->compare)(ptr->get(),value); // Compare data values
    if (pos == 0) 				// If data value exists in tree
      return FALSE;				//    indicate node not added
    else if (pos > 0) {				// Data down left subtree?
      if (avl)
	stack.push (Stack_Entry ((Binary_Node*)ptr,LEFT)); // Push parent
      if (ptr->get_ltree() == NULL) {		// If at leaf node
	ptr->set_ltree ((new Binary_Node<Type> (value))); // Add node to ltree
	this->number_nodes++;			// Update node count
	break;					// Break out of loop and exit
      }
      else {
	ptr = ptr->get_ltree();			// Else point to left subtree
	continue;				// And continue search
      }
    }
    else {					// Else down right subtree
      if (avl)
	stack.push (Stack_Entry ((Binary_Node*)ptr,RIGHT)); // Push on stack
      if (ptr->get_rtree() == NULL) {		// If at leaf node
	ptr->set_rtree ((new Binary_Node<Type> (value))); // Add node to rtree
	this->number_nodes++;		        // Update node count
	break;					// Break out of loop and exit
      }
      else {
	ptr = ptr->get_rtree();			// Grab right subtree dir
	continue;				// And continue to search;
      }
    }
  }
  if (avl)					// Balance it if an AVL tree
    Binary_Tree::avl_put_balance (stack);

  this->reset();				// Invalidate current position
  return TRUE;					// Return success
}


// remove -- Remove a value from the sorted binary tree. Deletion of a node
//           that has both left and right subtrees is done by descending down 
//           the rightmost branch of the left subtree of the element to be
//           deleted until a leaf is encountered, at which point the change is
//           propagated back.
// Input:    Reference to value to remove
// Output:   TRUE if item removed, FALSE otherwise

// For a Binary Tree, call remove_internal without the avl flag
template <class Type>
inline Boolean Binary_Tree<Type>::remove (const Type& value) {
  return this->remove_internal(value);
}


// remove -- Remove node at current position in the tree
// Input:    None
// Output:   Value of node removed from tree

template <class Type>
inline Boolean Binary_Tree<Type>::remove () {
  return this->remove_internal (this->value());
}


// remove_internal -- does the actual work of removing a value from bin tree
//                    for avl trees, will make call to check avl balance
// Input:          -- value to remove + optional Boolean for AVL trees
// output          -- TRUE if item sucessfully removed. FALSE otherwise.
template <class Type>
Boolean Binary_Tree<Type>::remove_internal
                           (const Type& value, Boolean avl) {
  if (this->root == NULL)			// If there are no nodes
    return FALSE;				// indicate failure
  BT_Stack stack1;				// Allocate traversal stack
  Left_Right route = NONE;			// Last subtree taken
  Binary_Node<Type> *ptr = (Binary_Node<Type>*)this->root; // Start at root
  Binary_Node<Type> *parent_ptr = NULL;		// Save pointer to parent
  Binary_Node<Type> *ptr1, *ptr2;		// temp ptrs to nodes
  while (TRUE) {				// Until we find location
    int pos = (*this->compare)(ptr->get(),value); // Compare data values
    if (pos == 0) {				// If node to delete is found
      if (ptr->get_rtree() == NULL) {		// If no right subtree
	if (route == LEFT)			// If child of parent's ltree
	  parent_ptr->set_ltree(ptr->get_ltree()); // Set to left subtree
	else if (route == RIGHT)
	  parent_ptr->set_rtree(ptr->get_ltree()); // Set to right subtree
	else this->root = ptr->get_ltree();	// Make ltree the new root
      }
      else if (ptr->get_ltree() == NULL) {	// Else if no left subtree
	if (route == LEFT)			// If child of parent ltree
	  parent_ptr->set_ltree(ptr->get_rtree()); // Set to left subtree
	else if (route == RIGHT)
	  parent_ptr->set_rtree(ptr->get_rtree()); // Set to right subtree
	else this->root = ptr->get_rtree();	   //    rtree is the new root.
      }
  
      // Node(a) with value to be deleted has both a left and right subtree.
      // We need to look for the node(b) with the next smallest value and
      // copy it's value into node(a). Then adjust the parent of node(b) 
      // to point at node(b)'s left subtree (right subtree will always be 
      // NULL).  ptr is left pointing at node(b) so it is the
      // one which is eventually deleted.
      else {
	if (avl) 				// for avl trees
	  stack1.push (Stack_Entry((Binary_Node*)ptr,LEFT)); // push on stack
        ptr1 = ptr;				// Save node with matched data
	ptr2 = ptr1;				// last parent initially ptr
	ptr = ptr->get_ltree();			// Start with node's ltree
	while (ptr->get_rtree() != NULL) {	// Follow rtree til null rtree
	  if (avl) 				// for avl trees
	    stack1.push (Stack_Entry((Binary_Node*)ptr,RIGHT)); // push on stack
	  ptr2 = ptr;				// save last parent
	  ptr = ptr->get_rtree();		// get right subtree
	}
	ptr1->set (ptr->get());			// Move next smallest value up
	if (ptr1 == ptr2) 			// ltree had no rtrees
	  ptr2->set_ltree (ptr->get_ltree());	// Del node is parents ltree
	else 
	  ptr2->set_rtree (ptr->get_ltree());	// Del node is parents rtree
      }

      // DELETE the node ptr points at
      this->number_nodes--;			// Decrement node count
      if (this->number_nodes == 0) 		// If no more nodes in tree
	this->root = NULL;			// Nullify root pointer
      ptr->set_ltree (NULL);			// Nullify left subtree pointer
      ptr->set_rtree (NULL);			// Nullify right subtree pointer
      delete ptr;				// Deallocate memory
      this->reset();				// Invalidate current position<
      break;					// exit loop
    }
    else if (pos > 0) {				// Data down left subtree?
      if (ptr->get_ltree() == NULL) {		// If at leaf node
	return FALSE;				// Indicate node not found
      }
      else {
	if (avl) 				// if avl tree
	  stack1.push (Stack_Entry((Binary_Node*)ptr,LEFT)); // push on stack1
	parent_ptr = ptr;			// Save parent pointer
	route = LEFT;				// Save route taken
	ptr = ptr->get_ltree();			// point to left subtree
	continue;				// And continue to search;
      }
    }
    else {					// Else down right subtree
      if (ptr->get_rtree() == NULL) 		// If at leaf node
	return FALSE;				// Indicate success
      else {
	if (avl) 				// If an avl tree
	  stack1.push (Stack_Entry((Binary_Node*)ptr,RIGHT)); // push on stack
	parent_ptr = ptr;			// Save parent pointer
	route = RIGHT;				// Save route taken
	ptr = ptr->get_rtree();			// Point to right subtree
	continue;				// And continue to search;
      }
    }
  }
  // The node has been removed.  Now every node in the path of the deleted
  // node must be checked for possible re-balancing if this is an AVL tree
  if (avl)
    Binary_Tree::avl_remove_balance (stack1);
  return TRUE;
}



      

// find -- Find a value in the sorted binary tree 
// Input:  Reference to value to find
// Output: Current position updated and TRUE if item found, FALSE otherwise

template <class Type>
Boolean Binary_Tree<Type>::find (const Type& value) {
  for (this->reset (); this->next (); )  	// For each node in the tree
    if ((*this->compare)(this->value(), value) == 0) // If value found in cache
      return TRUE;				// Indicate item found
  return FALSE;					// Else indicate failure
}


// operator<< -- Output a binary tree by printing it sideways where the root is
//               printed at the left margin. To obtain the normal orientation,
//               rotate the output 90 degrees clockwise
// Input:        Reference to output stream, reference to Binary_Tree<Type>
// Output:       Reference to output stream

template <class Type> Binary_Tree {
ostream& operator<< (ostream& os, const Binary_Tree<Type>& b) {
  Type##_print_tree((Binary_Node<Type>*)b.get_root(),os); // Print tree 
  return os;					 // Return output stream
}
}


template <class Type> Binary_Tree {
void Type##_print_tree (const Binary_Node<Type>* b, ostream& os) {
  static indent = 0;				// Temporary variables
  if (b != NULL) {				// If not at bottom of tree
    indent += 1;				// Indent node
    Type##_print_tree (b->get_rtree(),os);	// Output the right subtree
    for (int i = 1; i < indent; i++)		// For each level of tree
      os << "     ";				// Indent some number of spaces
      os << b->get() << "\n";			// Output node data value
    Type##_print_tree (b->get_ltree(),os);	// Output the left subtree
    indent -= 1;				// Decrement indent level
  }
}}

// operator<< -- Output a binary tree by printing it sideways where the root is
//               printed at the left margin. To obtain the normal orientation,
//               rotate the output 90 degrees clockwise
// Input:        Reference to output stream, reference to Binary_Tree<Type>
// Output:       Reference to output stream

template <class Type> Binary_Tree {
ostream& operator<< (ostream& os, const Binary_Tree<Type>* b) {
  Type##_print_tree((Binary_Node<Type>*)b->get_root(),os); // Print tree
  return os;					  // Return output stream
}
}


// operator= -- Overload the assignment operator to copy a Binary_Tree object
//              to another Binary Tree object
// Input:       Reference to Binary_Tree
// Output:      Reference to Binary_Tree

template <class Type>
Binary_Tree<Type>& Binary_Tree<Type>::operator= (Binary_Tree<Type>& b) {
  delete (Binary_Node<Type>*)this->root;	// Delete old tree nodes
  this->compare = b.compare;			// Pointer to compare function
  this->root = b.root;				// Nullify root pointer
  this->number_nodes = b.number_nodes;
  this->current_position () = b.current_position ();
  this->root = this->copy_tree ((Binary_Node<Type>*)b.root);
  return *this;					// Return tree reference
}


// balance -- Build a perfectly balanced binary tree from the existing tree
//            and delete old tree and storage. This uses the private recursive
//            method baltree() to construct the left and then right subtrees.
// Input:     None
// Output:    None

template <class Type>
void Binary_Tree<Type>::balance () {
  Binary_Node<Type>* p;				// Temporary node pointer
  if (this->number_nodes != 0) {		// If there are nodes in tree
    this->reset ();				// Recalculate node cache
    p = this->baltree (this->number_nodes);	// Generate balanced tree
    delete (Binary_Node<Type>*)this->root;	// Delete old tree
    this->root = p;				// Point to new balanced tree
  }
}

template <class Type>
Binary_Node<Type>* Binary_Tree<Type>::baltree (long n) {
  long nleft, nright;				// Number nodes in ltree,rtree
  Binary_Node<Type>* p;				// Temporary pointer
  if (n == 0)					// If no more nodes left
    return NULL;				// Return NULL pointer
  nleft = n >> 1;				// Node count for left subtree
  nright = n - nleft - 1;			// Node count for right subtree
  p = new Binary_Node<Type> ();			// Allocate new node
  p->set_ltree(this->baltree (nleft));		// Create left subtree
  p->set ((this->next(), this->value()));	// Set node value
  p->set_rtree(this->baltree (nright));		// Create right subtree
  return p;					// Return pointer to subtree
}


// 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>
inline void Binary_Tree<Type>::set_compare (Type##_Tree_Compare c) {
  if (c)					// If compare function given
    this->compare = c;				// Set pointer
  else
    this->compare = &Type##_default_node_compare; // Pointer to default compare
}


// operator== -- Compare binary trees for same values and structure
// Input:        Constant reference to another binary tree
// Output:       TRUE/FALSE

template <class Type>
Boolean Binary_Tree<Type>::operator== (Binary_Tree<Type>& t) {
  Boolean t1, t2;
  for (this->reset(), t.reset();		// Start at first node of each
       (t1 = this->next()) && (t2 = t.next());) // For each node in tree
    if ((*this->compare)(this->value(), t.value()) != 0) // If different value
      return FALSE;					 // Trees not equal
  if (t1 == FALSE)					 // If no more nodes 
    if (t.next () == FALSE)				 // in either tree
      return TRUE;					 // Trees are equal
    else
      return FALSE;
  return FALSE;						 // Else not equal
}


// operator!= -- Compare binary trees for different values and/or structure
// Input:        Constant reference to another binary tree
// Output:       TRUE/FALSE

template <class Type>
inline Boolean Binary_Tree<Type>::operator!=(Binary_Tree<Type>& t) {
  return (! (*this == t));
}

#endif						// End BINARY_TREEH #if


