#include "stdstuff.h"
#include "Tree.h"

void Tree::purge (TNode* subroot) {

  if (subroot == NULL) return; // nothing to purge
  purge (subroot -> left); // dispose of the left subtree
  purge (subroot -> right); // dispose of the right subtree
  delete subroot; // get rid of the root node

}


Tree::~Tree () {

  purge (root);

}


// iterative insert used because, when there is a relatively straightforward
// iterative method, it will typically be more efficient than a recursive one.
bool Tree::insert (int data) {

  TNode *p = NULL, *c = root, *n;
  bool wentRight;

  while (c != NULL && c -> data != data) {
    if (data < c -> data) {
      p = c; c = c -> left;  wentRight = false;
    } else {
      p = c; c = c -> right; wentRight = true;
    }
  }

  if (c != NULL) return false;  // data exists

  n = new TNode (data, NULL, NULL);
  if (p == NULL) {
    root = n;
  } else  if (wentRight) {
    p -> right = n;
  } else {
    p -> left = n;
  }

  size++;
  return true;

}


bool Tree::remove (int data) {

  TNode *p = NULL, *c = root, *n;
  bool wentRight;

  while (c != NULL && c -> data != data) {
     if (data < c -> data) {
        p = c; c = c -> left;  wentRight = false;
     } else {
        p = c; c = c -> right; wentRight = true;
     }
  }

  if (c == NULL) return false;  // data does not exists

  if ((c -> left == NULL) || (c -> right == NULL)) {

    // the simple case - either no children or just one

    if (c -> left != NULL) {
      n = c -> left;  // parent is to refer to our left child
    } else {
      n = c -> right; // may or may not be NULL
    }

    if (p == NULL) {
       root = n;
    } else if (wentRight) {
       p -> right = n;
    } else {
       p -> left = n;
    }

  } else {

    // the complex case - two children

    // keep track of the node of interest
    n = c;

    // now resume our progress down the tree ->
    // first we take one step to the left
    p = c; c = c -> left;
    wentRight = false;
    // and then we go as far to the right as we can
    while (c -> right != NULL) {
        p = c; c = c -> right;
        wentRight = true;
    }

    // c now refers to the node to be deleted, and p to its
    //  parent ->  first copy the data in the node to be deleted
    // to the node of interest
    n -> data = c -> data;

    // and then delete the node (note - p cannot be NULL)
    if (wentRight) {
       p -> right = c -> left;
    } else {
       p -> left = c -> left;
    }

  }

  delete c;

  size--;
  return true;

}


void Tree::subDisplay (String2002 leftPreString, String2002 midPreString,
                                 String2002 rightPreString, TNode *subRoot) {

  String2002 valueString, blankString;
  ostringstream formatter(ostringstream::out);

  if (subRoot == NULL) {

    cout << midPreString << "NULL\n";

  } else {

    // we want valueString to contain the data value followed by a hyphen.
    // the following is ugly but does the job.
    formatter << (subRoot -> data) << "-" << ends;
    valueString = formatter.str();
    // blankString is to consist of all blanks and to have the same
    // length as valueString.  this approach is crude but portable.
    for (int i = 0; i < valueString.length(); i++) {
      blankString += ' ';
    }

    subDisplay (rightPreString + blankString + "| ",
                rightPreString + blankString + "|-",
                rightPreString + blankString + "  ", subRoot -> right);
    cout << midPreString <<  valueString << "|\n";
    subDisplay (leftPreString + blankString + "  ",
                leftPreString + blankString + "|-",
                leftPreString + blankString + "| ", subRoot -> left);

  }

}


void Tree::display () {

  subDisplay ("", "", "", root);

}


bool Tree::subRotateLL (TNode *&subroot, int data) {

  TNode *n;

  if (subroot == NULL) return false; // value does not exist

  if (subroot -> data == data) {

    // we've found the right root note

    // we can't rotate of there's no left child
    if (subroot -> left == NULL) return false;

    // do the rotation
    n = subroot -> left;
    subroot -> left = n -> right;
    n -> right = subroot;
    subroot = n;

    return true;

  }

  if (subroot -> data > data) {
    return subRotateLL (subroot -> left, data);
  } else {
    return subRotateLL (subroot -> right, data);
  }

}


bool Tree::rotateLL (int data) {

  return subRotateLL (root, data);

}


bool Tree::subRotateRR (TNode *&subroot, int data) {

  TNode *n;

  if (subroot == NULL) return false; // value does not exist

  if (subroot -> data == data) {

    // we've found the right root note

    // we can't rotate of there's no right child
    if (subroot -> right == NULL) return false;

    // do the rotation
    n = subroot -> right;
    subroot -> right = n -> left;
    n -> left = subroot;
    subroot = n;

    return true;

  }

  if (subroot -> data > data) {
    return subRotateRR (subroot -> left, data);
  } else {
    return subRotateRR (subroot -> right, data);
  }

}


bool Tree::rotateRR (int data) {

  return subRotateRR (root, data);

}


int Tree::subHeight (TNode *subRoot, bool &isBalanced) {

  int leftHeight, rightHeight; // heights of left and right subtrees
  bool leftSubtreeBalanced, rightSubtreeBalanced;

  if (subRoot == NULL) {
    isBalanced = true;
    return 0;
  }

  leftHeight = subHeight (subRoot -> left, leftSubtreeBalanced);
  rightHeight = subHeight (subRoot -> right, rightSubtreeBalanced);

  // we're balanced if our left and right subtrees are both balanced and
  // the heights of the left and right subtrees don't differ by more than one.
  isBalanced = leftSubtreeBalanced && rightSubtreeBalanced &&
               (abs(leftHeight - rightHeight) <= 1);

  if (leftHeight >= rightHeight) {
    return 1 + leftHeight;
  } else {
    return 1 + rightHeight;
  }

}

int Tree::height (bool &isBalanced) {

   return subHeight (root, isBalanced);

}