//
// 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/19/89 -- Initial design and implementation
// Updated: MBN 09/19/89 -- Added conditional exception handling
// Updated: MJF 03/12/90 -- Added group names to RAISE
//
// The Binary_Tree class implements the type-generic  structural methods of the
// parameterized Binary_Tree<Type>  class  and is  a friend of  the Binary Node
// class.  The  Binary_Tree   class  is  intended for  the    sole  use  of the
// parameterized  Binary_Tree<Type>    class.    The    Binary_Tree<Type> class
// implements simple,  dynamic,   sorted  sequences.  Users who  require 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.
//

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

IMPLEMENT Pair<Binary_Node*,int>
IMPLEMENT Stack<Pair<Binary_Node*,int>>;


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

Binary_Tree::~Binary_Tree () {}


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

Binary_Tree::Binary_Tree () {
  this->root = NULL;				// Initialize root pointer
  this->number_nodes = 0;			// Initialize node count
  this->state.forward = TRUE;			// Assume Forward direction;
}


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

Binary_Tree::Binary_Tree (const Binary_Tree& b) {
  IGNORE (b);
  this->root = NULL;				// Initialize root pointer
  number_nodes = 0;				// Initialize node count
  state.forward = TRUE;			// Assume forward direction
}


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

void Binary_Tree::clear () {
  delete root;
  root = NULL;
  number_nodes = 0;
  reset();
}

  

// calc_depth (recurse thru the Tree and return zero-based depth)
//   if update_bal is not NULL, then the avl balance for this node is
//   updated.  This avl update should be called after balancing the tree
//   as an AVL tree cannot have it's balance othere than -1, 0 1.

long Binary_Tree::calc_depth
                (Binary_Node* node, long depth, Boolean update_bal) {
  if (node == NULL) {				// Null nodes don't count
    if (depth > 0)		                // If not the root
      --depth;					//   depth bumped 1 too many
    return depth;
  }
  depth++;					// Do left and right subtrees
  long ldepth = this->calc_depth (node->ltree, depth, update_bal);
  long rdepth = this->calc_depth (node->rtree, depth, update_bal);

  // It is an error if rdepth - ldepth is other than -1 0 or 1.
  if (update_bal)		                // If we need to update balance
    node->avl_balance =(int)(rdepth - ldepth);	// it's right tree depth - left

  if (ldepth > rdepth)				// Return count of deepest tree
    return ldepth;
  else
    return rdepth;
}

// current-node -- Returns node at the current position

Binary_Node* Binary_Tree::node () {
  if (this->state.stack.is_empty())
    return NULL;
  else {
    Stack_Entry se = this->state.stack.top();
    return (Binary_Node*)se.get_first();
  }
}

// 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.  Binary trees only use inorder and inorder_reverse
// so the code for dealing with the other traversal types is commented out
// (almost identical copy of this is in N_Tree)

Boolean Binary_Tree::next_internal (Traversal_Type ttype) {
  Binary_Node *node, *ptr1;
  Binary_Node *last_node = NULL;
  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 (Stack_Entry (node,index));
    state.forward = forward;
    
  }
  else {					// Stack has some entries, so
    stack_entry = state.stack.top();		//  get top entry from stack
    node = (Binary_Node*)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->subtree(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 (Stack_Entry (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 = (Binary_Node*)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->subtree(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 (Stack_Entry (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 = (Binary_Node*)stack_entry.get_first(); //  load up node
	  index = (int)stack_entry.get_second();	//  and subtree index
	}
      }
    }
  }
}




  // maintain the balance of an AVL tree after a put.  The balance of
  // depths between the right subtree and left subtree are maintained
  // for each node. When this balance differs by more than 1, a single
  // or double rotation is done depending on the constellation to put
  // the balance of that node back to zero.  A single or double
  // rotation on the parent of the inserted node does the job.  Nodes
  // above the parent are not affected.

void Binary_Tree::avl_put_balance (BT_Stack &stack) {
  Binary_Node *p1, *p2, *raised_node=NULL;	// alloc tmp ptrs to Node
  Binary_Node *ptr;
  Left_Right route=NONE;
  Boolean more_todo = TRUE;
  while (stack.length() > 0) {			// Loop thru nodes on stack
    Stack_Entry stack_entry = stack.pop();	// Pop next stack_entry
    ptr = (Binary_Node*)stack_entry.get_first(); // Get Node 
    route = (Left_Right)stack_entry.get_second();// Get the subtree
    if (raised_node != NULL) {			// A node was rotated up
      if (route == LEFT)			// For a left route
	ptr->ltree = raised_node;		//  change ltree to raised node
      else if (route == RIGHT)			// or for right route
	ptr->rtree = raised_node;		//  change rtree to raised node
      raised_node = NULL;
    }
    if (more_todo == FALSE)			// Exit loop when all balanced
      break;
    
    if (route == LEFT) {			// Node inserted as an LTREE
      switch (ptr->avl_balance) {		// Depending on node's balance
      case 1:
	ptr->avl_balance = 0;			// Set node as balanced
	more_todo = FALSE;
	break;
      case 0:
	ptr->avl_balance = -1;			// Set node as 1 heavy on left
	break;
      case -1:					// Will need to rotate
	more_todo = FALSE;
	p1 = ptr->ltree;			
	if (p1->avl_balance == -1) {		// Single Right Rotation
	  ptr->ltree = p1->rtree;
	  p1->rtree = ptr;
	  p1->avl_balance = 0;
	  ptr->avl_balance = 0;
	  raised_node = p1;			// This node bubbled up
	}					// End Single right rotation
	else {					// Double Right Rotation
	  p2 = p1->rtree;
	  p1->rtree = p2->ltree;
	  p2->ltree = p1;
	  ptr->ltree = p2->rtree;
	  p2->rtree = ptr;
	  if (p2->avl_balance == -1)		// update balance for ptr
	    ptr->avl_balance = 1;
	  else
	    ptr->avl_balance = 0;
	  if (p2->avl_balance == 1)		// update balance for p1
	    p1->avl_balance = -1;
	  else
	    p1->avl_balance = 0;
	  p2->avl_balance = 0;			// update balance for p2
	  raised_node = p2;			// This node now moved up
	  break;
	}					// End Left Right Rotation
      }						// End switch
    }						// End LTREE path
    
    else {					// Node inserted as an RTREE
      switch (ptr->avl_balance) {
      case -1:
	ptr->avl_balance = 0;			// Node is now balanced
	more_todo = FALSE;			// Tree is now balanced
	break;
      case 0:
	ptr->avl_balance = 1;			// Node is 1 heavy on right
	break;
      case 1:					// Will need to rotate
	more_todo = FALSE;
	p1 = ptr->rtree;
	if (p1->avl_balance == 1) {		// Single Left Rotation
	  ptr->rtree = p1->ltree;
	  p1->ltree = ptr;
	  p1->avl_balance = 0;
	  ptr->avl_balance = 0;
	  raised_node = p1;
	}					// End Single Left Rotation
	else {					// Right/Left Rotation
	  p2 = p1->ltree;
	  p1->ltree = p2->rtree;
	  p2->rtree = p1;
	  ptr->rtree = p2->ltree;
	  p2->ltree = ptr;
	  if (p2->avl_balance == 1)		// Update balance for ptr
	    ptr->avl_balance = -1;
	  else
	    ptr->avl_balance = 0;
	  if (p2->avl_balance == -1)		// Update balance for p1
	    p1->avl_balance = 1;
	  else
	    p1->avl_balance = 0;
	  p2->avl_balance = 0;			// update balance for p2
	  raised_node = p2;			// This node now moved up
	  break;
	}					// End Right/Left Rotation
      }						// End switch
    }						// End RTREE path
  }

  if (raised_node != NULL) {			// When a node gets raised
    this->root = raised_node;			//  raised_node to be root
  }
}

// Balances the nodes in the path of a removed node for an AVL Binary Tree
// The parent nodes and index to their subtrees are maintained in a Stack of 
// Stack_entrys
 
void Binary_Tree::avl_remove_balance (BT_Stack &stack) {
  Binary_Node *p, *p1, *p2, *raised_node=NULL;	// Temporary pointers to nodes
  Boolean more_todo=TRUE;			// When more_todo is FALSE, done.
  Left_Right route=NONE;
  while (stack.length() > 0) {			// Loop thru nodes on stack
    Stack_Entry stack_entry = stack.pop();	// Get next stack_entry
    p = (Binary_Node*)stack_entry.get_first();	// Get Node 
    route = (Left_Right)stack_entry.get_second();// Get the subtree

    // UPDATE PARENT TO POINT AT RAISED NODE FROM PREVIOUS ITERATION
    if (raised_node != NULL) {			// If there is a raised node
      if (route == LEFT)			//    See what side was changed
	  p->ltree = raised_node;		//    Update ltree
      else
	p->rtree = raised_node;			//    or update rtree
      raised_node = NULL;			//    raised_node taken care of.
    }

    if (more_todo == FALSE)			// Tree is balanced
      break;

    // BALANCE LEFT SUBTREE OF NODE P.  Note that this is VERY similar 
    // to the code below to balance the right side.  Changes here are likely
    // necessary below also.

    if (route == LEFT) {
      switch (p->avl_balance) {
      case -1:					// Set balance to 0. 
	p->avl_balance = 0;			//   balance parent node
	break;
      case 0:					// Set balance to 1.  Tree is 
	p->avl_balance = 1;			//   all balanced.
	more_todo = FALSE;
	break;
      case 1:					// Need to rotate
	p1 = p->rtree;
	if (p1->avl_balance >= 0) {		
	  p->rtree = p1->ltree;			// Single left rotate
	  p1->ltree = p;
	  raised_node = p1;
	  if (p1->avl_balance == 0) {		// Update p and p1 balance
	    p->avl_balance = 1;
	    p1->avl_balance = -1;
	    more_todo = FALSE;
	  }
	  else {
	    p->avl_balance = 0;
	    p1->avl_balance = 0;
	  }
	}
	else {					// Double right left rotate
	  p2 = p1->ltree;
	  p1->ltree = p2->rtree;
	  p2->rtree = p1;
	  p->rtree = p2->ltree;
	  p2->ltree = p;
	  int b2 = p2->avl_balance;
	  if (b2 == 1)				// Set new balance for node p
	    p->avl_balance = -1;
	  else
	    p->avl_balance = 0;
	  if (b2 == -1)				// Set new balance for node p1
	    p1->avl_balance = 1;
	  else 
	    p1->avl_balance = 0;

	  p2->avl_balance = 0;			// Set new balance for node p2
	  raised_node = p2;		
	}
      }
    }
    // BALANCE RIGHT SUBTREE OF NODE P.  Note that this is VERY similar
    // to the code above to balance the left side.  Changes here are likely
    // necessary above also.
    else {
      switch (p->avl_balance) {
      case 1:					// Set balance to 0. 
	p->avl_balance = 0;			//   balance parent node
	break;
      case 0:					// Set balance to 1.  Tree is 
	p->avl_balance = -1;			//   all balanced.
	more_todo = FALSE;
	break;
      case -1:					// Need to rotate
	p1 = p->ltree;
	if (p1->avl_balance <= 0) {		// Single right rotate
	  p->ltree = p1->rtree;
	  p1->rtree = p;
	  raised_node = p1;
	  if (p1->avl_balance == 0) {		// Update p and p1 balance
	    p->avl_balance = -1;
	    p1->avl_balance = 1;
	    more_todo = FALSE;			
	  }
	  else {
	    p->avl_balance = 0;
	    p1->avl_balance = 0;
	  }
	}
	else {					// Double left right rotate
	  p2 = p1->rtree;
	  p1->rtree = p2->ltree;
	  p2->ltree = p1;
	  p->ltree = p2->rtree;
	  p2->rtree = p;
	  int b2 = p2->avl_balance;
	  if (b2 == -1)				// Set new balance for node p
	    p->avl_balance = 1;
	  else
	    p->avl_balance = 0;
	  if (b2 == 1)				// Set new balance for node p1
	    p1->avl_balance = -1;
	  else
	    p1->avl_balance = 0;

	  p2->avl_balance = 0;			// Set new balance for node p2
	  raised_node = p2;
	}
      }
    }
  }

  // If raised_node is non_null, after all the balancing is done, it means
  // we have a new root. 
  if (raised_node != NULL) {
    this->root = raised_node;
  }
}
			  

// value_error -- Raise exception for Binary_Tree<Type>::value()
// Input:         Character string of type
// Output:        None

void Binary_Tree::value_error (const char* Type) {
  RAISE (Error, SYM(Binary_Tree), SYM(Invalid_Cpos),
	 "Binary_Tree<%s>::value(): Invalid current position", Type);
}


// remove_error -- Raise exception for Binary_Tree<Type>::remove()
// Input:          Character string of type
// Output:         None

void Binary_Tree::remove_error (const char* Type) {
  RAISE (Error, SYM(Binary_Tree), SYM(Invalid_Cpos),
	 "Binary_Tree<%s>::remove(): Invalid current position", Type);
}

