/*
  Travis Gadberry
  Patrick Hesser
  Chris Ladewig

  UnbalancedBinaryTree.cpp
  21Mar05
*/

#include "UnbalancedBinaryTree.h"

using namespace std;

        /**
         * Implements an unbalanced binary search tree.
         * Note that all "matching" is based on the < method.
		 * Note: Class makes use of interface of comparable parameter
         */

        /**
         * Construct the tree.
         */
        template <class Comparable>
        UnbalancedBinaryTree<Comparable>::UnbalancedBinaryTree( const Comparable & notFound ) :
          root( NULL ), ITEM_NOT_FOUND( notFound )
        {
        }


        /**
         * Copy constructor.
         */
        template <class Comparable>
        UnbalancedBinaryTree<Comparable>::
        UnbalancedBinaryTree( const UnbalancedBinaryTree<Comparable> & rhs ) :
          root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )
        { 
            *this = rhs;
        }

        /**
         * Destructor for the tree.
         */
        template <class Comparable>
        UnbalancedBinaryTree<Comparable>::~UnbalancedBinaryTree( )
        {
            makeEmpty( );
        }

        /**
         * Insert x into the tree; duplicates are ignored.
         */
        template <class Comparable>
        void UnbalancedBinaryTree<Comparable>::insert( const Comparable & x )
        {
            insert( x, root );
        }

        /**
         * Remove x from the tree. Nothing is done if x is not found.
         */
        template <class Comparable>
        void UnbalancedBinaryTree<Comparable>::remove( const Comparable & x )
        {
            remove( x, root );
        }


        /**
         * Find the smallest item in the tree.
         * Return smallest item or ITEM_NOT_FOUND if empty.
         */
        template <class Comparable>
        const Comparable & UnbalancedBinaryTree<Comparable>::findMin( ) const
        {
            return elementAt( findMin( root ) );
        }

        /**
         * Find the largest item in the tree.
         * Return the largest item of ITEM_NOT_FOUND if empty.
         */
        template <class Comparable>
        const Comparable & UnbalancedBinaryTree<Comparable>::findMax( ) const
        {
            return elementAt( findMax( root ) );
        }

        /**
         * Find item x in the tree.
         * Return the matching item or ITEM_NOT_FOUND if not found.
         */
        template <class Comparable>
        const Comparable & UnbalancedBinaryTree<Comparable>::
                                 find( const Comparable & x )
        {
	 	time_t t1, t2;
	 	t1 = clock();

		BinariNode<Comparable> *result = find(x,root);
		
		t2 = clock();
		searchTime = (t2 - t1)/CLOCKS_PER_SEC;

            return elementAt(result);
        }

        /**
         * Make the tree logically empty.
         */
        template <class Comparable>
        void UnbalancedBinaryTree<Comparable>::makeEmpty( )
        {
            makeEmpty( root );
        }

        /**
         * Test if the tree is logically empty.
         * Return true if empty, false otherwise.
         */
        template <class Comparable>
        bool UnbalancedBinaryTree<Comparable>::isEmpty( ) const
        {
            return root == NULL;
        }

        /**
         * Print the tree contents in sorted order.
         */
        template <class Comparable>
        void UnbalancedBinaryTree<Comparable>::printTree( ) const
        {
            if( isEmpty( ) )
                cout << "Empty tree" << endl;
            else
                printTree( root );
        }

        /**
         * Deep copy.
         */
        template <class Comparable>
        const UnbalancedBinaryTree<Comparable> &
        UnbalancedBinaryTree<Comparable>::
        operator=( const UnbalancedBinaryTree<Comparable> & rhs )
        {
            if( this != &rhs )
            {
                makeEmpty( );
                root = clone( rhs.root );
            }
            return *this;
        }

        /**
         * Internal method to get element field in node t.
         * Return the element field or ITEM_NOT_FOUND if t is NULL.
         */
        template <class Comparable>
        const Comparable & UnbalancedBinaryTree<Comparable>::
        elementAt( BinariNode<Comparable> *t ) const
        {
            if( t == NULL )
                return ITEM_NOT_FOUND;
            else
                return t->element;
        }

        /**
         * Internal method to insert into a subtree.
         * x is the item to insert.
         * t is the node that roots the tree.
         * Set the new root.
         */
        template <class Comparable>
        void UnbalancedBinaryTree<Comparable>::
        insert( const Comparable & x, BinariNode<Comparable> * & t )
        {
            if( t == NULL )
                t = new BinariNode<Comparable>( x, NULL, NULL );
            else if( x < t->element )
				insert( x, t->left );
            else if( t->element < x )
				insert( x, t->right );
         }


        /**
         * Internal method to remove from a subtree.
         * x is the item to remove.
         * t is the node that roots the tree.
         * Set the new root.
         */
        template <class Comparable>
        void UnbalancedBinaryTree<Comparable>::
        remove( const Comparable & x, BinariNode<Comparable> * & t ) const
        {
            if( t == NULL )
                return;   // Item not found; do nothing
            if( x < t->element )
                remove( x, t->left );
            else if( t->element < x )
                remove( x, t->right );
            else if( t->left != NULL && t->right != NULL ) // Two children
            {
                t->element = findMin( t->right )->element;
                remove( t->element, t->right );
            }
            else
            {
                BinariNode<Comparable> *oldNode = t;
                t = ( t->left != NULL ) ? t->left : t->right;
                delete oldNode;
            }
        }

        /**
         * Internal method to find the smallest item in a subtree t.
         * Return node containing the smallest item.
         */
        template <class Comparable>
        BinariNode<Comparable> *
        UnbalancedBinaryTree<Comparable>::findMin( BinariNode<Comparable> *t ) const
        {
            if( t == NULL )
                return NULL;
            if( t->left == NULL )
                return t;
            return findMin( t->left );
        }

        /**
         * Internal method to find the largest item in a subtree t.
         * Return node containing the largest item.
         */
        template <class Comparable>
        BinariNode<Comparable> *
        UnbalancedBinaryTree<Comparable>::findMax( BinariNode<Comparable> *t ) const
        {
            if( t != NULL )
                while( t->right != NULL )
                    t = t->right;
            return t;
        }

        /**
         * Internal method to find an item in a subtree.
         * x is item to search for.
         * t is the node that roots the tree.
         * Return node containing the matched item.
         */
        template <class Comparable>
        BinariNode<Comparable> *
        UnbalancedBinaryTree<Comparable>::
        find( const Comparable & x, BinariNode<Comparable> *t )
        {
			if(increments++, (t == NULL) )
                return NULL;
            else if(increments++, x < t->element )
                return find( x, t->left );
            else if(increments++, t->element < x )
                return find( x, t->right );
            else
			return t;    // Match
        }

        template <class Comparable>
        int 
		UnbalancedBinaryTree<Comparable>::
		getIncrements()
		{
			return increments;
		}
        template <class Comparable>
 		double 
		UnbalancedBinaryTree<Comparable>::
		getCreationTime()
		{
			return creationTime;
		}

        template <class Comparable>
		double 
		UnbalancedBinaryTree<Comparable>::
		getSearchTime()
		{
			return searchTime;
		}

        template <class Comparable>
        void
		UnbalancedBinaryTree<Comparable>::
		insertIntArray(int * A, int n)
		{
		    time_t t1, t2;
		    t1 = clock();

			for(int j = 0; j < n; j++)
				insert(A[j],root);
			
			t2 = clock();
			creationTime = (t2 - t1)/CLOCKS_PER_SEC;
		}

        template <class Comparable>
        void
            UnbalancedBinaryTree<Comparable>::
            insertIntVector(vector<int> V)
            {
              time_t t1, t2;
              t1 = clock();

              int n = V.size();
              int * A = new int[n];
              for(int i=0; i<n; i++)
                A[i] = V.at(i);

              for(int j = 0; j<n; j++)
                insert(A[j], root);

              t2 = clock();
              creationTime = (t2 - t1)/CLOCKS_PER_SEC;
            }		

        template <class Comparable>
        void
		UnbalancedBinaryTree<Comparable>::
		resetIncrements()
		{
			increments = 0;
			creationTime = 0;
			searchTime = 0;
		}






/****** NONRECURSIVE VERSION*************************
        template <class Comparable>
        BinariNode<Comparable> *
        UnbalancedBinaryTree<Comparable>::
        find( const Comparable & x, BinariNode<Comparable> *t ) const
        {
            while( t != NULL )
                if( x < t->element )
                    t = t->left;
                else if( t->element < x )
                    t = t->right;
                else
                    return t;    // Match

            return NULL;   // No match
        }
*****************************************************/

        /**
         * Internal method to make subtree empty.
         */
        template <class Comparable>
        void UnbalancedBinaryTree<Comparable>::
        makeEmpty( BinariNode<Comparable> * & t ) const
        {
            if( t != NULL )
            {
                makeEmpty( t->left );
                makeEmpty( t->right );
                delete t;
            }
            t = NULL;
        }

        /**
         * Internal method to print a subtree rooted at t in sorted order.
         */
        template <class Comparable>
        void UnbalancedBinaryTree<Comparable>::printTree( BinariNode<Comparable> *t ) const
        {
            if( t != NULL )
            {
                printTree( t->left );
                cout << t->element << endl;
                printTree( t->right );
            }
        }

        /**
         * Internal method to clone subtree.
         */
        template <class Comparable>
        BinariNode<Comparable> *
        UnbalancedBinaryTree<Comparable>::clone( BinariNode<Comparable> * t ) const
        {
            if( t == NULL )
                return NULL;
            else
                return new BinariNode<Comparable>( t->element, clone( t->left ), clone( t->right ) );
        }