/*
 * Copyright (c) 2007 Vojtech Mencl
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup genericadt
 * @{
 */

/**
 * @file
 * @brief	Extended AVL tree implementation.
 *
 * This file implements Extended AVL tree type and operations.
 *
 * Extended AVL tree (ExtAvl tree) has the following properties:
 * @li it is binary search tree with unique keys
 * @li right subtree of every node is Avl tree
 * @li height of left subtree of every node is not greater then height of right subtree + 1
 * @li nodes with the same keys are linked to the tree nodes of the same key, they are not tree nodes
 * @li every node is part of doubly linked list with head
 * @li nodes are connected in the list ascendentaly according to their keys
 *
 * Be careful of using this tree because of base atribute, which is added to every inserted
 * node key.
 */

#include <adt/extavl.h>
#include <debug.h>
#include <panic.h>

#define AVLTREE_LEFT 0
#define AVLTREE_RIGHT 1

/* Returns height of tree -1 */ 
#define extavltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))

/** Search first occurence (oldest node with this key) of given key in Extended AVL tree.
 *
 * @param t Extended AVL tree.
 * @param key Key to be searched.
 *
 * @return Pointer to node or NULL if there is no such key.
 */
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key)
{
	extavltree_node_t *cur;

	cur = t->root;
	while (cur != NULL) {
		if (cur->key < key) {
			cur = cur->rgt;
		} else if (cur->key > key) {
			cur = cur->lft;
		} else { 
			return cur;
		}
	}
	return NULL;
}
								   
/** Insert new node into ExtAVL tree.
 *
 * New node's key must be set - to that key will be added base (default 0).
 *
 * @param t ExtAVL tree structure.
 * @param newnode New node to be inserted.
 */ 
void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode)
{	
	extavltree_node_t *cur;
	extavltree_node_t *son;
	extavltree_node_t *gpa;
	extavltree_node_t *par;
	uint64_t key;

	ASSERT(t);
	ASSERT(newnode);
	
	/*
	 * Creating absolute key.
	 */
	newnode->key = key = newnode->key + t->base;
	

	/*
	 * Insert first node into empty tree.
	 */
	if (t->root == NULL) {
		newnode->lft = NULL;
		newnode->rgt = NULL;
		newnode->lft_height = 0;
		newnode->rgt_height = 0;
		newnode->par = NULL;
		newnode->next = &t->head;
		newnode->prev = &t->head;

		t->head.prev = newnode;
		t->head.next = newnode;
		t->root = newnode;
		return;
	}

	/*
	 * Tree is not empty - search for the right place for new node.
	 */
	cur = t->root;
	while(true) {
		if (cur->key < key) {
			if (!cur->rgt) {
                		/*
				 * We have reach leaf. New node will be right son.
				 */
				cur->rgt = newnode;

				newnode->lft = NULL;
				newnode->rgt = NULL;
				newnode->lft_height = 0;
				newnode->rgt_height = 0;
                		newnode->par = cur;
				
				newnode->prev = cur;
				newnode->next = cur->next;
				cur->next->prev = newnode;
				cur->next = newnode;
                		break;
            		}
			cur = cur->rgt;
		} else if (cur->key > key) {
			if (!cur->lft) {
                		/*
				 * We have reach leaf. New node will be left son.
				 */
				cur->lft = newnode;

				newnode->lft = NULL;
				newnode->rgt = NULL;
				newnode->lft_height = 0;
				newnode->rgt_height = 0;
				newnode->par = cur;
				
				gpa = cur;
				while ((gpa != &t->head) && (gpa->key == cur->key))
					gpa = gpa->prev;
				newnode->next = gpa->next;
				newnode->prev = gpa;
				gpa->next->prev = newnode;
				gpa->next = newnode;
				break;
            		}
			cur = cur->lft;
		} else {
			/*
			 * Key has been previously inserted into tree. Make new node as a tree node
			 * and old tree node move to the prev. Old tree node will be list node.
			 */
			
			newnode->prev = cur;
			newnode->next = cur->next;
			cur->next->prev = newnode;
			cur->next = newnode;

			newnode->par = cur->par;
			cur->par = NULL;
			newnode->lft = cur->lft;
			cur->lft = NULL;
			newnode->rgt = cur->rgt;
			cur->rgt = NULL;
			newnode->lft_height = cur->lft_height;
			cur->lft_height = 0;
			newnode->rgt_height = cur->rgt_height;
			cur->rgt_height = 0;

			if (newnode->lft) newnode->lft->par = newnode;
			if (newnode->rgt) newnode->rgt->par = newnode;
			if (newnode->par) {
				if (newnode->par->lft == cur)
					newnode->par->lft = newnode;
				else
					newnode->par->rgt = newnode;
			} else {
				t->root = newnode;
			}
			return;
		}
	}

	/*
	 * Balancing all nodes from newnode's parent down to root. All nodes must be checked
	 * because delete min operation can corrupt heights and only insert operation can
	 * repair it.
	 */
	cur = newnode->par;
	while (cur) {
		if (cur->key > key) {
			/*
			 * Insertion was made in the left subtree - repair left height 
			 * and check balance of current node.
			 */
			cur->lft_height = extavltree_tree_height(cur->lft) + 1;

			if ((cur->rgt_height - cur->lft_height) <= -2) { 
				/*
				 * Balance was corrupted, must be repaired through LL or LR rotation.
				 */
				par = cur->par; 
				son = cur->lft;
				if ((son->rgt_height - son->lft_height) != 1) { 
					/*
					 * LL rotation
					 */
					
					gpa = son;
					cur->lft = son->rgt;
					if (cur->lft != NULL) cur->lft->par = cur;
					cur->par = son;
					son->rgt = cur;
					/*
					 * Repair heights.
					 */
					cur->lft_height = son->rgt_height;
					son->rgt_height = extavltree_tree_height(cur) + 1;
				} else { 
					/*
					 * LR rotation
					 */
					
					gpa = son->rgt;
					son->rgt = gpa->lft;
					if (gpa->lft != NULL) gpa->lft->par = son;
					gpa->lft = son;
					son->par = gpa;
					cur->lft = gpa->rgt;
					if (gpa->rgt != NULL) gpa->rgt->par = cur;
					gpa->rgt = cur;
					cur->par = gpa;
					/*
					 * Repair heights.
					 */
					cur->lft_height = gpa->rgt_height;
					son->rgt_height = gpa->lft_height;
					gpa->rgt_height = extavltree_tree_height(cur) + 1;
					gpa->lft_height = extavltree_tree_height(son) + 1;
				}

				/*
				 * Change parent pointers or if current node is root then 
				 * change root atribute pointer.
				 */
				gpa->par = par;
				if (par) {
					if (par->lft == cur)
						par->lft = gpa;
					else
						par->rgt = gpa;
				} else {
					t->root = gpa;
				}
				cur = par;
			} else {
				/*
				 * Current node is balanced, continue balancing of its parent.
				 */
				cur = cur->par;
			}
		} else {
			/*
			 * Insertion was made in the right subtree - repair right height 
			 * and check balance of current node.
			 */
			cur->rgt_height = extavltree_tree_height(cur->rgt) + 1;

			if ((cur->rgt_height - cur->lft_height) >= 2) {
				/*
				 * Balance was corrupted, must be repaired through LL or LR rotation.
				 */
				par = cur->par;
				son = cur->rgt;
				if ((son->rgt_height - son->lft_height) != -1) {
					/*
					 * RR rotation
					 */
					gpa = son;
					cur->rgt = son->lft;
					if (cur->rgt != NULL) cur->rgt->par = cur;
					cur->par = son;
					son->lft = cur;
					/*
					 * Repair heights.
					 */
					cur->rgt_height = son->lft_height;
					son->lft_height = extavltree_tree_height(cur) + 1;
				} else {
					/*
					 * RL rotation
					 */
					gpa = son->lft;
					son->lft = gpa->rgt;
					if (gpa->rgt != NULL) gpa->rgt->par = son;
					gpa->rgt = son;
					son->par = gpa;
					cur->rgt = gpa->lft;
					if (gpa->lft != NULL) gpa->lft->par = cur;
					gpa->lft = cur;
					cur->par = gpa;
					/*
					 * Repair heights.
					 */
					cur->rgt_height = gpa->lft_height;
					son->lft_height = gpa->rgt_height;
					gpa->lft_height = extavltree_tree_height(cur) + 1;
					gpa->rgt_height = extavltree_tree_height(son) + 1;
				}

				/*
				 * Change parent pointers or if current node is root then 
				 * change root atribute pointer.
				 */				
				gpa->par = par;
				if (par) {
					if (par->lft == cur)
						par->lft = gpa;
					else
						par->rgt = gpa;
				} else {
					t->root = gpa;
				}
				cur = par;
			} else {
				/*
				 * Current node is balanced, continue balancing of its parent.
				 */
				cur = cur->par;
			}
		} 
	}
}

/** Delete node from ExtAVL tree.
 *
 * @param t ExtAVL tree structure.
 * @param node Address of node which will be deleted.
 */
void extavltree_delete(extavltree_t *t, extavltree_node_t *node)
{
	extavltree_node_t **gpapar;
	extavltree_node_t *cur; 
	extavltree_node_t *par; 
	extavltree_node_t *gpa;
	int8_t dir;
	int8_t dir2=0;
	int16_t balance;
	
	ASSERT(t);
	ASSERT(node);

	/*
	 * Delete node from list.
	 */
	node->next->prev = node->prev;
	node->prev->next = node->next;

	if (!node->par) {
		if (t->root != node) { 
			/*
			 * It is list node (not a tree node). Needn't repair tree or anything else.
			 */
			return;
		}
		gpapar = &(t->root);
	} else {
		/*
		 * Find tree pointer which points to node.
		 */
		if (node->par->lft == node) {
			gpapar = &(node->par->lft);
		} else {
			gpapar = &(node->par->rgt);
		}
	}
	
	
	if ((&t->head != node->prev) && (node->prev->key == node->key)) {
		/*
	 	 * Deleted node has at least one node node with the same key which is closest previous 
		 * neighbor in the list, copy node atributes into previous node and end.
	 	 */
		cur = node->prev;
		cur->lft = node->lft;
		cur->rgt = node->rgt;
		cur->par = node->par;
		cur->lft_height = node->lft_height;
		cur->rgt_height = node->rgt_height;
		*gpapar = cur;

		if (node->lft) node->lft->par = cur;
		if (node->rgt) node->rgt->par = cur;
		return;
	}
	
	/*
	 * Check situation in the tree around deleted node.
	 */
	if (!node->lft) {
		/*
		 * Deleted node has not left son. Right son will take deleted node's place.
		 */
		gpa = node->par; 
		if (node->rgt) node->rgt->par = gpa;
		if (!gpa) {
			/*
			 * Deleted node is root node. Balancing is finished, change only
			 * root pointer in extavltree structure.
			 */
			*gpapar = node->rgt;	
			return;
		} 
		dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
		*gpapar = node->rgt;
	} else {
		/*
		 * Node has left son.
		 */
		cur = node->lft;
		if (!cur->rgt) {
			/*
			 * Left son of node hasn't got right son. Left son will take deleted node's place.
			 */
			*gpapar = cur;
			cur->par = node->par;
			dir = AVLTREE_LEFT;
			cur->rgt = node->rgt;
			if (node->rgt) node->rgt->par = cur; 
			gpa = cur;
			cur->rgt_height = node->rgt_height;
			cur->lft_height = node->lft_height;
			/*
			 * cur->lft_height will be decreased in repair cycle.
			 */
		} else {
			/*
			 * Node has left and right son. Find a node with smallest key in left subtree
			 * and change that node with deleted node.
			 */
			while (cur->rgt != NULL)
				cur = cur->rgt;
			
			*gpapar = cur;
			cur->rgt = node->rgt;
			if (node->rgt) node->rgt->par = cur; 
			gpa = cur->par;
			gpa->rgt = cur->lft;
			if (cur->lft) cur->lft->par = gpa;
			cur->lft = node->lft;
			cur->lft->par = cur;
			cur->par = node->par;
			dir = AVLTREE_RIGHT;
			cur->lft_height = node->lft_height;
			cur->rgt_height = node->rgt_height;
			/*
			 * gpa->rgt_height and cur->lft_height will be repaired in repair cycle.
			 */
		}
		/*
		 * Deleted node is root node. Balancing is finished.
		 */
		if (!gpa) return;
	}
	
	/*
	 * Repair cycle which goes from gpa node down to root.
	 */
	for(;;) {
		/*
		 * Find tree pointer which points to the currently balanced node. When balanced
		 * node is root, root pointer from extavltree structure is taken.
		 */
		if (!gpa->par)
			gpapar = &(t->root);
		else {
			if (gpa->par->lft == gpa) {
				gpapar = &(gpa->par->lft);
				dir2 = AVLTREE_LEFT;
			} else {
				gpapar = &(gpa->par->rgt);
				dir2 = AVLTREE_RIGHT;
			}
		}

		if (dir == AVLTREE_LEFT) {
			/*
			 * Deletition was made in left subtree.
			 */
			gpa->lft_height--;
			balance = gpa->rgt_height - gpa->lft_height;
			if (balance == 1) {
				/*
				 * Stop balancing, tree is balanced.
				 */
				break;
			} else if (balance == 2) {
				/*
				 * Bad balance, heights of left and right subtrees differs more then is allowed.
				 */
				par = gpa->rgt;

				if ((par->rgt_height - par->lft_height) == -1) {
					/*
					 * RL rotation
					 */
					
					cur = par->lft;
					par->lft = cur->rgt;
					cur->rgt = par;
					gpa->rgt = cur->lft;
					cur->lft = gpa;
					
					/*
					 * Repair balances.
					 */
					par->lft_height = cur->rgt_height;
					gpa->rgt_height = cur->lft_height;
					cur->lft_height = extavltree_tree_height(gpa) + 1; //POZOR nelze: cur->lft_height = gpa->lft_height + 1; - vyska cur je diky timeoutu nesttabilni
					cur->rgt_height = par->rgt_height + 1; //POZOR zmena: cur->rgt_height = extavltree_tree_height(par) + 1;
					
					/*
					 * Repair paternity.
					 */
					if (gpa->rgt) gpa->rgt->par = gpa;
					if (par->lft) par->lft->par = par; 
					cur->par = gpa->par;
					gpa->par = cur;
					par->par = cur;

					/*
					 * Repair tree pointer which points to the current node and do the next step.
					 */
					*gpapar = cur;
					gpa = cur->par; 
				} else {
					/*
					 * RR rotation
					 */
					
					gpa->rgt = par->lft;
					gpa->rgt_height = par->lft_height;
					if (par->lft) par->lft->par = gpa;
					par->lft = gpa;
					
					/*
					 * Repair paternity.
					 */
					par->par = gpa->par;
					gpa->par = par;
					
					/*
					 * Repair balances.
					 */
					balance = par->rgt_height - par->lft_height;
					par->lft_height++;
					
					/*
					 * Repair tree pointer which points to the current node, ends when tree is balanced 
					 * or do the next step.
					 */
					*gpapar = par;
					if (balance == 0) break;
					gpa = par->par;
				}
			} else {
				/*
				 * Current node is balanced - perform balance check of its parent.
				 */
				gpa = gpa->par;
			}
		} else { 
			/*
			 * Balance right son.
			 */
			gpa->rgt_height--;
			balance = gpa->rgt_height - gpa->lft_height;
			if (balance == -1) {
				/*
				 * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion.
				 */
				break;
			} else if (balance == -2) {
				/*
				 * Balance was corrupted - must be repaired.
				 */
				par = gpa->lft;

				if ((par->rgt_height - par->lft_height) >= +1) { 
					/*
					 * If balance is -2 then par node always exists.
					 */
					if ((gpa->lft_height - (extavltree_tree_height(par))) == 1) {
						/*
						 * LR rotation. Height of par subtree is not decreased due to timeout operation.
						 */
						
						cur = par->rgt;
						par->rgt = cur->lft;
						cur->lft = par;
						gpa->lft = cur->rgt;
						cur->rgt = gpa;
						
						/*
					 	 * Repair balances.
					 	 */						
						par->rgt_height = cur->lft_height;
						gpa->lft_height = cur->rgt_height;
						cur->rgt_height = gpa->rgt_height + 1; 
						cur->lft_height = extavltree_tree_height(par) + 1;

						/*
						 * Repair paternity.
						 */
						if (gpa->lft) gpa->lft->par = gpa;
						if (par->rgt) par->rgt->par = par;
						cur->par = gpa->par;
						gpa->par = cur;
						par->par = cur;

						/*
					 	 * Repair tree pointer which points to the current node and do the next step.
						 */
						*gpapar = cur;
						gpa = cur->par; 
					} else {
					       	/*
						 * Left subtree of cur has been already decreased by timeout operation.
						 */	
						gpa = gpa->par;
					}
				} else { 
					/*
					 * LL rotation.
					 */
					
					int prevlftheight = gpa->lft_height;
					gpa->lft = par->rgt;
					gpa->lft_height = par->rgt_height;
					if (par->rgt) par->rgt->par = gpa;
					par->rgt = gpa;
					
					/*
					 * Repair paternity.
					 */
					par->par = gpa->par;
					gpa->par = par;
					
					/*
					 * Repair height.
					 */
					balance = par->rgt_height - par->lft_height;
					par->rgt_height = extavltree_tree_height(gpa) + 1;
					
					/*
					 * Repair tree pointer which points to the current node, ends when heights in par nodes are
					 * balanced and height of par subtree wasn't decreased due to timeout operation orr do 
					 * the next step.
					 */
					*gpapar = par;	
					if (balance == 0 && par->rgt_height == prevlftheight) return;
					gpa = par->par;
				}
			} else {
				/*
				 * Current node is balanced - perform balance check of its parent.
				 */
				gpa = gpa->par;
			}
		}
		/*
		 * When root is reached then end balancing.
		 */
		if (!gpa) return;

		dir = dir2;
	} 
}


/** Delete node from ExtAVL tree with the smallest key.
 *
 * @param t ExtAVL tree structure.
 */
bool extavltree_delete_min(extavltree_t *t)
{
	extavltree_node_t *expnode;
	
	ASSERT(t);
	
	expnode = t->head.next;
	
	if (&t->head == expnode) return false;

	if (expnode->key != expnode->next->key) {
		/*
		 * Repair tree data structure.
		 */
		if (!expnode->par) {
			/*
			 * Delete root node which musn't have left son.
			 */
			
			ASSERT(!expnode->lft);
			t->root = expnode->rgt;
			if (expnode->rgt) expnode->rgt->par = NULL;
		} else if (expnode->rgt) {
			/*
			 * Always delete parent of left son.
			 */
			
			expnode->rgt->par = expnode->par;
			expnode->par->lft = expnode->rgt;
			expnode->par->lft_height = expnode->rgt_height;
		} else {
			/*
			 * Deleted node doesn't have right son.
			 */
			
			expnode->par->lft = NULL;
			expnode->par->lft_height = 0;
		}
	} else if (expnode->next == &t->head) {
		/*
		 * Special case of deleting last node with key equal 0.
		 */
		t->root = NULL;
	}
	
	/*
	 * Delete node from the list.
	 */
	t->head.next = expnode->next;
	expnode->next->prev = &t->head;

	return true;
}