// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition" by Clifford A. Shaffer, Prentice Hall, 2007.
// Source code Copyright (C) 2006 by Clifford A. Shaffer.

// This file includes all of the pieces of the BST implementation

// Include the node implementation
#include "binnode.ht"

// Include the dictionary ADT
#include "dictionary.h"

// Binary Search Tree implementation for the Dictionary ADT
template <class Key, class Elem, class Comp, class getKey>
class BST : public Dictionary<Key, Elem, Comp, getKey> {
private:
  BinNode<Elem>* root;   // Root of the BST
  int nodecount;         // Number of nodes in the BST

  // Private "helper" functions
  void clearhelp(BinNode<Elem>*);
  BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
  BinNode<Elem>* deletemin(BinNode<Elem>*, BinNode<Elem>*&);
  BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,
                            BinNode<Elem>*&);
  bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;
  void printhelp(BinNode<Elem>*, int) const;

public:
  BST() { root = NULL; nodecount = 0; }  // Constructor
  ~BST() { clearhelp(root); }            // Destructor

  void clear()
    { clearhelp(root); root = NULL; nodecount = 0; }

  bool insert(const Elem& it) {
    root = inserthelp(root, it);
    nodecount++;
    return true;
  }

  bool remove(const Key& K, Elem& it) {
    BinNode<Elem>* t = NULL;
    root = removehelp(root, K, t);
    if (t == NULL) return false;  // Nothing found
    it = t->val();
    nodecount--;
    delete t;
    return true;
  }

  bool removeAny(Elem& it) {  // Delete min value
    if (root == NULL) return false; // Empty tree
    BinNode<Elem>* t;
    root = deletemin(root, t);
    it = t->val();
    delete t;
    nodecount--;
    return true;
  }

  bool find(const Key& K, Elem& it) const
    { return findhelp(root, K, it); }

  int size() { return nodecount; }

  void print() const {
    if (root == NULL) cout << "The BST is empty.\n";
    else printhelp(root, 0);
  }
};

// Clean up BST by releasing space back free store
template <class Key, class Elem, class Comp, class getKey>
void BST<Key, Elem, Comp, getKey>::
clearhelp(BinNode<Elem>* root) {
  if (root == NULL) return;
  clearhelp(root->left());
  clearhelp(root->right());
  delete root;
}

// Insert a node into the BST, returning the updated tree
template <class Key, class Elem, class Comp, class getKey>
BinNode<Elem>* BST<Key, Elem, Comp, getKey>::
inserthelp(BinNode<Elem>* root, const Elem& it) {
  if (root == NULL)  // Empty tree: create node
    return (new BinNodePtr<Elem>(it, NULL, NULL));
  if (Comp::lt(getKey::key(it), getKey::key(root->val())))
    root->setLeft(inserthelp(root->left(), it));
  else root->setRight(inserthelp(root->right(), it));
  return root;       // Return tree with node inserted
}

// Delete the minimum value from the BST, returning the revised BST
template <class Key, class Elem, class Comp, class getKey>
BinNode<Elem>* BST<Key, Elem, Comp, getKey>::
deletemin(BinNode<Elem>* root, BinNode<Elem>*& S) {
  if (root->left() == NULL) { // Found min
    S = root;
    return root->right();
  }
  else {                         // Continue left
    root->setLeft(deletemin(root->left(), S));
    return root;
  }
}

// Return in R the element (if any) with value K.
// Return the updated subtree with R removed from the tree.
template <class Key, class Elem, class Comp, class getKey>
BinNode<Elem>* BST<Key, Elem, Comp, getKey>::
removehelp(BinNode<Elem>* root, const Key& K,
           BinNode<Elem>*& R) {
  if (root == NULL) return NULL; // Val is not in tree
  else if (Comp::lt(K, getKey::key(root->val())))
    root->setLeft(removehelp(root->left(), K, R));
  else if (Comp::gt(K, getKey::key(root->val())))
    root->setRight(removehelp(root->right(), K, R));
  else {                               // Found: remove it
    BinNode<Elem>* temp;
    R = root;
    if (root->left() == NULL)       // Only a right child
      root = root->right();      //  so point to right
    else if (root->right() == NULL) // Only a left child
      root = root->left();       //  so point to left
    else {                    // Both children are non-empty
      root->setRight(deletemin(root->right(), temp));
      Elem te = root->val();
      root->setVal(temp->val());
      temp->setVal(te);
      R = temp;
    }
  }
  return root;
}

// Find a node with the given key value
template <class Key, class Elem, class Comp, class getKey>
bool BST<Key, Elem, Comp, getKey>:: findhelp(
      BinNode<Elem>* root, const Key& K, Elem& e) const {
  if (root == NULL) return false;          // Empty tree
  else if (Comp::lt(K, getKey::key(root->val())))
    return findhelp(root->left(), K, e);   // Check left
  else if (Comp::gt(K, getKey::key(root->val())))
    return findhelp(root->right(), K, e);  // Check right
  else { e = root->val();  return true; }  // Found it
}

// Print out a BST
template <class Key, class Elem, class Comp, class getKey>
void BST<Key, Elem, Comp, getKey>::
printhelp(BinNode<Elem>* root, int level) const {
  if (root == NULL) return;           // Empty tree
  printhelp(root->left(), level+1);   // Do left subtree
  for (int i=0; i<level; i++)         // Indent to level
    cout << "  ";
  cout << root->val() << "\n";        // Print node value
  printhelp(root->right(), level+1);  // Do right subtree
}