public class BinomialHeap
{

	
	static int MIN=-5000;
	public BinomialHeap()
	{
	
	}
			
	public BHNode insert (BHNode head,Node node)
	{
		// TODO: Add your code here
		BHNode head1=new BHNode();
		head1.node=node;
		head1.parent=null;
		head1.child=null;
		head1.prev=head1.next=head1;
		head1.outdegree=0;
		head1.last=true;
		
		//debug("heap2");

		return merge(head,head1);
	}


	//____return null if empty____
	public Node returnMin (BHNode head)
	{
		// TODO: Add your code here
		BHNode s=head;	
		BHNode min=head;;
		while(s!=null && !s.last)
		{
			if(s.node.returnkey()<min.node.returnkey())
				min=s;

			s=s.next;
		}
				
		return min.node;
	}


	public BHNode deleteMin (BHNode head)
	{
		// TODO: Add your code here
		BHNode s=head;	
		BHNode min=head;;
		while(s!=null && !s.last)
		{
			if(s.node.returnkey()<min.node.returnkey())
				min=s;

			s=s.next;
		}
				
		min.prev.next=min.next;
		min.next.prev=min.prev;
		min.child.parent=null;
		return merge(head,min.child);
	}
	
	public BHNode link(BHNode head1,BHNode head2)
	{
		if(head1.outdegree!=head2.outdegree)
			return null;
		
		BHNode 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)
		{
		BHNode 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;
			parent.outdegree++;
		
		return parent;
		
	}
	
	public BHNode merge(BHNode head1,BHNode head2)
	{
		//____do binary addition
		BHNode mhead;
		BHNode t=null;
		
		debug("displaying the heaps");
		//____Display Initial heaps___
		System.out.println("\nHeap 1 :");
		display(head1,0);
		System.out.println("\nHeap 2 :");
		display(head2,0);
		
		debug("checking for null cond");
	
		
		if(head1==null)
		{
			mhead=head2;
			return mhead;
		}	
		if(head2==null)
		{
			mhead=head1;
			return mhead;
		}	

/*		
		if(head1.outdegree<head2.outdegree)
		{
			mhead=head1;
			mhead.last=false;
			
			head1=head1.next;
			if(head2.last)
			{
				mhead.next=head2;
				t=head2;
			}
				
				
				
		}
		else 
		{
			mhead=head2;
			//mhead.last=false;
			
			head2=head2.next;
			
			if(head1.last)
			{
				System.out.println("attaching head1");
				t=mhead.next=head1;
				System.out.println("Kry : " + t.node.returnkey());
				
			}
			
		}
		
//		System.out.println("Display mhead init :");
//		display(mhead,0);
//		System.out.println("----------------");

		if(t==null) 
			t=mhead;
*/			

		debug("starting semi-merging");			

		mhead=new BHNode();
		t=mhead;
		debug("starting semi-merging");			

		
		int flag=0;
		do
		{
		
					
			if(t.node!=null)
				System.out.println("Key : " + t.node.returnkey());
				
			if((flag%2)!=1 && (head1.outdegree<=head2.outdegree || flag==2))
			{
				t.next=head1;
				if(head1.last)
					flag=flag | 1;
				head1=head1.next;
				
			}
			else if(flag<2 && (head2.outdegree<=head1.outdegree || (flag%2)==1))
			{
				t.next=head2;
				if(head2.last)
					flag=flag | 2;
				head2=head2.next;
			}
			
				
			t.next.prev=t;
			t=t.next;
			t.last=false;
		}while((flag & 3)<3);
		
		
		debug("semi-merged");
		
		/*
		if(head1.outdegree<head2.outdegree)
		{
			t.next=head1;

			t.next.prev=t;
			t=t.next;
			t.last=false;
			
			t.next=head2;

			t.next.prev=t;
			t=t.next;
			t.last=false;
		}
		else 
		{
			t.next=head2;

			t.next.prev=t;
			t=t.next;
			t.last=false;
			
			t.next=head1;

			t.next.prev=t;
			t=t.next;
			t.last=false;
		}*/

		
		mhead=mhead.next;
		
		//System.out.println("Kry : " + t.node.returnkey());
	//____t points to last node now___
		
		t.prev.last=false;
		t.last=true;
		t.next=mhead;
		mhead.prev=t;
		
		
		//____Now all the heaps are in increasing order_____
		System.out.println("\nNow displaying the merged heap in merging\n");
		display(mhead,0);
		
		
		t=mhead;
		
		BHNode oldt=null;
		while(t.last==false)
		{
			if(t.outdegree!=t.next.outdegree || 
				(t.next.next.outdegree==t.next.outdegree && t.next.last==false))
			{
				oldt=t;
				t=t.next;
			}
			else
			{
			
				if(t.node.returnkey()<=t.next.node.returnkey())
				{
					
				System.out.println("merging...1");
					t.last=t.next.last;
					
					BHNode oldnext=t.next.next;
			
					link(t,t.next);
					t.next=oldnext;	
					
					//t=t.next;
					
			//		display(mhead,0);
				}
				else
				{
					System.out.println("merging...2");
					if(oldt==null)
						mhead=t.next;
					else
						oldt.next=t.next;
					
					BHNode oldtnext=t.next;
					link(t.next,t);
					
					if(oldtnext.last)
						oldtnext.next=mhead;
						
					//t.next.next=oldtnext;
					
					t=oldtnext;
					
										
				//	display(mhead,0);
					debug("display finished");
				}
			}
			//oldt=t;
			//t=t.next;
			debug("infinite");
		}
		
		t.last=true;
		t.next=mhead;
		//____Have to consider last more carefully!!
		
		debug("prev point");
		//_____Update prev pointers
		t=mhead;
		while(t.last==false)
		{
			t.next.prev=t;
			t=t.next;
		}
			
		mhead.prev=t;
		
		System.out.println("\nNow displaying the final heap in merging\n");
		display(mhead,0);
		debug("Merge completed");
			
		return mhead;
	}
	
	public void debug(String str)
	{
		System.out.println(str);
		System.out.flush();
	}
	
	public void display(BHNode head,int space)
	{
		if(head==null) 
			return;
		
		BHNode 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);
	}
			
					
}