template <class T>
struct RBTreeNode
{
	T _data;// 我們不清楚紅黑樹結(jié)點(diǎn)里面存的是什么,可能是string，內(nèi)置類型，又或是鍵值對(duì)，取決于map和set里面存的是什么
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	enum color _col;

	RBTreeNode(const T& data)
		:_data(data)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
	{}
};

template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
	
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;//pair鍵值對(duì)的關(guān)鍵嗎是常量
	};

template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:

	private:
		RBTree<K, K, SetKeyOfT> _t;
	};


template <class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;// T代表紅黑樹結(jié)點(diǎn)的存儲(chǔ)內(nèi)容的類型

	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		bool insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};

template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		bool insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

template<class T>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T> Self;
	Node* _node;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}

	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}

			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		//右子樹 根 左子樹
		if (_node->_left)
		{
			//找左子樹的最右結(jié)點(diǎn)，其實(shí)就是次大的結(jié)點(diǎn)
			_node = _node->_left;
			while (_node->_right)
			{
				_node = _node->_right;
			}
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;

			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//如果cur是parent的右，則直接讓_node指向到parent即可
			_node = parent;
		}

		return *this;//返回迭代器對(duì)象
	}
	bool operator!=(const Self& it)const//const修飾表示在該成員函數(shù)內(nèi)部，不能修改對(duì)象的任何成員變量
	{
		return this->_node != it._node;
	}

	bool operator==(const Self& it)const//const對(duì)象和非const對(duì)象都可以調(diào)用
	{
		return this->_node == it._node;
	}
};

template <class K>
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
	template <class K>	
	class set
	{
	public:
		//set表層的普通迭代器底層用的依舊是const_iterator，就是不允許對(duì)set的迭代器指向內(nèi)容進(jìn)行修改
		typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator const_iterator;
		iterator begin()//const
		{
			return _t.begin();
			//普通對(duì)象調(diào)用的begin()返回的是普通迭代器，而set上層要求返回的都是const迭代器，發(fā)生類型不兼容問題
			//庫是怎么解決的呢？
			// 
			//set的begin和end沒有提供兩個(gè)版本，僅僅只提供了const版本，強(qiáng)制性要求set的普通對(duì)象和const對(duì)象底層都去調(diào)用
			//紅黑樹const版本的begin()和end()
			//注意：如果是普通對(duì)象發(fā)生調(diào)用const函數(shù)，那么在const函數(shù)內(nèi)部，普通對(duì)象也會(huì)被當(dāng)作const對(duì)象進(jìn)行處理。
			//      所以底層調(diào)用的紅黑樹的begin，自動(dòng)就是const版本的begin()
		}
		iterator end()//const
		{
			return _t.end();
		}

template <class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;// node里面存的是鍵值對(duì)或key類型變量
	typedef __RBTreeIterator<T, Ref, Ptr> Self;//迭代器
	
	Ref operator*()
	{
		return _node->_data;// 如果是set就是key，如果是map就是鍵值對(duì),這里返回引用
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
}


template <class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;// T代表紅黑樹結(jié)點(diǎn)的存儲(chǔ)內(nèi)容的類型
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
	iterator begin()//給普通對(duì)象調(diào)用
	{
		Node* left = _root;
		while (left && left->_left)// 這棵樹有可能是空樹，若不為空樹找到左樹最小結(jié)點(diǎn)
		{
			left = left->_left;
		}

		return iterator(left);// 不能瞎用引用啊，這里的迭代器對(duì)象出了begin()作用域就銷毀了，引用就出大事了！
	}
	const_iterator begin()const//給const對(duì)象調(diào)用
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}

		return const_iterator(left);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	const_iterator end()const
	{
		return const_iterator(nullptr);
	}

template <class K, class V>
class map
{
public:
	// 1.取未實(shí)例化類模板里面的類型時(shí)，無論是內(nèi)部類還是內(nèi)嵌類型，都需要加typename，告訴編譯器類模板后面的東西是類型
	// 因?yàn)轭惸０謇锩孢€有可能是靜態(tài)成員，靜態(tài)成員也是可以通過類名+域訪問符進(jìn)行訪問的，編譯器無法確定是類型還是靜態(tài)成員
	// 2.圖紙里面怎么能直接取東西呢？肯定是需要對(duì)這樣的情況進(jìn)行特殊處理的
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K,V>>::iterator iterator;
	// 編譯器不會(huì)編譯模板，編譯的都是模板實(shí)例化之后的代碼，所以iterator是靜態(tài)成員還是內(nèi)嵌類型，編譯器都確定不了。
	//typename就是先告訴一下編譯器，這里是類型，先不要取這個(gè)類型，等到模板實(shí)例化好之后你再去取這個(gè)類型。
	//圖紙里面有水果，你先不要去拿這個(gè)水果，等到按照?qǐng)D紙實(shí)例化為蘋果樹之后，你再取這個(gè)蘋果
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;

	//map的迭代器需要提供兩個(gè)版本
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	const_iterator begin()const
	{
		return _t.begin();
	}
	const_iterator end()const
	{
		return _t.end();
	}
private:
	RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t;
};

pair<iterator, bool> Insert(const T& data)
//紅黑樹必須通過結(jié)點(diǎn)里面存儲(chǔ)的key來進(jìn)行比較才可以插入結(jié)點(diǎn)，所以出現(xiàn)了kot仿函數(shù)對(duì)象
{
	KeyOfT kot;
	Node* parent = nullptr;
	Node* cur = _root;
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return make_pair(iterator(_root), true);
	}

	while (cur)
	{
		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* curit = cur;//保存一下cur的位置否則下面旋轉(zhuǎn)調(diào)色過程中，cur有可能被改了
	if (kot(parent->_data) > kot(data))
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	while (parent && parent->_col == RED)
	{
		Node* grandparent = parent->_parent;
		if (parent == grandparent->_left)
		{
			Node* uncle = grandparent->_right;

			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;

				cur = grandparent;
				parent = cur->_parent;
			}
			else if (cur == parent->_left)
			{
				RotateR(grandparent);
				grandparent->_col = RED;
				parent->_col = BLACK;
				break;
			}
			else if (cur == parent->_right)
			{
				RotateL(parent);
				RotateR(grandparent);
				cur->_col = BLACK;
				grandparent->_col = RED;
				break;
			}
			else
			{
				assert(false);
			}
		}
		else
		{
			Node* uncle = grandparent->_left;
			if (uncle && uncle->_col == RED)
			{
				grandparent->_col = RED;
				uncle->_col = parent->_col = BLACK;

				cur = grandparent;
				parent = cur->_parent;
			}
			else if (cur == parent->_right)
			{
				RotateL(grandparent);
				parent->_col = BLACK;
				grandparent->_col = RED;
				break;
			}

			else if (cur == parent->_left)
			{
				RotateR(parent);
				RotateL(grandparent);
				cur->_col = BLACK;
				grandparent->_col = RED;
				break;
			}
			else
			{
				assert(false);
			}
		}
	}
	_root->_col = BLACK;
	
	return make_pair(iterator(curit), true);
}

pair<iterator, bool> Insert(const T& data)
//紅黑樹必須通過結(jié)點(diǎn)里面存儲(chǔ)的key來進(jìn)行比較才可以插入結(jié)點(diǎn)，所以出現(xiàn)了kot仿函數(shù)對(duì)象
{
	KeyOfT kot;
	Node* parent = nullptr;
	Node* cur = _root;
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return make_pair(iterator(_root), true);
	}

	while (cur)
	{
		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* curit = cur;//保存一下cur的位置否則下面旋轉(zhuǎn)調(diào)色過程中，cur有可能被改了
	if (kot(parent->_data) > kot(data))
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	while (parent && parent->_col == RED)
	{
		Node* grandparent = parent->_parent;
		if (parent == grandparent->_left)
		{
			Node* uncle = grandparent->_right;

			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;

				cur = grandparent;
				parent = cur->_parent;
			}
			else if (cur == parent->_left)
			{
				RotateR(grandparent);
				grandparent->_col = RED;
				parent->_col = BLACK;
				break;
			}
			else if (cur == parent->_right)
			{
				RotateL(parent);
				RotateR(grandparent);
				cur->_col = BLACK;
				grandparent->_col = RED;
				break;
			}
			else
			{
				assert(false);
			}
		}
		else
		{
			Node* uncle = grandparent->_left;
			if (uncle && uncle->_col == RED)
			{
				grandparent->_col = RED;
				uncle->_col = parent->_col = BLACK;

				cur = grandparent;
				parent = cur->_parent;
			}
			else if (cur == parent->_right)
			{
				RotateL(grandparent);
				parent->_col = BLACK;
				grandparent->_col = RED;
				break;
			}

			else if (cur == parent->_left)
			{
				RotateR(parent);
				RotateL(grandparent);
				cur->_col = BLACK;
				grandparent->_col = RED;
				break;
			}
			else
			{
				assert(false);
			}
		}
	}
	_root->_col = BLACK;
	
	return make_pair(iterator(curit), true);
}

int main()
{
	list<int> lt;
	vector<int> v;
	list<int>::const_iterator clit = lt.begin();
	vector<int>::const_iterator cvit = v.begin();

	return 0;
}

template <class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;// node里面存的是鍵值對(duì)或key類型變量
	typedef __RBTreeIterator<T, Ref, Ptr> Self;//迭代器
	typedef __RBTreeIterator<T, T&, T*> iterator;
	Node* _node;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}
	//如果是const迭代器調(diào)用，這里是構(gòu)造。如果是普通迭代器調(diào)用，這里是拷貝構(gòu)造。
	__RBTreeIterator(const iterator& it)
		:_node(it._node)
	{}

template <class K>	
class set
{
public:
	pair<iterator, bool> insert(const K& key)//這里的迭代器被替換為const_iterator
	{
		//return _t.Insert(key);
		//Insert返回的是普通迭代器，普通迭代器不能直接拷貝構(gòu)造給const迭代器，類型不同，但我們可以自己寫拷貝構(gòu)造。
		//這里肯定不能再使用const修飾來進(jìn)行解決了，因?yàn)閕nsert功能就是要寫嘛，又不具有讀的功能，實(shí)現(xiàn)const版本干嘛？？？
	
		pair<typename RBTree<K, K, SetKeyOfT<K>>::iterator, bool> ret = _t.Insert(key);
		//必須用紅黑樹底層的普通迭代器類型接收Insert返回的鍵值對(duì)，因?yàn)閟et的所有迭代器都是底層const迭代器typedef出來的
	
		return pair<iterator, bool>(ret.first, ret.second);
		//這里在利用Insert的返回值重新拷貝構(gòu)造一個(gè)鍵值對(duì)，用普通迭代器構(gòu)造const迭代器，然后返回具有const迭代器的鍵值對(duì)
	
	
		//********set這個(gè)地方即使自己寫了拷貝構(gòu)造，在返回的時(shí)候也依舊不能直接強(qiáng)轉(zhuǎn)，這誰能想到??？？？？？？？？？？？？
	}
private:
	RBTree<K, K, SetKeyOfT<K>> _t;
};