#include<iostream>
#include<cassert>
using namespace std;
enum Color//利用枚举来给红黑树配色
{
  RED,
  BLACK
};
template<class T>
struct RBTreeNode
{
  RBTreeNode(const T& data)
    :_data(data)
    , _color(RED)//这里一定要给红色，如果给黑色其他路径就要涉及到也要加黑色结点，更加麻烦
    , _left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
  {}
  RBTreeNode* _left;
  RBTreeNode* _right;
  RBTreeNode* _parent;
  T _data;
  Color _color;//结点的配色
};
template<class T,class Ref, class Ptr>
struct RBTreeIterator//红黑树的迭代器
{
  typedef RBTreeNode<T> Node;
  typedef RBTreeIterator<T, Ref, Ptr> Self;
  typedef RBTreeIterator<T, T&, T*> iterator;
  Node* _node;
  RBTreeIterator(Node* node)
    :_node(node)
  {}
  //普通迭代器传给普通迭代器用的是默认生成的拷贝构造
  //当迭代器是const的时候用的就是普通迭代器构造的const迭代器
  RBTreeIterator(const iterator& s)
    :_node(s._node)
  {}
  Ref operator*()
  {
    return _node->_data;
  }
  Ptr operator->()
  {
    return &_node->_data;
  }
  Self& operator++()
  {
    if (_node->_right)//右子树不为空
    {
      Node* cur = _node->_right;
      while (cur->_left)
      {
        cur = cur->_left;
      }
      _node = cur;
    }
    else//左子树为空
    {
      Node* parent = _node->_parent;
      Node* cur = _node;
      while (parent && parent->_left != cur)
      {
        cur = parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  Self& operator--()
  {
    if (_node->_left)//左子树不为空
    {
      Node* cur = _node->_left;
      while (cur && cur->_right)
      {
        cur = cur->_right;
      }
      _node = cur;
    }
    else
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      while (parent && cur != parent->_right)
      {
        cur = parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  bool operator!=(const Self& it)
  {
    return _node != it._node;
  }
  bool operator==(const Self& it)
  {
    return _node == it._node;
  }
};
template<class K, class T, class KeyOFV>
class RBTree
{
  typedef RBTreeNode<T> Node;
public:
  typedef RBTreeIterator<T, T&, T*> iterator;
  typedef RBTreeIterator<T, const T&, const T*> const_iterator;
  iterator begin()
  {
    Node* cur = _root;
    while (cur && cur->_left)
    {
      cur = cur->_left;
    }
    return iterator(cur);
  }
  iterator end()
  {
    return iterator(nullptr);
  }
  const_iterator begin()const
  {
    Node* cur = _root;
    while (cur && cur->_left)
    {
      cur = cur->_left;
    }
    return const_iterator(cur);
  }
  const_iterator end()const
  {
    return const_iterator(nullptr);
  }
  pair<iterator, bool> Insert(const T& data)
  {
    if (_root == nullptr)
    {
      _root = new Node(data);
      _root->_color = BLACK;
      return make_pair(iterator(_root), true);
    }
    Node* cur = _root;
    Node* parent = nullptr;
    KeyOFV kot;//仿函数对象
    while (cur)
    {
      if (kot(cur->_data) > kot(data))
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (kot(cur->_data) < kot(data))
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return make_pair(iterator(cur), false);
      }
    }
    cur = new Node(data);//这里默认是红色结点
    Node* newnode = cur;//因为cur会变位置，所以储存一下新节点
    if (kot(parent->_data) > kot(data))
    {
      cur->_parent = parent;
      parent->_left = cur;
    }
    else if (kot(parent->_data) < kot(data))
    {
      cur->_parent = parent;
      parent->_right = cur;
    }
    //如果父节点为空就代表cur是根节点，没必要调整了
    //还要判断cur结点是否与父节点的颜色均为红色
    while (parent && parent->_color == RED)
    {
      Node* grandfather = parent->_parent;//祖父结点
      if (parent == grandfather->_left)//新增结点在祖父左
      {
        Node* uncle = grandfather->_right;
        //情况一
        if (uncle && uncle->_color == RED)//这里不要忘记验证uncle的存在
        {
          parent->_color = BLACK;
          uncle->_color = BLACK;
          grandfather->_color = RED;
          cur = grandfather;//最后让cur等于祖父结点的位置
          parent = cur->_parent;
        }
        else
        {
          if (parent->_left == cur)//情况二
          {
            RotateR(grandfather);//右单旋
            grandfather->_color = RED;
            parent->_color = BLACK;
          }
          else if (parent->_right == cur)//情况三
          {
            RotateL(parent);//左单旋
            RotateR(grandfather);//右单旋
            cur->_color = BLACK;
            grandfather->_color = RED;
          }
          break;//第二种和第三种情况变完之后因为最上面的组节点变为黑，所以这里跳出循环
        }
      }
      else//新增结点在祖父右
      {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_color == RED)//情况一
        {
          uncle->_color = BLACK;
          parent->_color = BLACK;
          grandfather->_color = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else {
          if (cur == parent->_right)//情况二
          {
            RotateL(grandfather);
            grandfather->_color = RED;
            parent->_color = BLACK;
          }
          else if (cur == parent->_left)//情况三
          {
            RotateR(parent);
            RotateL(grandfather);
            cur->_color = BLACK;
            grandfather->_color = RED;
          }
          break;
        }
      }
    }
    _root->_color = BLACK;
    return make_pair(iterator(newnode), true);
  }
  void RotateL(Node* parent)//左单旋
  {
    Node* pparent = parent->_parent;
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (pparent)
    {
      if (pparent->_left == parent)
        pparent->_left = subR;
      else
        pparent->_right = subR;
    }
    else
    {
      _root = subR;
    }
    subR->_parent = pparent;
  }
  void RotateR(Node* parent)//右单旋
  {
    Node* pparent = parent->_parent;
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (pparent)
    {
      if (pparent->_left == parent)
        pparent->_left = subL;
      else
        pparent->_right = subL;
    }
    else
    {
      _root = subL;
    }
    subL->_parent = pparent;
  }
  void Inorder()
  {
    _Inorder(_root);
  }
  bool IsBalanceTree()
  {
    if (_root == nullptr)
      return true;
    if (_root->_color != BLACK)
    {
      cout << "根不为黑色" << endl;
      return false;
    }
    int count = 0;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_color == BLACK)
        count++;
      cur = cur->_left;//找一条路径上的黑节点
    }
    _IsBalanceTree(_root, 0, count);
  }
private:
  bool _IsBalanceTree(Node* root, int k, int sum)//验证
  {
    if (root == nullptr)
    {
      if (k == sum)//这里代表当前路径点和最左边的路径点相同
        return true;
      else
      {
        cout << "每条路径上黑色结点数量不同" << endl;
      }
      return false;
    }
    if (root->_color == BLACK)
      k++;
    if (root->_parent && root->_parent->_color == RED && root->_color == RED)
    {
      cout << root->_parent->_data.first << endl;
      return false;
    }
    return _IsBalanceTree(root->_left, k, sum) && _IsBalanceTree(root->_right, k, sum);
  }
  void _Inorder(Node* _root)
  {
    if (_root == nullptr)
      return;
    _Inorder(_root->_left);
    cout << _root->_data.first << ":" << _root->_data.second << endl;
    _Inorder(_root->_right);
  }
  Node* _root = nullptr;
};

#include"RBTree.h"
namespace baiye
{
  template<class K>
  class set
  {
    struct setKeyOFV
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    typedef typename RBTree<K, K, setKeyOFV>::const_iterator iterator;//这里无论是非const迭代器也不能修改set的值，所以要变成const版本
    typedef typename RBTree<K, K, setKeyOFV>::const_iterator const_iterator;
    iterator begin()const
    {
      return _t.begin();
    }
    iterator end()const
    {
      return _t.end();
    }
    pair<iterator, bool> insert(const K& key)
    {
      pair<typename RBTree<K, K, setKeyOFV>::iterator, bool> it = _t.Insert(key);//这里接收的是普通迭代器
      return pair<iterator, bool>(it.first, it.second);//这里用普通迭代器构造const迭代器
    }
  private:
    RBTree<K, K, setKeyOFV> _t;
  };
  void settest()
  {
    int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    set<int>s;
    for (auto& e : arr)
    {
      s.insert(e);
    }
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl;
  }
}

#include"RBTree.h"
namespace baiye
{
  template<class K, class V>
  class map
  {
    struct mapKeyOFV
    {
      const K& operator()(const pair<const K, V>& kv)
      {
        return kv.first;
      }
    };
  public:
    typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::iterator iterator;
    typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::const_iterator const_iterator;
    iterator begin()
    {
      return _p.begin();
    }
    iterator end()
    {
      return _p.end();
    }
    const_iterator begin()const
    {
      return _p.begin();
    }
    const_iterator end()const
    {
      return _p.end();
    }
    pair<iterator, bool> insert(const pair<const K, V>& kv)
    {
      return _p.Insert(kv);
    }
    V& operator[](const K& key)
    {
      pair<iterator, bool> it = insert(make_pair(key, V()));
      return it.first->second;
    }
  private:
    RBTree<K, pair<const K, V>, mapKeyOFV> _p;
  };
  void maptest()
  {
    int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    map<int, int> m;
    for (auto& e : arr)
    {
      m.insert(make_pair(e, e));
    }
    map<int, int>::iterator it = m.begin();
    while (it != m.end())
    {
      cout << it->first << " ";
      ++it;
    }
    cout << endl;
  }
}