// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- // 
// C++ Source Code File Name: tree.cpp
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced by: Doug Gaer
// File Creation Date: 11/07/1996
// Date Last Modified: 03/17/1999
// ----------------------------------------------------------- // 
// ------------- Program description and details ------------- // 
// ----------------------------------------------------------- // 
/*
THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

This is a simple class implementation of a binary search tree
used to create a tree of character strings. The char * data type
in the TreeNode class is used as a pointer to a pre-allocated
strings. The tree structure itself stores a hierarchal collection
of nodes. Each node stores a pointer to a unique character string
along with left and right pointers to other nodes in the tree.
*/
// ----------------------------------------------------------- // 
#include <iostream.h>
#include <string.h>

class Tnode; // Forward class name

// VisitFunc is a pointer to void(Tnode *Node) that points to
// a visit function used to process node data during tree traversals
typedef void (*VisitFunc)(Tnode *Node); 

// (T)ree (N)ode base class
class Tnode
{
public:
  Tnode() { right = left = 0; data = 0; }
  Tnode(char *key, Tnode *l = 0, Tnode *r = 0) {
    data = strdup(key); left = l; right = r; 
  }
  
public:
  char *data;   // data for this tree 
  Tnode *right; // subtree to the right 
  Tnode *left;  // subtree to the left 
};

// Binary Search (T)ree class
class Tree : public Tnode
{
public:
  Tree() { root = 0; }
  ~Tree() { Clear(); }
  Tree(const Tree &t) { this->Copy(t); }
  void operator=(const Tree &t) { this->Copy(t); }
  
public:
  int Add(char *key);
  int Remove(char *key);
  int Find(char *key);
  void Clear();
  int Copy(const Tree &t);
  void PrintTree(VisitFunc Visit) { PrintInOrder(root, Visit); }
  int GetHeight() { return Height(root); }
  
private: // Functions for internal processing only
  Tnode *SearchForParent(Tnode *node, char *key, Tnode *&parent, int &side);
  Tnode *Insert(Tnode *&root, char *key, int &exists);
  Tnode *DetachNode(Tnode *&root, Tnode *node, Tnode *parent, int side);
  Tnode *GetParentOfSuccessor(Tnode *node);
  Tnode *Detach(Tnode *&root, char *key);
  int Delete(Tnode *&root, char *key);
  void PrintInOrder(Tnode *tree, VisitFunc Visit);
  void DeleteTree(Tnode *t);
  Tnode *DupTree(Tnode *t);
  int Height(Tnode *t);
  
private:
  Tnode *root; // Pointer to the top of the tree 
};

int Tree::Add(char *key)
// Add an entry to the tree. 
{
  int exists;
  Insert(root, key, exists);
  return exists == 0; // Return true if the key did not already exist
}

int Tree::Remove(char *key)
// Remove a node from the tree.
// Returns zero if the node does not exist.
{
  return Delete(root, key);
}

void Tree::Clear()
// Clear the tree.
{
  DeleteTree(root);
  root = 0;
}

int Tree::Find(char *key)
// Search the tree for matching entry 
{
  Tnode *parent;
  int side;

  // Search the tree
  Tnode *node = SearchForParent(root, key, parent, side);
 
  return node != 0; // Return true if the matching node is found
}

int Tree::Copy(const Tree &t)
// Copy tree t into the tree object that invoked the call. 
{
  Clear();
  Tnode *r = DupTree(t.root);

  if(r) {
    root = r; // Tree was copied from the bottom up
    return 1;
  }
  return 0; // Tree was not copied
}

Tnode *Tree::Insert(Tnode *&root, char *key, int &exists)
// Insert a new node into the tree. Returns the matching node,
// new or old and may modify the root pointer.
{
  Tnode *parent;
  int side;

  // Look for a place to insert the node
  Tnode *node = SearchForParent(root, key, parent, side);

  if(node == 0) { // Node does not exist in the tree
    node = new Tnode(key);
    if(parent) {
      if(side) parent->right = node; else parent->left = node;
    }
    else // No parent, so this is the new root
      root = node;
    
    exists = 0;
  }
  else
    exists = 1;

  return node;
}

Tnode *Tree::SearchForParent(Tnode *node, char *key, Tnode *&parent, int &side)
// Returns the parent of the matching node, as well as the node itself. 
// Each node to the left is smaller then the given node, and each node
// to right is larger.
{
  parent = 0;
  while(node) {
    if(strcmp(key, node->data) == 0) break;
    parent = node;
    if(strcmp(key, node->data) < 0) { // Node is smaller
      side = 0;
      node = node->left;
    }
    else { // Node is larger
      side = 1;
      node = node->right;
    }
  }
  return node;
}

Tnode *Tree::DetachNode(Tnode *&root, Tnode *node, Tnode *parent, int side)
// Detach the node with parent from the tree. The node is the left
// child if side equals zero or right child if side equals one.
// Returns a pointer to the node.
{
  Tnode *psucc; // Parent of successor
  Tnode *replacement;

  if(node) {
    if(node->left == 0 || node->right == 0) {
      // At lease one child is null, so use the other as the replacement
      replacement = (node->left) ? node->left : node->right;
    }
    else { // Neither child is null
      psucc = GetParentOfSuccessor(node); // Guaranteed not to be null
      if(psucc == node) { // Immediate successor
	replacement = psucc->right;
      }
      else {
	// Detach replacement from its current loaction and
        // relocate it to where node used to be
	replacement = psucc->left;
	psucc->left = psucc->left->right;
        replacement->right = node->right;
      }

      // Finish reloacting replacement to where node used to be
      replacement->left = node->left;
    }

    if(parent) { // Fix parent of node to point to replacement
      if(side)
        parent->right = replacement; else parent->left = replacement;
    }
    else root = replacement; // No parent, so node was the root
  }
  return node;
}

Tnode *Tree::GetParentOfSuccessor(Tnode *node)
// Used by the Tree::DetachNode() function to find the parent of
// the successor node. Returns zero if no successor is found.
{
  Tnode *parent = 0;

  // Go right once, then all the way to the left
  Tnode *q = node->right;
  if(q) {
    parent = node;
    while(q->left) {
      parent = q;
      q = q->left;
    }
  }
  return parent;
}

Tnode *Tree::Detach(Tnode *&root, char *key)
// Detaches the node matching key from the tree.
{
  int side;
  Tnode *parent, *node;
  node = SearchForParent(root, key, parent, side);
  return DetachNode(root, node, parent, side);
}

int Tree::Delete(Tnode *&root, char *key)
// Deletes the node from the tree. 
// Returns zero if the node does not exist.
{
  Tnode *node = Detach(root, key);
  delete node;
  return node != 0;
}

void Tree::DeleteTree(Tnode *t)
// Recursive function used to clear the tree from the bottom up.
{
  if(t == 0) return;
  if(t->left == 0) return; else DeleteTree(t->left);
  if(t->right == 0) return; else DeleteTree(t->right);
  delete t;
}

void Tree::PrintInOrder(Tnode *tree, VisitFunc Visit)
// Visit each node of tree Tree in in-order, (first the Left
// subtree, then the parent, then the Right subtree), with 
// tail recursion removed
{
  while(tree) {
    PrintInOrder(tree->left, Visit);
    Visit(tree);
    tree = tree->right;
  }
}

Tnode *Tree::DupTree(Tnode *t)
// Recursive function that to duplicates a tree using
// postorder traversal.
{
  if(t == 0) return 0;
  Tnode *l = DupTree(t->left);
  Tnode *r = DupTree(t->right);
  return new Tnode(t->data, l, r);
}

int Tree::Height(Tnode *t)
// The height of a tree is the maximum of the height of
// its two subtrees. Returns the hight of the tree.
{
  int h = 0;
  if(t != 0) {
    int lh = Height(t->left);
    int rh = Height(t->right);
    h = ((lh > rh) ? lh : rh) +1;
  }
  return h;
}

// Test program code starts here
// *********************************************************** //
char *InputData()
// Input a line of text from the console
{
  char buf[255];
  cout << "Input Data: ";
  cin.getline(buf, sizeof(buf));
  unsigned len = 0;
  for(unsigned i = 0; (buf[i] != ' ') && (buf[i] != '\0'); i++) len++;
  char *s = new char[len];
  s[len] = '\0';
  memmove(s, buf, len);
  return s;
}

void PrintNode(Tnode *node)
// Visit function used to print the node data to the console
{
  cout << node->data << endl;
}

void SkipToEol(istream &s)
// Used to clear istream
{
  char c;
  s.clear();
  while(s.get(c) && c != '\n') { ; }
}

int Quit()
// Terminate the program
{
  cout << "Exiting..." << endl;
  return 0;
}

void pause()
// Pause the program 
{
  cout << endl;
  cout << "Press enter to continue..." << endl;
  cin.get();
}

void Menu(void)
// List the program options
{
  cout << "(?)   Help (prints this menu)" << endl;
  cout << "(A)   Add an item to the tree" << endl;
  cout << "(B)   Build a tree of strings" << endl;
  cout << "(C)   Clear the tree" << endl;
  cout << "(D)   Delete an item from the tree" << endl;
  cout << "(F)   Find an item in the tree" << endl;
  cout << "(H)   Display the tree height" << endl;
  cout << "(L)   List tree items in order" << endl; 
  cout << "(Q)   Quit this program" << endl; 
}

// Create an array of words to load in the tree
const int Items = 5; // Adjust this number if any more items are added
char *TreeData[Items] = { "EASY", "COOK", "DELTA", "ABLE", "BAKER", };

int main()
// Test program's main thread of execution
{
  Menu(); // Display the options menu
  
  char key;
  char *key_buf;
  Tree tree;
  int i, rv = 1;

  while(rv) {
    if (!cin) { // Input is in fail state
       SkipToEol(cin); // Go to end of line
       if (!cin) {  // Can't fix
          cout << "Input stream is broken" << endl;
          return 0;
       }
    }
    cout << '>';
    cin >> key;
    if (!cin) continue; // Fix at top of loop
    switch(key) {
      case 'a' : case 'A' :
	SkipToEol(cin);
	key_buf = InputData();
	tree.Add(key_buf);
	break;

      case 'b' : case 'B' :
	SkipToEol(cin);
	  // Add the entries to the tree
	for(i = 0; i < Items; i++) {
	  // Exit loop if Items is greater then the number of array elements  
	  if(TreeData[i] == 0) break; // 0 means the array is empty
	  tree.Add(TreeData[i]);
	}
	break;

      case 'c' : case 'C' :
	SkipToEol(cin);
	tree.Clear();
	break;

      case 'd' : case 'D' :
	SkipToEol(cin);
	key_buf = InputData();
	if(tree.Remove(key_buf)) {
	  cout << "Removed " << key_buf << endl;
	}
	else {
	  cout << key_buf << " does not exists in the tree" << endl;
	}
	break;

      case 'f' : case 'F' :
	SkipToEol(cin);
	key_buf = InputData();
	if(tree.Find(key_buf)) {
	  cout << "Found entry " << key_buf << endl;
	}
	else {
	  cout << key_buf << " does not exists in the tree" << endl;
	}
	break;	

      case 'l' : case 'L' :
	SkipToEol(cin);
	tree.PrintTree(PrintNode);
	break;	 

      case 'h' : case 'H' :
	SkipToEol(cin);
	cout << "Height = " << tree.GetHeight() << endl;
	break;

      case 'q' : case 'Q' :
	rv = Quit();
	break;

      case '?' : 
	SkipToEol(cin);
	Menu();
	break;

      default:
        cout << "Unrecognized command" << endl;
    }
  }
  return 0;
}
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
