#ifndef RedBlackTreeUtils
#define RedBlackTreeUtils

/*
void RBTree::Insert(TNode *&head, TNode *ins);

TNode *RBTree::Remove(TNode *&head, TKey &rem);
TNode *RBTree::RemoveMin(TNode *&head);
TNode *RBTree::RemoveMax(TNode *&head);

TNode *RBTree::Merge(TNode *head1, TNode *head2);
void RBTree::Partition(TNode *headIn1, const TKey &splitter, TNode *&headOut1, TNode *&headOut2);

bool RBTree::Verify(const TNode *head);
*/

namespace RBTree {

// *** Internal Stuff ***
template <class TNode> inline bool red(const TNode *x) {
	if (x == NULL) return false;
	return x->red;
}
template <class TNode> inline void rotR(TNode *&h) {
	TNode *x = h->left; h->left = x->right;
	x->right = h; h = x;
}
template <class TNode> inline void rotL(TNode *&h) {
	TNode *x = h->right; h->right = x->left;
	x->left = h; h = x;
}
template <class TNode> void rotRL(TNode *&h) {
	TNode *y = h->right, *x = y->left;
	y->left = x->right; x->right = y;
	h->right = x->left; x->left = h;
	h = x;
}
template <class TNode> void rotLR(TNode *&h) {
	TNode *y = h->left, *x = y->right;
	y->right = x->left; x->left = y;
	h->left = x->right; x->right = h;
	h = x;
}

// *** Utilities ***
// O(log(n)) : Insert caller-allocated item
template <class TNode>
void Insert(TNode *&head, TNode *ins, bool sw) {
	//base case: the empty spot where the node should be has been found
	if (head == NULL) {
		ins->left = ins->right = NULL;
		ins->red = true;
		//put it here, replacing the NULL
		head = ins;
		return;
	}
	if (red(head->left) && red(head->right)) {
		//split '4-nodes' on the way down
		head->red = true;
		head->left->red = false;
		head->right->red = false;
	}
	if (*ins < *head) {
		//it goes somewhere in the left sub-tree
		RBTree::Insert(head->left, ins, false);
		if (head->red && head->left->red && sw)
			rotR(head);
		if (red(head->left) && red(head->left->left)) {
			rotR(head);
			head->red = false;
			head->right->red = true;
		}
	} else
#ifndef ALLOW_DUPLICATES
	if (*head < *ins)
#endif
	{
		//it goes somewhere in the right sub-tree
		RBTree::Insert(head->right, ins, true);
		if (head->red && head->right->red && !sw)
			rotL(head); 
		if (red(head->right) && red(head->right->right)) {
			rotL(head);
			head->red = false;
			head->left->red = true;
		}
	}
#ifndef ALLOW_DUPLICATES
	else {
		// 'ins' is in the tree already; do nothing
	}
#endif
}
template <class TNode>
inline void Insert(TNode *&head, TNode *ins) {
	Insert(head, ins, false);
	head->red = false;
}

//returns true if the height decreased
template <class TNode>
bool RbFixupRightHeavy(TNode *&head) {
	if (head->left == NULL) {
		if (head->red) {
			if (head->right->left == NULL) {
				rotL(head);
			} else {
				rotRL(head);
				head->left->red = false;
			}
		} else {
			TNode *const right = head->right;
			if (!right->red) {
				if (right->right == NULL) {
					if (right->left == NULL) {
						right->red = true;
						return true;
					} else {
						rotRL(head);
						head->red = false;
					}
				} else {
					rotL(head);
					head->right->red = false;
				}
			} else {
				if (right->left->left == NULL) {
					if (right->left->right == NULL) {
						rotL(head);
						head->red = false;
						head->left->right->red = true;
					} else {
						rotRL(head);
						head->right->left->red = false;
					}
				} else {
					rotL(head);
					rotRL(head->left);
					head->red = false;
				}
			}
		}
	} else {
		if (head->red) {
			if (!red(head->right->left)) {
				rotL(head);
			} else {
				rotRL(head);
				head->left->red = false;
			}
		} else {
			if (head->left->red) {
				//This case is never reached.
				head->left->red = false;
			} else {
				TNode *const right = head->right;
				if (!right->red) {
					if (!right->left->red) {
						if (!right->right->red) {
							right->red = true;
							return true;
						} else {
							rotL(head);
							head->right->red = false;
						}
					} else {
						rotRL(head);
						head->red = false;
					}
				} else {
					if (!right->left->right->red) {
						if (!right->left->left->red) {
							rotL(head);
							head->left->right->red = true;
						} else {
							rotL(head);
							rotRL(head->left);
						}
						head->red = false;
					} else {
						rotRL(head);
						head->right->left->red = false;
					}
				}
			}
		}
	}
	return false;
}

//returns true if the height decreased
template <class TNode>
bool RbFixupLeftHeavy(TNode *&head) {
	if (head->right == NULL) {
		if (head->red) {
			if (head->left->right == NULL) {
				rotR(head);
			} else {
				rotLR(head);
				head->right->red = false;
			}
		} else {
			TNode *const left = head->left;
			if (!left->red) {
				if (left->left == NULL) {
					if (left->right == NULL) {
						left->red = true;
						return true;
					} else {
						rotLR(head);
						head->red = false;
					}
				} else {
					rotR(head);
					head->left->red = false;
				}
			} else {
				if (left->right->right == NULL) {
					if (left->right->left == NULL) {
						rotR(head);
						head->red = false;
						head->right->left->red = true;
					} else {
						rotLR(head);
						head->left->right->red = false;
					}
				} else {
					rotR(head);
					rotLR(head->right);
					head->red = false;
				}
			}
		}
	} else {
		if (head->red) {
			if (!red(head->left->right)) {
				rotR(head);
			} else {
				rotLR(head);
				head->right->red = false;
			}
		} else {
			if (head->right->red) {
				//This case is never reached.
				head->right->red = false;
			} else {
				TNode *const left = head->left;
				if (!left->red) {
					if (!left->right->red) {
						if (!left->left->red) {
							left->red = true;
							return true;
						} else {
							rotR(head);
							head->left->red = false;
						}
					} else {
						rotLR(head);
						head->red = false;
					}
				} else {
					if (!left->right->left->red) {
						if (!left->right->right->red) {
							rotR(head);
							head->right->left->red = true;
						} else {
							rotR(head);
							rotLR(head->right);
						}
						head->red = false;
					} else {
						rotLR(head);
						head->left->right->red = false;
					}
				}
			}
		}
	}
	return false;
}

template <class TNode>
TNode *RemoveMin(TNode *&head, bool &heightDecrease) {
	TNode *found;
	//special case used for finding the node to replace a higher deleted node
	if (head->left != NULL) {
		//remove node from left subtree
		found = RemoveMin(head->left, heightDecrease);
		if (heightDecrease) heightDecrease = RbFixupRightHeavy(head);
	} else {
		found = head;
		//there is no left node, put any right one as the new parent
		head = head->right;
		heightDecrease = !found->red && head == NULL;
		if (head != NULL) head->red = false;
	}
	return found;
}

// O(log(n)) : Remove leftmost selected item - caller responsible for deallocation
template <class TNode>
TNode *RemoveMin(TNode *&head) {
	bool heightDecrease;
	if (head == NULL) return NULL;
	return RemoveMin(head, heightDecrease);
}

template <class TNode>
TNode *RemoveMax(TNode *&head, bool &heightDecrease) {
	TNode *found;
	//special case used for finding the node to replace a higher deleted node
	if (head->right != NULL) {
		//remove node from left subtree
		found = RemoveMax(head->right, heightDecrease);
		if (heightDecrease) heightDecrease = RbFixupLeftHeavy(head);
	} else {
		found = head;
		//there is no right node, put any left one as the new parent
		head = head->left;
		heightDecrease = !found->red && head == NULL;
		if (head != NULL) head->red = false;
	}
	return found;
}

// O(log(n)) : Remove rightmost selected item - caller responsible for deallocation
template <class TNode>
TNode *RemoveMax(TNode *&head) {
	bool heightDecrease;
	if (head == NULL) return NULL;
	return RemoveMax(head, heightDecrease);
}

// O(log(n)) : Remove selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *Remove(TNode *&head, TKey &del, bool &heightDecrease) {
	TNode *found;
	if (head == NULL) {
		heightDecrease = false;
		found = NULL; // Not found
	} else if (del < *head) {
		//it could be somewhere in the left sub-tree
		found = RBTree::Remove(head->left, del, heightDecrease);
		if (heightDecrease) heightDecrease = RbFixupRightHeavy(head);
	} else if (*head < del) {
		//it could be somewhere in the right sub-tree
		found = RBTree::Remove(head->right, del, heightDecrease);
		if (heightDecrease) heightDecrease = RbFixupLeftHeavy(head);
	} else {
		//if we got here then we have found the item
		found = head;
		if (head->left == NULL) {
			//there is no left node, put any right one as the new parent
			//the right could be NULL, but if so this also does what we want.
			head = head->right;
			heightDecrease = !found->red && head == NULL;
			if (head != NULL) head->red = false;
		} else if (head->right == NULL) {
			//there was no right node, but we already know there is a left one so use that
			head = head->left;
			heightDecrease = false;
			head->red = false;
		} else {
			//difficult case: We need to find a replacement for this node in the tree.
			//this uses leftmost node of the right sub-tree
			TNode *temp = RemoveMin(head->right, heightDecrease);
			//now copy all of the old details in the node being reused
			temp->left = head->left;
			temp->right = head->right;
			temp->red = head->red;
			//switch it with the old one
			head = temp;
			//rebalance in case the remove above unbalanced the tree
			if (heightDecrease) heightDecrease = RbFixupLeftHeavy(head);
		}
	}
	return found;
}

// O(n) : Remove selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *Remove(TNode *&head, TKey &del) {
	bool heightDecrease;
	return Remove(head, del, heightDecrease);
}

// *** Combining ***
// O(nlog(n+m)) fastest if head2 has fewer items
template <class TNode>
TNode *Merge(TNode *head1, TNode *head2) {
	TNode *l, *r, *curr = head2;
	while (curr != NULL) {
		//remember both children
		l = curr->left;
		r = curr->right;
		//insert current node into other tree
		RBTree::Insert(head1, curr);
		if (r != NULL) {
			//recursively add original left subtree
			head1 = Merge(head1, l);
			//iteratively add original right subtree
			curr = r;
		} else
			//iteratively add original left subtree
			curr = l;
	}
	return head1;
}

// O(nlog(n))
template <class TNode, class TKey>
void Partition(TNode *headIn1, const TKey &splitter, TNode *&headOut1, TNode *&headOut2) {
	TNode *l, *r, *curr = headIn1;
	while (curr != NULL) {
		//remember both children
		l = curr->left;
		r = curr->right;
		//decide which list to insert into
		if (*curr < splitter)
			RBTree::Insert(headOut1, curr);
		else
			RBTree::Insert(headOut2, curr);
		if (r != NULL) {
			//recursively continue partitioning left subtree
			RBTree::Partition(l, splitter, headOut1, headOut2);
			//iteratively continue partitioning right subtree
			curr = r;
		} else
			//iteratively continue partitioning left subtree
			curr = l;
	}
}

template <class TNode>
bool Verify(const TNode *head, int &numBlack) {
	int numLeft=0, numRight=0;
	if (head != NULL) {
		if (head->left != NULL) {
			if ((*head < *(head->left))
			|| (head->red && head->left->red)
			|| !Verify(head->left, numLeft)) return false;
		}
		if (head->right != NULL) {
			if ((*(head->right) < *head)
			|| (head->red && head->right->red)
			|| !Verify(head->right, numRight)) return false;
		}
		if (numLeft != numRight) return false;
		numBlack = numLeft + (head->red ? 0 : 1);
	}
	return true;
}	

template <class TNode>
bool Verify(const TNode *head) {
	int numBlack=0;
	return (!red(head)) && Verify(head, numBlack);
}

} //namespace RBTree

#endif