#ifndef ScapegoatTreeUtils
#define ScapegoatTreeUtils

#include <cmath>

// http://en.wikipedia.org/wiki/Scapegoat_tree

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

void ScapegoatTree::Insert(TNode *&head, TNode *ins, int size = TreeCount(head), float alpha = 2/3.f);

TNode *ScapegoatTree::Remove(TNode *&head, TKey &rem, int nodeCount, int &MaxNodeCount);
TNode *ScapegoatTree::RemoveMin(TNode *head);
TNode *ScapegoatTree::RemoveMax(TNode *head);

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

bool TreeVerify(const TNode *head, int MaxNodeCount = TreeCount(head), float alpha = 2/3.f) {
*/

namespace ScapegoatTree {

// *** Internal Stuff ***
// returns next node in the list following this subtree
template <class TNode>
TNode *List2Tree(TNode *&head, int count) {
	if (count == 1) {
		TNode *last = head->right;
		head->left = head->right = NULL;
		return last;
	}
	int leftCount = count/2;
	TNode *newhead = List2Tree(head, leftCount), *last;
	if (count > 2)
		last = List2Tree(newhead->right, count-leftCount-1);
	else {
		last = newhead->right;
		newhead->right = NULL;
	}
	newhead->left = head;
	head = newhead;
	return last;
}

// O(n) : Re-balance an entire tree
template <class TNode>
void TreeRebalance(TNode *&head, int count/* = TreeCount(head)*/) {
	head = Tree2List(head);
	List2Tree(head, count);
}

// *** Utilities ***
// O(n) : Amortized O(log(n)) : Insert caller-allocated item
template <class TNode>
void Insert_Aux(TNode *&head, TNode *ins, int &scapegoatCount, int depth, float alpha) {
	//base case: the empty spot where the node should be has been found
	if (head == NULL) {
		ins->left = ins->right = NULL;
		//put it here, replacing the NULL
		head = ins;
		if (depth < 0)
			scapegoatCount = 1;	// flag that a rebalance is needed
	} else if (*ins < *head) {
		//it goes somewhere in the left sub-tree
		Insert_Aux(head->left, ins, scapegoatCount, depth-1, alpha);
		if (scapegoatCount) {
			int brotherCount = TreeCount(head->right);
			int size = scapegoatCount + brotherCount + 1;
			if (scapegoatCount > size * alpha) {
				// we found our scapegoat
				TreeRebalance(head, size);
				scapegoatCount = 0;
			} else
				scapegoatCount = size;
		}
	} else
#ifndef ALLOW_DUPLICATES
	if (*head < *ins)
#endif
	{
		//it goes somewhere in the right sub-tree
		Insert_Aux(head->right, ins, scapegoatCount, depth-1, alpha);
		if (scapegoatCount) {
			int brotherCount = TreeCount(head->left);
			int size = scapegoatCount + brotherCount + 1;
			if (scapegoatCount > size * alpha) {
				// we found our scapegoat
				TreeRebalance(head, size);
				scapegoatCount = 0;
			} else
				scapegoatCount = size;
		}
	}
#ifndef ALLOW_DUPLICATES
	else {
		// 'ins' is in the tree already; do nothing
	}
#endif
}

template <class TNode>
void Insert(TNode *&head, TNode *ins, int size/* = TreeCount(head)*/, float alpha = 2/3.f) {
	int scapegoatCount = 0;
	Insert_Aux(head, ins, scapegoatCount, static_cast<int>(log((float)size+1)/log(1/alpha)), alpha);
}

// O(n) : Amortized O(log(n)) : Remove leftmost selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *RemoveMin(TNode *head) {
	TNode *found = NULL;
	if (head != NULL) {
		FindMin_Aux(head);
		found = head;
		head = head->right;
	}
	return found;
}

// O(n) : Amortized O(log(n)) : Remove rightmost selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *RemoveMax(TNode *head) {
	TNode *found = NULL;
	if (head != NULL) {
		FindMax_Aux(head);
		found = head;
		head = head->left;
	}
	return found;
}

// O(n) : Amortized O(log(n)) : Remove selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *Remove(TNode *&head, TKey &rem, int nodeCount, int &maxNodeCount) {
	TNode *found = ::TreeRemove(head, rem);
	if (nodeCount <= maxNodeCount / 2) {
		maxNodeCount = nodeCount;
		TreeRebalance(head, nodeCount);
	}
	return found;
}

// *** 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
		ScapegoatTree::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)
			ScapegoatTree::Insert(headOut1, curr);
		else
			ScapegoatTree::Insert(headOut2, curr);
		if (r != NULL) {
			//recursively continue partitioning left subtree
			ScapegoatTree::Partition(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, int MaxNodeCount/* = TreeCount(head)*/, float alpha = 2/3.f) {
	return ::TreeVerify(head) &&
		TreeDepth(head) < static_cast<int>(log((float)MaxNodeCount*2)/log(1/alpha));
}

} //namespace ScapegoatTree

#endif