/*
  Travis Gadberry
  Patrick Hesser
  Chris Ladewig

  BalancedBinaryTree.cpp
  21Mar05
*/

#include "BalancedBinaryTree.h"

using namespace std;

  /**
   * Implements an unbalanced binary search tree.
   * Note that all "matching" is based on the < method.
  */

template <class Comparable>
BalancedBinaryTree<Comparable>::
BalancedBinaryTree(const Comparable & notFound) :
           root(NULL), ITEM_NOT_FOUND(notFound)
{
}


template <class Comparable>
BalancedBinaryTree<Comparable>::
BalancedBinaryTree(const BalancedBinaryTree<Comparable> & rhs) :
             root(NULL), ITEM_NOT_FOUND(rhs.ITEM_NOT_FOUND) { 
  *this = rhs;
}

template <class Comparable>
BalancedBinaryTree<Comparable>::
~BalancedBinaryTree() {
  makeEmpty();
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
insert(const Comparable & x) {
  insert(x, root);
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
remove(const Comparable & x) {
  remove(x, root);
}


template <class Comparable>
const Comparable &
BalancedBinaryTree<Comparable>::
findMin() const {
  return elementAt(findMin(root));
}

template <class Comparable>
const Comparable &
BalancedBinaryTree<Comparable>::
findMax() const {
  return elementAt(findMax(root));
}

template <class Comparable>
const Comparable &
BalancedBinaryTree<Comparable>::
find(const Comparable & x) {
  time_t t1, t2;
  t1 = clock();

  BinaryNode<Comparable> *result = find(x,root);
		
  t2 = clock();
  searchTime = (t2 - t1)/CLOCKS_PER_SEC;

  return elementAt(result);
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
makeEmpty() {
  makeEmpty(root);
}

template <class Comparable>
bool
BalancedBinaryTree<Comparable>::
isEmpty() const {
  return root == NULL;
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
printTree() const {
  if(isEmpty())
  cout << "Empty tree" << endl;
  else
  printTree(root);
}

template <class Comparable>
const BalancedBinaryTree<Comparable> &
BalancedBinaryTree<Comparable>::
operator=(const BalancedBinaryTree<Comparable> & rhs) {
  if(this != &rhs) {
    makeEmpty();
    root = clone(rhs.root);
  }
  return *this;
}

template <class Comparable>
const Comparable & BalancedBinaryTree<Comparable>::
elementAt(BinaryNode<Comparable> *t) const {
  if(t == NULL)
    return ITEM_NOT_FOUND;
  else
    return t->element;
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
insert(const Comparable & x, BinaryNode<Comparable> * & t) {
  if(t == NULL)
    t = new BinaryNode<Comparable>(x, NULL, NULL);
  else if(x < t->element)
    insert(x, t->left);
  else if(t->element < x)
    insert(x, t->right);
}


template <class Comparable>
void
BalancedBinaryTree<Comparable>::
remove(const Comparable & x, BinaryNode<Comparable> * & t) const {
  if(t == NULL)
    return;   // Item not found; do nothing
  if(x < t->element)
    remove(x, t->left);
  else if(t->element < x)
    remove(x, t->right);
  else if(t->left != NULL && t->right != NULL) // Two children 
  {
    t->element = findMin(t->right)->element;
    remove(t->element, t->right);
  }
  else {
    BinaryNode<Comparable> *oldNode = t;
    t = (t->left != NULL) ? t->left : t->right;
    delete oldNode;
  }
}

template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::
findMin(BinaryNode<Comparable> *t) const {
  if(t == NULL)
    return NULL;
  if(t->left == NULL)
    return t;
  return findMin(t->left);
}

template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::findMax(BinaryNode<Comparable> *t) const {
  if(t != NULL)
    while(t->right != NULL)
  t = t->right;
    return t;
}

template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::
find(const Comparable & x, BinaryNode<Comparable> *t) {
  if(increments++, (t == NULL))
    return NULL;
  else if(increments++, x < t->element)
    return find(x, t->left);
  else if(increments++, t->element < x)
    return find(x, t->right);
  else
    return t;    // Match
}

template <class Comparable>
int 
BalancedBinaryTree<Comparable>::
getIncrements() {
  return increments;
}

template <class Comparable>
double 
BalancedBinaryTree<Comparable>::
getCreationTime() {
  return creationTime;
}

template <class Comparable>
double 
BalancedBinaryTree<Comparable>::
getSearchTime() {
  return searchTime;
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
insertIntArray(int * A, int n) {
  time_t t1, t2;
  t1 = clock();

  QuickSort* quick = new QuickSort(A,n);
  quick->sort();
  int * B = quick->getArray();

  BalancedTreeRecursion(B,0,n-1);
			
    t2 = clock();
    creationTime = (t2 - t1)/CLOCKS_PER_SEC;
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
insertIntVector(const vector<int> V) {
  time_t t1, t2;
  t1 = clock();

  int n = V.size();
  int * A = new int[n];
  for(int i=0; i<n; i++)
    A[i] = V.at(i);

  QuickSort* quick = new QuickSort(A,n);
  quick->sort();
  int * B = quick->getArray();

  BalancedTreeRecursion(B, 0, n-1);

  t2 = clock();
  creationTime = (t2 - t1)/CLOCKS_PER_SEC;
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
BalancedTreeRecursion(int* A, int P, int Q)
{

	int temp = (P+Q)/2;
	insert(A[temp], root);
	int J = temp-1;
	int K = J + 2;
	if(J <= P)
	{
		insert(A[P],root);
	}
	else
		BalancedTreeRecursion(A,P,J);
	if(K >= Q)
	{
		insert(A[Q],root);
	}
	else
		BalancedTreeRecursion(A,K,Q);
}
		

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
resetIncrements() {
  increments = 0;
  creationTime = 0;
  searchTime = 0;
}






/****** NONRECURSIVE VERSION*************************
template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::
find(const Comparable & x, BinaryNode<Comparable> *t) const {
  while(t != NULL)
    if(x < t->element)
      t = t->left;
    else if(t->element < x)
      t = t->right;
    else
      return t;    // Match

  return NULL;   // No match
}
*****************************************************/

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
makeEmpty(BinaryNode<Comparable> * & t) const {
  if(t != NULL) {
    makeEmpty(t->left);
    makeEmpty(t->right);
    delete t;
  }
  t = NULL;
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
printTree(BinaryNode<Comparable> *t) const {
  if(t != NULL) {
    printTree(t->left);
    cout << t->element << endl;
    printTree(t->right);
  }
}

template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::
clone(BinaryNode<Comparable> * t) const {
  if(t == NULL)
    return NULL;
  else
    return new BinaryNode<Comparable>(t->element, clone(t->left), clone(t->right));
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
rotateRight(BinaryNode<Comparable> *t) {
  BinaryNode<Comparable> temp = t->left;
  t->left = temp->right;
  temp->right = t;
  t = temp;
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
rotateLeft(BinaryNode<Comparable> *t) {
  BinaryNode<Comparable> temp = t->right;
  t->right = temp->left;
  temp->left = t;
  t = temp;
}

template <class Comparable>
int
BalancedBinaryTree<Comparable>::
getHeight(BinaryNode<Comparable> *t) {
  int left_height = 0;
  int right_height = 0;
  if(t->left)
    left_height = getHeight(t->left);
  if(t->right)
    right_height = getHeight(t->right);
  if(right_height >= left_height)
    return (right_height + 1);
  else
    return (left_height + 1);
}

template <class Comparable>
void
BalancedBinaryTree<Comparable>::
balance(BinaryNode<Comparable> *t) {
  int left_height = getHeight(t->left);
  int right_height = getHeight(t->right);

  if(left_height-right_height > 1) {
    int next_left = getHeight(t->left->left);
    int next_right = getHeight(t->left->right);
    if(next_right-next_left > 1) {
      rotateLeft(t->left);
      balance(t->left);
    }
    if(next_left-next_right > 1) {
      rotateRight(t->left);
      balance(t->left);
    }
  }
  if(right_height-left_height > 1) {
    int next_left = getHeight(t->right->left);
    int next_right = getHeight(t->right->right);
    if(next_right-next_left > 1) {
      rotateLeft(t->right);
      balance(t->right);
    }
    if(next_left-next_right > 1) {
      rotateRight(t->right);
      balance(t->right);
    }
  }
}