/*
  Travis Gadberry
  Patrick Hesser
  Chris Ladewig

  UnbalancedBinaryTree.h
  21Mar05
*/

#ifndef UNBALANCED_BINARY_TREE_H
#define UNBALANCED_BINARY_TREE_H

        #include "dsexceptions.h"
        #include <iostream>       // For NULL
        #include <vector>
        #include <time.h>

        using namespace std;

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

        template <class Comparable>
        class BinariNode
        {
            Comparable element;
            BinariNode *left;
            BinariNode *right;

            BinariNode( const Comparable & theElement, BinariNode *lt, BinariNode *rt )
              : element( theElement ), left( lt ), right( rt ) { }
            friend class UnbalancedBinaryTree<Comparable>;
        };


        // UnbalancedBinaryTree 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
        // Comparable findMax( )  --> Return largest 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 UnbalancedBinaryTree
        {
          public:
            explicit UnbalancedBinaryTree( const Comparable & notFound );
            UnbalancedBinaryTree( const UnbalancedBinaryTree & rhs );
            ~UnbalancedBinaryTree( );

            const Comparable & findMin( ) const;
            const Comparable & findMax( ) const;
            const Comparable & find( const Comparable & x );
            bool isEmpty( ) const;
            void printTree( ) const;

            void makeEmpty( );
            void insert( const Comparable & x );
            void remove( const Comparable & x );
            int getIncrements();
            double getCreationTime();
            double getSearchTime();
            void insertIntArray(int *, int);
            void insertIntVector(vector<int>);
            void resetIncrements();

            const UnbalancedBinaryTree & operator=( const UnbalancedBinaryTree & rhs );

          private:
            BinariNode<Comparable> *root;
            const Comparable ITEM_NOT_FOUND;

            const Comparable & elementAt( BinariNode<Comparable> *t ) const;

            void insert( const Comparable & x, BinariNode<Comparable> * & t );
            void remove( const Comparable & x, BinariNode<Comparable> * & t ) const;
            BinariNode<Comparable> * findMin( BinariNode<Comparable> *t ) const;
            BinariNode<Comparable> * findMax( BinariNode<Comparable> *t ) const;
            BinariNode<Comparable> * find( const Comparable & x, BinariNode<Comparable> *t );
            void makeEmpty( BinariNode<Comparable> * & t ) const;
            void printTree( BinariNode<Comparable> *t ) const;
            BinariNode<Comparable> * clone( BinariNode<Comparable> *t ) const;

			int increments;
			double creationTime, searchTime;
        };


#endif