//////////////////////////////////////////////////////////////////////////
//  Node Implementations (for BinaryTree)

template <typename T>
sort::Node<T>::Node( )
{
    Left = nullptr;
    Right = nullptr;
    Parent = nullptr;
}

template <typename T>
sort::Node<T>::~Node( )
{
    if (Left)
        delete Left;
    if (Right)
        delete Right;
}


//////////////////////////////////////////////////////////////////////////
//  BinaryTree Implementations

template <typename T>
sort::BinaryTree<T>::BinaryTree( )
{
    m_Root = nullptr;
}

template <typename T>
sort::BinaryTree<T>::~BinaryTree( )
{
    Clear( );

    for( Node<T> * node : m_NodeReserve )
    {
        delete node;
    }
}

template <typename T>
void sort::BinaryTree<T>::Initialize( const std::vector<T> & data )
{
    Clear( );

    m_InitReserveSize = data.size( );

    while( m_NodeReserve.size( ) < data.size( ) )
    {
        AddNodeToReserve( new Node<T>( ) );
    }
}

template <typename T>
void sort::BinaryTree<T>::Run( const std::vector<T> & data )
{
    for( uint i = 0; i < data.size( ); i++ )
    {
        AddValueToNodeSlot( nullptr, &m_Root, data[i]);
    }
}

template <typename T>
std::string sort::BinaryTree<T>::Name( ) const
{
    return "Binary Tree Sort";
}

template <typename T>
void sort::BinaryTree<T>::FillSortedData( std::vector<T> & target ) const
{
    if( !m_Root )
        return;

    target.reserve( m_InitReserveSize );

    ProcessNodeToSortedData( *m_Root, target );
}

template <typename T>
void sort::BinaryTree<T>::ProcessNodeToSortedData(
    const Node<T> & targetNode,
    std::vector<T> & targetContainer
    ) const
{
    if( targetNode.Left )
        ProcessNodeToSortedData( *targetNode.Left, targetContainer );

    targetContainer.push_back( targetNode.Value );

    if (targetNode.Right )
        ProcessNodeToSortedData( *targetNode.Right, targetContainer );
}

template <typename T>
void sort::BinaryTree<T>::AddValueToNodeSlot( Node<T> * parent, Node<T> ** slot, const T & value )
{
    if ( *slot == nullptr )
    {
        Node<T> * newNode = GetNewNode( );
        newNode->Parent = parent;
        newNode->Value = value;

        *slot = newNode;
    }
    else
    {
        if( value < (*slot)->Value )
            AddValueToNodeSlot( *slot, &(*slot)->Left, value );
        else
            AddValueToNodeSlot( *slot, &(*slot)->Right, value );
    }
}

template <typename T>
void sort::BinaryTree<T>::AddNodeToReserve( sort::Node<T> * node )
{
    node->Left = nullptr;
    node->Right = nullptr;
    node->Parent = nullptr;
    node->Value = T(); // Note: Could cause performance problems on a complex type T
    m_NodeReserve.push_back( node );
}

template <typename T>
sort::Node<T> * sort::BinaryTree<T>::GetNewNode( )
{
    if( m_NodeReserve.size() == 0 )
    {
        std::cout << "Performance warning: New node manually allocated in sort::BinaryTree.\n";
        return new Node<T>( );
    }

    return GetReservedNode( );
}

template <typename T>
sort::Node<T> * sort::BinaryTree<T>::GetReservedNode( )
{
    Node<T> * result;
    result = m_NodeReserve.back( );
    m_NodeReserve.pop_back( );
    return result;
}

template <typename T>
void sort::BinaryTree<T>::Clear( )
{
    if( m_Root )
        delete m_Root;

    m_Root = nullptr;
}