/*
 * Copyright (c) 2006 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	AVL tree implementation.
 *
 * This file implements AVL tree type and operations.
 *
 * Implemented AVL tree has the following properties:
 * @li it is binary search tree with non-unique keys
 * @li Difference of heights of left and right subtree of every node is max 1.
 *
 * Every node has pointer to its parent which allows insertion of multiple identical keys
 * into tree.
 * 
 * Be careful of using this tree because of base atribute, which is added to every inserted
 * node key. There is no rule in which order nodes with the same key are visited.
 */

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


#define AVLTREE_LEFT 0
#define AVLTREE_RIGHT 1


/** Search first occurence of given key in AVL tree.
 *
 * @param t AVL tree.
 * @param key Key to be searched.
 *
 * @return Pointer to value or NULL if there is no such key.
 */
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
{
	avltree_node_t *p;
	
	/*
	 * Iteratively descend to the leaf that can contain the searched key.
	 */
	p = t->root;
	while (p != NULL) {
		if (p->key > key)
			p = p->lft;
		else if (p->key < key)
			p = p->rgt;
		else { 
			return p;
		}
	}
	return NULL;
}


/** Insert new node into AVL tree.
 *
 * @param t AVL tree.
 * @param newnode New node to be inserted.
 */ 
void avltree_insert(avltree_t *t, avltree_node_t *newnode)
{	
	avltree_node_t *par; 
	avltree_node_t *gpa;
	avltree_node_t *top;
	avltree_node_t **dpc;
	uint64_t key;

	ASSERT(t);
	ASSERT(newnode);

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

	/*
	 * Iteratively descend to the leaf that can will contain new node.
	 * Last node with non-zero balance in the way to leaf is stored as top -
	 * it si place of possible balance failure.
	 */
	dpc = &t->root;
	gpa = NULL;
	top = t->root;
	while (par = *dpc) {
		if (par->balance != 0) {
			top = par;
		}
		gpa = par;
		dpc = par->key > key? &par->lft: &par->rgt;
	}

	/*
	 * Initialize new node.
	 */
	newnode->key = key;
	newnode->lft = NULL;
	newnode->rgt = NULL;
	newnode->par = gpa;
	newnode->balance = 0;

	/*
	 * Insert first node into empty tree.
	 */
	if (t->root == NULL) {
		*dpc = newnode;
		return;
	}

	/*
	 * Insert new node into previously found leaf place.
	 */
	*dpc = newnode;

	/*
	 * If tree contains one node - end.
	 */
	if (top == NULL) return;

	/*
	 * Store pointer of top's father which points to the node with potentialy broken 
	 * balance (top).
	 */
	if (top->par == NULL)
		dpc = &t->root;
	else 
		if (top->par->lft == top)
			dpc = &(top->par->lft);
		else
			dpc = &(top->par->rgt);

	/*
	 * Repair all balances on the way from top node to newly inserted node.
	 */
	par = top;
	while (par != newnode) {
		if (par->key > key) {
			par->balance--;
			par = par->lft;
		} else {
			par->balance++;
			par = par->rgt;
		}
	}
	
	/*
	 * To balance tree we must check and balance top node.
	 */
	if (top->balance == -2) {
		par = top->lft;
		if (par->balance == -1) {
			/*
			 * LL rotation.
			 */
			top->lft = par->rgt;
			if (top->lft != NULL) top->lft->par = top;
			par->par = top->par;
			top->par = par;
			par->rgt = top;
			par->balance = top->balance = 0;
			*dpc = par;
		} else { 
			/*
			 * LR rotation.
			 */
			ASSERT(par->balance == 1);
			
			gpa = par->rgt;
			par->rgt = gpa->lft;
			if (gpa->lft != NULL) gpa->lft->par = par;
			gpa->lft = par;
			par->par = gpa;
			top->lft = gpa->rgt;
			if (gpa->rgt != NULL) gpa->rgt->par = top;
			gpa->rgt = top;
			gpa->par = top->par;
			top->par = gpa;
			
			if (gpa->balance == -1) {
				par->balance = 0;
				top->balance = 1;
			} else if (gpa->balance == 0) {
				par->balance = top->balance = 0;
			} else {
				par->balance = -1;
				top->balance = 0;
			}
			gpa->balance = 0;
			*dpc = gpa;
		}
	} else if (top->balance == 2) { 
		par = top->rgt;
		if (par->balance == 1) {
			/*
			 * RR rotation.
			 */
			top->rgt = par->lft;
			if (top->rgt != NULL) top->rgt->par = top;
			par->par = top->par;
			top->par = par;
			par->lft = top;
			par->balance = top->balance = 0;
			*dpc = par;
		} else {
			/*
			 * RL rotation.
			 */
			ASSERT(par->balance == -1);
			
			gpa = par->lft;
			par->lft = gpa->rgt;
			if (gpa->rgt != NULL) gpa->rgt->par = par;
			gpa->rgt = par;
			par->par = gpa;
			top->rgt = gpa->lft;
			if (gpa->lft != NULL) gpa->lft->par = top;
			gpa->lft = top;
			gpa->par = top->par;
			top->par = gpa;

			if (gpa->balance == 1) {
				par->balance = 0;
				top->balance = -1;
			} else if (gpa->balance == 0) {
				par->balance = top->balance = 0;
			} else {
				par->balance = 1;
				top->balance = 0;
			}
			gpa->balance = 0;
			*dpc = gpa;
		}
	} else { 
		/*
		 * Balance is not broken, insertion is finised.
		 */
		return;
	}

}

/** Delete node from AVL tree.
 *
 * Because of allowed multiple identical keys parent pointers are essential
 * during deletition.
 * 
 * @param t AVL tree structure.
 * @param node Address of node which will be deleted.
 */
void avltree_delete(avltree_t *t, avltree_node_t *node)
{
	avltree_node_t *cur;
	avltree_node_t *par;
	avltree_node_t *gpa;
	uint8_t dir;

	ASSERT(t);
	ASSERT(node);
	
	
	if (node->lft == NULL) { 
		if (node->rgt) {
			/*
			 * Replace node with its only right son. 
			 *
			 * Balance of right son will be repaired in balancing cycle.
			 */
			cur = node->rgt;
			cur->par = node->par;
			gpa = cur;
			dir = AVLTREE_RIGHT;
			cur->balance = node->balance; 
		} else {
			if (node->par == NULL) {
				/*
				 * Tree has only one node - it will be empty tree and balancing can end.
				 */
				t->root = NULL;
				return;
			}
			/*
			 * Node has no child, will be deleted with no substitution.
			 */
			gpa = node->par;
			cur = NULL;
			dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
		}
	} else {
		/*
		 * Node has left and right son. Find a node with smallest key in left subtree
		 * and replace deleted node with that node.
		 */
		for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
			;
		
		//cur obsahuje uzel, ktery vlozim misto uzlu node
		
		if (cur != node->lft) {
			/*
			 * The most right node of deleted node's left subtree was found. Replace
			 * deleted node with this node. Cutting founded node has two cases in 
			 * dependence on its left son.
			 */ 
			if (cur->lft) {
				/*
				 * Founded node has left son.
				 */
				gpa = cur->lft;
				gpa->par = cur->par;
				dir = AVLTREE_LEFT;
				gpa->balance = cur->balance; 
			} else {
				dir = AVLTREE_RIGHT;
				gpa = cur->par;
			}
			cur->par->rgt = cur->lft;
			cur->lft = node->lft;
			cur->lft->par = cur; 
		} else { 
			/*
			 * Left son of node hasn't got right son. Left son will take deleted node's place.
			 */
			dir = AVLTREE_LEFT;
			gpa = cur; 
		}
		if (node->rgt) node->rgt->par = cur; 
		cur->rgt = node->rgt;
		cur->balance = node->balance;
		cur->par = node->par;
	}
	
	/*
	 * Repair parent nodes pointer which pointed previously to deleted node.
	 */
	if (node->par == NULL) { 
		t->root = cur;
	} else { 
		if (node->par->lft == node) {
			node->par->lft = cur;
		} else {
			node->par->rgt = cur;
		}
	}
	
	/*
	 * Repair cycle which repairs balances of nodes in way from cutted noded down to root.
	 */
	for(;;) {
		if (dir == AVLTREE_LEFT) {
			/*
			 * Deletition was made in left subtree.
			 */
			gpa->balance++;
			if (gpa->balance == +1) {
				/*
				 * Stop balancing, tree is balanced.
				 */
				break;
			} else if (gpa->balance == +2) { 
				/*
				 * Bad balance, heights of left and right subtrees differs more then is allowed.
				 */
				par = gpa->rgt;

				if (par->balance == -1)	{
					/*
					 * RL rotation.
					 */
					
					cur = par->lft;
					par->lft = cur->rgt;
					cur->rgt = par;
					gpa->rgt = cur->lft;
					cur->lft = gpa;
					
					/*
					 * Repair balances and paternity of childs in dependence on
					 * balance factor of grand child (cur).
					 */
					if (cur->balance == +1) {
						par->balance = 0;
						gpa->balance = -1;
						if (gpa->rgt) gpa->rgt->par = gpa;
						par->lft->par = par; 
					} else if (cur->balance == 0) {
						par->balance = gpa->balance = 0;
						if (gpa->rgt) gpa->rgt->par = gpa;
						if (par->lft) par->lft->par = par;
					} else {
						par->balance = +1;
						gpa->balance = 0;
						if (par->lft) par->lft->par = par; 
						gpa->rgt->par = gpa;
					}
					cur->balance = 0;
					
					/*
					 * Repair paternity.
					 */
					cur->par = gpa->par;
					gpa->par = cur;
					par->par = cur;

					/*
					 * Repair pointer which pointed to balanced node. If it was root then balancing
					 * is finished else continue in next iteration (parent node).
					 */
					if (cur->par == NULL) {
						t->root = cur;	
						break;
					} else 
						if (cur->par->lft == gpa) {
							cur->par->lft = cur;
							dir = AVLTREE_LEFT;
						} else {
							cur->par->rgt = cur;
							dir = AVLTREE_RIGHT;
						}
					gpa = cur->par;
				} else {
					/*
					 * RR rotation.
					 */
					
					gpa->rgt = par->lft;
					if (par->lft) par->lft->par = gpa;
					par->lft = gpa;
					
					/*
					 * Repair paternity.
					 */
					par->par = gpa->par;
					gpa->par = par;
					
					if (par->balance == 0) {
						/*
						 * Right child of balanced node is balanced, after RR rotation is done, whole
						 * tree will be balanced.
						 */
						par->balance = -1;
						gpa->balance = +1;

						/*
				  	 	 * Repair pointer which pointed to balanced node and finish balancing.
						 */
						if (par->par == NULL) {
							t->root = par;	
						} else 
							if (par->par->lft == gpa) {
								par->par->lft = par;
							} else {
								par->par->rgt = par;
							}
						break; 
					} else {
						par->balance = gpa->balance = 0;
						/*
						 * Repair pointer which pointed to balanced node. If it was root then balancing
						 * is finished else continue in next iteration (parent node).
						 */
						if (par->par == NULL) {
							t->root = par;	
							break;
						} else {
							
							if (par->par->lft == gpa) {
								par->par->lft = par;
								dir = AVLTREE_LEFT;
							} else {
								par->par->rgt = par;
								dir = AVLTREE_RIGHT;
							}
						}
					}
					gpa = par->par;
				}
			} else {
				/*
				 * Repair pointer which pointed to balanced node. If it was root then balancing
				 * is finished else continue in next iteration (parent node).
				 */
				if (!gpa->par) break;

				if (gpa->par->lft == gpa) { 
					dir = AVLTREE_LEFT;
				} else {
					dir = AVLTREE_RIGHT;
				}
				gpa = gpa->par;
			}
		} else { 
			/*
			 * Deletition was made in right subtree.
			 */
			gpa->balance--;
			if (gpa->balance == -1) {
				/*
				 * Stop balancing, tree is balanced.
				 */
				break;
			} else if (gpa->balance == -2) {
				/*
				 * Bad balance, heights of left and right subtrees differs more then is allowed.
				 */
				par = gpa->lft;
				
				if (par->balance == +1) {
					/*
					 * LR rotation.
					 */
					
					cur = par->rgt;
					par->rgt = cur->lft;
					cur->lft = par;
					gpa->lft = cur->rgt;
					cur->rgt = gpa;
					
					/*
					 * Repair balances and paternity of childs in dependence on
					 * balance factor of grand child (cur).
					 */
					if (cur->balance == -1) {
						par->balance = 0;
						gpa->balance = +1;
						if (gpa->lft) gpa->lft->par = gpa;
						par->rgt->par = par;
					} else if (cur->balance == 0) {
						par->balance = gpa->balance = 0;
						if (gpa->lft) gpa->lft->par = gpa;
						if (par->rgt) par->rgt->par = par; 
					} else {
						par->balance = -1;
						gpa->balance = 0;
						if (par->rgt) par->rgt->par = par;
						gpa->lft->par = gpa;
					}
					cur->balance = 0;

					/*
					 * Repair paternity.
					 */
					cur->par = gpa->par;
					gpa->par = cur;
					par->par = cur;

					/*
					 * Repair pointer which pointed to balanced node. If it was root then balancing
					 * is finished else continue in next iteration (parent node).
					 */
					if (cur->par == NULL) {
						t->root = cur;	
						break; 
					} else 
						if (cur->par->lft == gpa) {
							cur->par->lft = cur;
							dir = AVLTREE_LEFT;
						} else {
							cur->par->rgt = cur;
							dir = AVLTREE_RIGHT;
						}
					gpa = cur->par;
				} else { 
					/*
					 * LL rotation.
					 */
					
					gpa->lft = par->rgt;
					if (par->rgt) par->rgt->par = gpa;
					par->rgt = gpa;
					/*
					 * Repair paternity.
					 */
					par->par = gpa->par;
					gpa->par = par;
					
					if (par->balance == 0) {
						/*
						 * Left child of balanced node is balanced, after RR rotation is done, whole
						 * tree will be balanced.
						 */
						par->balance = +1;
						gpa->balance = -1;
						
						/*
				  	 	 * Repair pointer which pointed to balanced node and finish balancing.
						 */
						if (par->par == NULL) {
							t->root = par;
						} else 
							if (par->par->lft == gpa) { 
								par->par->lft = par;
							} else {
								par->par->rgt = par;
							}
						break;
					} else {
						par->balance = gpa->balance = 0;
						
						/*
						 * Repair pointer which pointed to balanced node. If it was root then balancing
						 * is finished else continue in next iteration (parent node).
						 */
						if (par->par == NULL) {
							t->root = par;
							break;
						} else {
							if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna
								par->par->lft = par;
								dir = AVLTREE_LEFT;
							} else {
								par->par->rgt = par;
								dir = AVLTREE_RIGHT;
							}
						}
					}
					gpa = par->par;
				}
			} else {
				/*
				 * Repair pointer which pointed to balanced node. If it was root then balancing
				 * is finished else continue in next iteration (parent node).
				 */
				if (!gpa->par) break;

				if (gpa->par->lft == gpa) {
					dir = AVLTREE_LEFT;
				} else {
					dir = AVLTREE_RIGHT;
				}
				gpa = gpa->par;
			}
		}
	}
}


/** Delete node from AVL tree with the smallest key and set base of tree to that key.
 *
 * @param t AVL tree structure.
 */
avltree_node_t *avltree_delete_min(avltree_t *t)
{
	avltree_node_t *node;
	uint64_t key;
	
	/*
	 * Start search of smallest key in tree in the root node and
	 * continue in cycle to the most left node in the tree which
	 * must have smallest key.
	 */
	node = t->root;
	if (!node) return false;
	
	while (node->lft != NULL)
		node = node->lft;
	
	/*
	 * Store key and use avltree_delete function to delete node from tree.
	 */
	key = node->key;
	avltree_delete(t,node); 

	/*
	 * Change base to the key of deleted node.
	 */
	t->base = key;

	return true;
}