# Red-Black Tree Map
# Properties of a Red-Black tree map:
# * every node is either red or black
# * root is black
# * every leaf (null) is black
# * if a node is red, then both its children are black
# * for each node, all simple path from the node to descendant
#   leaves contain the same number of black nodes
#
# Operations:
# * search average O(lg n) worst O(lg n)
# * insert average O(lg n) worst O(lg n)
# * delete average O(lg n) worst O(lg n)
class RBTreeMap[K: Comparable, E]
	super BinTreeMap[K, E]

	redef type N: RBTreeNode[K, E]

	redef fun []=(key, item) do
		insert_node(new RBTreeNode[K, E](key, item))
	end

	redef fun insert_node(node) do
		super
		insert_fixup_case1(node)
	end

	# Case 1: node is root
	# color node as black
	# it adds a black node on every path so we do nothing else
	private fun insert_fixup_case1(node: N) do
		if node.parent == null then
			node.is_red = false
		else
			insert_fixup_case2(node)
		end
	end

	# Case 2: parent is black
	# it do not add black node so we do nothing else
	private fun insert_fixup_case2(node: N) do
		if node.parent.is_red then insert_fixup_case3(node)
	end

	# Case 3: node, parent and uncle are red
	# this is a LLr or RRr conflict
	# we recolor recursively the tree to the root
	private fun insert_fixup_case3(node: N) do
		if node.uncle != null and node.uncle.is_red then
			node.parent.is_red = false
			node.uncle.is_red = false
			node.grandparent.is_red = true
			insert_fixup_case1(node.grandparent.as(not null))
		else
			insert_fixup_case4(node)
		end
	end

	# Case 4: node and parent are red, uncle is black
	# this is a LRb or RLb conflict
	# we rotate the tree to balance it
	private fun insert_fixup_case4(node: N) do
		if node == node.parent.right and node.parent == node.grandparent.left then
			rotate_left(node.parent.as(not null))
			node = node.left.as(not null)
		else if node == node.parent.left and node.parent == node.grandparent.right then
			rotate_right(node.parent.as(not null))
			node = node.right.as(not null)
		end
		insert_fixup_case5(node)
	end

	# Case 5: node and parent are red, uncle is black
	# this is a LLb or RRb conflict
	# we rotate the tree to balance it
	private fun insert_fixup_case5(node: N) do
		node.parent.is_red = false
		node.grandparent.is_red = true
		if node == node.parent.left then
			rotate_right(node.grandparent.as(not null))
		else
			rotate_left(node.grandparent.as(not null))
		end
	end

	# TODO implement RBTree::delete
	redef fun delete(key) is abstract

	redef fun dot_down(node, f) do
		if node.left != null then dot_down(node.left.as(not null), f)
		f.write node.to_dot
		if node.parent != null then f.write "\"{node.parent.as(not null)}\" -> \"{node}\"[dir=back];\n"
		if node.right != null then dot_down(node.right.as(not null), f)
	end
end