#pragma once
#include<iostream>
#include<map>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<cassert>
#include<time.h>
using namespace std;
enum Color
{
  RED,
  BLACK
};
//此时按照库里面的代码实现方法，所以此时我们需要把这棵红黑树进行一定的改变（重点也就是模板参数的改变，从两个模板参数变成一个）
//从而让这棵红黑树满足泛型的要求，可以达到传不同的模板参数就能实现不同的类型（具体指的是：key模型、key/value模型）
//但是注意：此时因为map中调用红黑树时，传的是pair结构体，并且pair结构体比较大小的方式和我们实现的比较方式是有区别的，所以需要改进
template<class T>
class RBTreeNode
{
public:
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  T _data;
  Color _color;
  RBTreeNode(const T& data)
    :_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(RED)
  {}
};
//搞定了模板参数比较大小的问题，此时进入迭代器有关问题
template<class T, class Ref, class Ptr>//此时Ref/Ptr这两个模板参数可以说是异常的熟悉，不服就去复习list（目的：就是为了实现const类型的迭代器和普通类型的迭代器）
struct __RBTreeIterator
{
  typedef RBTreeNode<T> Node;
  typedef __RBTreeIterator<T, Ref, Ptr> iterator;
  Node* _node;
  __RBTreeIterator(Node* node)//用一个node来构造该迭代器（如下述使用cur结点，iterator(cur)）
    :_node(node)
  {}
  //此时由于set的普通迭代器和const迭代器都是const迭代器，所以当set在使用 iterator begin(){ return _t.begin()};
  //时，就会因为_t.begin()接口是红黑树中的接口，所以是一个普通迭代器，但是返回值iterator却是一个const迭代器
  //所以我们需要有一个普通迭代器转换为const迭代器的构造函数（不好理解）
  //但是此时想要实现这个构造函数，此时有一个坑，因为我们使用的是模板，所以并不知道对应迭代器是什么类型，所以需要把模板参数给到
  __RBTreeIterator(const __RBTreeIterator<T, T&, T*>& it)
    :_node(it._node)//注意：const迭代器可以隐式类型转换成普通迭代器
  {}
  //1.typedef __RBTreeIterator<T, T&, T*> iterator;如果传到上述拷贝构造函数的是这个类型，那么此时就是拷贝构造函数
  //2.typedef __RBTreeIterator<T, const T&, const T*> const_iterator;如果是这个类型，那么此时就是构造函数（本质就是自己构造成自己 ）
  Ref operator*()//解引用返回的自然而然就是对应的数据
  {
    return _node->_data;
  }
  Ptr operator->()//这个位置有待复习
  {
    return &_node->_data;
  }
  bool operator==(const iterator& it)
  {
    return _node == it._node;
  }
  bool operator!=(const iterator& it)
  {
    return _node != it._node;
  }
  iterator& operator++()
  {//红黑树的加加，就是按照中序走走而已（但，注意：此时的++的前提是，已经处于begin位置了，所以根本不需要找begin位置）
    if (_node->_right != nullptr)
    {//1.此时表示的就是当右子树存在的时候，我们就去找右子树的最左结点（注意：是在最左结点的前提下）
      Node* subLeft = _node->_right;
      while (subLeft->_left != nullptr)          //         13
      {                                          //       8    17
        subLeft = subLeft->_left;              //     1  11 15 25
      }                                          //      6      22 27
      _node = subLeft;
    }
    else
    {//2.右为空，我们就沿着根的路径，找孩子是父亲左的那个祖先(也就是当++了一步，从1来到6的时候，此时6的右为空，我们就需要返回到8)
     //此时的8也就是6的祖先，也就是祖先的左孩子是6的父亲的那个结点
      Node* cur = _node;
      Node* parent = cur->_parent;
      while (parent != nullptr && parent->_right == cur)//这步一定要先判断一个parent不等于nullptr，不然如果为空，就会导致很坑，因为使用了空指针去访问parent指针
      {
        cur = parent;
        parent = parent->_parent;//这步就是为了找到8，并且为了防止死循环，所以上述条件一定需要指明cur在那个结点的右
      }
      //代码走到这里，就说明，找到祖先结点，也就是下一个结点，此时迭代就行
      _node = parent;
    }
    return *this;//this表示Node结点指针的地址，而*this表示的就是this指针指向的地址
  }
  iterator operator--()
  {//减减同理加加，中序左根右，减减就变成右根左
    if (_node->_left != nullptr)
    {
      //1.左不为空，找左子树的最右孩子
      Node* subRight = _node-> _left;
      while (subRight->_right != nullptr)
      {
        subRight = subRight->_right;
      }
      _node = subRight;
    }
    else//2.明白条件，也就是左为空的情况下
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      while (parent != nullptr && parent->_left == cur)                           //         13
      {//上面这个循环不要困惑，如果在左边的话，不进循环之间找父结点进行           //       8    17
        cur = parent;                                                           //     1  11 15 25
        parent = parent->_parent;                                               //      6      22 27
      }                                                          
      _node = parent;
    }
  }
};
//此时由于map和set中比较大小的方式不同，所以红黑树中的比较方式需要改变，最好的方法就是使用仿函数
//也就是让key去比较大小，而不是直接用pair去比较大小，所以此时也就是把pair中的key取出来，使用pair中的key去进行比较
template<class K, class T,class KeyOfT>//此时红黑树本身是不知道T是什么的，只有调用这棵红黑树的类知道，所以此时需要改进
class RBTree                           //例：map知道它是pair结构体，而set知道它是Key(所以此时就使用这个参数作为一个返回值去使用)
{                                      //并且明白：这个位置写博客的时候要去画一个图
public:
  typedef RBTreeNode<T> Node;
  typedef __RBTreeIterator<T, T&, T*> iterator;
  typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
public:
  RBTree()
    :_root(nullptr)
  {}
  ~RBTree()
  {
    _Destory(_root);
    _root = nullptr;//好习惯
  }
  iterator begin()
  {
    Node* cur = _root;
    while (cur != nullptr && cur->_left != nullptr)//目的：找最左结点
    {
      cur = cur->_left;
    }
    return iterator(cur);//调用迭代器类中的结点构造函数，构造一个Node结点
  }
  iterator end()
  {
    return iterator(nullptr);//注意：end是最后一个结点的下一个数据，所以直接用空去构造就行了
  }
  const_iterator begin()const
  {
    Node* cur = _root;
    while (cur != nullptr && cur->_left != nullptr)
    {
      cur = cur->_left;
    }
    return const_iterator(cur);
  }
  const_iterator end()const
  {
    return const_iterator(nullptr);
  }
  Node* Find(const K& key)
  {
    Node* cur = _root;
    KeyOfT kot;
    while (cur != nullptr)
    {
      if (kot(cur->_data) > key)//表示的就是使用KeyOfT去定义一个对象，帮助我们取出对应模板类型的data数据，本质是在调用（）这个仿函数
      {
        cur = cur->_left;
      }
      else if (kot(cur->_data) < key)
      {
        cur = cur->_right;
      }
      else
      {
        return cur;
      }
    }
    return nullptr;
  }
  pair<iterator,bool> Insert(const T& data)//此时一定要支持map实现方括号，实现方括号就涉及到插入接口
  {
    if (_root == nullptr)
    {
      _root = new Node(data);
      _root->_color = BLACK;
      return make_pair(iterator(_root), true);//注意：方括号的返回值一定是返回两个量，一个是迭代器的地址，一个是bool值，值得注意的是，迭代器的地址中对于map来说就是一个pair结构体
    }
    KeyOfT kot;
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur != nullptr)
    {
      if (kot(cur->_data) < kot(data))
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (kot(cur->_data) > kot(data))
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return make_pair(iterator(cur), false);
      }
    }
    cur = new Node(data);//此时默认初始化的时候，创建的就是一个红色结点
    Node* newnode = cur;//此时因为cur会不断的迭代，所以这个位置需要先保存一下
    //cur->_color = RED;
    if (kot(parent->_data) > kot(data))
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    while (parent != nullptr && parent->_color == RED)//因为变色可能会一直向上，直到遇到root结点，所以需要判断到root结点，也就是parent=nullptr的时候
    {
      //根据原理：1.将父结点和叔叔结点变成黑色，爷爷结点变成黑色（前提是uncle不为空）
      Node* pparent = parent->_parent;
      if (pparent->_left == parent)//叔叔结点需要判断左右
      {
        Node* uncle = pparent->_right;
        //此时就找到叔叔结点了，根据原理，此时就需要进行判断
        if (uncle != nullptr && uncle->_color == RED)
        {
          //（uncle存在且为红）满足该条件，就走自己的变色规则（parent和uncle变红，pparent变黑）就行
          parent->_color = BLACK;
          uncle->_color = BLACK;
          pparent->_color = RED;
          //搞定完之后，再根据原理，需要判断爷爷结点的父结点是红色还是黑色（迭代循环走走）
          cur = pparent;
          parent = cur->_parent;
          //parent = pparent->_parent;//这种写法虽然更快，但是没有真正按照迭代的原理来，每一步都要按照原理来最好，容易看懂
        }
        else
        {     
          if (parent->_left == cur)
          {
            //满足该条件就是一个单旋
            RotateR(pparent);
            parent->_color = BLACK;
            pparent->_color = RED;
          }
          else
          {
            //双旋
            RotateL(parent);
            RotateR(pparent);
            cur->_color = BLACK;//双旋会导致cur去做根，所以cur变黑，单旋由于parent做根，所以parent变黑
            pparent->_color = RED;
            //上面两步就是双旋变色的关键，下面这个变色可有可无
            parent->_color = RED;//这个只是为了保持红色而已，本质上没有变，最终让代码还可以进入循环进行判断，防止有的场景问题
          }
          break;//单旋或者双旋完，此时该子树的颜色就正常了，就可以退出该循环了
        }
      }
      else
      {
        Node* uncle = pparent->_left;
        if (uncle != nullptr && uncle->_color == RED)//同理
        {
          //符合变色规则，就开始变色
          parent->_color = BLACK;
          uncle->_color = BLACK;
          pparent->_color = RED;
          cur = pparent;
          parent = cur->_parent;
          //parent = pparent->_parent;//最好不要这样写，因为这样写，会导致cur的位置没有改变，迭代不了cur，只迭代了parent
        }
        else
        {//两个场景是类似的，可以当作一个场景看
          if (parent->_right == cur)
          {
            RotateL(pparent);
            parent->_color = BLACK;
            pparent->_color = RED;
          }
          else
          {
            RotateR(parent);
            RotateL(pparent);
            cur->_color = BLACK;
            pparent->_color = RED;
          }
          break;
        }
      }
    }
    _root->_color = BLACK;//此时就可以不需要判断，某个根结点的父结点是否为空，因为如果爷爷结点的父结点为黑色了，这个循环就会被终止，这步就是多余的，但是如果是真的走到了root结点，root结点被置红了，那么循环终止的这个代码就尤为重要
    return make_pair(iterator(newnode), true);//因为会迭代，所以需要使用newnode，不能使用cur
  }
private:
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* pparent = parent->_parent;
    parent->_right = subRL;
    if (subRL != nullptr)
    {
      subRL->_parent = parent;
    }
    subR->_left = parent;
    parent->_parent = subR;
    if (pparent == nullptr)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = subR;
      }
      else
      {
        pparent->_right = subR;
      }
      subR->_parent = pparent;
    }
  }
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* pparent = parent->_parent;
    parent->_left = subLR;
    if (subLR != nullptr)
    {
      subLR->_parent = parent;
    }
    subL->_right = parent;
    parent->_parent = subL;
    if (pparent == nullptr)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = subL;
      }
      else
      {
        pparent->_right = subL;
      }
      subL->_parent = pparent;
    }
  }
public:
  void _Destory(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _Destory(root->_left);
    _Destory(root->_right);
    delete root;
  }
  void InOrder()//中序打印AVL树
  {
    _InOrder(_root);
    cout << endl;
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    else
    {
      _InOrder(root->_left);//这边递归不要传参，你真的是人才啊
      cout << root->_kv.first << " ";
      _InOrder(root->_right);
    }
  }
private:
  Node* _root;
};