public class FibonacciHeap
{

	
	public	FBNode head;
	public FBNode min;
	public int n;
	public int maxn;
	
	static int MIN=-5000;
	public FibonacciHeap()
	{
		head=null;
		min=null;
		n=0;
		maxn=0;
	}
			
	public FBNode insert (Node node)
	{
		// TODO: Add your code here
		FBNode head1=new FBNode();
		head1.node=node;
		head1.parent=null;
		head1.child=null;
		head1.prev=head1.next=head1;
		head1.outdegree=0;
		head1.last=false;
		head1.marked=false;
		
		//debug("heap2");

	 	if(n==0 || head==null)
	 	{
	 		head1.last=true;
	 		head=head1;
	 		min=head;
	 		n++;
	 	}
	 	else //___Insert in beginning of list___
	 	{
	 		head1.next=head;
	 		head1.prev=head.prev;
	 		head.prev.next=head1;
	 		head.prev=head1;
	 	
	 		
	 		head=head1;
	 		
	 		if(min==null || min.node.returnkey()>head1.node.returnkey())
	 			min=head1;
	 		n++;
	 		
	 	}
	 	

		if(n>maxn)	maxn=n;
	 	return head1;
	 	
	}


	private void insert (FBNode h)
	{
		// TODO: Add your code here
		h.parent=null;
		h.marked=false;
		h.last=false;
		
		//debug("heap2");

	 	if(n==0 || head==null)
	 	{
	 		n=0;
	 		
			h.prev=h.next=h;
	 		h.last=true;
	 		head=h;
	 	
	 		min=head;
	 		n++;
	 	}
	 	else //___Insert in beginning of list___
	 	{
	 		h.next=head;
	 		h.prev=head.prev;
	 		head.prev.next=h;
	 		head.prev=h;
	 		
	 		head=h;
	 		
	 		if(min==null || min.node.returnkey()>h.node.returnkey())
	 			min=h;
	 	
	 		n++;
	 		
	 		
	 	}
	 	
	 	if(n>maxn) maxn=n;
	 	
	}



	//____return null if empty____
	public Node returnMin ()
	{
		return min.node;
	}


	public Node deleteMin ()
	{
		FBNode m=min;
		//debug("delete min sytart");
		display(head,0);
		if(m!=null)
		{

			//debug("adding its children to root list");
			int oldn=n;

			FBNode next=m.child;
			FBNode childt=next;
			if(next!=null)
			{
				FBNode lastchild=m.child.prev;
				
				do
				{
					childt=next;
					//debug("child is : " + childt.node.returnkey());
					next=childt.next;
					insert(childt);
				}while(childt!=lastchild);
			}
			else
			{
				//debug("no child");
			}
			
			
			//debug("removing min from list of nodes");
			//____remove m from the list of nodes
			m.prev.next=m.next;
			m.next.prev=m.prev;
			if(head==m)
				head=m.next;
	
			//debug("going to consolidate");			
			//display(head,0);
			
			//____update minimum pointer
			if(m.next==m)
				min=null;
			else
				min=m.next;
				
			//___consolidate
			
			consolidate();
			n=oldn-1;
			
		//	debug("n= " + n);
		}
		return m.node;
	}
	
	public FBNode link(FBNode head1,FBNode head2)
	{
		if(head1.outdegree!=head2.outdegree)
			return null;
		
		FBNode parent,child;
	/*	if(head1.node.returnkey()<=head2.node.returnkey())
		{
			parent=head1; 
			child=head2;
		}
		else
		{
			parent=head2;
			child=head1;
		}
	*/	
		parent=head1;
		child=head2;
		
		if(parent.child!=null)
		{
			FBNode lastchild=parent.child.prev;
			lastchild.next=child;
			child.next=parent.child;
			child.prev=lastchild;
			parent.child.prev=child;
			lastchild.last=false;
		}
		else
		{
			parent.child=child;
			child.next=child.prev=child;
			
		}

		child.parent=parent;
		child.last=true;
		child.marked=false;
		
		parent.outdegree++;
		
		return parent;
		
	}
	
	
	public FibonacciHeap union(FibonacciHeap h1,FibonacciHeap h2)
	{
		
		//___Create new heap
		FibonacciHeap heap=new FibonacciHeap();
		heap.min=h1.min;
		
		//____Now link up the lists properly
		h1.head.prev.next=h2.head;
		h2.head.prev.next=h1.head;
		
		FBNode temp=h1.head.prev;
		h1.head.prev=h2.head.prev;
		h2.head.prev=temp;
		temp.last=false;
		
		//____Update min and n of the new heap___
		if(heap.min==null || h2.min!=null && h2.min.node.returnkey()<h1.min.node.returnkey())
			heap.min=h2.min;
			
		heap.n=h1.n+h2.n;
		
		return heap;
	}
	
	
	public void consolidate()
	{
		//debug("no of nodes : " + n);
		int arraysize=maxn;
		FBNode array[]=new FBNode[arraysize];
		int i=0;
		for(i=0;i<arraysize;i++)
			array[i]=null;
	

	
		FBNode t=head;
		FBNode x,y;
		int d;
		
		debug("Consolidating");
				display(head,0);
		do
		{
			//___Deal with special case___
			if(t==null) 
				break;
				
			FBNode next=t.next;
			x=t;
			d=x.outdegree;
		//	debug("Con : " + x.node.returnkey() + "degree : " + d);
	
			if(!(d>=0 && d<maxn))
			{
			
				debug("Outside Alarm..."  + maxn);
					debug("Con : " + x.node.returnkey() + "degree : " + d);
			}

			while(array[d]!=null)
			{
				//debug("linking...");
				y=array[d];
				if(x.node.returnkey()>y.node.returnkey())
				{
					FBNode t1=x;
					x=y;
					y=t1;
				}
				//___Remove y from root list__
			//	y.prev.next=y.next;
			//	y.next.prev=y.prev;
		
				link(x,y); //___x is the parent
				
				array[d]=null;


				d++;
				
				
			if(!(d>=0 && d<maxn))
			{
			
				debug("Inside Alarm..."  + maxn);
					debug("Con : " + x.node.returnkey() + "degree : " + d);
			}
			
			}
			//debug("assigning...");
			array[d]=x;
			
			t=next;
			//debug("t : " + t.node.returnkey());
		}while(t!=head);
		
		min=null;
		head=null;
		
	
		debug("array to list");
		n=0;
		for(i=0;i<arraysize;i++)
		{
			//debug("on array pos : "  +i);
			if(array[i]!=null)
			{
				insert(array[i]);
				if(min==null || array[i].node.returnkey()< min.node.returnkey())
					min=array[i];
			}
		}
		
		display(head,0);
		
	}	
	
	
	public boolean decreaseKey(FBNode fnode,int val)
	{
		if(val>fnode.node.returnkey())
			return false;
		
		fnode.node.key=val;
		
		FBNode y=fnode.parent;
		if(y!=null && fnode.node.returnkey()<y.node.returnkey())
		{
			cut(fnode);
			cascadeCut(y);
		}
		
		if(fnode.node.returnkey()<min.node.returnkey())
			min=fnode;
			
			return true;
		
	}
	
	public Node returnNode(FBNode fnode)
	{
			return fnode.node;
	}
	
	private void cut(FBNode child)
	{
		
		//___Remove child from its parent list
		//___If only one child___
		if(child.next==child)
		{
			child.parent.child=null;
		}
		else
		{
			child.prev.next=child.next;
			child.next.prev=child.prev;
			if(child.parent.child==child)
			{
				child.parent.child=child.next;
			}
		}
		
		child.parent.outdegree--;
		
		insert(child);
		
			
	}
	
	
	private void cascadeCut(FBNode y)
	{
		FBNode z=y.parent;
		if(z!=null) // If parent exists
		{
			if(y.marked==false)
			{
				y.marked=true;
			}
			else
			{
				cut(y);
				cascadeCut(z);
			}
		}
	}
			
	
	
		
		
	public void display(FBNode head,int space)
	{
		if(head==null) 
			return;
		
		FBNode t=head;
		do
		{
		//	//debug("infinite");
			int i;
			for(i=0;i<space;i++)
				System.out.print(" ");
			System.out.println(t.node.returnkey());
			display(t.child,space+2);
			
			t=t.next;
		}while(t!=head);
		
		System.out.flush();
	}
			
	public void debug(String str)
	{
		System.out.println(str);
		System.out.flush();
	}
					
}