#ifndef AATreeUtils
#define AATreeUtils

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

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

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

namespace AATree {

// *** Internal Stuff ***
template <class TNode>
void Skew(TNode *&head) {
	if (head->left != NULL && head->level == head->left->level) {
		TNode *x = head->left;
		head->left = x->right;
		x->right = head;
		head = x;
	}
}

template <class TNode>
void Split(TNode *&head) {
	if (head->right != NULL && head->right->right != NULL &&
			head->level == head->right->right->level) {
		TNode *x = head->right;
		head->right = x->left;
		x->left = head;
		head = x;
		++head->level;
	}
}

// *** Utilities ***
// O(log(n)) : Insert caller-allocated item
template <class TNode>
void Insert_Aux(TNode *&head, TNode *ins) {
	//base case: the empty spot where the node should be has been found
	if (head == NULL) {
		ins->left = ins->right = NULL;
		ins->level = 0;
		//put it here, replacing the NULL
		head = ins;
		return;
	}
	if (*ins < *head) {
		//it goes somewhere in the left sub-tree
		Insert_Aux(head->left, ins);
	} else
#ifndef ALLOW_DUPLICATES
	if (*head < *ins)
#endif
	{
		//it goes somewhere in the right sub-tree
		Insert_Aux(head->right, ins);
	}
#ifndef ALLOW_DUPLICATES
	else {
		// 'ins' is in the tree already; do nothing
		return;
	}
#endif
	Skew(head);
	Split(head);
}

template <class TNode>
inline void Insert(TNode *&head, TNode *ins) {
	Insert_Aux(head, ins);
}

/*****************
*** Unfinished ***
*****************/
// O(log(n)) : Remove selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *Remove(TNode *&head, TKey &rem) {
	static TNode *DeletePtr = NULL, *LastPtr = NULL;
	TNode *found;

	if (head == NULL) {
		found = NULL; // Not found
	} else {
		// Step 1: Search down tree
		//         set LastPtr and DeletePtr
		LastPtr = head;
		if (rem < *head)
			found = AATree::Remove(head->left, rem);
		else /*if (*head < rem)*/ {
			DeletePtr = head;
			found = AATree::Remove(head->right, rem);
		}

		// Step 2: If at the bottom of the tree and
		//         item is present, we remove it
		if (head == LastPtr && DeletePtr != NULL && rem == *DeletePtr) {
			found = head;
			DeletePtr->item = head->item;
			DeletePtr = NULL;
			head = head->right;
		}

		// Step 3: Otherwise, we are not at the bottom;
		//         rebalance
		else if (
			head->left != NULL && head->left->level < head->level - 1 ||
			head->right != NULL && head->right->level < head->level - 1)
		{
			if (head->right->level > --head->level)
				head->right->level = head->level;
			Skew(head);
			Skew(head->right);
			Skew(head->right->right);
			Split(head);
			Split(head->right);
		}
	}
	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
		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)
			AATree::Insert(headOut1, curr);
		else
			AATree::Insert(headOut2, curr);
		if (r != NULL) {
			//recursively continue partitioning left subtree
			AATree::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, const int &headlevel) {
	if (head != NULL) {
		if (head->left != NULL) {
			if ((*head < *(head->left))
			|| (head->right == NULL)
			|| (head->level == head->left->level)
			|| !Verify(head->left, head->level)) return false;
		}
		if (head->right != NULL) {
			if ((*(head->right) < *head)
			|| (headlevel == head->level && head->level == head->right->level)
			|| !Verify(head->right, head->level)) return false;
		}
	}
	return true;
}	

template <class TNode>
bool Verify(const TNode *head) {
	int headlevel = -1;
	return Verify(head, headlevel);
}

} //namespace AATree

#endif