#include <cstdlib>
#include <iostream>
#include <strstream>
using namespace std;

#include "BinarySearchTree.hh"

template< typename KeyType, typename ValueType >
BSTNode< KeyType, ValueType >::BSTNode( const KeyType &key, 
                                        const ValueType &value,
                                        BSTNode *pParent, 
                                        BSTNode *pLeft, 
                                        BSTNode *pRight )

    // Memberwise initialization list -- this is effectively the same
    // as saying m_key = key, except that it calls the copy constructor
    // instead of the assignment operator if the thing that's being
    // copied is a class
    : m_key( key ),
      m_value( value ),
      m_pParent( pParent ),
      m_pLeft( pLeft ),
      m_pRight( pRight )
{
    // Empty body
}


template< typename KeyType, typename ValueType >
BSTNode< KeyType, ValueType >*
BSTNode< KeyType, ValueType >::Clone( void ) const
{
    return new BSTNode( m_key, m_value );
}


template< typename KeyType, typename ValueType >
bool
BSTNode< KeyType, ValueType >::HasParent( void ) const
{
    return ( m_pParent != NULL );
}


template< typename KeyType, typename ValueType >
bool
BSTNode< KeyType, ValueType >::HasGrandparent( void ) const
{
    return ( HasParent() && m_pParent->HasParent() );
}


template< typename KeyType, typename ValueType >
bool
BSTNode< KeyType, ValueType >::IsLeftChild( void ) const
{
    return ( HasParent() && (m_pParent->m_pLeft == this) );
}


template< typename KeyType, typename ValueType >
bool
BSTNode< KeyType, ValueType >::IsRightChild( void ) const
{
    return ( HasParent() && (m_pParent->m_pRight == this) );
}


template< typename KeyType, typename ValueType >
bool
BSTNode< KeyType, ValueType >::IsLeaf( void ) const
{
    return ( GetNumChildren() == 0 );
}


template< typename KeyType, typename ValueType >
int
BSTNode< KeyType, ValueType >::GetNumChildren( void ) const
{
    int count = 0;

    if( m_pLeft != NULL )
    {
        count++;
    }
    if( m_pRight != NULL )
    {
        count++;
    }

    return count;
}


#ifndef NDEBUG
template< typename KeyType, typename ValueType >
void
BSTNode< KeyType, ValueType >::Print( ostream &out,
                                      string filler ) const
{
    // A string stream to hold output data in a C++ string
    ostrstream outStr;
    
    // Print the data in the node to the string stream. I do it
    // this way to keep all the spacing right.
    outStr << "(" << m_key << ", " << m_value << ")" << ends;

    // Grab the string representation of the data from the string stream.
    string dataStr = outStr.str();

    // Create enough blanks to justify out not quite to the 
    // end of the data
    string blanks( dataStr.length() - 1, ' ' );
  
    // Output the "parent link" for this node along with 
    // the actual data.
    out << "--" << dataStr;
  
    // If there is no right subtree, end the line and print a line of filler.
    if ( m_pRight == NULL ) 
    {
        out << endl;
        out << filler << "  " << blanks 
            << (m_pLeft == NULL ?  " " : "|") << endl;
    }
    // If there is a right subtree, print it recursively.
    else 
    {
        m_pRight->Print( out, filler + "  " + 
                         blanks + (m_pLeft == NULL ? " " : "|") );
    }

    // If there is a left subtree, print it; start by justifying out
    // (didn't have to do that for the right because we printed the
    // data for this node on the right subtree's line).
    if ( m_pLeft != NULL ) 
    {
        out << filler + "  " + blanks + "\\";
        m_pLeft->Print( out, filler + "  " + blanks + " " );
    }
}
#endif // NDEBUG