/**
 *
 * id1:207032764
 * name1:Nitsan Honen
 * username1:nitsanhonen
 * id2:206539496
 * name2:Nitzan Zacharia
 * username2:zacharia1
 *
 */


/**
 * FibonacciHeap
 *
 * An implementation of Fibonacci heap over positive integers.
 *
 */
public class FibonacciHeap
{
	public int numTrees; 
	public HeapNode first;
	public HeapNode min;
	public int totalLinks;
	public int totalCuts;
	public int size;


	/**
	 *
	 * Constructor to initialize an empty heap.
	 *
	 */
	public FibonacciHeap()
	{
		numTrees = 0;
		first = null;
		min = null;
		totalLinks = 0;
		totalCuts = 0;
		size = 0;
	}


	/**
	 *
	 * pre: key > 0
	 *
	 * Insert (key,info) into the heap and return the newly generated HeapNode.
	 * 
	 * written by: Nitzan Z.
	 *
	 */
	public HeapNode insert(int key, String info) {

		//acts as an envelope function for InsertHelper
		HeapNode Node = new HeapNode(key, info);
		return insertHelper(Node, true);
	}


	/**
	 *
	 * pre:  isNew == true iff Node was created by the insert() method, false otherwise.
	 *
	 * Inserts the HeapNode Node into the heap and returns the newly inserted HeapNode.
	 *
	 * written by: Nitzan Z.
	 *
	 */
	private HeapNode insertHelper(HeapNode Node, boolean isNew){
		int key = Node.key;

		//if the heap is empty, insert Node as the first & minimal root
		if(this.first==null) {
			this.first=Node;
			Node.next=Node;
			Node.prev = Node;
			this.min = Node;

		}

		//else, insert it as the first node of the root list,
		//update the necessary prev/next pointers
		else
		{
			Node.next = this.first;
			Node.prev = this.first.prev;
			this.first.prev.next = Node;
			this.first.prev = Node;
			this.first = Node;
			if(key<this.min.key) { //update the min pointer if necessary 
				this.min = Node;
			}
		}

		//if the node was generated by the Insert() method, update size
		if(isNew) size ++;
		numTrees++;
		return Node;
	}


	/**
	 *
	 * Return the minimal HeapNode, null if empty.
	 *
	 *  written by: Nitzan Z.
	 *
	 */
	public HeapNode findMin()
	{
		return this.min;
	}


	/**
	 *
	 * Recursive helper function that manages the actual process of consolidation
	 * for each tree in the heap
	 *
	 * pre: node.rank <= arr.length
	 * 
	 * written by: Nitzan Z.
	 *
	 */
	private void recMove(HeapNode[] arr, HeapNode node) {

		//base case: if there's no tree of the same rank in the array, place the node there.
		//no need for another base case since the array size ensures will reach an empty cell.
		if(arr[node.rank]==null)
		{
			arr[node.rank] = node; 
			this.numTrees--;
			return; 
		}

		//rec step: a tree of the same rank found
		else { 
			int ind = node.rank;
			HeapNode combined = linkTrees(node, arr[node.rank]); //link the trees 
			arr[ind] = null; //empty the cell
			recMove(arr, combined); //continue recursively with the merged tree of rank: node.rank+1
		}
	}


	/**
	 *
	 * Helper function that manages consolidation of the heap
	 * 
	 * written by: Nitzan Z.
	 *
	 */
	private void consolidating() {

		//builds an array of size> log(n)
		HeapNode[] arr = new HeapNode[2+(int)(Math.log(size) / 0.48121)];
		while(this.first!=null)
		{
			HeapNode node = this.first;
			if(this.first.next == this.first) //if we reached the last root in the heap
			{
				this.first=null;
			}
			else
			{
				this.first=node.next; //remove the root from the heap
				HeapNode last = node.prev;
				last.next=this.first;
				this.first.prev=last;
			}
			node.next = null;
			node.prev=null;//detach the node from pointing to the heap
			recMove(arr, node); //insert node to the array, link accordingly if needed
		}

		//update num of trees to zero before re-inserting the updated linked trees
		this.numTrees=0;
		this.min = null;  //delete the pointer to the current min
		int count = 0;
		HeapNode minPointer = null;

		//re-insert the trees to the heap, updating the number of trees and the minimum accordingly
		for(int i=(arr.length-1);i>=0;i--)
		{
			if(arr[i]!=null) {
				count++;
				int key_root = arr[i].key;
				HeapNode root_node = insertHelper(arr[i], false);
				if (minPointer==null) {
					minPointer = root_node;
				}
				else if(key_root<minPointer.key) {

					minPointer = root_node;
				}
			}
		}
			this.min = minPointer;
			this.numTrees = count;
	}


	/**
	 *
	 * Delete the minimal item
	 * 
	 * written by: Nitzan Z.
	 *
	 */
	public void deleteMin() {
		if(this.min==null) //if the heap is empty, nothing to delete
			return;
		deleteRoot(this.min); //remove the current min from the root list

		// consolidate the heap (which will also update the min pointer) if the heap is not empty
		if (this.size>0) consolidating();

	}


	/**
	 *
	 * given a pointer to a root, deletes it from the heap.
	 * 
	 * written by: Nitzan Z.
	 *
	 */
	private void deleteRoot(HeapNode root)
	{
		//if the root is not a singleton, add its children to the root list, update relevant pointers
		if(root.rank>0)
		{
			HeapNode child = root.child;
			HeapNode node = child;
			root.child = null;
			child.prev.next = root.next;
			root.next.prev = child.prev;
			child.prev = root.prev;
			root.prev.next = child;

			while(node != null)
			{
				node.parent = null;
				if(node.mark) {
				node.mark = false;}
				if(node.next == child)
				{
					break;
				}
				else node= node.next;
			}
			child.parent = null;
			if(this.first==root) this.first=child;
			this.numTrees += root.rank-1;
			this.totalCuts += root.rank;
		}

		//if the heap will not be empty after deleting root, remove it and update relevant pointers
		else if(this.numTrees>1)
		{
			root.next.prev = root.prev;
			root.prev.next= root.next;
			if(this.first==root) this.first=root.next;
			this.numTrees--;
		}

		//if root is the only node in the heap, update the pointers so the heap is empty
		else {
			this.first=null;
			this.numTrees = 0;
		}
		root.prev = null;
		root.next = null;
		if(size>0) {size --;} //update size if necessary 
        if(this.size==0) {this.min=null;} //update min if necessary 
	}


	/**
	 *
	 * pre: 0<diff<x.key
	 *
	 * Decrease the key of x by diff and fix the heap.
	 * 
	 * written by: Nitsan H.
	 *
	 */
	public void decreaseKey(HeapNode x, int diff)
	{
		x.key -= diff; //decrease key by diff

		// if x's new key violates the heap property,
		// fix it by cutting it from its parent (continue recursively if needed)
		if(x.parent != null && x.key < x.parent.key){
			cascadingCuts(x);
		}

		//if x is a root, update the min if necessary
		else if(x.parent == null && x.key < this.min.key){this.min = x;}
	}


	/**
	 *
	 * Delete the x from the heap.
	 *
	 * written by: Nitsan H.
	 *
	 */
	public void delete(HeapNode x)
	{
		if(x == this.min){ //if x is the minimal element, perform deleteMin()
			deleteMin();
			return;
		}
		HeapNode min = this.min;

		//if x is not a root, perform decreaseKey() to turn it to one prior to deletion.
		if(x.parent != null){
			int diff = x.key - x.parent.key + 1;
			decreaseKey(x, diff);
		}

		//decreaseKey might change the minimum to be x,
		//so we move the pointer back to the real minimum
		this.min = min;
		deleteRoot(x); //delete x, which is now a root
	}


	/**
	 *
	 * Return the total number of links.
	 *
	 * written by: Nitzan Z.
	 *
	 */
	public int totalLinks()
	{
		return this.totalLinks;
	}


	/**
	 *
	 * Return the total number of cuts.
	 *
	 * written by: Nitzan Z.
	 *
	 */
	public int totalCuts()
	{
		return this.totalCuts;
	}


	/**
	 *
	 * Meld the heap with heap2
	 * 
	 * written by: Nitsan H.
	 *
	 */
	public void meld(FibonacciHeap heap2)
	{
		//update the necessary values to be the sum (of said values) of both heaps
		this.size += heap2.size;
		this.totalLinks += heap2.totalLinks;
		this.totalCuts += heap2.totalCuts;

		//if both heaps are not empty, concatenate them
		if(this.numTrees != 0 && heap2.numTrees != 0){
			HeapNode first2 = heap2.first;
			HeapNode last1 = this.first.prev;
			this.first.prev = first2.prev;
			first2.prev.next = this.first;
			first2.prev = last1;
			last1.next = first2;
			if(heap2.min.key < this.min.key){this.min = heap2.min;} //update min if necessary 
		}

		//if current heap is empty, update its pointers to be the ones of heap2
		else if(this.numTrees == 0 && heap2.numTrees != 0){
			this.first = heap2.first;
			this.min = heap2.min;
		}
		this.numTrees += heap2.numTrees;
	}


	/**
	 *
	 * Return the number of elements in the heap
	 *
	 * written by: Nitsan H.
	 *
	 */

	public int size()
	{
		return this.size;
	}


	/**
	 *
	 * Return the number of trees in the heap.
	 *
	 * written by: Nitsan H.
	 *
	 */
	public int numTrees()
	{
		return this.numTrees;
	}


	/**
	 *
	 * pre: root1.rank == root2.rank
	 *
	 * Link two trees of the same rank
	 * 
	 * written by: Nitsan H.
	 *
	 */
	private HeapNode linkTrees(HeapNode root1, HeapNode root2){
		HeapNode minRoot = root2;
		HeapNode maxRoot = root1;

		//update the pointers to determine which root will be the root of the merged tree
		// and which will be its child
		if(root1.key < root2.key){
			minRoot = root1;
			maxRoot = root2;
		}
		HeapNode tempChild = minRoot.child;
		minRoot.child = maxRoot;
		maxRoot.parent = minRoot;

		//if minRoot has children, update the necessary pointers to add maxRoot to its children list
		if(tempChild != null){
			maxRoot.next = tempChild;
			maxRoot.prev = tempChild.prev;
			tempChild.prev = maxRoot;
			maxRoot.prev.next = maxRoot;
		}
		else{ //else, insure minRoot's children list (containing only maxRoot) is circular. 
			maxRoot.prev = maxRoot;
			maxRoot.next = maxRoot;
		}
		minRoot.rank++; 
		this.totalLinks++;
		return minRoot;
	}


	/**
	 *
	 * pre: childNode.parent in not null
	 *
	 * Cut a node from its parent and insert as a new tree to the heap
	 * 
	 * written by: Nitsan H.
	 *
	 */
	private void cut(HeapNode childNode){
		totalCuts++;
		HeapNode parent = childNode.parent;
		childNode.parent = null;
		childNode.mark = false;
		parent.rank--;
		if(childNode.next == childNode){ //if parent was of rank 1, delete the child pointer
			parent.child = null;
		}
		else{ // if the parent had other children, update the necessary pointers
			parent.child = childNode.next;
			childNode.prev.next = childNode.next;
			childNode.next.prev = childNode.prev;
		}

		//add childNode to the root list of the heap
		//by creating a new heap and melding it with the original one.
		FibonacciHeap newHeap = new FibonacciHeap();
		newHeap.numTrees++;
		newHeap.first = childNode;
		newHeap.min = childNode;
		childNode.next = childNode;
		childNode.prev = childNode;
		meld(newHeap);
	}


	/**
	 *
	 * Recursively cuts a node's parent from its grandparent if the parent is marked
	 * 
	 * written by: Nitsan H.
	 *
	 */
	private void cascadingCuts(HeapNode childNode){
		HeapNode parent = childNode.parent;
		if(parent != null){ //performs a cut only if childNode is not a root
			cut(childNode);
			if(parent.parent != null){

				//base case: if childNode has a parent which is not marked, mark it.
				if(!parent.mark){
					parent.mark = true;
				}
				else{ //rec step: if childNode has a marked parent, continue recursively
					cascadingCuts(parent);
				}
			}
		}

	}


	/**
	 * Class implementing a node in a Fibonacci Heap.
	 *
	 */
	public static class HeapNode{
		public int key;
		public String info;
		public HeapNode child;
		public HeapNode next;
		public HeapNode prev;
		public HeapNode parent;
		public int rank;
		public boolean mark;

		public HeapNode(int key, String val)
		{
			this.key = key;
			this.info = val; 
			child = null;
			next = null;
			prev = null;
			parent = null;
			rank = 0;
			mark = false;
		}
	}
}