#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);

}


bool Tree::subInsert (TNode *&subRoot, int data, bool &heightChanged) {

  bool subHeightChanged;

  if (subRoot == NULL) {
    subRoot = new TNode (data, NULL, NULL, 0);
    heightChanged = true; return true;
  }

  if (subRoot -> data == data) return false;  // value already in tree

  if (subRoot -> data > data) {

    // insert into left subtree

    if (!subInsert (subRoot -> left, data, subHeightChanged)) {
      return false;  // value was already in tree
    }

    if (subHeightChanged) {

      subRoot -> balance--; // our left subtree has grown

      if (subRoot -> balance == 0) {
        // we were right heavy and are now balanced (no change in height)
        heightChanged = false; return true;
      }

      if (subRoot -> balance == -1) {
        // we were balanced and are now left heavy (height has increased)
        heightChanged = true; return true;
      }

      // balance must be -2: a rotation is required

      // decide which kind of rotation is required
      if (subRoot -> left -> balance == -1) {
        rotateLL (subRoot);
      } else {
        rotateLR (subRoot);
      }

      // rotations leave the subtree with the same height that it
      // had before the insertion was performed.
      heightChanged = false; return true;

    } else {

      heightChanged = false; return true;

    }

  } else {

    // insert into right subtree

    if (!subInsert (subRoot -> right, data, subHeightChanged)) {
      return false;  // value was already in tree
    }

    if (subHeightChanged) {

      subRoot -> balance++; // our right subtree has grown

      if (subRoot -> balance == 0) {
        // we were left heavy and are now balanced (no change in height)
        heightChanged = false; return true;
      }

      if (subRoot -> balance == 1) {
        // we were balanced and are now right heavy (height has increased)
        heightChanged = true; return true;
      }

      // balance must be +2: a rotation is required

      // decide which kind of rotation is required
      if (subRoot -> right -> balance == 1) {
        rotateRR (subRoot);
      } else {
        rotateRL (subRoot);
      }

      // rotations leave the subtree with the same height that it
      // had before the insertion was performed.
      heightChanged = false; return true;

    } else {

      heightChanged = false; return true;

    }

  }

}


bool Tree::insert (int data) {

  bool success;

  success = subInsert (root, data, success);

  if (success) size++;

  return success;

}


int Tree::getSize() const {

  return size;

}


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

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

  if (subRoot == NULL) {

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

  } else {

    // we want valueString to contain the data value and balance factor
    // followed by a hyphen the following is ugly but does the job.
    formatter << (subRoot -> data) << "(" << (subRoot -> balance)
              << ")-" << 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 () const {

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

}


void Tree::rotateLL (TNode *&subRoot) {

  TNode *A = subRoot, *B;

  // debugging code
  if ((A -> balance != -2) || (A -> left == NULL) ||
      (A -> left -> balance != -1) ) {
    cout << "\nrotateLL used incorrectly\n.";
    return;
  }
  cout << "\nPerforming an LL rotation at node containing "
       << A -> data << endl;

  // locate the second node of interest
  B = A -> left;

  // adjust balance factors
  B -> balance = A -> balance = 0;

  // do the pointer surgery
  A -> left = B -> right;
  B -> right = A;
  subRoot = B;

}


void Tree::rotateLR (TNode *&subRoot) {

  TNode *A = subRoot, *B, *C;

  // debugging code
  if ((A -> balance != -2) || (A -> left == NULL) ||
      (A -> left -> balance != 1) || (A -> left -> right == NULL) ) {
    cout << "\nrotateLR used incorrectly\n.";
    return;
  }
  cout << "\nPerforming an LR rotation at node containing "
       << A -> data << endl;

  // locate the other nodes of interest
  B = A -> left; C = B -> right;

  // adjust balance factors
  if (C -> balance == 1) {
    A -> balance = 0; B -> balance = -1;
  } else if (C -> balance == -1) {
    A -> balance = 1; B -> balance = 0;
  } else {
    A -> balance = B -> balance = 0;
  }
  C -> balance = 0;

  // do the pointer surgery
  A -> left = C -> right;
  B -> right = C -> left;
  C -> right = A; C -> left = B;
  subRoot = C;

}


void Tree::rotateRR (TNode *&subRoot) {

  TNode *A = subRoot, *B;

  // debugging code
  if ((A -> balance != 2) || (A -> right == NULL) ||
      (A -> right -> balance != 1) ) {
    cout << "\nrotateRR used incorrectly\n.";
    return;
  }
  cout << "\nPerforming an RR rotation at node containing "
       << A -> data << endl;

  // locate the second node of interest
  B = A -> right;

  // adjust balance factors
  B -> balance = A -> balance = 0;

  // do the pointer surgery
  A -> right = B -> left;
  B -> left = A;
  subRoot = B;

}


void Tree::rotateRL (TNode *&subRoot) {

  TNode *A = subRoot, *B, *C;

  // debugging code
  if ((A -> balance != 2) || (A -> right == NULL) ||
      (A -> right -> balance != -1) || (A -> right -> left == NULL) ) {
    cout << "\nrotateRL used incorrectly\n.";
    return;
  }
  cout << "\nPerforming an RL rotation at node containing "
       << A -> data << endl;

  // locate the other nodes of interest
  B = subRoot -> right; C = B -> left;

  // adjust balance factors
  if (C -> balance == -1) {
    A -> balance = 0; B -> balance = 1;
  } else if (C -> balance == 1) {
    A -> balance = -1; B -> balance = 0;
  } else {
    A -> balance = B -> balance = 0;
  }
  C -> balance = 0;

  // do the pointer surgery
  A -> right = C -> left;
  B ->left = C -> right;
  C -> left = A; C -> right = B;
  subRoot = C;

}