import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.lang.Math;




class Heaps 
{
	
	static Edge[] graph;
	
	static int[] noofedges;
	static int totalvertices,totaledges;
	 static int MAXWT=999999;
	
	public Heaps()
	{
		
	}
	
	static public void createGraphM(int v, int e)
	{
		int i,j,k;

		graph=new Edge[v];
		totalvertices=v;
		totaledges=e;
		
	
		for(i=0;i<v;i++)
			graph[i]=null;
		
		noofedges=new int[v];

		int totaladded=0;
		boolean matrix[][]=new boolean[v][v];		
		for(i=0;i<v;i++)
			for(j=0;j<v;j++)
				matrix[i][j]=false;

		//___First connect the graph
		Random r=new Random();
		for(i=1;i<v;i++)
		{
			int cv=r.nextInt(i);
			int wt=r.nextInt(MAXWT);
			connect(i,cv,wt);
			matrix[i][cv]=true;
			matrix[cv][i]=true;
		}
		
		for(i=0;i<e-v;i++)
		{
			int v1=r.nextInt(v);
			int v2=r.nextInt(v);
			while(v1==v2 || matrix[v1][v2])
			{
				v2++;
				if(v2==v)
				{
					v1++;
					v2=0;
				}
				if(v1==v)
				{
					v1=0;
					v2=0;
				}
			}
			int wt=r.nextInt(MAXWT);
			connect(v1,v2,wt);
			matrix[v1][v2]=true;
			matrix[v2][v1]=true;
			
				
		}
	}
	
	
	static public void createGraph(int v,int e)
	{
		int i,j,k;

		graph=new Edge[v];
		totalvertices=v;
		totaledges=e;
		
	
		for(i=0;i<v;i++)
			graph[i]=null;
		
		noofedges=new int[v];
		int totaladded=0;
		
		Random r= new Random();
		
		for(i=0;i<e;i++)
		{
			int rv=r.nextInt(v);
			if(noofedges[rv]>=v-1)
			{	
				i--;
			}
			else
				noofedges[rv]++;
		}
		
		for(i=0;i<v;i++)
		{
			System.out.println("Vertex : " + i + "  edges : " + noofedges[i]);
			
		}
		
		
		//___First connect the graph
		for(i=1;i<v;i++)
		{
			int cv=r.nextInt(i);
			int wt=r.nextInt(MAXWT);
			connect(i,cv,wt);
		}
		
		
		int targetv[]=new int[v];
		int vcount=0;

		//____Now add many edges__
		for(i=0;i<v;i++)
		{
			if(i==v-1)
				break;
			
			//____First put all the vertices in an array___
			vcount=0;
			for(j=i+1;j<v;j++)
			{
				if(noofedges[j]>0)
				{
					targetv[vcount++]=j;
					System.out.println(" " + j);
					
				}
				else
				{
					targetv[vcount++]=-1;
				}
			}
		
			Edge p = graph[i];
			while(p!=null)
			{
				if(p.vertex>i)
						targetv[p.vertex-i-1]=-1;
				
				p=p.next;
			}
					
			int noe=noofedges[i];
			System.out.println("Now adding " + noe +"  edges for" + i);
			System.out.flush();
			//____Now connect these vertices___
			
		
			for(j=0;j<noe;j++)
			{
				int cv=r.nextInt(vcount);
				if(targetv[cv]!=-1)
				{
					targetv[cv]=-1;
					int wt=r.nextInt(MAXWT);
					connect(i,targetv[cv],wt);
					noofedges[i]--;
					noofedges[targetv[cv]]--;
			
				}
				else //___Traverse until a valid vertex is found
				{
					while(cv<vcount && targetv[cv]==-1)
					{
						cv++;					
					}
					if(cv==vcount) //___Traverse backwards
					{
						//cv--;
						while(cv>=0 && targetv[cv]==-1)
						{
							cv--;					
						}
					
					}
					
					if(cv>=0 && targetv[cv]!=-1)
					{
						targetv[cv]=-1;
						int wt=r.nextInt(MAXWT);
						connect(i,targetv[cv],wt);
						noofedges[i]--;
						noofedges[targetv[cv]]--;
					}
					else
					{
						System.out.println("Out of vertices");
						System.out.flush();
					}	
				}	
			}
		}
	}

	
	
	static private void connect(int v1,int v2, int wt)
	{
		if(v1==v2)
		return;
		Edge e1=new Edge(v2,wt);
		e1.next=graph[v1];
		graph[v1]=e1;
		
		e1=new Edge(v1,wt);
		e1.next=graph[v2];
		graph[v2]=e1;
		
	//	System.out.println("Connecting : "  + v1+","+v2);
	//	System.out.flush();
	}
	

	//1 for binary , 2 for fibonacci
	static private long  prims(int heaptype,boolean comments)
	{

	
		int i;
		long starttime=1 , endtime=0;
		
		
		if(heaptype==2)
		{
			
			starttime=new Date().getTime();

			Object[] llist=new FBNode[totalvertices];
			FibonacciHeap bh=new FibonacciHeap();
		
			int parentv[]=new int[totalvertices];
			boolean inheap[]=new boolean[totalvertices];
			int root=0;
			int extracted=0;
			Node n;

		
			//___Insert infinity
			for(i=0;i<totalvertices;i++)
			{
					llist[i]=bh.insert(new Node(MAXWT+1,i));
			}
	
			for(i=0;i<totalvertices;i++)
			{
				parentv[i]=-1;
				inheap[i]=true;
			}
			parentv[root]=root;
			
			bh.decreaseKey((FBNode)llist[root],0);
			
			//___Main algo
			while(extracted<totalvertices)
			{
				n=bh.deleteMin();
				extracted++;
				inheap[n.nodeid]=false;
			//	System.out.println("Extracted : " + n.nodeid);
	
				Edge  p =graph[n.nodeid];
				while(p!=null)
				{
					if(inheap[p.vertex]==true && p.wt<bh.returnNode((FBNode)llist[p.vertex]).returnkey())
					{
						parentv[p.vertex]=n.nodeid;
						bh.decreaseKey((FBNode)llist[p.vertex],p.wt);
					}
					p=p.next;
				}
			}			
		
			endtime=new Date().getTime();
			//___Now print the MCST
			System.out.println("Total time taken : " + (endtime-starttime) + " milliseconds");
			if(comments)
			{
			System.out.println("Using Fibonacci Heap...\nThe MCST is : ");

			for(i=0;i<totalvertices;i++)
			{
				if(parentv[i]!=-1)
				System.out.println(" " + i +" , " + parentv[i]);
				
			}
			}
			System.out.flush();
		} //___Fibonacci Heap

		if(heaptype==1)
		{

			starttime=new Date().getTime();

			BinaryHeap bh=new BinaryHeap(totalvertices+3);
			int parentv[]=new int[totalvertices];
			boolean inheap[]=new boolean[totalvertices];
			int root=0;
			int extracted=0;
			Node n;

		
			//___Insert infinity
			for(i=0;i<totalvertices;i++)
			{
					bh.insert(new Node(MAXWT+1,i));
			}
	
			for(i=0;i<totalvertices;i++)
			{
				parentv[i]=-1;
				inheap[i]=true;
			}
			parentv[root]=root;
			
			bh.decreaseKey(root,0);
			
			//___Main algo
			while(extracted<totalvertices)
			{
				n=bh.deleteMin();
				extracted++;
				inheap[n.nodeid]=false;
		
				Edge  p =graph[n.nodeid];
				while(p!=null)
				{
					if(inheap[p.vertex]==true && p.wt<bh.returnNode(p.vertex).returnkey())
					{
						parentv[p.vertex]=n.nodeid;
						bh.decreaseKey(p.vertex,p.wt);
					}
					p=p.next;
				}
			}			
		
		
			endtime=new Date().getTime();
			//___Now print the MCST

		
			System.out.println("Total time taken : " + (endtime-starttime) + " milliseconds");

			if(comments)
			{
					System.out.println("Using Binary Heap...\nThe MCST is : ");
			for(i=0;i<totalvertices;i++)
			{
				if(parentv[i]!=-1)
				System.out.println(" " + i +" , " + parentv[i]);
				
			}
			System.out.flush();
			}
		} //___Binary Heap
		
		return (endtime-starttime);
								
	}	
	

	static private void displaygraph()
	{
	
		System.out.println("Displaying Graph...");
		System.out.println("No of vertices : " + totalvertices + "   No of edges : " + totaledges);
		int i;
		for(i=0;i<totalvertices;i++)
		{
			System.out.println("Vertex no : " + i + " -- " );
			Edge p=graph[i];
			while(p!=null)
			{
				System.out.println("   "+p.vertex+","+p.wt);
				p=p.next;
			}
		}
		System.out.flush();
	}
	

	
	public static void main(String args[])
	{
	
	
		int v,e,comments;
		v=500;

		e=120000;
		comments=0;
		if(args.length>=3)
		{
			v=Integer.parseInt(args[0]);
			e=Integer.parseInt(args[1]);
			comments=Integer.parseInt(args[2]);
		}

/*
		int maxi=30;

		int[] list=new int[maxi];
		Object[] llist=new FBNode[maxi];
		
		int i;
		Random r=new Random();
		for(i=0;i<maxi;i++)
		{
			list[i]=500+r.nextInt(9999);
		}
		//FibonacciHeap bh=new FibonacciHeap();
		BinaryHeap bh=new BinaryHeap(maxi+5);
		
		for(i=0;i<maxi;i++)
		{
			bh.insert(new Node(list[i],i));
		}
	
		for(i=0;i<maxi;i++)
		{		
		//	bh.decreaseKey((FBNode)llist[i],100);
			bh.decreaseKey(i,100);
		}
	
	
		Arrays.sort(list,0,maxi);
		Node n;		

		for(i=0;i<30;i++)
		{
			System.out.println("Next element is : " + list[i]);
			n=bh.deleteMin();
			System.out.println("deleteMin element is : "  + n.returnkey());
			//		bh.display(bh.head,0);
		}*/
		

	System.out.println("\nGenerating Graph");
	createGraphM(v,e);
	System.out.println("Graph Generated having "+ v + " vertices , "+ e + " edges.");
	
	try{
	new Thread().sleep(5000);
	}
	catch(Exception exc)
	{}
	
	boolean comm=false;
	if(comments>0)
		comm=true;
		


		//if(comm) displaygraph();
		
		long t;
		System.out.println("\nRunning Prim's Algorithm using Binary Heap");
		t=prims(1,comm);
		
		System.out.println("t/(n.n.log(n)) : " + (double)(t)/(v*v*Math.log(v)));
		
			try{
	new Thread().sleep(5000);
	}
	catch(Exception exc)
	{}
		System.out.println("\nRunning Prim's Algorithm using Fibonacci Heap");
		t=prims(2,comm);
		System.out.println("t/(n.n) : " + (double)(t)/(v*v));
		System.out.println("t/(n.log(n)) : " + (double)(t)/(v*Math.log((double)v)));
		

	
	}
}