// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): ?? SUNY Stony Brook students

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 


#include <string.h>


/*****************************public routines******************************/
//
//constructor.
//
template <class Key, class Item>
BinarySearchTree<Key,Item>::BinarySearchTree()
{
  _count = 0;
  _root = NULL;
}
//
// Destructor.
//
template <class Key, class Item>
BinarySearchTree<Key,Item>::~BinarySearchTree()
{
  clear();
}

//
//
//
template <class Key, class Item>
ContainerNode*
BinarySearchTree<Key,Item>::insert(Key passed_key, Item passed_item)
{
    BinarySearchTreeNode<Key,Item>* node;
    node = new BinarySearchTreeNode<Key,Item>;
    if (!node) {
       error("BinarySearchTree<Key,Item>::insert(): free store exhausted.");
       return(0);
    }
   
    _count++; 
    node->key = passed_key;
    node->item = passed_item;
    
    if (!_root) {
       _root = node;
       return (ContainerNode*) node;
    }

    BinarySearchTreeNode<Key,Item> *x, *y;
    y = NULL;
    x = _root;
    while (x) {
       y = x;
       if ( node->key < x->key)
          x = x->left;
       else
          x = x->right;
    }
    node->parent = y;

    if (node->key < y->key) 
       y->left = node;
    else
       y->right = node;
    return (ContainerNode*) node; 
}

//
//search a key in the tree.
//
template <class Key, class Item>
BinarySearchTreeNode<Key,Item>* 
BinarySearchTree<Key,Item>::search(const Key& passed_key) const
{ 
   if ( (!_root) || (_root->key == passed_key) )
      return _root;
   BinarySearchTreeNode<Key,Item>* x = _root;
   while ( x && (x->key != passed_key) ) {
      if (passed_key < x->key)
         x = x->left;
      else
         x = x->right;
   }
   if (!x)
      warning("BinarySearchTree<Key,Item>::search(): key is not found.");
   return x;
}
//
// Search an item in the tree
//
template <class Key, class Item> 
BinarySearchTreeNode<Key,Item>*
BinarySearchTree<Key,Item>::searchItem(const Item& passed_item) const
{
   if ( (!_root) || 
	(ElementOps<Item>::compareItems(_root->item, passed_item)==0))
      return _root;
   BinarySearchTreeNode<Key,Item>* x = treeSearchItem(_root,passed_item);
   if (!x)
      warning("BinarySearchTree<Key,Item>::searchItem: item is not found.");
   return x;
}
//
//Query on membership.
//
template <class Key, class Item>
Bool
BinarySearchTree<Key,Item>::memberQ(const Item& e) const
{
   if (searchItem(e))
      return TRUE;
   else
      return FALSE;
}

//
//Find the successor for a node in the tree.
//
template <class Key, class Item>
BinarySearchTreeNode<Key,Item>*
BinarySearchTree<Key,Item>::successor(BinarySearchTreeNode<Key,Item>* x) const
{
   if (!x) {
      error("BinarySearchTree<Key,Item>::successor(): NULL pointer.");
      return (x);
   }

   if (x->right)
      return treeMinimum(x->right);
   BinarySearchTreeNode<Key,Item>* y = x->parent;
   while ( y && (x == y->right) ) {
      x = y;
      y = y->parent;
   }
   if (!y) 
      warning("BinarySearchTree<Key,Item>::successor(): No successor is found.");
   return y;
}   
//
//
//
template <class Key, class Item>
BinarySearchTreeNode<Key,Item>*
BinarySearchTree<Key,Item>::predecessor(BinarySearchTreeNode<Key,Item>* x) const{
   if (!x) {    
      error("BinarySearchTree<Key,Item>::predecessor(): NULL pointer."); 
      return (x);
   } 
   if (x->left)
      return treeMaximum(x->left);
   BinarySearchTreeNode<Key,Item>* y = x->parent;
   while ( y && (x == y->left) ) { 
      x = y; 
      y = y->parent; 
   } 
   if (!y)  
      warning("BinarySearchTree<Key,Item>::predecessor(): No predecessor is found.");
   return y; 
 
}
//
//Remove a key from the tree.
//
template <class Key, class Item>
void 
BinarySearchTree<Key,Item>::remove(BinarySearchTreeNode<Key,Item>* passed_node)
{
  if (!passed_node) {
     warning("BinarySearchTree<Key,Item>::remove() : NULL pointer.");
     return;
  }
  
  BinarySearchTreeNode<Key,Item> *y, *x;
  if ( (!passed_node->left) || (!passed_node->right) )
     y = passed_node;
  else
     y = successor(passed_node);
  if (y->left) 
     x = y->left; 
  else
     x = y->right;
  if (x)
     x->parent = y->parent;
  if (!y->parent)
     _root = x;
  else if (y == y->parent->left) 
     y->parent->left = x;
  else 
     y->parent->right = x;
  if (y != passed_node) {
     passed_node->key = y->key;
     passed_node->item = y->item;
  }
  delete y;  //????
  _count--;
}


//
//Remove an item from the tree.
//
template <class Key, class Item>
void
BinarySearchTree<Key,Item>::remove(Item passed_item)
{
   BinarySearchTreeNode<Key,Item> *x;
   x = searchItem(passed_item);
   remove(x);
}
//
// Remove all the node in the tree.
//
template <class Key, class Item>
void
BinarySearchTree<Key,Item>::clear()
{
  treeKill(_root);
  _root = NULL;
}
//
//Find the minimum key in the tree.
//
template <class Key, class Item>
ContainerNode*
BinarySearchTree<Key,Item>::minimum() const
{
  BinarySearchTreeNode<Key,Item> *x;
  x = treeMinimum(_root);
  return (ContainerNode *) x;
}

//
//Find the maximum key in the tree.
//
template <class Key, class Item>
ContainerNode*
BinarySearchTree<Key,Item>::maximum() const
{ 
   BinarySearchTreeNode<Key,Item> *x;
   x = treeMaximum(_root);
   return (ContainerNode *) x; 
} 
 
//
//Delete the minimum key in the tree
//
template <class Key, class Item>
Item
BinarySearchTree<Key,Item>::extractMin()
{
   BinarySearchTreeNode<Key,Item> *x;
   x = (BinarySearchTreeNode<Key,Item> *) minimum() ;
   Item item = x->item;
   remove(x);
   return item;
}

//
//Delete the maximum key in the tree.
//
template <class Key, class Item>
Item
BinarySearchTree<Key,Item>::extractMax()
{
   BinarySearchTreeNode<Key,Item> *x;
   x = (BinarySearchTreeNode<Key,Item> *) maximum();
   Item item = x->item; 
   remove(x); 
   return item; 
} 

//
//Print out the tree in inorderwalk.
//
template <class Key, class Item>
void 
BinarySearchTree<Key,Item>::inorderWalk(ostream& os) const
{
   if (!_root) {
     os << "<Empty Binary Search Tree>" << endl;
     return;
   }
   os << "<";
   inorderTreeWalk(os, _root);
   os << ">";
   os << endl;
}

// 
//Print out the tree in preorder 
// 
template <class Key, class Item> 
void 
BinarySearchTree<Key,Item>::preorderWalk(ostream& os) const
{
   if (!_root) {  
     os << "<Empty Binary Search Tree>" << endl;
     return;
   }
   os << "<"; 
   preorderTreeWalk(os, _root); 
   os << ">";
   os << endl;
}
 
// 
//print out the tree in postorder. 
// 
template <class Key, class Item> 
void 
BinarySearchTree<Key,Item>::postorderWalk(ostream& os) const
{
   if (!_root) {   
      os << "<Empty Binary Search Tree>" << endl;
      return;
   }
   os << "<"; 
   postorderTreeWalk(os, _root);
   os << ">"; 
   os << endl;
}
  
//
//print out all the items in the tree.
//
template <class Key, class Item>
ostream& 
BinarySearchTree<Key,Item>::print(ostream& os)
{ 
   if (!_root) {
      os << "(Empty Binary Search Tree)" << endl;
      return os;
   } 
   os << "(";
   Iterator<Item> get_next(this);
   Item i;
   while (get_next(i))
       os << i << " ";
   os << ")" <<endl ;
   return os;
}
//
// Display the tree in human-readable way.
//
template <class Key, class Item>
ostream&
BinarySearchTree<Key,Item>::display(ostream& os) const
{  
   if (!_root) {
      os << "<Empty Binary Search Tree>" << endl;
      return os;
   }
   //char order[20];
   //os<<"Which traversal do you want? (inorder, postorder, preorder)" << endl;
   //cin >> order;
   //if (strcmp(order, "inorder") == 0) {

      inorderWalk(os);

   //   return os;
   //}
   //else if (strcmp(order, "postorder") == 0) {
   //   postorderWalk(os);
   //   return os;
   //}
   //else if (strcmp(order, "preorder") == 0) {
   //   preorderWalk(os);
   //   return os;
   //}
   //else {
   //   display(os);
   //   return os;
   //}
   return os;
}

//
// Randomly permutate the all the key in the tree, then rebuild
// it, for testing.
//
template <class Key, class Item>
void
BinarySearchTree<Key,Item>::scramble() 
{
   if (_count <= 1)
      return; 
   int i, j;
   BinarySearchTreeNode<Key,Item>** tree;
   tree = new BinarySearchTreeNode<Key,Item>*[_count + 1];
   if (!tree) {
      error("BinarySearchTree<Key,Item>::scramble(): free store is exhausted.");
      return;
   }
   BinarySearchTreeNode<Key,Item>* tmp;
   for (i = 1; i <= _count; i ++) {
       tree[i] = new BinarySearchTreeNode<Key,Item>;
       tmp =  getNode(i);
       tree[i]->key = tmp->key;
       tree[i]->item = tmp->item;
   }

   int count = _count;
   clear();
 
   // generate a random permutation on tree[].
   for(i = count; i >= 1; i--) {
       j = (int)Link_randomLong() % i + 1 ; //generate a random number in [1,i)
       tmp = tree[i];
       tree[i] = tree[j]; //swap tree[i] with tree[j].
       tree[j] = tmp;
    }
    
    // rebuild the tree from the permutation
    for (i = 1; i <= count; i++) {
        insert(tree[i]->key,tree[i]->item); 
        delete tree[i];
    }
    delete [] tree;
}

//
// Change a key in the tree.
//
template <class Key, class Item>
void 
BinarySearchTree<Key,Item>::changeKey(BinarySearchTreeNode<Key,Item>* node, 
                                      Key k) 
{
  if (!node) {   
    error("BinarySearchTree<Key,Item>::changeKey() : NUll pointer.");
    return;
  }
  if ( k == node->key) {  
     warning("BinarySearchTree<Key,Item>::changeKey() : key is not changed.");
     return;
  }
  Key tmpk;
  Item tmpi;
  BinarySearchTreeNode<Key,Item> *x, *predx, *succx;

  if ( k < node->key) {
     node->key = k;
     x = node;
     predx = predecessor(x);
     while ( (predx) && (predx->key > k) ) {
       tmpk = predx->key;
       tmpi = predx->item;
       predx->key = x->key;
       predx->item = x->item;
       x->key = tmpk;
       x->item = tmpi;
       x = predx;
       predx = predecessor(x);
     } 
  }  
  else { 
  //if ( k > node->key) {
     node->key = k;   
     x = node;
     succx = successor(x);
     while ( (succx) && (succx->key < k) ) {
       tmpk = succx->key; 
       tmpi = succx->item; 
       succx->key = x->key; 
       succx->item = x->item;
       x->key = tmpk;
       x->item = tmpi;
       x = succx;
       succx = successor(x);   
     }   
  }
}

//
//Merge another tree into cureent tree and destory the tree merged.
//
template <class Key, class Item>
void
BinarySearchTree<Key,Item>::merge(BinarySearchTree<Key,Item> &T)
{
   int Tsize = T.size();
   if (!Tsize)
      return;
   BinarySearchTreeNode<Key,Item> *tmp;
   for (int i = 1; i <= Tsize; i++) {
      tmp = T.getNode(i);
      insert(tmp->key, tmp->item);
   } 
   T.clear();
}

//
//Get ith node in the tree.
//
template <class Key, class Item>
BinarySearchTreeNode<Key,Item>*
BinarySearchTree<Key,Item>::getNode(int index) const
{
   BinarySearchTreeNode<Key,Item> *node = 0;
   int j = index;
   treeIterate(_root, node, j);
   return node;
}
//
//Iterate the items in the tree.
//
template <class Key, class Item>
int
BinarySearchTree<Key,Item>::iterate(Iterator<Item>& iterator, Item& item) const
{
   if (_count <= 0)
       return 0;
   if (iterator._index > _count || iterator._index < 0)
       return 0;
   else {
       iterator._index++;
       BinarySearchTreeNode<Key,Item> *node = 0; 
       int index = iterator._index;
       treeIterate(_root, node, index);
       if (node) {
           item = node->item;
           return 1;
       } else
           return 0;
   }

}
//
// operator = , copy a tree to another tree.
//
template <class Key, class Item>
BinarySearchTree<Key,Item>&
BinarySearchTree<Key,Item>::operator=(const BinarySearchTree<Key, Item>& tree)
{
  if (&tree == this)
      return *this;
   clear();
   int size = tree.size(); 
   if (!size)
      return *this;

   BinarySearchTreeNode<Key,Item> *tmp, *node;
   for (int i = 1; i <= size; i++) {
     node = new BinarySearchTreeNode<Key,Item>;
     tmp = tree.getNode(i);
     insert(tmp->key, tmp->item);
   }
   return *this;
 
}
//
// Calculate the height of the tree.
//
template <class Key, class Item>
int
BinarySearchTree<Key,Item>::height() const 
{
   return treeHeight(_root);
}

/*******************private routines*******************************/
//
//Find the minimum in the subtree rooted at x.
//
template <class Key, class Item>
BinarySearchTreeNode<Key,Item>*
BinarySearchTree<Key,Item>::treeMinimum(BinarySearchTreeNode<Key,Item>* y) const
{ 
  if (!y) 
     return (0);
  BinarySearchTreeNode<Key,Item> *x = y;
  while (x->left)
     x = x->left;
  return x;
}

//
// Find the maximum in the subtree rooted at x.
//
template <class Key, class Item>
BinarySearchTreeNode<Key,Item>* 
BinarySearchTree<Key,Item>::treeMaximum(BinarySearchTreeNode<Key,Item>* y) const
{
  if (!y)
     return (0);
  BinarySearchTreeNode<Key,Item> *x = y;
  while (x->right)
     x = x->right;
  return x;
}
// 
//Search for a key in the subtree rooted on x. 
// 
template <class Key, class Item> 
BinarySearchTreeNode<Key,Item>*  
BinarySearchTree<Key,Item>::treeSearch(BinarySearchTreeNode<Key,Item>* x,
                                       const Key& k) const
{
  if ( (!x) || (k == x->key) )
     return x;
  if ( k < x->key)
     return treeSearch(x->left, k);
  else
     return treeSearch(x->right, k);
}

//
// Search for an item in the subtree rooted on x.
//
template <class Key, class Item> 
BinarySearchTreeNode<Key,Item>*
BinarySearchTree<Key,Item>::treeSearchItem(BinarySearchTreeNode<Key,Item>* x,
                                           const Item& item) const
{
  if ( (!x) || (ElementOps<Item>::compareItems(item, x->item)==0 ))
     return x;
  BinarySearchTreeNode<Key,Item>* node;
  node = treeSearchItem(x->left, item);
  if (node)
     return node;
  else
     return treeSearchItem(x->right, item);
}

//
// Delete the subtree rooted at x.
//

template <class Key, class Item> 
void
BinarySearchTree<Key,Item>::treeKill(BinarySearchTreeNode<Key,Item>* x)
{
   if (!x)
      return;
   treeKill(x->left);
   treeKill(x->right);
   delete x;
   _count--;
}

//
// print out the subtree rooted at x in inorder walk
//
template <class Key, class Item>
void
BinarySearchTree<Key,Item>::inorderTreeWalk(ostream& os,
				BinarySearchTreeNode<Key,Item>* x) const
{
   if (x) {
      inorderTreeWalk(os, x->left);
      os << "(";
      os << x->key;
      os << ",";
      ElementOps<Item>::displayItem(os, x->item);
      os << ")";
      inorderTreeWalk(os, x->right);
   }
}

// 
//print out the subtree rooted at x in preorder walk. 
// 
template <class Key, class Item> 
void
BinarySearchTree<Key,Item>::preorderTreeWalk(ostream& os, 
				BinarySearchTreeNode<Key,Item>* x) const 
{
   if (x) { 
      os << "("; 
      os << x->key; 
      os << ","; 
      ElementOps<Item>::displayItem(os, x->item);
      os << ")";
      preorderTreeWalk(os, x->left);   
      preorderTreeWalk(os, x->right);
   }
}

//
// print out the subtree rooted at x in postorder walk.
//
template <class Key, class Item>  
void 
BinarySearchTree<Key,Item>::postorderTreeWalk(ostream& os, 
				BinarySearchTreeNode<Key,Item>* x) const 
{
   if (x) { 
      postorderTreeWalk(os, x->left);
      postorderTreeWalk(os, x->right);
      os << "(";  
      os << x->key;  
      os << ",";  
      ElementOps<Item>::displayItem(os, x->item);
      os << ")";
   }
}
//
// Iterate ith node in the subtree rooted at x.
//
template <class Key, class Item>
void
BinarySearchTree<Key,Item>::treeIterate(BinarySearchTreeNode<Key,Item>* x, 
                                        BinarySearchTreeNode<Key,Item>*& node,
                                        int& index) const
{ 
   if ( index <= 0) 
      return;
   if (x) {
      treeIterate(x->left, node, index);
      index--;
      if (!index) {
         node = x;
         return;
      }
      treeIterate(x->right, node, index);
   }
}

//
// Calculate the height of subtree rooted on x.
//

template <class Key, class Item>
int 
BinarySearchTree<Key,Item>::treeHeight(BinarySearchTreeNode<Key,Item>* x) const
{
   if (!x)
      return -1;
   int lefth = treeHeight(x->left);
   int righth = treeHeight(x->right);
 
   if (lefth > righth)
      return 1 + lefth;
   else
      return 1 + righth;

}