/* #################################
   # Programmer: Tim Glasgow       #
   # Date Started: March 15, 2016  #
   # Last Commit: March 18, 2016   #
   # Purpose: Implement simple BST #
   # Environment: Linux/GNU        #
   # Version: 1.0.3                #
   #################################
*/

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;


/* ####################################
   # Name: printStuff                 #
   # Signature: 1a                    #
   # Purpose: Make cout more readable #
   ####################################
*/
void printStuff(string output, unsigned char numericCharacter, unsigned char mode) 
{
  if (mode == 0)
  {
    cout << output << endl;

    return;
  } //end if

  else
  {
    cout << output << (int)numericCharacter << endl;
    return;
  } //end else
} //end printStuff


/* ####################################
   # Name: node                       #
   # Signature: 1b                    #
   # Purpose: Implement tree node     #
   ####################################
*/
class node
{
  public:
    unsigned char key;
    node *parent = NULL;
    node *leftChild = NULL;
    node *rightChild = NULL;

    bool isRoot; //0 is not root, 1 is root
    bool side; //0 for left of parent, 1 for right of parent
    bool parentEmpty() const { return parent==NULL; }
    bool leftEmpty() const { return leftChild==NULL; }
    bool rightEmpty() const { return rightChild==NULL; }

}; //end class Node


/* ####################################
   # Name: binaryTree                 #
   # Signature: 1c                    #
   # Purpose: Implement all functions #
   #          of a binary search tree #
   ####################################
*/
class binaryTree
{
  public:
    node *root = NULL;
    bool rootEmpty() const { return root==NULL; }


/*  ####################################
    # Name: insertNode                 #
    # Signature: 1c-a                  #
    # Purpose: Insert node into tree   #
    ####################################
*/
    binaryTree insertNode( binaryTree &theTree, node &insertion, node *examinedNode, unsigned char keyIn )
    {
      if ( theTree.rootEmpty())
      {
        insertion.key = keyIn;
        insertion.isRoot = 1;
        theTree.root = &insertion;
        return theTree; //end if
      }//end if
      else
      {
        if ( examinedNode->key <= keyIn )
        {
          if (examinedNode->rightEmpty())
          {
            insertion.key = keyIn;
            insertion.side = 1;
            insertion.isRoot = 0;
            examinedNode->rightChild = &insertion;
            examinedNode->rightChild->parent = examinedNode;
            return theTree;
          }//end 2nd nested if
          else
          {
            theTree = theTree.insertNode( theTree, insertion, examinedNode->rightChild, keyIn);
            return theTree;
          }//end 2nd nested else
        }//end nested if
        else
        {
          if (examinedNode->leftEmpty())
          {
            insertion.key = keyIn;
            insertion.side = 0;
            insertion.isRoot = 0;
            examinedNode->leftChild = &insertion;
            examinedNode->leftChild->parent = examinedNode;
            return theTree;
          }//end 2nd nested if
          else
          {
            theTree = theTree.insertNode( theTree, insertion, examinedNode->leftChild, keyIn);
            return theTree;
          }//end 2nd nested else
        }//end nested else
      }//end else

      return theTree;
    }//end insertNode


/*  #####################################
    # Name: searchTree                  #
    # Signature: 1c-b                   #
    # Purpose: Find and return key node #
    #####################################
*/
    node *searchTree( binaryTree &theTree, node *searchedNode, unsigned char keySearch )
    {
      if ( theTree.rootEmpty() ){
        printStuff("Empty tree, no values found", 0, 0); //1a
        return searchedNode;
      }//end if

      if ( searchedNode->key == keySearch)
      {
        printStuff ("value found", 0, 0); //1a
        node *returnedNode = searchedNode; //1b
        searchedNode = NULL;
        return returnedNode;
      }//end if
      else
      {
        if ( (searchedNode->key < keySearch) && !(searchedNode->rightEmpty()) )
        {
          searchedNode = searchTree( theTree, searchedNode->rightChild, keySearch); //1c-b
          return searchedNode;
        }//end nested if
        else if ( (searchedNode->key > keySearch) && !(searchedNode->leftEmpty()) )
        {
          searchedNode = searchTree( theTree, searchedNode->leftChild, keySearch); //1c-b
          return searchedNode;
        }//end nested else-if
      }//end else

      printStuff("value not found", 0, 0); //1a
    }//end searchTree


/*  ######################################
    # Name: deleteNode                   #
    # Signature: 1c-c                    #
    # Purpose: Remove key node from tree #
    ######################################
*/
    binaryTree deleteNode( binaryTree &theTree, node *deletionNode, unsigned char keyDel )
    {
      if ( theTree.rootEmpty())
      {
        printStuff("Deletion node not found in tree", 0, 0);
        return theTree; //end if
      }//end if
      else
      {
        deletionNode = theTree.searchTree( theTree, deletionNode, keyDel ); //1b, 1c-b
      }//end else

      if ( (deletionNode->leftEmpty()) && (deletionNode->rightEmpty()) )
      {
        printStuff("Children are empty, deleting node", 0, 0); //1a
        if(!deletionNode->isRoot)
        {
          if (deletionNode->side)
          {
            deletionNode->parent->rightChild = NULL;
          }//end 2nd nested if
          else
          {
            deletionNode->parent->leftChild = NULL;
          }//end 2nd nested else
        }//end nested if
        else
        {
          printStuff("the tree is now empty", 0, 0); //1a
          theTree.root = NULL;
        }//end nested else
         deletionNode->parent = NULL;
        return theTree;
      }//end if

      if ( deletionNode->leftEmpty() && !deletionNode->rightEmpty() )
      {
        printStuff("Has right child, deleting node", 0, 0); //1a
        if(!deletionNode->isRoot)
        {
          if (deletionNode->side)
          {
            deletionNode->parent->rightChild = deletionNode->rightChild;
            deletionNode->parent->rightChild->side = deletionNode->side;
            deletionNode->rightChild->parent = deletionNode->parent;
          }//end 2nd nested if
          else
          {
            deletionNode->parent->leftChild = deletionNode->rightChild;
            deletionNode->rightChild->parent = deletionNode->parent;
            deletionNode->parent->leftChild->side = deletionNode->side;
          }//end 2nd nested else
        }//end nested if
        else
        {
          deletionNode->rightChild->isRoot = 1;
          deletionNode->rightChild->parent = NULL;
          theTree.root = deletionNode->rightChild;
        }//end nested else

        deletionNode->parent = NULL;
        return theTree;
      }//end if

      if ( !deletionNode->leftEmpty() && deletionNode->rightEmpty() )
      {
        printStuff("Has left child, deleting node", 0, 0);
        if(!deletionNode->isRoot)
        {
          if (deletionNode->side)
          {
            deletionNode->parent->rightChild = deletionNode->leftChild;
            deletionNode->rightChild->parent = deletionNode->parent;
            deletionNode->parent->rightChild->side = deletionNode->side;
          }//end 2nd nested if
          else
          {
            deletionNode->parent->leftChild = deletionNode->leftChild;
            deletionNode->leftChild->parent = deletionNode->parent;
            deletionNode->parent->leftChild->side = deletionNode->side;
          }//end 2nd nested else
        }//end nested if
        else
        {
          deletionNode->leftChild->isRoot = 1;
          deletionNode->leftChild->parent = NULL;
          theTree.root = deletionNode->leftChild;  
        }//end nested else
        deletionNode->parent = NULL;
        return theTree;
      }//end if

      if ( !deletionNode->leftEmpty() && !deletionNode->rightEmpty() )
      {
        printStuff("Has two children, deleting node and replacing with right minimum", 0, 0); //1a
        node *rightMin = theTree.findRightMin(deletionNode->rightChild); //1b, 1c-d
        unsigned char tempKey = rightMin->key;
        rightMin = deletionNode;
        rightMin->key = tempKey;
      }//end if

      return theTree;
    }//end deleteNode


/*  ####################################
    # Name: findRightMin               #
    # Signature: 1c-d                  #
    # Purpose: Find min value in right #
    #           sub-tree               #
    ####################################
*/
    node *findRightMin(node *minNode)
    {
      if( minNode->leftEmpty() )
      {
        node *returnedNode = minNode; //1b
        minNode = NULL;
        return returnedNode;
      }//end if
      else
      {
        minNode = findRightMin(minNode->leftChild); //1c-d
        return minNode;
      }//end else
    }//end minNode;


}; //end class binaryTree


int main()
{
  printStuff("program initialized", 0, 0); //1a

  printStuff("creating the tree", 0, 0); //1a
    binaryTree myTree; //1c
    printStuff("tree created" ,0 ,0); //1a

  printStuff("creating insertion nodes" ,0 ,0); //1a
    node insertionNode[128]; //1b
    printStuff("node created", 0, 0); //1a

  printStuff("inserting nodes", 0, 0); //1a

  myTree = myTree.insertNode(myTree, insertionNode[24], myTree.root, 25); //1c-a
    printStuff("Tree Root Value is Now: ", myTree.root->key, 1); //1a

  printStuff("Inserting nodes", 0, 0); //1a
  myTree = myTree.insertNode(myTree, insertionNode[0], myTree.root, 3); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[1], myTree.root, 7); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[2], myTree.root, 2); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[3], myTree.root, 4); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[4], myTree.root, 5); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[5], myTree.root, 6); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[6], myTree.root, 9); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[7], myTree.root, 1); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[8], myTree.root, 8); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[9], myTree.root, 10); //1c-a

  myTree = myTree.insertNode(myTree, insertionNode[10], myTree.root, 13); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[11], myTree.root, 17); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[12], myTree.root, 12); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[13], myTree.root, 14); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[14], myTree.root, 15); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[15], myTree.root, 16); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[16], myTree.root, 19); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[17], myTree.root, 11); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[18], myTree.root, 18); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[19], myTree.root, 20); //1c-a

  myTree = myTree.insertNode(myTree, insertionNode[20], myTree.root, 23); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[21], myTree.root, 27); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[22], myTree.root, 22); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[23], myTree.root, 24); //1c-a
  //myTree = myTree.insertNode(myTree, insertionNode[24], myTree.root, 25); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[25], myTree.root, 26); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[26], myTree.root, 29); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[27], myTree.root, 21); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[28], myTree.root, 28); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[29], myTree.root, 30); //1c-a

  myTree = myTree.insertNode(myTree, insertionNode[30], myTree.root, 33); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[31], myTree.root, 37); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[32], myTree.root, 32); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[33], myTree.root, 34); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[34], myTree.root, 35); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[35], myTree.root, 36); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[36], myTree.root, 39); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[37], myTree.root, 31); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[38], myTree.root, 38); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[39], myTree.root, 40); //1c-a

  myTree = myTree.insertNode(myTree, insertionNode[40], myTree.root, 43); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[41], myTree.root, 47); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[42], myTree.root, 42); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[43], myTree.root, 44); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[44], myTree.root, 45); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[45], myTree.root, 46); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[46], myTree.root, 49); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[47], myTree.root, 41); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[48], myTree.root, 48); //1c-a
  myTree = myTree.insertNode(myTree, insertionNode[49], myTree.root, 50); //1c-a

  for (unsigned char i = 0; i < 50; i++)
  {
    printStuff("Searching for: ", i+1, 1); //1a
    myTree.searchTree( myTree, myTree.root, i+1); //1c-b
  }//end for loop

  for (unsigned char i = 0; i < 50; i++)
  {
    printStuff("Deleting key: ", i+1, 1); //1a
    myTree = myTree.deleteNode(myTree, myTree.root, i+1); //1c-c
    if(!myTree.rootEmpty() )
      printStuff("Root value is now: ", myTree.root->key, 1); //1a
  }//end for loop
  
  for (unsigned char i = 0; i < 50; i++)
  {
    printStuff("Searching for: ", i+1, 1); //1a
    myTree.searchTree( myTree, myTree.root, i+1); //1c-b
  }//end for loop

} //end main