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

}