#ifndef _BINARY_TREE_SORT_H_

#include "../BenchmarkFramework/Benchmarkable.h"
#include "../Types.h"



namespace sort
{

    template <typename T>
    class Node
    {
    public:

        T Value;
        Node * Left, * Right, * Parent;

        Node( );
        ~Node( );
    };





    template <typename T>
    class BinaryTree : public bf::BenchmarkableSort <T>
    {
    public:
        BinaryTree( );
        virtual ~BinaryTree( );

        void Initialize( const std::vector<T> & data ) override;
        void Run( const std::vector<T> & data ) override;
        std::string Name( ) const override;


    protected:
        void FillSortedData( std::vector<T> & targetContainer ) const override;


    private:
        void AddNodeToReserve( Node<T> * node );
        void AddValueToNodeSlot( Node<T> * parent, Node<T> ** slot, const T & value );

        void ProcessNodeToSortedData(
            const Node<T> & targetNode,
            std::vector<T> & targetContainer
            ) const;

        Node<T> * GetNewNode( );
        Node<T> * GetReservedNode( );

        void Clear( );



        std::vector<Node<T> *> m_NodeReserve;
        int m_InitReserveSize; // Datastructure size reserved upon the call to Initialize()

        Node<T> * m_Root;
    };
}

#include "BinaryTreeSort.inl"

#endif // !_BINARY_TREE_SORT_H_