#pragma once
#include <string>

#include <math.h>

#define GREATER(a,b) (b < a)
#define SMALLER(a,b) (a < b)
#define EQUAL(a,b) !GREATER(a,b) && !SMALLER(a,b)


namespace CommonUtilities
{
    template <class T>
    class BinaryTree
    {
        struct Node
        {
            T myData;
            Node* myMin;
            Node* myMax;

            Node(const T& aValues);

            Node* operator+();
            Node* operator-();
            T& operator*();

            bool operator<(Node& aNode);

            Node* Find(const T& aVal, Node*& aParent);
            void Insert(Node* aNode);

            Node* RotateAllRight();

            Node* RotateRight();

            void VineToTree();

            void Compress(size_t aCount);

            size_t Count();

            void Delete();

            void BuildString(std::string& aString, int aDepth);

        };

    public:
        BinaryTree();
        ~BinaryTree();

        //Returnerar true om elementet finns i mängden, och false annars.
        bool HasElement(const T& aValue) const;

        //Stoppar in elementet i mängden, om det inte redan finns där. Gör
        //ingenting annars.
        void Insert(const T& aValue);

        //Plockar bort elementet ur mängden, om det finns. Gör ingenting annars.
        void Remove(const T& aValue);

        void DSWBalance();
        void BuildString(std::string& aString);

    private:
        Node* myRoot;
    };

    template<class T>
    inline BinaryTree<T>::Node::Node(const T & aValues)
    {
        myMax = nullptr;
        myMin = nullptr;
        myData = aValues;
    }

    template<class T>
    inline typename BinaryTree<T>::Node * BinaryTree<T>::Node::operator+()
    {
        if (myMax)
        {
            return +myMax;
        }
        return this;
    }

    template<class T>
    inline typename BinaryTree<T>::Node * BinaryTree<T>::Node::operator-()
    {
        if (myMin)
        {
            return -myMin;
        }
        return this;
    }

    template<class T>
    inline T & BinaryTree<T>::Node::operator*()
    {
        return myData;
    }

    template<class T>
    inline bool BinaryTree<T>::Node::operator<(Node & aNode)
    {
        return SMALLER(myData, aNode.myData);
    }

    template<class T>
    inline typename BinaryTree<T>::Node * BinaryTree<T>::Node::Find(const T & aVal, Node*& aParent)
    {
        if (!this || EQUAL(aVal, myData))
        {
            return this;
        }

        aParent = this;

        if (GREATER(aVal, myData))
        {
            return myMax->Find(aVal, aParent);
        }

        if (SMALLER(aVal, myData))
        {
            return myMin->Find(aVal, aParent);
        }
    }

    template<class T>
    inline void BinaryTree<T>::Node::Insert(Node * aNode)
    {
        if (GREATER(*aNode, *this))
        {
            if (myMax)
            {
                myMax->Insert(aNode);
            }
            else
            {
                myMax = aNode;
            }
        }
        else if (SMALLER(*aNode, *this))
        {
            if (myMin)
            {
                myMin->Insert(aNode);
            }
            else
            {
                myMin = aNode;
            }
        }
        else
        {
            //myData = aNode->myData; overwrite
            delete aNode;
        }
    }

    template<class T>
    inline typename  BinaryTree<T>::Node* BinaryTree<T>::Node::RotateAllRight()
    {
        if (!this)
        {
            return this;
        }
        Node* currentTop = this;
        while (currentTop->myMin)
        {
            currentTop = currentTop->RotateRight();
        }
        currentTop->myMax = currentTop->myMax->RotateAllRight();
        return currentTop;
    }

    template<class T>
    inline typename  BinaryTree<T>::Node * BinaryTree<T>::Node::RotateRight()
    {
        if (!myMin)
        {
            return this;
        }
        Node* left = myMin;
        Node* root = this;

        root->myMin = left->myMax;
        left->myMax = root;

        return left;
    }

    template<class T>
    inline void BinaryTree<T>::Node::VineToTree()
    {
        size_t size(Count());
        size_t leaveCount = size + 1 - pow(2,floor(log2(size + 1)));

        Compress(leaveCount);

        size -= leaveCount;
        while (size > 1)
        {
            Compress(size / 2);
            size /= 2;
        }
    }

    template<class T>
    inline void BinaryTree<T>::Node::Compress(size_t aCount)
    {
        Node* scanner = this;
        for (size_t i = 0; i < aCount; i++)
        {
            Node* child = scanner->myMax;
            scanner->myMax = child->myMax;
            scanner = scanner->myMax;
            child->myMax = scanner->myMin;
            scanner->myMin = child;
        }
    }

    template<class T>
    inline size_t BinaryTree<T>::Node::Count()
    {
        if (this)
        {
            return myMin->Count() + myMax->Count() + 1;
        }
        return 0;
    }

    template<class T>
    inline void BinaryTree<T>::Node::Delete()
    {
        if (!this)
        {
            return;
        }
        myMax->Delete();
        myMin->Delete();
        delete this;
    }

    template<class T>
    inline void BinaryTree<T>::Node::BuildString(std::string& aString ,int aDepth)
    {
        if (!this)
        {
            return;
        }
        myMin->BuildString(aString, aDepth + 1);
        aString += std::string(aDepth, '~') + std::to_string(myData) + "\n";
        myMax->BuildString(aString, aDepth + 1);
    }

    template<class T>
    inline BinaryTree<T>::BinaryTree()
    {
        myRoot = nullptr;
    }

    template<class T>
    inline BinaryTree<T>::~BinaryTree()
    {
        myRoot->Delete();
    }

    template<class T>
    inline bool BinaryTree<T>::HasElement(const T & aValue) const
    {
        Node* _;
        return myRoot->Find(aValue, _);
    }

    template<class T>
    inline void BinaryTree<T>::Insert(const T & aValue)
    {
        if (myRoot)
        {
            myRoot->Insert(new Node(aValue));
        }
        else
        {
            myRoot = new Node(aValue);
        }
    }

    template<class T>
    inline void BinaryTree<T>::Remove(const T & aValue)
    {
        Node* parent = nullptr;
        Node* found = myRoot->Find(aValue, parent);
        if (!found) { return; }

        if (!parent) // ==> myroot == found
        {
            if (myRoot)
            {
                if (found->myMin)
                {
                    myRoot = found->myMin;
                    if (found->myMax)
                    {
                        (+myRoot)->myMax = found->myMax;
                    }
                }
                else if (found->myMax)
                {
                    myRoot = found->myMax;
                }
                else
                {
                    myRoot = nullptr;
                }
            }
        }
        else if (found->myMin && found->myMax)
        {
            if (parent->myMin == found)
            {
                parent->myMin = found->myMin;
            }
            else
            {
                parent->myMax = found->myMin;
            }
            (+found->myMin)->myMax = found->myMax;
        }
        else
        {
            Node* one = (found->myMin ? found->myMin : found->myMax);

            if (parent->myMin == found)
            {
                parent->myMin = one;
            }
            else
            {
                parent->myMax = one;
            }
        }

        delete found;

    }

    template<class T>
    inline void BinaryTree<T>::DSWBalance()
    {
        myRoot = myRoot->RotateAllRight(); //create backbone
        myRoot->VineToTree();
    }

    template<class T>
    inline void BinaryTree<T>::BuildString(std::string & aString)
    {
        myRoot->BuildString(aString, 0);
    }

}