/* File: bst.C      Copyright glh 8/15/94 */
#include "bst.H"

template<class T>
Bnode<T>* BST<T>::SubtreeMin(Bnode<T>* v) const
{
  if (v == 0)
    return 0;
  while (v->lchild != 0)
    v = v->lchild;
  return v;
}

template<class T>
Bnode<T>* BST<T>::SubtreeMax(Bnode<T>* v) const
{
  if (v == 0)
    return 0;
  while (v->rchild != 0)
    v = v->rchild;
  return v;
}

template<class T>
Bnode<T>* BST<T>::Search(Bnode<T>* u, int key, Boolean& success) const
{
  success = false;
  Bnode<T>* v = u;
  if (u != 0) {
    while (v != 0 && key != v->data.Key()) {
      u = v;  // copy v to u before moving to a child
      if (key < v->data.Key())
        v = v->lchild;
      else
        v = v->rchild;
    }
    if (v != 0)
      success = true;
    else
      v = u;  // v gets last vertex visited prior to NULL
  }
  return v;
}

template<class T>
T& BST<T>::Search(int key, Boolean& success) const
{
  Bnode<T>* v = Search(root, key, success);
  if (success == true)
    return v->data;
  else
    return *(new T);  // unsuccessful search, return a dummy value
}

template<class T>
Boolean BST<T>::Insert(T item)
{
  Boolean found;
  Bnode<T>* new_node = new Bnode<T>(item);
  assert(new_node != 0);
  if (root == 0)
    root = new_node;
  else {
    Bnode<T>* v = Search(root, item.Key(), found);
    if (found == true) {  // item is already in tree
        delete new_node;
        return false;
    }
    if (item.Key() < v->data.Key())
      BinaryTree<T>::InsertLeaf(new_node, v, left);
    else
      BinaryTree<T>::InsertLeaf(new_node, v, right);
  }
  return true;
}

template<class T>
Boolean BST<T>::Delete(int key)
{
  Boolean found;
  Bnode<T>* v = Search(root, key, found);
  if (found == false)
    return false;
  if (v->lchild == 0 || v->rchild == 0) {  // case 1 or 2
    if (v->lchild != 0) {  // case 2, v has a left child
      if (v->parent->lchild == v)
        v->parent->lchild = v->lchild;
      else
        v->parent->rchild = v->lchild;
      v->lchild->parent = v->parent;
    }
    else if (v->rchild != 0) {  // case 2, v has a right child
      if (v->parent->lchild == v)
        v->parent->lchild = v->rchild;
      else 
        v->parent->rchild = v->rchild;
      v->rchild->parent = v->parent;
    }
    else  // case 1
      if (v->parent->lchild == v)
         v->parent->lchild = 0;
      else
         v->parent->rchild = 0;
    delete v; 
  }
  else {  // case 3
    Bnode<T>* p = SubtreeMax(v->lchild);  // p is the predecessor of v
    v->data = p->data;
    if (p->lchild != 0) {  // case 2, p has a left child
      if (p->parent->lchild == p) 
        p->parent->lchild = p->lchild;
      else 
        p->parent->rchild = p->lchild;
      p->lchild->parent = p->parent;
    }
    else if (p->rchild != 0) {  // case 2, p has a right child
      if (p->parent->lchild == p)
        p->parent->lchild = p->rchild;
      else 
        p->parent->rchild = p->rchild;
      p->rchild->parent = p->parent;
    }
    else  // case 1
      if (p->parent->lchild == p)
         p->parent->lchild = 0;
      else
         p->parent->rchild = 0;
    delete p; 
  }
  return true;
}

template<class T>
T& BST<T>::Minimum(Boolean& success) const
{
  success = false;
  if (root == 0)
    return *(new T);  // no minimum, return dummy value
  success = true;
  return SubtreeMin(root)->data;
}

template<class T>
T& BST<T>::Maximum(Boolean& success) const
{
  success = false;
  if (root == 0)
    return *(new T);  // no maximum, return dummy value
  success = true;
  return SubtreeMax(root)->data;
}

template<class T>
T& BST<T>::Predecessor(int key, Boolean& success) const
{
  Bnode<T>* v = Search(root, key, found);
  if(success == false);
    return *(new T);  // unsuccessful search, return dummy value
  if (v->lchild != 0)
    return SubtreeMax(v->lchild)->data;
  Bnode<T>* p = v->parent;
  while (p != 0 && v == p->lchild) {
    v = p;
    p = p->parent;
  }
  if (p == 0)
    return *(new T); // no predecessor, return dummy value
  return p->data;
}

template<class T>
T& BST<T>::Successor(int key, Boolean& success) const
{
  Bnode<T>* v = Search(root, key, success);
  if (success == false)
    return *(new T);  // unsuccessful search, return dummy value
  if (v->rchild != 0)
    return SubtreeMin(v->rchild)->data;
  Bnode<T>* p = v->parent;
  while (p != 0 && v == p->rchild) {
    v = p;
    p = p->parent;
  }
  if (p == 0)
    return *(new T); // no successor, return dummy value
  return p->data;
}