// Author: <Your Name Here>
//
// Specification of a templated BinarySearchTree class which maps
// keys to values (duplicated keys are not allowed)
// 
// See BSTNode.hh for methods which must be implemented by the
// KeyValue and ValueType types

#ifndef BINARYSEARCHTREE_HH
#define BINARYSEARCHTREE_HH


#ifndef NDEBUG
    // <iostream> and <string> necessary only if we're planning on using the
    // debug Print() function.  Note that we do *not* do a 
    // "using namespace std" declaration here -- this is to avoid pulling 
    // in the entire contents of the std namespace into any hapless file 
    // which happens to #include this one!
#   include <iostream>
#   include <string>
#endif // NDEBUG

#include "BSTNode.hh"


//
// The BinarySearchTree class
//
template< typename KeyType, typename ValueType >
class BinarySearchTree
{
public:
    //
    // Canonical form: the 4 functions that all classes with dynamic
    // memory should have:
    //

    // (1) Default constructor
    BinarySearchTree( void );

    // (2) Copy constructor
    BinarySearchTree( const BinarySearchTree &other );

    // (3) Assign Op
    const BinarySearchTree& operator=( const BinarySearchTree &other ); 

    // (4) Destructor
    //   Note that the destructor is declared virtual in this inheritance
    //   tree.  Why do you think this is necessary?
    virtual ~BinarySearchTree( void );


    //
    // Accessors 
    //   Note that these methods are declared 'const' because they do not 
    //   modify the tree!.
    // 

    // Returns the number of elements in the BST
    int             GetSize( void ) const;

    // Given a key, 'returns' (via a reference parameter) the value 
    // associated with it in this BST.  Returns true if the key is in 
    // the tree, false otherwise
    virtual bool    Find( const KeyType &key, 
                          ValueType &value ) const;

    // Dynamically allocates two arrays containing the keys and values
    // stored in this BST.  The values will be in sorted order, and the
    // key at index 'i' in pKeys will correspond to the value at index 'i' 
    // in pValues.  This method will *not* deallocate any memory which 
    // pKeys or pValues point at when they are passed in to this method, 
    // and assumes that the client will delete pKeys and pValues.  Returns 
    // an int specifying the number of elements in the arrays (-1 if 
    // there was an error)
    int             GetDataAsArray( KeyType *&pKeys, 
                                    ValueType *&pValues ) const;
    
#ifndef NDEBUG
    // Print out a view of this tree for debugging purposes.  This
    // code requires operator<< for both KeyType and ValueType, so 
    // you can remove this if you're not debugging.  You can "turn off"
    // printing by compiling in "release mode" (ie, by #defining "NDEBUG")
    void            Print( std::ostream &out = std::cout ) const;
#endif // NDEBUG

    //
    // Mutators 
    //   These methods change the state of the tree
    // 

    // Inserts a new key/value pair into the BST.  Returns true if this
    // key did not previously exist in the tree, false otherwise.  If the
    // key previously existed in the tree, will overwrite the old value
    // with the new value
    virtual bool    Insert( const KeyType &newKey,
                            const ValueType &newValue );

protected:
    //
    // Non-modifying helper functions
    //

    // Finds the node associated with a given key.  Returns NULL
    // if the tree is empty; otherwise, returns the parent of
    // where 'key' should be
    BSTNode< KeyType, ValueType >* FindNode( const KeyType &key ) const;

    // Recursively copies the key/value pairs in the tree into the key
    // (pKeys) and value (pValues) arrays.  The copying is done via an
    // in-order traversal of the subtrees rooted at pCurrNode (ie,
    // the data in the arrays will be ordered by key value).  Assumes 
    // that pKeys and pValues pointers are properly initialized; does
    // nothing if pCurrNode == NULL.  The return value of this method
    // is the current number of valid items in the array (ie, the
    // next index to copy into)
    int             RecursiveCopy( KeyType pKeys[],
                                   ValueType pValues[],
                                   BSTNode< KeyType, ValueType > *pCurrNode,
                                   int currIndex ) const;


    //
    // Mutating helper functions
    //

    // Recursively copy the tree rooted at pOtherRoot, returning
    // a pointer to the newly copied subtree.  Does *not* 
    // deallocate any memory.
    BSTNode< KeyType, ValueType >* Copy( const BSTNode< KeyType, ValueType > * const pOtherRoot );

    // Reset this tree by recursively deallocating its memory 
    // and resetting data members
    void            Destroy( BSTNode< KeyType, ValueType > * const pRoot );


    //
    // Data members
    //
    // Here, we follow a subset of the "hungarian" naming convention, 
    // where data members are prefaced with a "m_" and pointers with a
    // "p".  Hungarian is *not* required for this class, but some sort
    // of consistant naming convention *is*.
    //

    // The root of the BST.  What is a "mutable" data member?  It's a 
    // data member that can be modified >>even if the instance of this 
    // class is declared const<<!  This has one very important effect:
    //     This data member can be modifed by any class
    //     method, even if it is declared 'const'!
    // The reason the root pointer is declared mutable will become
    // important when we look at SplayTree::Find() and SplayTree::Splay()
    mutable BSTNode< KeyType, ValueType > *m_pRoot;

    // The number of elements in the BST
    int             m_numElts;
};




#endif // BINARYSEARCHTREE_HH