#ifndef AVL_TREE_H
#define AVL_TREE_H

#include <cassert>
#include <algorithm>

#ifdef _PRINT
#include <vector>
#include <iostream>
#include <memory>
#include <functional>
#endif // _PRINT

namespace ghost{

/// AVL樹
template<typename ComparableT>
class AVLTree{
public:
    typedef ComparableT DataType;

private:
    /// 節(jié)點，緩存了自身的高度
    struct Node_{
        DataType data;        // 可進行比較的數(shù)據(jù)
        Node_* pLeftChild;   // 指向左兒子
        Node_* pRightChild;  // 指向右兒子
        int height;           // 作為根節(jié)點的樹高度，

        Node_()
            : pLeftChild(0)
            , pRightChild(0)
            , height(0) // 約定葉子高度為0，故節(jié)點高度初始化為0
        {

        }
        explicit Node_(const DataType& d)
            : data(d)
            , pLeftChild(0)
            , pRightChild(0)
            , height(0) // 約定葉子高度為0，故節(jié)點高度初始化為0
        {

        }

        Node_(const Node_&) = delete;
        Node_& operator =(const Node_&) = delete;
    };
    Node_* pRoot_;   // 指向根節(jié)點

public:
    /// 默認(rèn)初始化為空樹
    AVLTree()
        : pRoot_(0)
    {
#ifdef _PRINT
        std::cout<<"創(chuàng)建AVL樹"<<std::endl;
#endif // _PRINT
    }
    ~AVLTree()
    {
        Clear();
    }

    AVLTree(const AVLTree&) = delete;
    AVLTree& operator =(const AVLTree&) = delete;

public:
    /// 獲取樹高度，空樹返回-1，只有個節(jié)點返回0
    int GetHeight() const{return GetHeight_(pRoot_);}

#ifdef _PRINT
    /// 打印者，即需要打印的對象
    class Printer{
    public:
        virtual ~Printer(){}

    public:
        virtual void Print() const{}
        virtual bool IsValid() const{return false;}
    };

    typedef std::shared_ptr<Printer> PSharedPrinter;         // 打印者共享指針
    typedef std::vector<PSharedPrinter> PrinterContainer;   // 打印者共享指針的容器

    /// 節(jié)點打印者
    class NodePrinter : public Printer{
        Node_* pNode_;
        size_t width_;
        PrinterContainer& nextPrinters_;

    public:
        NodePrinter(Node_* p, PrinterContainer& printers)
            : pNode_(p)
            , width_(0)
            , nextPrinters_(printers)
        {
            assert(pNode_);
            UpdateWidth();
        }
        virtual ~NodePrinter(){}
        NodePrinter(const NodePrinter&) = delete;
        NodePrinter& operator =(const NodePrinter&) = delete;

    public:
        void UpdateWidth()
        {
            width_ = CalcDataWidth_(pNode_->data);
        }

        virtual void Print() const
        {
            // 計算左右子樹寬度
            size_t leftChildWidth = CalcWidth_(pNode_->pLeftChild);
            size_t rightChildWidth = CalcWidth_(pNode_->pRightChild);  // +1是為了將數(shù)據(jù)隔開

            // 打印左邊空白
            for (size_t i = 0; i < leftChildWidth; ++i)
            {
                std::cout<<' ';
            }
            // 打印節(jié)點
            std::cout<<"["<<pNode_->data<<"]";
            // 打印右邊空白
            for (size_t i = 0; i < rightChildWidth; ++i)
            {
                std::cout<<' ';
            }

            // 將左兒子放入下一層需要打印的節(jié)點集合中
            if (pNode_->pLeftChild)
            {
                nextPrinters_.push_back(PSharedPrinter(new NodePrinter(pNode_->pLeftChild, nextPrinters_)));
            }
            // 將自身所占空位放入下一層需要打印的節(jié)點集合中
            nextPrinters_.push_back(PSharedPrinter(new BlankPrinter(width_)));
             // 將右兒子放入下一層需要打印的節(jié)點集合中
            if (pNode_->pRightChild)
            {
                nextPrinters_.push_back(PSharedPrinter(new NodePrinter(pNode_->pRightChild, nextPrinters_)));
            }
            // 將自身所占空位放入下一層需要打印的節(jié)點集合中
            nextPrinters_.push_back(PSharedPrinter(new BlankPrinter(width_)));
        }
        virtual bool IsValid() const{return true;}
    };

    /// 空白打印者，主要完成打印父節(jié)點所占用的空白
    class BlankPrinter : public Printer{
        size_t count_;
    public:
        explicit BlankPrinter(size_t c) : count_(c){}
        virtual ~BlankPrinter(){}
    public:
        virtual void Print() const
        {
            for (size_t i = 0; i < count_; ++i)
            {
                std::cout<<' ';
            }
        }
    };

    /// 廣度優(yōu)先打印節(jié)點，目前只支持打印int型數(shù)據(jù)
    void Print() const
    {
        std::cerr<<"不支持打印的數(shù)據(jù)類型："<<typeid(DataType).name()<<"\n";
    }

private:
    /// 計算十進制數(shù)位數(shù)
    static size_t CalcDataWidth_(int n)
    {
        assert(false);
    }
    /**
    計算樹寬度
    因為約定空樹寬度為0，葉子寬度為1，所以樹寬度等于左右子樹寬度和+數(shù)據(jù)所占的位數(shù)
    */
    static size_t CalcWidth_(const Node_* pRoot)
    {
        if (!pRoot)
        {
            return 0;
        }
        return CalcWidth_(pRoot->pLeftChild) + CalcWidth_(pRoot->pRightChild) + CalcDataWidth_(pRoot->data);
    }
#endif // _PRINT

public:
    /// 插入數(shù)據(jù)
    void Insert(const DataType& data)
    {
#ifdef _PRINT
        std::cout<<"插入數(shù)據(jù)："<<data<<std::endl;
#endif // _PRINT
        Insert_(data, pRoot_);
    }
    /// 刪除數(shù)據(jù)
    void Erase(const DataType& data)
    {
#ifdef _PRINT
        std::cout<<"刪除數(shù)據(jù)："<<data<<std::endl;
#endif // _PRINT
        Erase_(data, pRoot_);
    }

    /// 清空
    void Clear()
    {
#ifdef _PRINT
        std::cout<<"清空"<<std::endl;
#endif // _PRINT
        // 銷毀所有節(jié)點
        RecursDestroyNode_(pRoot_);
        pRoot_ = 0;
    }

private:
    /// 創(chuàng)建節(jié)點
    static Node_* CreateNode_(const DataType& data)
    {
        return new Node_(data);
    }
    /// 銷毀節(jié)點
    static void DestroyNode_(Node_* pNode)
    {
        delete pNode;
    }
    /// 遞歸銷毀節(jié)點
    static void RecursDestroyNode_(Node_* pNode)
    {
        if (pNode)
        {
            // 先遞歸銷毀子節(jié)點
            RecursDestroyNode_(pNode->pLeftChild);
            RecursDestroyNode_(pNode->pRightChild);
            // 再銷毀自身
            DestroyNode_(pNode);
        }
    }

    /// 獲取樹高度，約定空樹高度為-1
    static int GetHeight_(const Node_* pRoot)
    {
        return pRoot ? pRoot->height : -1;
    }
    /**
    計算樹高度
    因為約定空樹高度為-1，葉子高度為0，所以樹高度等于左右子樹較高者高度+1
    */
    static int CalcHeight_(const Node_* pRoot)
    {
        assert(pRoot);  // 斷言樹存在
        return std::max(GetHeight_(pRoot->pLeftChild), GetHeight_(pRoot->pRightChild)) + 1;
    }

    /**
    與子樹進行單旋轉(zhuǎn)
    由于旋轉(zhuǎn)后節(jié)點將成為其原兒子的兒子，故節(jié)點指針pNode將會指向其原兒子
    pChild1指向被旋轉(zhuǎn)的兒子成員指針，pChild2指向另一個兒子成員指針
    */
    static void SingleRatateWithChild_(Node_*& pNode, Node_* Node_::* pChild1, Node_* Node_::* pChild2)
    {
        assert(pChild1 && pChild2); // 斷言成員變量指針有效

        assert(pNode);   // 斷言節(jié)點存在

        // 節(jié)點的兒子1重定向于兒子1的兒子2
        Node_* pOriginalChild = pNode->*pChild1;
        pNode->*pChild1 = pOriginalChild->*pChild2;
        // 節(jié)點的原兒子1的兒子2重定向于節(jié)點
        pOriginalChild->*pChild2 = pNode;

        // 旋轉(zhuǎn)之后需要重新計算高度
        pNode->height = CalcHeight_(pNode);
        pOriginalChild->height = CalcHeight_(pOriginalChild);

        // pNode指向其原兒子
        pNode = pOriginalChild;
    }

    /// 與左子樹進行單旋轉(zhuǎn)
    static void RotateWithLeftChild_(Node_*& pNode)
    {
        SingleRatateWithChild_(pNode, &Node_::pLeftChild, &Node_::pRightChild);
    }

    /// 與右子樹進行單旋轉(zhuǎn)
    static void RotateWithRightChild_(Node_*& pNode)
    {
        SingleRatateWithChild_(pNode, &Node_::pRightChild, &Node_::pLeftChild);
    }

    /**
    與子樹進行雙旋轉(zhuǎn)
    由于旋轉(zhuǎn)后節(jié)點將成為其原兒子的兒子，故節(jié)點指針pNode將會指向其原兒子
    pChild1指向被旋轉(zhuǎn)的兒子成員指針，pChild2指向另一個兒子成員指針
    */
    static void DoubleRatateWithChild_(Node_*& pNode, Node_* Node_::* pChild1, Node_* Node_::* pChild2)
    {
        assert(pChild1); // 斷言成員變量指針有效

        // 先對兒子進行一次旋轉(zhuǎn)
        SingleRatateWithChild_(pNode->*pChild1, pChild2, pChild1);
        // 再對自己進行一次旋轉(zhuǎn)
        SingleRatateWithChild_(pNode, pChild1, pChild2);
    }

    /// 與左子樹進行雙旋轉(zhuǎn)
    static void DoubleRotateWithLeftChild_(Node_*& pNode)
    {
        DoubleRatateWithChild_(pNode, &Node_::pLeftChild, &Node_::pRightChild);
    }

    /// 與右子樹進行雙旋轉(zhuǎn)
    static void DoubleRotateWithRightChild_(Node_*& pNode)
    {
        DoubleRatateWithChild_(pNode, &Node_::pRightChild, &Node_::pLeftChild);
    }

    /**
    確定左子樹是否過高（破壞了AVL平衡條件），是則與其進行旋轉(zhuǎn)
    當(dāng)在左子樹中插入新節(jié)點，或者在右子樹中刪除節(jié)點時使用
    */
    static void RatateWithLeftChildIfNeed_(Node_*& pNode)
    {
        // AVL平衡條件為左右子樹高度相差不超過1
        // 左子樹比右子樹高2，需要通過旋轉(zhuǎn)來使之重新達(dá)到AVL平衡條件
        if (2 == GetHeight_(pNode->pLeftChild) - GetHeight_(pNode->pRightChild))
        {
            if (GetHeight_(pNode->pLeftChild->pLeftChild) > GetHeight_(pNode->pLeftChild->pRightChild))
            {
                // 左子樹的左子樹高于左子樹的右子樹，應(yīng)當(dāng)與左子樹進行單旋轉(zhuǎn)
                RotateWithLeftChild_(pNode);
            }
            else
            {
                // 左子樹的右子樹高于左子樹的左子樹，應(yīng)當(dāng)與左子樹進行雙旋轉(zhuǎn)
                DoubleRotateWithLeftChild_(pNode);
            }
        }
    }

    /**
    確定右子樹是否過高（破壞了AVL平衡條件），是則與其進行旋轉(zhuǎn)
    當(dāng)在右子樹中插入新節(jié)點，或者在左子樹中刪除節(jié)點時使用
    */
    static void RatateWithRightChildIfNeed_(Node_*& pNode)
    {
        // AVL平衡條件為左右子樹高度相差不超過1
        // 右子樹比左子樹高2，需要通過旋轉(zhuǎn)來使之重新達(dá)到AVL平衡條件
        if (2 == GetHeight_(pNode->pRightChild) - GetHeight_(pNode->pLeftChild))
        {
            if (GetHeight_(pNode->pRightChild->pRightChild) > GetHeight_(pNode->pRightChild->pLeftChild))
            {
                // 右子樹的右子樹高于右子樹的左子樹，應(yīng)當(dāng)與右子樹進行單旋轉(zhuǎn)
                RotateWithRightChild_(pNode);
            }
            else
            {
                // 右子樹的左子樹高于右子樹的右子樹，應(yīng)當(dāng)與右子樹進行雙旋轉(zhuǎn)
                DoubleRotateWithRightChild_(pNode);
            }
        }
    }

    /**
    插入新節(jié)點：
        如果當(dāng)前節(jié)點為空則說明找到了插入的位置，創(chuàng)建新節(jié)點，返回插入成功
        如果數(shù)據(jù)小于當(dāng)前節(jié)點數(shù)據(jù)則到左子樹中插入，如果插入成功，可能需要旋轉(zhuǎn)使之重新平衡（左子樹過高），重新計算高度
        如果數(shù)據(jù)大于當(dāng)前節(jié)點數(shù)據(jù)則道右子樹中插入，如果插入成功，可能需要旋轉(zhuǎn)使之重新平衡（右子樹過高），重新計算高度
        如果數(shù)據(jù)等于當(dāng)前節(jié)點數(shù)據(jù)則什么都不做，返回插入失敗
    */
    static bool Insert_(const DataType& data, Node_*& pNode)
    {
        if (!pNode)
        {
            // 找到位置，創(chuàng)建節(jié)點
            pNode = CreateNode_(data);
            assert(pNode); // 斷言創(chuàng)建節(jié)點成功
            return true;
        }
        else if (data < pNode->data)
        {
            // 將較小的數(shù)據(jù)插入到左子樹
            if (Insert_(data, pNode->pLeftChild))
            {
                // 成功插入新節(jié)點
                // 如果需要，則與左子樹進行旋轉(zhuǎn)以維持AVL平衡條件
                RatateWithLeftChildIfNeed_(pNode);

                // 重新計算高度
                pNode->height = CalcHeight_(pNode);
                return true;
            }
        }
        else if (data > pNode->data)
        {
            // 將較大的數(shù)據(jù)插入到右子樹
            if (Insert_(data, pNode->pRightChild))
            {
                // 成功插入新節(jié)點
                // 如果需要，則與右子樹進行旋轉(zhuǎn)以維持AVL平衡條件
                RatateWithRightChildIfNeed_(pNode);

                // 重新計算高度
                pNode->height = CalcHeight_(pNode);
                return true;
            }
        }
        else
        {
            // 重復(fù)數(shù)據(jù)（什么也不做，或者進行計數(shù)）
        }
        return false;
    }

    /**
    刪除節(jié)點
    查找被刪除的節(jié)點：
        如果當(dāng)前節(jié)點為空則說明沒有找到被刪除的節(jié)點，返回刪除失敗
        如果被刪除的數(shù)據(jù)小于節(jié)點數(shù)據(jù)，則在節(jié)點的左子樹中查找并刪除，如果刪除成功，可能需要旋轉(zhuǎn)使之重新平衡（右子樹過高），重新計算高度
        如果被刪除的數(shù)據(jù)大于節(jié)點數(shù)據(jù)，則在節(jié)點的右子樹中查找并刪除，如果刪除成功，可能需要旋轉(zhuǎn)使之重新平衡（左子樹過高），重新計算高度
        如果被刪除的數(shù)據(jù)等于節(jié)點數(shù)據(jù)，則找到被刪除的節(jié)點，開始刪除，返回刪除成功

    刪除節(jié)點過程，將被刪除的節(jié)點作為標(biāo)記節(jié)點：
        如果標(biāo)記節(jié)點存在左右雙子樹，利用右子樹的最小節(jié)點的數(shù)據(jù)替換此節(jié)點數(shù)據(jù)，然后刪除右子樹的最小節(jié)點：
            如果右子樹有左子樹，從左子樹中找到最小節(jié)點，將其右子樹提升一級，可能需要旋轉(zhuǎn)使其父節(jié)點重新平衡（其父節(jié)點的右子樹過高），重新計算其父節(jié)點高度
            如果右子樹沒有左子樹，此時右子樹則即是最小節(jié)點，將其右子樹提升一級
        可能需要旋轉(zhuǎn)使標(biāo)記節(jié)點重新平衡（標(biāo)記節(jié)點的左子樹過高），重新計算標(biāo)記節(jié)點高度

        如果標(biāo)記節(jié)點不存在左右雙子樹，刪除標(biāo)記節(jié)點，提升其子樹
    */
    static bool Erase_(const DataType& data, Node_*& pNode)
    {
        if (!pNode)
        {
            // 沒有找到節(jié)點
            return false;
        }
        else if (data < pNode->data)
        {
            // 節(jié)點較小，在左子樹中刪除
            if (Erase_(data, pNode->pLeftChild))
            {
                // 成功刪除節(jié)點
                // 如果需要，則與右子樹進行旋轉(zhuǎn)以維持AVL平衡條件
                RatateWithRightChildIfNeed_(pNode);

                // 重新計算高度
                pNode->height = CalcHeight_(pNode);
                return true;
            }
        }
        else if (data > pNode->data)
        {
            // 節(jié)點較大，在右子樹中刪除
            if (Erase_(data, pNode->pRightChild))
            {
                // 成功刪除節(jié)點
                // 如果需要，則與左子樹進行旋轉(zhuǎn)以維持AVL平衡條件
                RatateWithLeftChildIfNeed_(pNode);

                // 重新計算高度
                pNode->height = CalcHeight_(pNode);
                return true;
            }
        }
        else
        {
            // 找到了需要被刪除的節(jié)點
            if (pNode->pLeftChild && pNode->pRightChild)
            {
                // 存在雙子樹，利用右子樹最小節(jié)點替換，并刪除右子樹最小節(jié)點
                Node_* pMin = pNode->pRightChild;
                if (pNode->pRightChild->pLeftChild)
                {
                    // 右子樹存在左子樹，從右子樹的左子樹中找最小節(jié)點
                    Node_* pMinParent = pNode->pRightChild;
                    while (pMinParent->pLeftChild->pLeftChild)
                    {
                        pMinParent = pMinParent->pLeftChild;
                    }
                    pMin = pMinParent->pLeftChild;

                    // 提升最小節(jié)點的右子樹
                    pMinParent->pLeftChild = pMin->pRightChild;

                    // 如果需要，最小節(jié)點的父節(jié)點則與其右子樹進行旋轉(zhuǎn)以維持AVL平衡條件
                    RatateWithRightChildIfNeed_(pMinParent);

                    // 重新計算最小節(jié)點的父節(jié)點的高度
                    pMinParent->height = CalcHeight_(pMinParent);
                }
                else
                {
                    // 右子樹不存在左子樹，那么提升右子樹的右子樹
                    pNode->pRightChild = pNode->pRightChild->pRightChild;
                }
                // 用最小節(jié)點替換
                pNode->data = pMin->data;

                // 刪除最小節(jié)點
                DestroyNode_(pMin);

                // 如果需要，則與左子樹進行旋轉(zhuǎn)以維持AVL平衡條件
                RatateWithLeftChildIfNeed_(pNode);

                // 重新計算高度
                pNode->height = CalcHeight_(pNode);
            }
            else
            {
                // 不存在雙子樹，則直接用兒子替換
                Node_* pTemp = pNode;
                pNode = pNode->pLeftChild ? pNode->pLeftChild : pNode->pRightChild;
                // 銷毀節(jié)點
                DestroyNode_(pTemp);
            }
            return true;
        }
        return false;
    }

}; // class AVLTree

#ifdef _PRINT
template<>
void AVLTree<int>::Print() const
{
    if (!pRoot_)
    {
        return;
    }

    PrinterContainer nextPrinters; // 下一層需要打印的對象集合
    nextPrinters.push_back(PSharedPrinter(new NodePrinter(pRoot_, nextPrinters)));

    while (nextPrinters.end() != std::find_if(nextPrinters.begin(), nextPrinters.end(), std::mem_fn(&Printer::IsValid)))
    {
        auto printers(std::move(nextPrinters));  // 當(dāng)前需要打印的對象集合
        // 打印一行
        std::for_each(printers.begin(), printers.end(), std::mem_fn(&Printer::Print));
        // 換行
        std::cout<<std::endl;
    }
}

template<>
size_t AVLTree<int>::CalcDataWidth_(int n)
{
    if (0 == n)
    {
        return 1+2; // +2是為[]符號占位
    }
    size_t ret = 2; // 2是為[]符號占位
    if (0 > n)
    {
        // 復(fù)數(shù)，添加符號位
        ++ret;
        n = -n;
    }
    while (n)
    {
        ++ret;
        n /= 10;
    }
    return ret;
}

#endif // _PRINT

} // namespace ghost

#endif // AVL_TREE_H

#define _PRINT

#include "AVLTree.h"
#include <iostream>
#include <ctime>

/// 打印AVL樹
template<typename T>
void PrintAVLTree(const ghost::AVLTree<T>& tree)
{
#ifdef _PRINT
    std::cout<<"--------------AVLTree--------------"<<std::endl;
    tree.Print();
    std::cout<<"------------------------------------------"<<std::endl;
#else
    std::cerr<<"未開啟打印預(yù)處理器，不提供AVL樹的打印！\n";
#endif // _PRINT
}

static const size_t TEST_DATA_COUNT = 10;          // 測試數(shù)據(jù)的個數(shù)
static const size_t TEST_DATA_LOWER_LIMIT = 0;    // 測試數(shù)據(jù)的下限
static const size_t TEST_DATA_UPPER_LIMIT = 10;  // 測試數(shù)據(jù)的上限

/// 隨機構(gòu)造測試數(shù)據(jù)
int BuildTestData()
{
    return TEST_DATA_LOWER_LIMIT + rand() % (TEST_DATA_UPPER_LIMIT-TEST_DATA_LOWER_LIMIT);
}

int main()
{
    srand((int)time(0));

    ghost::AVLTree<int> tree;

    // 隨機插入測試數(shù)據(jù)
    for (size_t i = 0; i < TEST_DATA_COUNT; ++i)
    {
        tree.Insert(BuildTestData());
        PrintAVLTree(tree);
    }

    // 隨機刪除測試數(shù)據(jù)
    for (size_t i = 0; i < TEST_DATA_COUNT; ++i)
    {
        tree.Erase(BuildTestData());
        PrintAVLTree(tree);
    }

//    tree.Insert(5);
//    PrintAVLTree(tree);
//
//    tree.Insert(2);
//    PrintAVLTree(tree);
//
//    tree.Insert(8);
//    PrintAVLTree(tree);
//
//    tree.Insert(1);
//    PrintAVLTree(tree);
//
//    tree.Insert(4);
//    PrintAVLTree(tree);
//
//    tree.Insert(7);
//    PrintAVLTree(tree);
//
//    tree.Insert(3);
//    PrintAVLTree(tree);
//
//    tree.Insert(6); // 此時應(yīng)觸發(fā)一次單旋轉(zhuǎn)
//    PrintAVLTree(tree);
    return 0;
}