/* approach1.cpp shows a first try at the implementation details
 *  of an O-O binary tree.
 *
 * It performs Insert() and Delete() by requiring that the pointer
 *  to the node containing Insert() be passed (as a reference),
 *  along with the value to be inserted.
 *
 * To avoid clutter, each approach is defined using typedef,
 *  instead of as a template, tho conversion is straightforward.
 *
 * This code may be freely copied and distributed, provided this
 * notice is included.
 *
 * Joel Adams, February 29, 1996.
 *             February 7, 2000: NonEmptyBST constructor bug fixed
 */

#include <iostream>
using namespace std;

typedef int BSTElem;

//******************** BST ********************************
class BST
{
 public:
  BST() {}
  virtual ~BST() {}

  virtual bool isEmpty() const = 0;
  virtual bool contains(const BSTElem & elem) const = 0;
  virtual BSTElem minimum() const = 0;

  virtual void insert(const BSTElem & elem, BST * & accessPtr) = 0;
  virtual void remove(const BSTElem & elem, BST * & accessPtr) = 0;

  void print(ostream & out = cout);
  virtual void printSideways(ostream & out, int level) const = 0;

 private:
  BST(const BST & original);              // disallow copying
  BST & operator=(const BST & original);  //  and assignment
};


//******************** NonEmptyBST ********************************
class NonEmptyBST : public BST
{
public:
  NonEmptyBST(const BSTElem & elem);
  NonEmptyBST(const BSTElem & elem, BST * leftChild, BST * rightChild);
  virtual ~NonEmptyBST();
  
  bool isEmpty() const;
  bool contains(const BSTElem & elem) const;
  BSTElem minimum() const;

  void insert(const BSTElem & elem, BST * & access);
  void remove(const BSTElem & elem, BST * & accessPtr);

  virtual void printSideways(ostream & out, int level) const;

private:  
  BSTElem data;
  BST * left;
  BST * right;
};


//******************** EmptyBST ********************************
class EmptyBST: public BST
{
public:
  EmptyBST() {}
  virtual ~EmptyBST() {}
  
  bool isEmpty() const;
  bool contains(const BSTElem & elem) const;
  BSTElem minimum() const;

  void insert(const BSTElem & elem, BST *  & accessPtr);
  void remove(const BSTElem & elem, BST * & accessPtr);

  virtual void printSideways(ostream & out, int level) const;
};


//**************** BST Functions ******************************

void BST::print(ostream & out)
{
  this->printSideways(out, 0);
}

//**************** NonEmptyBST Functions ******************************

NonEmptyBST::NonEmptyBST(const BSTElem & elem)
{
  data = elem;
  left = new EmptyBST();
  right = new EmptyBST();
}


NonEmptyBST::NonEmptyBST(const BSTElem & elem,
			   BST * leftChild,
			   BST * rightChild)
{
  data = elem;
  left = leftChild;
  right = rightChild;
}


NonEmptyBST::~NonEmptyBST()
{
  delete left;
  delete right;
}

bool NonEmptyBST::isEmpty() const
{
  return false;
}

bool NonEmptyBST::contains(const BSTElem & elem) const
{
  if (data == elem)
    return true;
  else if (data < elem)
    return left->contains(elem);
  else
    return right->contains(elem);
}

void NonEmptyBST::insert(const BSTElem & elem, BST * & access)
{
  if (data == elem)
    cerr << "\n*** " << elem << " is already in tree!\n" << endl;
  else if (elem < data)
    left->insert(elem, left);
  else
    right->insert(elem, right);
}

BSTElem NonEmptyBST::minimum() const
{
  if (left->isEmpty())
    return data;
  else
    return left->minimum();
}

void NonEmptyBST::remove(const BSTElem & elem, BST * & accessPtr)
{
  if (elem < data)
    left->remove(elem, left);
  else if (elem > data)
    right->remove(elem, right);
  else if (left->isEmpty() && right->isEmpty())    // no non-empty subtrees
    {
      BST * tempPtr = accessPtr;                   // save ptr to self
      accessPtr = left;                            // recycle left child
      delete right;                                // deallocate right child
      left = right = NULL;                         // deallocate self
      delete tempPtr;
    }
  else if (left->isEmpty())                       // 1 non-empty subtree (A)
    {
      BST * tempPtr = accessPtr;                  // save ptr to self
      accessPtr = right;                          // adjust parent ptr
      delete left;                                // delete EmptyBST
      left = right = NULL;                        // deallocate self
      delete tempPtr;
    }
  else if (right->isEmpty())                      // 1 non-empty subtree (B)
    {
      BST * tempPtr = accessPtr;                  // save ptr to self
      accessPtr = left;                           // reset parent ptr
      delete right;                               // delete EmptyBST
      left = right = NULL;                        // deallocate self
      delete tempPtr;
    }
  else                                        // 2 non-empty subtrees
    {
      data = right->minimum();                // change self to
                                              //  next biggest value
      right->remove(data, right);             // remove that value from right
    }
}
     
void NonEmptyBST::printSideways(ostream & out, int level) const
{
  right->printSideways(out, level+1);
  for (int i = 0; i < level; i++)
    out << "     ";
  out << data << endl;
  left->printSideways(out, level+1);
}

//##################### EmptyBST Functions ########################

bool EmptyBST::isEmpty() const
{
  return true;
}

bool EmptyBST::contains(const BSTElem & ) const
{
    return false;
}

BSTElem EmptyBST::minimum() const
{
  cerr << "\nminimum(): BST is empty!\n" << endl;
  return BSTElem(0);
}
  
void EmptyBST::insert(const BSTElem & elem, BST * & accessPtr)
{
  BST * tempPtr = accessPtr;         // save parent ptr 
  accessPtr = new NonEmptyBST(elem, tempPtr, new EmptyBST);
}

void EmptyBST::remove(const BSTElem & elem, BST * & accessPtr)
{
  cerr << "\nremove(): " << elem << " not found!" << endl;
}

void EmptyBST::printSideways(ostream & out, int level) const
{
  for (int i = 0; i < level; i++)
    out << "     ";
  out << '#' << endl;
}


//******************* main *************************************
int main()
{
  BST *theTree = new EmptyBST;
  
  theTree->print();
  
  theTree->insert(4, theTree);
  theTree->insert(2, theTree);
  theTree->insert(6, theTree);
  theTree->insert(1, theTree);
  theTree->insert(3, theTree);
  theTree->insert(5, theTree);
  theTree->insert(7, theTree);

  theTree->print();
  cout << "\n--- removing 4 -----------------------------------\n";
  theTree->remove(4, theTree);
  theTree->print();
  cout << "\n--- removing 3 ----------------------------------\n";
  theTree->remove(3, theTree);
  theTree->print();
  cout << "\n--- removing 6 ----------------------------------\n";
  theTree->remove(6, theTree);
  theTree->print();
}