/* approach2.cpp shows a second approach to the implementation details
 *  of an O-O binary tree.
 *
 * Instead of requiring the passing of the access pointer
 *  to Insert() and remove(), this approach requires that
 *  a node 'know' the address of the access pointer
 *  (this address being stored in the BST base class).
 *
 * By passing the address of the access pointer to the constructor(s),
 * this approach only requires it to be passed once instead of each
 * time Insert() or remove() is called...
 *
 * This code may be freely copied and distributed, provided this
 * notice is included.
 *
 * Joel Adams, March 5, 1996.
 *             February 7, 2000: NonEmptyBST constructor bug fixed.
 */

#include <iostream>
using namespace std;

typedef int BSTElem;

// *********************** BST ****************************
class BST
{
 public:
  BST(BST * * parent);
  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) = 0;
  virtual bool remove(const BSTElem & elem) = 0;

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

  // protected:
  void setParentsPtrAddress(BST * * newParentsPtrAddr);
  BST * * getParentsPtrAddress() const;

  void setParentsPtr(BST * newParentsPtr);
  BST * getParentsPtr() const;
  
private:
  
  BST * * myParentsPtrAddress;

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

// *********************** NonEmptyBST ****************************
class NonEmptyBST : public BST
{
public:
  NonEmptyBST(BST * * parentsPtrAddress, const BSTElem & elem);
  NonEmptyBST(BST * * ParentsPtrAddress, const BSTElem & elem,
	      BST * leftChild, BST * rightChild);
  ~NonEmptyBST();
  
  bool isEmpty() const;
  bool contains(const BSTElem & elem) const;
  BSTElem minimum() const;
  
  void insert(const BSTElem & elem);
  bool remove(const BSTElem & elem);

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

  BST * getLeft() const;
  BST * getRight() const;
  BST * * getLeftAddr();
  BST * * getRightAddr();
  void setLeft(BST * newLeft);
  void setRight(BST * newRight);

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

  // disllow copying and assignment
  NonEmptyBST(const NonEmptyBST & original);
  NonEmptyBST & operator=(const NonEmptyBST & original);
};



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

  void insert(const BSTElem & elem);
  bool remove(const BSTElem & elem);

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

private:
    // disllow copying and assignment
  EmptyBST(const EmptyBST & original);
  EmptyBST & operator=(const EmptyBST & original);
};


// ###################### BST Functions ##########################

BST::BST(BST * * parentsPtrAddress)
{
  myParentsPtrAddress = parentsPtrAddress;
}

void BST::setParentsPtrAddress(BST * * newParentsPtrAddress)
{
  myParentsPtrAddress = newParentsPtrAddress;
}

void BST::setParentsPtr(BST * newParentsPtr)
{
  *myParentsPtrAddress = newParentsPtr;
}


BST * * BST::getParentsPtrAddress() const
{
  return myParentsPtrAddress;
}

BST * BST::getParentsPtr() const
{
  return *myParentsPtrAddress;
}

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

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

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

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

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

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

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


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

bool NonEmptyBST::remove(const BSTElem & elem)
{
  if (elem < data)
    return left->remove(elem);
  else if (elem > data)
    return right->remove(elem);
  else if (left->isEmpty() && right->isEmpty())            // 2 empty subtrees
    {
      BST * tempPtr = getParentsPtr();             
      setParentsPtr(new EmptyBST(getParentsPtrAddress())); // save parent ptr
      delete left;                                         // delete EmptyBSTs
      delete right;
      left = right = NULL;                                 // delete self
      delete tempPtr;
    }
  else if (left->isEmpty())                                // only left empty
    {
      BST * tempPtr = getParentsPtr();                     // save parent ptr
      setParentsPtr(right);                                // reset parent ptr
      right->setParentsPtrAddress(getParentsPtrAddress()); // fix right.parent
      delete left;                                         // delete left
      left = right = NULL;                                 // delete self
      delete tempPtr;
    }
  else if (right->isEmpty())                               // only right empty
    {
      BST * tempPtr = getParentsPtr();                     // save parent ptr
      setParentsPtr(left);                                 // reset parent ptr
      left->setParentsPtrAddress(getParentsPtrAddress());  // fix left.parent
      delete right;                                        // delete right
      left = right = NULL;                                 // delete self
      delete tempPtr;
    }
  else                                    // 2 non-empty subtrees
    {
      data = right->minimum();            // change my value to
                                          //   next biggest value
      right->remove(data);                // remove that value from right
    }
  return true;
}

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


BST * NonEmptyBST::getLeft() const
{
  return left;
}

BST * NonEmptyBST::getRight() const
{
  return right;
}

BST * * NonEmptyBST::getLeftAddr()
{
  return &left;
}

BST * * NonEmptyBST::getRightAddr()
{
  return &right;
}

void NonEmptyBST::setLeft(BST * newLeft)
{
  if (newLeft != NULL)
    left = newLeft;
}

void NonEmptyBST::setRight(BST * newRight)
{
  if (newRight != NULL)
    right = newRight;
}



// *********************** EmptyBST Functions  ****************************


EmptyBST::EmptyBST(BST * * ParentsPtrAddress) : BST(ParentsPtrAddress)
{}

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

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

BSTElem EmptyBST::minimum() const
{
  cerr << "\nminimum: BST is empty!" << endl;
  return BSTElem(0);
}

void EmptyBST::insert(const BSTElem & elem)
{
  // retrieve address of pointer to this node
  BST * * pPtrAddr = getParentsPtrAddress();
  
  // create new node containing elem, recycling *this as its left subtree.
  NonEmptyBST * tempPtr = new NonEmptyBST(pPtrAddr, elem, this, NULL);
  
  // make my old parentsPtr point to the new NonEmpty node
  setParentsPtr(tempPtr);

  // make my parent pointer address the address of 'left' in the new node
  setParentsPtrAddress(tempPtr->getLeftAddr());
  
  // create a new EmptyBST for the 'right' child
  tempPtr->setRight( new EmptyBST(tempPtr->getRightAddr()));
 }

bool EmptyBST::remove(const BSTElem & elem)
{
  cerr << "\nremove: " << elem << " not found!" << endl;
  return false;
}


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

  theTree->printSideways(cout);
  cout << "\n----------------------------------\n" << endl;
  
  theTree->insert(4);
  theTree->insert(2);
  theTree->insert(6);
  theTree->insert(1);
  theTree->insert(3);
  theTree->insert(5);
  theTree->insert(7);
  theTree->printSideways(cout);

  cout << "--- removing 4 -------------------------------" << endl;
  theTree->remove(4);
  theTree->printSideways(cout);

  cout << "--- removing 3 -------------------------------" << endl;
  theTree->remove(3);
  theTree->printSideways(cout);

  cout << "--- removing 6 -------------------------------" << endl;
  theTree->remove(6);
  theTree->printSideways(cout);
}