/************************************************
   BinarySearchTree.C
   CMSC-341  Spring 2004 Project3
   Spencer Shimko, Section 001, sshimko1
   Created:  13 March 2004
   Current:  28 March 2004

   Header for modified Weiss's code to implement weight balance
   findMedian, special weight insert

I have read and I understand the course policy on cheating. By submitting the following program, I
am stating that the program was produced by my individual effort. 
***************************************************/

#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_

#include <iostream>       // For NULL
using namespace std;

// Binary node and forward declaration because g++ does
// not understand nested classes.
template <class Comparable>
class BinarySearchTree;

// Binary node of comparable type
template <class Comparable>
class BinaryNode
{
      // element in node
      Comparable element;
      // weight of this node
      int weight;
      // left an right subtrees
      BinaryNode *left;
      BinaryNode *right;
      
      // constructor 
      BinaryNode( const Comparable & theElement, int weight, BinaryNode *lt, BinaryNode *rt )
	 : element( theElement ), weight (weight), left( lt ), right( rt ) { }
      BinaryNode () {}
      friend class BinarySearchTree<Comparable>;
};


// BinarySearchTree class
//
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// Comparable find( x )   --> Return item that matches x
// Comparable findMin( )  --> Return smallest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order

template <class Comparable>
class BinarySearchTree
{
   public:
      explicit BinarySearchTree( const Comparable & notFound);
      BinarySearchTree( const BinarySearchTree & rhs );
      ~BinarySearchTree( );

      /**
       * Find the median value in the tree
       * Return: comparable value which is median of tree
       */
      const Comparable & findMedian( ) const;
 
      /**
       * weight balance the current bst
       */ 
      void weightBalance( ); 

      /**
       * Print the tree contents in sorted order.
       *  Param height: depth to print
       */
      int printTree( int h );

      /**
       * Return height of tree
       */
      int height( );

      // return minimum in tree 
      const Comparable & findMin( ) const;
      // remove element from tree
      void remove( const Comparable & x );
      // return true if tree is empty false otherwise
      bool isEmpty( ) const;
      // make tree empty
      void makeEmpty( );
      // insert comparable into tree
      bool insert( const Comparable & x );
      
      // assignment operator
      const BinarySearchTree & operator=( const BinarySearchTree & rhs );
      
   private:
      BinaryNode<Comparable> *root;
      Comparable ITEM_NOT_FOUND;
      const Comparable & elementAt( BinaryNode<Comparable> *t ) const;

      void weightBalance( BinarySearchTree & bt );
      const Comparable & findMedian( BinaryNode<Comparable> & t ) const;
      int printTree( BinaryNode<Comparable> *t, int h );

      void remove( const Comparable & x, BinaryNode<Comparable> * & t ) const;
      BinaryNode<Comparable> * findMin( BinaryNode<Comparable> *t ) const;
      bool insert( const Comparable & x, BinaryNode<Comparable> * & t ) const;
      void makeEmpty( BinaryNode<Comparable> * & t ) const;
      BinaryNode<Comparable> * clone( BinaryNode<Comparable> *t ) const;
};

#include "BinarySearchTree.C"
#endif