#include "RBTree.hpp"
#include "AVLTree.hpp"

using namespace Lenyiin;

void test_RBTree()
{
    // int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    RBTree<int, int> t;
    for (const auto& e : a)
    {
        t.Insert(std::make_pair(e, e));
    }

    t.PreOrder();
    t.InOrder();
    t.PostOrder();
    t.LevelOrder();

    std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;

    auto node = t.Find(5);
    if (node != nullptr)
    {
        std::cout << node->_kv.first << std::endl;
    }
    else
    {
        std::cout << "没找到" << std::endl;
    }

    auto pre = t.FindPredecessor(node);
    if (pre != nullptr)
    {
        std::cout << node->_kv.first << " 的前驱节点是: " << pre->_kv.first << std::endl;
    }
    else
    {
        std::cout << "前驱节点为空" << std::endl;
    }

    auto suc = t.FindSuccessor(node);
    if (suc != nullptr)
    {
        std::cout << node->_kv.first << " 的后继节点是: " << suc->_kv.first << std::endl;
    }
    else
    {
        std::cout << "后继节点为空" << std::endl;
    }

    t.Erase(7);
    t.LevelOrder();
    std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;

    t.Erase(15);
    t.LevelOrder();
    std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;
}

void testRB_AVLTree()
{
    const int n = 100000;
    std::vector<int> v;
    v.reserve(n);
    srand(time(0));
    for (size_t i = 0; i < n; i++)
    {
        v.push_back(rand());
    }

    RBTree<int, int> rbtree;
    AVLTree<int, int> avltree;

    size_t begin1 = clock();
    for (const auto& e : v)
    {
        rbtree.Insert(std::make_pair(e, e));
    }
    size_t end1 = clock();

    size_t begin2 = clock();
    for (const auto& e : v)
    {
        avltree.Insert(std::make_pair(e, e));
    }
    size_t end2 = clock();

    std::cout << "红黑树测试时间：" << end1 - begin1 << std::endl;
    std::cout << "AVL 测试时间：\t" << end2 - begin2 << std::endl;
}

int main()
{
    test_RBTree();
    testRB_AVLTree();

    return 0;
}