#ifndef TreeUtils
#define TreeUtils

#define ALLOW_DUPLICATES

#include "AVLTreeUtils.h"
#include "RedBlackTreeUtils.h"
#include "AATreeUtils.h"
#include "SplayTreeUtils.h"
#include "ScapegoatTreeUtils.h"

#pragma warning (disable : 4127)

/*
int TreeCount(const TNode *head);
TNode *Prev(const TNode *head, const TNode *curr);
TNode *Next(const TNode *head, const TNode *curr);
void InorderProcess(TNode *head, void ProcessItem(TNode *item)) {

TNode *Find(TNode *head, const TKey &find);
TNode *FindMin(TNode *head);
TNode *FindMax(TNode *head);

void TreeInsert(TNode *&head, TNode *ins);

TNode *TreeRemove(TNode *&head, TKey &rem);
TNode *TreeRemoveMin(TNode *&head);
TNode *TreeRemoveMax(TNode *&head);
void RemoveAll(TNode *head);

TNode *TreeMerge(TNode *head1, TNode *head2);
void TreePartition(TNode *headIn1, const TKey &splitter, TNode *&headOut1, TNode *&headOut2);
TNode *Tree2List(TNode *tree);

bool TreeVerify(const TNode *head);
bool DectectCycles(const TNode *head);
*/

// Returns the number of items in the tree
template <class TNode>
int TreeCount(const TNode *head) {
	int count = 0;
	while (head != NULL) {
		//recursively count left nodes (add one for this node)
		count += TreeCount(head->left) + 1;
		//iteratively count right nodes
		head = head->right;
	}
	return count;
}

template <class TNode>
int TreeDepth(const TNode *head) {
	if (head != NULL) {
		//recursively count depth (add one for this node)
		int lcount = TreeDepth(head->left);
		int rcount = TreeDepth(head->left);
		//iteratively count right depth
		return (lcount < rcount ? rcount : lcount) + 1;
	}
	return 0;
}

// O(n) : Average O(log(n))
template <class TNode>
TNode *Prev(const TNode *head, const TNode *curr) {
	if (head == NULL) return NULL;
#ifndef ALLOW_DUPLICATES
	if (*curr < *head) return Prev(head->left, curr);
	else if (*head < *curr) {
		const TNode *temp = Prev(head->right, curr);
		return (temp != NULL) ? temp : head;
	} else {
		return head->left;
	}
#else
	if (head == curr) return head->left;
	if (!(*head < *curr)) return Prev(head->left, curr);
	const TNode *temp = Prev(head->right, curr);
	return (temp != NULL) ? temp : head;
#endif
}

// O(n) : Average O(log(n))
template <class TNode>
TNode *Next(const TNode *head, const TNode *curr) {
	if (head == NULL) return NULL;
#ifndef ALLOW_DUPLICATES
	if (*head < *curr) return Next(head->right, curr);
	else if (*curr < *head) {
		const TNode *temp = Next(head->left, curr);
		return (temp != NULL) ? temp : head;
	} else {
		return head->right;
	}
#else
	if (head == curr) return head->right;
	if (!(*curr < *head)) return Next(head->right, curr);
	const TNode *temp = Next(head->left, curr);
	return (temp != NULL) ? temp : head;
#endif
}

// O(n)
template <class TNode>
void InorderProcess(TNode *head, void ProcessItem(TNode *item)) {
	while (head != NULL) {
		InorderProcess(head->left, ProcessItem);
		ProcessItem(head);
		head = head->right;
	}
}

// *** Searching ***
// O(n)
template <class TNode, class TKey>
TNode *Find(TNode *head, const TKey &find) {
	const TNode *curr = head;
	while (curr != NULL) {
		if (find < *curr) //is it less than
			curr = curr->left;
		else if (*curr < find) //is it greater than
			curr = curr->right;
		else //okay it must be equal - found
			break;
	}
	return curr;
}

// O(n)
template <class TNode>
TNode *FindMin(TNode *head) {
    if (head != NULL) {
		//while there are more left branches go left
        while (head->left != NULL)
            head = head->left;
	}
    return head;
}

// O(n)
template <class TNode>
TNode *FindMax(TNode *head) {
    if (head != NULL) {
		//while there are more right branches go right
        while (head->right != NULL)
            head = head->right;
	}
    return head;
}

// *** Utilities ***
// O(n) : Insert caller-allocated item
template <class TNode>
void TreeInsert(TNode *&head, TNode *ins) {
	TNode *curr = head;
	ins->left = ins->right = NULL;
	if (head == NULL) {
		head = ins;
	} else do {
		if (*ins < *curr) {
			//it goes somewhere in the left sub-tree
			if (curr->left == NULL) {
				curr->left = ins;
				break;
			}
			curr = curr->left;
		} else
#ifndef ALLOW_DUPLICATES
		if (*curr < *ins)
#endif
		{
			//it goes somewhere in the right sub-tree
			if (curr->right == NULL) {
				curr->right = ins;
				break;
			}
			curr = curr->right;
		}
#ifndef ALLOW_DUPLICATES
		else {
			// 'ins' is in the tree already; do nothing
			break;
		}
#endif
	} while (true);
}

template <class TNode>
TNode *TreeRemoveMin_Aux(TNode *&head) {
	TNode *found;
	//special case used for finding the node to replace a higher deleted node
	if (head->left != NULL)
		found = TreeRemoveMin_Aux(head->left);
	else {
		//if we got here then we have found the item
		found = head;
		//there is no left node, put any right one as the new parent
		head = head->right;
	}
	return found;
}

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

template <class TNode>
TNode *TreeRemoveMax_Aux(TNode *&head) {
	TNode *found;
	//special case used for finding the node to replace a higher deleted node
	if (head->right != NULL)
		found = TreeRemoveMax_Aux(head->right);
	else {
		//if we got here then we have found the item
		found = head;
		//there is no right node, put any left one as the new parent
		head = head->left;
	}
	return found;
}

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

// O(n) : Remove selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *TreeRemove(TNode *&head, TKey &rem) {
	TNode *found;
	//unexpected case: the item was not even in the tree
	if (head == NULL) {
		return NULL; // Not found
	} else if (rem < *head) {
		//the item to be removed is in the left sub-tree
		return TreeRemove(head->left, rem);
	} else if (*head < rem) {
		//the item to be removed is in the right sub-tree
		return TreeRemove(head->right, rem);
	} else {
		//if we got here then we have found the item
		found = head;
		if (head->left == NULL) {
			//there is no left node, put the right one as the new parent
			//the right could be NULL, but if so this also does what we want.
			head = head->right;
		} 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;
		} 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 = TreeRemoveMin_Aux(head->right);
			//now copy all of the old details in the node being reused
			temp->left = head->left;
			temp->right = head->right;
			//switch it with the old one
			head = temp;
		}
		return found;
	}
}

// O(n) : Remove all items - Deletion is performed here
template <class TNode>
void RemoveAll(TNode *&head) {
	TNode *it = head;
	while (it != NULL) {
		TNode *temp = it;
		if (it->right != NULL) {
			//recursively remove all nodes in the left subtree
			RemoveAll(it->left);
			//iteratively remove all nodes in the right subtree
			it = it->right;
		} else
			//iteratively remove all nodes in the left subtree
			it = it->left;
		delete temp;
	}
	head = NULL;
}

// O(n) : Remove all items (non recursive!) - Deletion is performed here
template <class TNode>
void RemoveAll_Iterative(TNode *&head) {
	TNode *it = head, *save;
	while (it != NULL) {
		if (it->left != NULL) {
			// Right rotation
			save = it->left;
			it->left = save->right;
			save->right = it;
		} else {
			save = it->right;
			delete it;
		}
		it = save;
	}
	head = NULL;
}

// *** Combining ***
//This could be made iterative in the same way as RemoveAll_Iterative above
// O(n*n) fastest if head2 has fewer items
template <class TNode>
TNode *TreeMerge(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
		TreeInsert(head1, curr);
		if (r != NULL) {
			//recursively add original left subtree
			head1 = TreeMerge(head1, l);
			//iteratively add original right subtree
			curr = r;
		} else
			//iteratively add original left subtree
			curr = l;
	}
	return head1;
}

// O(n*n)
template <class TNode, class TKey>
void TreePartition(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)
			TreeInsert(headOut1, curr);
		else
			TreeInsert(headOut2, curr);
		if (r != NULL) {
			//recursively continue partitioning left subtree
			TreePartition(l, splitter, headOut1, headOut2);
			//iteratively continue partitioning right subtree
			curr = r;
		} else
			//iteratively continue partitioning left subtree
			curr = l;
	}
}

template <class TNode>
bool TreeVerify(const TNode *head) {
	while (head != NULL) {
		if (head->left != NULL) {
			if ((*head < *(head->left))
			|| !TreeVerify(head->left)) return false;
		}
		if (head->right != NULL) {
			if (*(head->right) < *head) return false;
		}
		head = head->right;
	}
	return true;
}

template <class TNode>
bool DectectCyclesAux1(const TNode *slowCursor, const TNode *fastCursor) {
	if (!slowCursor || !fastCursor) return false;
	if (slowCursor == fastCursor) return true;
	return DectectCyclesAux2(slowCursor, fastCursor->left)
		|| DectectCyclesAux2(slowCursor, fastCursor->right);
}

template <class TNode>
bool DectectCyclesAux2(const TNode *slowCursor, const TNode *fastCursor) {
	if (!slowCursor || !fastCursor) return false;
	if (slowCursor == fastCursor ||
		slowCursor == fastCursor->left ||
		slowCursor == fastCursor->right) return true;
	return DectectCyclesAux1(slowCursor->left, fastCursor->left)
		|| DectectCyclesAux1(slowCursor->left, fastCursor->right)
		|| DectectCyclesAux1(slowCursor->right, fastCursor->left)
		|| DectectCyclesAux1(slowCursor->right, fastCursor->right);
}

template <class TNode>
bool DectectCycles(const TNode *head) {
	if (!head) return false;
	return DectectCycles1(head, head->left)
		|| DectectCycles1(head, head->right);
}

// http://thedailywtf.com/forums/thread/77314.aspx
// Converts a tree to a doubly-linked list
template <class TNode>
TNode *Tree2ListHelper(TNode *list, TNode *tree) {
	for (;;) {
		if (tree->right) {
			list = Tree2ListHelper(list, tree->right);
			list->left = tree;
		} else if (list)
			list->left = tree;
		tree->right = list;
		if (!tree->left)
			return tree;
		list = tree;
		tree = tree->left;
	}
}

template <class TNode>
TNode *Tree2List(TNode *tree) {
	if (!tree)
		return NULL;
	return Tree2ListHelper((TNode*)NULL, tree);
}

#pragma warning (default : 4127)

#endif