//
// Binary Search Tree Implementation
// Base class: Binary Tree Implementation
//

#include "btree.h"

template <class T>
class BSTree : protected BTree<T> {

 public:
  // Constructors
  BSTree () : BTree<T> () { }
  BSTree (T& item) : BTree<T> (item) { }

  // Make visibile traversals methods and height 
  void Inorder (void (*Visit) (T&, int)) { return BTree<T>::Inorder (Visit); }
  void Preorder (void (*Visit) (T&, int)) { return BTree<T>::Preorder (Visit); }
  void Postorder (void (*Visit) (T&, int)) { return BTree<T>::Postorder (Visit); }

  int Height () { return BTree<T>::Height (); }

  // New methods: Insert and delete 
  bool Insert (T& item) { return Insert (Root, item); }
  bool Insert (T* item) { return Insert (Root, *item); }
  bool Delete (T& item) { return Delete (Root, item); }
  bool Delete (T* item) { return Delete (Root, *item); }

  // Different Search 
  bool Search (T& item) { TreeNode<T>* P; return Search (Root, P, item); }
  bool Search (T* item) { TreeNode<T>* P; return Search (Root, P, *item); }

  // Find Max and Min 
  T& FindMax ();
  T& FindMin ();

 private:
  bool Insert (TreeNode<T>*&, T&);
  bool Delete (TreeNode<T>*&, T&);
  bool Search (TreeNode<T>*, TreeNode<T>*&, T&); 

};


template <class T>
bool BSTree<T>::Insert (TreeNode<T>*& R, T& item)
{
  TreeNode<T>* P;

  if (R == NULL)
    R = new TreeNode<T> (item, NULL, NULL); 
  else
    {
      // Find position where to insert
      if (Search (R, P, item) == true)
	return false;
      // Replace
      if (P->key < item)
	P->right = new TreeNode<T> (item, P->right, NULL);
      else
	P->left = new TreeNode<T> (item, P->left, NULL);
    }
  return true;
}

template <class T>
bool BSTree<T>::Delete (TreeNode<T>*& R, T& item)
{
  TreeNode<T> *P = R, *S = NULL, *PS = NULL, *PP = NULL;

  // Find Node to delete and its parent
  while (P && (P->key != item))
    {
      PP = P; 
      P = P->key > item ?  P->left : P->right;
    }
  if (P == NULL)
    return false;

  // Find Node used for replacement
  if (P->right != NULL)
    {
      for (S = P->right; S->left; S = S->left) PS = S;
      if (PS != NULL) 
	PS->left = S->right;
      else
	P->right = S->right;
    }
  else if (P->left != NULL)
    {
      for (S = P->left; S->right; S = S->right) PS = S;
      if (PS != NULL) 
	PS->right = S->left;
      else
	P->left = S->left;
    }

  // Replace
  if (PP != NULL)
    if (PP->key > item) 
      PP->left = S; 
    else 
      PP->right = S;
  else
    R = S;
  if (S != NULL)
    {
      S->left = P->left != S ? P->left : NULL;  
      S->right = P->right != S ? P->right : NULL; 
    }
  item = P->key; delete P;
  return true;
}

template <class T>
T& BSTree<T>::FindMax ()
{
  TreeNode<T> *P = Root, *PP = NULL;

  // G to right until no more nodes are available
  for (; P->right;)
    P = P->right;
  return P->key;
}

template <class T>
T& BSTree<T>::FindMin ()
{
  TreeNode<T> *P = Root, *PP = NULL;

  // Go to left until no more nodes are available
  for (; P->left;)
    P = P->left;
  return P->key;
}

template <class T>
bool BSTree<T>::Search (TreeNode<T>* R, TreeNode<T>*& P, T& item)
{
  /*  if (R == NULL)
        return false;
      P = R;
      if (item == R->key)
        return true;
      else if (item > R->key)
        return Search (R->right, P, item);
      else
        return Search (R->left, P, item);
      return false;
  */
  while (R != NULL)
    {
      P = R;
      if (R->key > item)
	R = R->left;
      else if (R->key < item)
	R = R->right;
      else
	{
	  item = R->key;
	  return true;
	}
    }
  return false;
}