#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::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 inconcorrectly\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 inconcorrectly\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 inconcorrectly\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 inconcorrectly\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;

}