// Author: <Your Name Here>
//
// Specification of a templated BSTNode containing Key/Value pairs.
//
// Note that the KeyType type/class for which this class is templatized
// *must* have the following functions implemented:
//    Default constructor
//    Copy constructor
//    Assignment op
//    operator<
//    operator>
//    operator==
//    operator!=
//    operator<<, if you use the Print() method
//
// The ValueType type/class for which this class is templatized
// *must* implement the following methods:
//    Default constructor
//    Copy constructor
//    Assignment op
//    operator<<, if you use the Print() method


#ifndef BSTNODE_HH
#define BSTNODE_HH

//
// The Binary Search Tree node struct. Contains the data for each node
// and also performs some important calculations on nodes to analyze
// tree structure.
//
template < class KeyType, class ValueType >
struct BSTNode 
{
public:
    //
    // Note that we do *not* follow canonical form, since this class 
    // does *not* have dynamic memory
    //

    // Construct a node by copying the given data members.
    BSTNode( const KeyType &key, 
             const ValueType &value,
             BSTNode *pParent = NULL, 
             BSTNode *pLeft = NULL, 
             BSTNode *pRight = NULL );

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

    // Copy the current instance into a new BSTNode.  The client is 
    // responsible for deleting this newly allocated BSTNode.  Note that
    // this method only copies the KeyType/ValueType pair; it does not 
    // copy the child pointers
    virtual BSTNode* Clone( void ) const;

    // True iff this node has a parent (i.e., if this node is *not* the root)
    bool            HasParent( void ) const;

    // True iff this node's parent has a parent.  
    bool            HasGrandparent( void ) const;

    // True iff this node is a left child of its parent.  Returns 
    // false if this node does not have a parent
    bool            IsLeftChild( void ) const;

    // True iff this node is a right child of its parent.  Returns 
    // false if this node does not have a parent
    bool            IsRightChild( void ) const;

    // True iff this node is a leaf.
    bool            IsLeaf( void ) const;

    // The number of children this node has (either 0, 1, or 2)
    int             GetNumChildren( void ) const;

    // Print this node and its subtree. (requires operator << from both
    // KeyType and ValueType). Should be called with default argument
    // for filler externally.
#ifndef NDEBUG
    void            Print( std::ostream &out = std::cout, 
                           std::string filler = "" ) const;
#endif

    //
    // Data
    //
    // Yes, you are reading this correctly; the data of this node struct
    // is public.  Anybody can modify the data in a BSTNode.  Leaving the
    // BSTNode data public should be safe, however, since the client of
    // the BinarySearchTree won't be able to access any of the BST's
    // BSTNodes
    //

    // The data inside this node
    KeyType m_key;
    ValueType m_value;

    // Pointers to the parent, left child, and right child of this node
    BSTNode *m_pParent;
    BSTNode *m_pLeft;
    BSTNode *m_pRight;
};


#endif // BSTNODE_HH