// binstree.cpp

#include "bstree.h"
#include <stdlib.h>

// Constructor for information class
information::information(char* wd, int pnum) {
   w = wd;
   pagenum = pnum;
}

void information::load(char* wd, int pnum) {
   w = wd;
   pagenum = pnum;
}

// Constructor for bstnode class
bstnode::bstnode(information item) {
   char* wd = item.word();
   key = new char[strlen(wd) + 1];
   strcpy(key, wd);
 
   data = new queue;
   data->insert(item.pagenumber());

   left = NULL;
   right = NULL;
}

void binstree::insert(information item) {
   bstnode *current, *previous;

   bstnode *found = srch(root, item.word());
   // Insert only page number if the node is already in the tree.
   if (found != NULL) {
      found->data->insert(item.pagenumber());
      return;
   }

   // Inserting non-existing nodes, first adjust pointers
   // to the correct position:
   current = root;                  
   previous = NULL;
   while (current != NULL)    {              // Search for leaf
      previous = current;
      if (strcmp(item.word(), current->key) < 0)
         current = current->left;
      else
         current = current->right;
   }

   if (previous == NULL)                     // Null tree?     
      addroot(item);
   else if (strcmp(item.word(), previous->key) < 0)
      addleft(previous, item);               // Add to left
   else                              
      addright(previous, item);              // Add to right
}

void binstree::addroot(information item) {
   bstnode *newNode = new bstnode(item);
   root = newNode;
   newNode->left = newNode->right = NULL;
}

void binstree::addleft(bstnode *p, information item) {
   bstnode *newNode = new bstnode(item);
   p->left = newNode;
}

void binstree::addright(bstnode *p, information item) {
   bstnode *newNode = new bstnode(item);
   p->right = newNode;
}

boolean binstree::search(char* itemkey) const {
   bstnode *nodeFound = srch(root, itemkey);
   
   return (nodeFound != NULL);
}

bstnode* binstree::srch(bstnode *p, char* itemkey) const {
   if (p != NULL) {
      if (strcmp(itemkey, p->key) == 0)
         return p;
      else if (strcmp(itemkey, p->key) < 0)
         return srch(p->left, itemkey);
      else 
         return srch(p->right, itemkey);
   } else 
      return NULL;
}

void binstree::retrieve(char* itemkey, int*& itemdata) const {
   int count, anItem;
   bstnode* target = srch(root, itemkey);

   if (target == NULL) {
      cout << "NOTFOUND !" << endl;
   } else {
      // A match is found
      queue* q = target->data; 
      // Copy all the entries in the queue to itemdata int array
      for (count = 0; count < q->length(); count++) {
         itemdata[count] = q->front();
         anItem = q->remove();
         q->insert(itemdata[count]);
      }  // end of for loop.
   }
}

// Removes the node which contains the itemkey from the tree
void binstree::remove(char* itemkey) {
   bstnode* cursor = root;
 
   // If the root contains the itemkey
   if ( ! strcmp(itemkey, root->key) ) {
      removenode(root);
      return;
   }

   while (cursor != NULL) {
      if ( cursor->left != NULL &&
           strcmp(itemkey, cursor->left->key) == 0) {
         removenode(cursor->left);
         return;
      } else if ( cursor->right != NULL &&
           strcmp(itemkey, cursor->right->key) == 0) {
         removenode(cursor->right);
         return;
      } else if (strcmp(itemkey, cursor->key) < 0) {
         cursor = cursor->left;
      } else //strcmp(itemkey, cursor->key) > 0 
         cursor = cursor->right;
   }  // end of while loop.
}  // end of method remove().

// Private: Removes the node pointed by pointer p which is the left
//          or right pointer of the node's parent.
void binstree::removenode(bstnode*& p) {
   bstnode* target = p; //target also points to the to-be-removed node.

   if ((p->left == NULL) && (p->right == NULL)) { 
      // Removing a leaf node.
      p = NULL;
   } else if ((p->left != NULL) && (p->right == NULL)) { 
      // Removing a node with left child only
      p = p->left;
   } else if (p->right != NULL && p->left == NULL) {
      // Removing a node with right child only
      p = p->right;
   } else if (p->left != NULL && p->right != NULL) {
      // Removing a node with two children
      // first moves to the left child of the node to be removed
      bstnode* current = p->left;
      bstnode* parent = current;
  
      // Move repeatedly to the right child until a leaf node is reached
      // or a node with only left chile is reached.
      while ((current != NULL) && (current->right != NULL)) {
         parent = current;
         current = current->right;
      }

      // Handles a special case
      if ( parent == current) {
         current->right = p->right;
         p = current;
      } else {
         // Lets the node pointed by current be the subinstreeitute for the 
         // node to be removed.
         parent->right = current->left;
         current->left = p->left;
         current->right = p->right;
         p = current;
      }
   }  // end of else if.
   delete target;
}

// Traverses the tree in one of the three ordertraversals: preoreder, 
// inordertraversal or postordertraversal.
void binstree::traverse(travtype ordertraversal) {
   if (ordertraversal == PREORDER)
      preordertraversal(root);
   else if (ordertraversal == INORDER) {
      inordertraversal(root);
   } else // (ordertraversal == POSTORDER)
      postordertraversal(root);

   cout << endl;
}

// Private: Traverse the tree in preordertraversal
void binstree::preordertraversal(bstnode* p) {
   if (p!=NULL) {
      p->see();
      preordertraversal(p->left);
      preordertraversal(p->right);
   }
}

// Private: Traverse the tree in inordertraversal
void binstree::inordertraversal(bstnode* p) {
   if (p!=NULL) {
      inordertraversal(p->left);
      if (p->key[0] != keyLetter) {;
         keyLetter = p->key[0];
//cout << "the keyLetter = " << keyLetter << " key = " << p->key << endl;
         cout << endl << keyLetter << endl << endl;
      }
      p->see();
      inordertraversal(p->right);
   }
}

// Private: Traverse the tree in postordertraversal
void binstree::postordertraversal(bstnode* p) {
   if (p!=NULL) {
      postordertraversal(p->left);
      postordertraversal(p->right);
      p->see();
   }
}

// Private: Deallocate the space for each node in postordertraversal.
void binstree::postorderdissolve(bstnode*& p) {
   if (p!=NULL) {
      postorderdissolve(p->left);
      postorderdissolve(p->right);
      delete p;
      p = NULL; 
   }
}

// =========== binstree Test class ==========

bstTest::bstTest() {
}