#include <memory>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <iterator>
#include <typeinfo>

template<class T, class _Alloc = std::allocator<T> >
class btree
{
    typedef std::allocator_traits<_Alloc> T_allocator_traits;

    struct node{
        inline static int m_LastID;

        T m_Data;

        int m_ID;
        node *m_pLeft;
        node *m_pRight;
        node *m_pParent;

        node(const T &Data) : m_pLeft(nullptr), m_pRight(nullptr), m_pParent(nullptr)
        {
            m_Data = Data;
            m_ID = m_LastID++;
        }
    };
    node *m_pRoot = nullptr;

    typedef typename T_allocator_traits::template rebind_alloc<node> node_allocator_type;
    typedef std::allocator_traits<node_allocator_type> node_alloc_traits;
    node_allocator_type node_allocator;

    void RecurseTree_internal(void (*cb)(int, T, int, int, int, int, void *), node *pNode, int Height, void *pContext)
    {
        if(!pNode)
            return;

        if(pNode->m_pLeft)
            RecurseTree_internal(cb, pNode->m_pLeft, Height + 1, pContext);
        cb(pNode->m_ID, pNode->m_Data,
            pNode->m_pLeft ? pNode->m_pLeft->m_ID : -1,
            pNode->m_pRight ? pNode->m_pRight->m_ID : -1,
            pNode->m_pParent ? pNode->m_pParent->m_ID : -1,
            Height, pContext);
        if(pNode->m_pRight)
            RecurseTree_internal(cb, pNode->m_pRight, Height + 1, pContext);
    }

    node *FindNode(const T &Data)
    {
        node *pNode = m_pRoot;
        while(pNode && pNode->m_Data != Data)
        {
            if(Data > pNode->m_Data)
                pNode = pNode->m_pRight;
            else
                pNode = pNode->m_pLeft;
        }

        return pNode;
    }

public:

    typedef T value_type;
    typedef value_type &reference;
    typedef const value_type &const_reference;

    class iterator
    {
    public:
        typedef ptrdiff_t difference_type;
        typedef btree::value_type value_type;
        typedef value_type *pointer;
        typedef value_type &reference;
        typedef std::input_iterator_tag iterator_category;

    private:
        node *m_pNode;

    public:
        iterator(node *pNode) : m_pNode(pNode) {};

        iterator &operator++()
        {
            node *pNext = m_pNode;
            if(pNext->m_pRight)
            {
                pNext = pNext->m_pRight;

                while(pNext->m_pLeft)
                    pNext = pNext->m_pLeft;
            }
            else
            {
                while(pNext && pNext->m_pParent && pNext->m_pParent->m_pRight == pNext)
                    pNext = pNext->m_pParent;
                pNext = pNext->m_pParent;
            }

            m_pNode = pNext;
            return *this;
        }

        iterator operator++(int)
        {
            iterator t = *this;
            ++(*this);
            return t;
        }

        reference operator*() const
        {
            return m_pNode->m_Data;
        }

        friend bool operator==(const iterator &a, const iterator &b)
        {
            return a.m_pNode == b.m_pNode;
        }

        friend bool operator!=(const iterator &a, const iterator &b)
        {
            return a.m_pNode != b.m_pNode;
        }
    };

    void insert(const T &Data)
    {
        node *t = node_alloc_traits::allocate(node_allocator, 1);
        node_alloc_traits::construct(node_allocator, t, Data);

        node **pRoot = &m_pRoot;
        while(*pRoot)
        {
            t->m_pParent = *pRoot;
            if(Data < (*pRoot)->m_Data)
                pRoot = &(*pRoot)->m_pLeft;
            else if(Data > (*pRoot)->m_Data)
                pRoot = &(*pRoot)->m_pRight;
            else
            {
                delete t;
                return;
            }
        }
        *pRoot = t;
    }

    void remove(const T &Data)
    {
        node *n = FindNode(Data);
        if(!n)
            return;

        node *s = nullptr;
        if(n->m_pRight && n->m_pLeft)
        {
            s = n->m_pRight;
            while(s->m_pLeft) s = s->m_pLeft;
            n->m_Data = s->m_Data;
            n = s;
            s = nullptr;
        }

        if(n->m_pLeft || n->m_pRight)
            s = n->m_pLeft ? n->m_pLeft : n->m_pRight;

        if(n->m_pParent->m_pRight == n)
            n->m_pParent->m_pRight = s;
        else
            n->m_pParent->m_pLeft = s;

        if(s)
            s->m_pParent = n->m_pParent;

        node_alloc_traits::destroy(node_allocator, n);
        node_alloc_traits::deallocate(node_allocator, n, 1);
    }

    void RecurseTree(void (*cb)(int, T, int, int, int, int, void *), void *pContext = nullptr)
    {
        RecurseTree_internal(cb, m_pRoot, 0, pContext);
    }

    iterator begin()
    {
        node *pSmallest = m_pRoot;
        while(pSmallest->m_pLeft)
            pSmallest = pSmallest->m_pLeft;

        return iterator(pSmallest);
    }

    iterator end()
    {
        return iterator(nullptr);
    }
};

void printcb(int id, int Value, int lid, int rid, int pid, int height, void *pContext)
{
    static int NullCount = 0;
    FILE *f = (FILE *)pContext;

    fprintf(f, "\tl%d [label=\"%d\"];\n", id, Value);
    fprintf(f, "l%d -> { ", id);
    if(lid >= 0 && rid >= 0)
        fprintf(f, "l%d l%d };\n",lid, rid);
    else if(lid >= 0)
    {
        fprintf(f, "l%d null%d };\n", lid, NullCount);
        fprintf(f, "\tnull%d [shape=point];\n", NullCount++);
    }
    else if(rid >= 0)
    {
        fprintf(f, "null%d l%d };\n", NullCount, rid);
        fprintf(f, "\tnull%d [shape=point];\n", NullCount++);
    }
    else
    {
        fprintf(f, "null%d null%d };\n", NullCount, NullCount + 1);
        fprintf(f, "\tnull%d [shape=point];\n", NullCount++);
        fprintf(f, "\tnull%d [shape=point];\n", NullCount++);
    }

    if(pid >= 0)
        fprintf(f, "l%d -> l%d [color=\"red\", constraint=false];\n", id, pid);
    else
    {
        fprintf(f, "l%d -> null%d [color=\"red\", constraint=false];\n", id, NullCount);
        fprintf(f, "null%d [shape=point, color=\"red\"];\n", NullCount++);
    }
}

int main(int argc, char **argv)
{
    btree<int> tree;
    for(int i = 0; i < 20; i++)
        tree.insert(rand() % 1000);

    //tree.Remove(658);

    FILE *Graph = fopen("graph.dot", "w");
    if(!Graph)
        return 1;

    fprintf(Graph, "digraph BST {\n");
    tree.RecurseTree(printcb, Graph);
    fprintf(Graph, "}\n");

    fclose(Graph);

    for(auto it : tree)
    {
        printf("%d ", it);
    }
    putchar('\n');

    return 0;
}