/*************************************************************
	Satish P Bhat
	
	Implementation of Fiduccia-Matheyses Heuristic
/*************************************************************/

/*	The program takes in the number of runs to compute the best balanced
bipartition, the input file name, the output file name and the balance factor as
its command line arguments		*/

/* This is the  " FM-Algo.cc" file */
#include "FM-Algo.h"

/*Appends the vertices/cells into the list of vertices*/
void Hypernode::AppendVertex(long num)
{
        List_Of_Vertices *temp = new List_Of_Vertices;
	List_Of_Vertices *temp1 = new List_Of_Vertices;	
	temp->Vertex_No=num;
	temp->next=NULL;
	if(list_of_vertices==NULL)
	{
		list_of_vertices = temp;
		counter++;
	}
	else
	{
		temp1 = list_of_vertices;	
		while(temp1->next != NULL)
		{
			temp1= temp1->next;
		}
		
		temp1->next = temp;
		counter++;
	}
}

/*Reads the File and puts the vertices in a list*/ 
void fileread(char* filename)
{
	FILE* fpt = NULL;
	long point,i=1,count=0;
	char c;
	
	fpt = fopen(filename,"r");
	if( fpt == 0 )
	{	
		cout<<"Error: File does not exist"<<endl;
		exit(0);
	}
	fscanf(fpt,"%d",&number_of_hyperedges);
	fscanf(fpt,"%d",&number_of_vertices);
	vertex = new Vertex[number_of_vertices+1];
	hypernode = new Hypernode[number_of_hyperedges +1];
	
	while(fscanf(fpt,"%d%c",&point,&c)!=EOF)
	{ 
		if(count == 0)
		{
			hypernode[i].weight=point;
			count=1;
		}
		else
		{
			hypernode[i].AppendVertex(point);
			vertex[point].AppendHypernode(i);			
		}
		if(c=='\n')
		{
			i++;
			count = 0;
		}
	} 
	fclose(fpt);
}

/*Appends the hypernode into the hypernode list*/
void Vertex::AppendHypernode(long num)
{	
	HypernodeList *temp = new HypernodeList;
	HypernodeList *temp1 = new HypernodeList;
	temp->hypernode_no = num;
	temp->next  = NULL;
	if(hypernodelist == NULL)
	{
		hypernodelist=temp;
		counter++;
	}
	else
	{
		temp1 = hypernodelist;	
		while(temp1->next!=NULL)
		{
			temp1 = temp1->next;
		}
		temp1->next = temp;
		counter++;
	}
}

/* Appends vertices into bucket data structure*/
void Bucket::AppendBucket(long num)
{
	BucketList *temp = new BucketList;
	BucketList *temp1;
	temp->vertex_no = num;
	temp->next  = NULL;
	temp->prev = NULL;
	
	if(blist == NULL)
	{
		blist=temp;
	}
	else
	{
		temp1 = blist;	
		while(temp1->next!=NULL)
		{
			temp1 = temp1->next;
		}
		temp->prev =temp1;
		temp1->next = temp;
	}
}

/* Deletes vertices from the bucket data structure*/
void Bucket::Delete(long verno)
{
	BucketList *temp;
	temp =blist;
	while( temp != NULL)
	{
		if( temp->vertex_no == verno)
		{
			if ( temp == blist)
			{
				blist = blist->next;
				if(blist != NULL)
				{
					blist->prev = NULL;
				}
				break;
			}
			else
			{
				if( temp->next == NULL)
				{
					temp->prev->next = NULL;
					break;
				}
				else 
				{
					temp->prev->next = temp->next;
					temp->next->prev = temp->prev;
					break;
				}
			}
		}
		temp = temp->next;
	}
}

/*Computes the Intial Partition of the vertices*/
void InitialPartition(long seed)
{
	long x=0,counter=0,counter1=0,i;
//	srand( (unsigned long)time( NULL ) );
	srand(seed);
	for( i = 1; i <=number_of_vertices ; i++)
	{
		vertex[i].gain = 0;
		vertex[i].locked = 0;
	}

	if(seed == 0)
	{
		for( i = 1; i <=number_of_vertices ; i++)
		{
			vertex[i].partition = 1;
		}

		
		while(counter < (number_of_vertices/2))
		{
			x = rand()%(number_of_vertices+1);
			if(x != 0)
			{
				if(vertex[x].partition != 2)
				{
					vertex[x].partition=2;
					counter++;
				}
			}	
		}
		p2count = counter;
		p1count = number_of_vertices - p2count;
	}
	else
	{
		long moves =0;
		long rev_moves=0;
		long rand_num;//no_to_move
		while( moves <= (long)p1count/4)
		{
			rand_num= rand()%(number_of_vertices+1);
			if( vertex[rand_num].partition == 1)
			{
				vertex[rand_num].partition = 2;
				moves++;
			}
		}
		while( rev_moves  <= (long)p2count/4)
		{
			rand_num = rand()%(number_of_vertices+1);
			if( vertex[rand_num].partition == 2)
			{
				vertex[rand_num].partition =1;
				rev_moves++;
			}
		}
		Size_Of_Partitions();		
	}	
}

/*Displays the vertices in each of the partitions*/ 
void displayPartition()
{
  	long i=1;
       while (i <= number_of_vertices)
	{	
		if( vertex[i].partition == 1)
		{
			p1count++;
		}
		i++;
	}
	i=1;
	while (i <= number_of_vertices)
	{	
		if( vertex[i].partition == 2)
		{
			p2count++;
		}
		i++;
	}
}


/*Computes the gains of the vertices*/
void Compute_cell_Gains()
 {
 	/*For each free cell 'i' g(i)=0 where 'g' is the Gain of the cell*/
	long i=1,hnode,hypernodeweight=0, index=0;
	HypernodeList * temp;
	List_Of_Vertices * temp1;
	while(i<= number_of_vertices)
	{
		
		if(vertex[i].locked == 0)
		{
			vertex[i].gain=0;
			temp = vertex[i].hypernodelist;
			while(temp!=NULL)
			{
				hnode = temp->hypernode_no;
				temp = temp->next;
				if(vertex[i].partition==1)
				{
					if(hypernode[hnode].partition1==1)
					{
						vertex[i].gain+=hypernode[hnode].weight;
					}
					if(hypernode[hnode].partition2==0)
					{
						vertex[i].gain-=hypernode[hnode].weight;
					}
				}
				if(vertex[i].partition==2)
				{
					if(hypernode[hnode].partition2==1)
					{
						vertex[i].gain+=hypernode[hnode].weight;
					}
					if(hypernode[hnode].partition1==0)
					{
						vertex[i].gain-=hypernode[hnode].weight;
					}
				}
				
			}
			long index = maxweight + vertex[i].gain;
			if ( vertex[i].partition == 1)
			{
				bucket1[index].AppendBucket(i);
			}
			if ( vertex[i].partition == 2)
			{
				bucket2[index].AppendBucket(i);
			}
			
		}
		i++;	
	}
}


/*Computes the weight of each vertex */
void display(HypernodeList * temp)
{
	for (long i = 1; i <= number_of_vertices; i++)
	{
		VertexWeight();
	}
	
}

/*Computes the weight of each vertex */
void VertexWeight()
{
	HypernodeList * temp;
	long wht = 0,i=1;
	while(i<=number_of_vertices)
	{
		wht = 0;
		temp = vertex[i].hypernodelist;
		while( temp != NULL)
		{
			wht+=hypernode[temp->hypernode_no].weight;
			temp = temp->next;
		}
		vertex[i].weight = wht;
		i++;
	}

}


/*Computes the Maximum weight of the vertices*/
void Compute_maxweight()
{
	long i=0 ;
	maxweight = 0;
	while(i < number_of_vertices)
	{
		if( vertex[i].weight > maxweight)
		{
			maxweight = vertex[i].weight;
		}
		
	i++;	
	}

}

/*Initialises the gain bucket data structure*/
void initializeBucket(long maxweight)
{
	long i,pos,gain;
	//cout<<"In Init Bucket"<<maxweight<<endl;
	for ( i = 0; i < (2*maxweight+1); i++)
	{
		bucket1[i].gain = i-maxweight;
		bucket1[i].blist = NULL;	
		bucket2[i].gain = i-maxweight;
		bucket2[i].blist = NULL;		
	}	
}


/*Displays the elemnts contained in the bucket data structure*/
void  DisplayBucket()
{
	long i;
	BucketList *temp1=new BucketList;
	cout<<"BUCKET 1 :"<<endl;
	for( i = 0 ; i < (2*maxweight +1);i++)
	{
		cout<<bucket1[i].gain<<"-> ";
		temp1 = bucket1[i].blist;
		while(temp1!=NULL)
		{	
			cout<<temp1->vertex_no<<" ,";
			temp1=temp1->next;
		}
			cout<<endl;
	}
	cout<<"BUCKET 2 :"<<endl;
	for( i = 0 ; i < (2*maxweight +1);i++)
	{
		
		cout<<bucket2[i].gain<<"-> ";
		temp1 = bucket2[i].blist;
		while(temp1!=NULL)
		{	
			cout<<temp1->vertex_no<<" ,";
			temp1=temp1->next;
		}
		cout<<endl;
	}
	
}

/*Returns the Base cell which satisfies the required criteria*/
long Select_Basecell(long bfactor)
{
	double size=0.0;
	BucketList *temp;
	double count1,count2,not_in_1=0,not_in_2=0;
	long vert=-1;
	char ch;
	count1 = p1count;
	count2 = p2count;
	Compute_Maxgain();
	if(gain1>=gain2 && gain1 != -1)
	{
		count1--;
		count2++;
		size =(float)(count2)/(float)(number_of_vertices)*100;
		if(((50-bfactor)<size) && (size<(50+bfactor)))
		{
			temp=bucket1[gain1].blist;
			vert=temp->vertex_no;
			vertex[vert].locked=1;
			bucket1[gain1].Delete(vert);
		}
		else
		{
			count1++;
			count2--;
			not_in_1=1;
		}
	}
	if((not_in_1 == 1 || (gain1<gain2)) && gain2!= -1)
	{
		count1++;
		count2--;
		size=(float)count1/(float)number_of_vertices*100;
		
		if(size >= ( 50-bfactor) && size<=(50+bfactor))
		{
			temp=bucket2[gain2].blist;
			vert=temp->vertex_no;
			vertex[vert].locked=1;
			bucket2[gain2].Delete(vert);	
		}
		else
		{
			count1--;
			count2++;
			not_in_1=0;
		}
	}
			
	if((not_in_1==0 && gain1 < gain2) && gain1 != -1 && gain2 !=-1)
	{
		count2++;
		count1--;
		size =(float)count2/(float)number_of_vertices*100;
		if(size >= ( 50-bfactor) && size<=(50+bfactor))
		{
			temp = bucket1[gain1].blist;
			vert = temp->vertex_no;
			vertex[vert].locked  = 1;
			bucket1[gain1].Delete(vert);
		}
		else
		{
			count1++;
			count2--;
		}
	}
	p1count = count1;
	p2count = count2;
	return(vert);

}



/*Updates the gains of the vertices */
void Updategain(long ver)
{
	long incr,i=0,j,To_part,To_nodes,From_nodes,oldGain,index;
	HypernodeList *hyplist=new HypernodeList;
	List_Of_Vertices *vlist=new List_Of_Vertices;
	HypernodeList * temp;
	temp = vertex[ver].hypernodelist;
	if(vertex[ver].partition ==1)
	{
		To_part = 2;
	}
	else 
	{
		To_part = 1;
	}
	
	hyplist = vertex[ver].hypernodelist;
	while( hyplist != NULL)
	{
	 	index=hyplist->hypernode_no;
		if(To_part == 2)
		{
			To_nodes = hypernode[index].partition2;
			From_nodes = hypernode[index].partition1;
			
		}
		else if (To_part == 1)
		{
			To_nodes = hypernode[index].partition1;
			From_nodes = hypernode[index].partition2;
			
		}
	
		if (To_nodes == 0)
		{	
			
			vlist = hypernode[index].list_of_vertices;
			while( vlist != NULL)
			{
				if ( vertex[vlist->Vertex_No].locked != 1)
				{
					
					oldGain = vertex[vlist->Vertex_No].gain ;
					vertex[vlist->Vertex_No].gain += hypernode[index].weight;
					UpdateBucket( vertex[vlist->Vertex_No].gain, oldGain, vlist->Vertex_No);
				}				
				vlist = vlist->next;
			}
		}
		else if (To_nodes == 1)
		{
			vlist = hypernode[index].list_of_vertices;
			while( vlist != NULL)
			{
				if ( vertex[vlist->Vertex_No].locked != 1)
				{
					if( vertex[vlist->Vertex_No].partition == To_part)
					{
						oldGain = vertex[vlist->Vertex_No].gain ;
						vertex[vlist->Vertex_No].gain -= hypernode[index].weight;
						UpdateBucket( vertex[vlist->Vertex_No].gain, oldGain, vlist->Vertex_No);
					}
				}				
				vlist = vlist->next;
			}
			
		}
		
		From_nodes--;
		To_nodes++;
		
		if (From_nodes ==0)
		{
			vlist = hypernode[index].list_of_vertices;
			while( vlist != NULL )
			{
				if ( vertex[vlist->Vertex_No].locked != 1)
				{
					oldGain = vertex[vlist->Vertex_No].gain ;
					vertex[vlist->Vertex_No].gain -= hypernode[index].weight;
					UpdateBucket(vertex[vlist->Vertex_No].gain,oldGain, vlist->Vertex_No);
					
				}
				vlist = vlist->next;
			}	
		}
		else if ( From_nodes ==1 )
		{
			vlist = hypernode[index].list_of_vertices;
			while( vlist != NULL)
			{
				if ( vertex[vlist->Vertex_No].locked != 1)
				{
					if( vertex[vlist->Vertex_No].partition == (To_part)%2 + 1)
					{
						oldGain = vertex[vlist->Vertex_No].gain ;
						vertex[vlist->Vertex_No].gain += hypernode[index].weight;
						UpdateBucket( vertex[vlist->Vertex_No].gain, oldGain, vlist->Vertex_No);
			
					}
				}				
				vlist = vlist->next;
			}
		}
		
		hyplist = hyplist->next;		
	}
}


/*Updates the Hypernodes*/
void updateh(long i )
{
	HypernodeList * temp ;
	temp = vertex[i].hypernodelist;
	while( temp != NULL)
	{	
		if ( vertex[i].partition == 1)
		{
			hypernode[temp->hypernode_no].partition2++;
			hypernode[temp->hypernode_no].partition1--;
		}
		else
		{
			hypernode[temp->hypernode_no].partition1++;
			hypernode[temp->hypernode_no].partition2--;
		}
		temp = temp->next;	
	} 
	
}


/*Updates the hypernodes*/
void Update_Hypernode_Partition()
{
	long h,i;
	List_Of_Vertices * temp;
	for( i =1; i <= number_of_hyperedges; i++)
	{
		hypernode[i].partition1 = 0;
		hypernode[i].partition2 = 0;
	}

	
	for( i =1; i <= number_of_hyperedges; i++)
	{
		temp = hypernode[i].list_of_vertices;	
		while( temp!=NULL)
		{
			h = temp->Vertex_No;
			if( vertex[h].partition ==1)
			{
				hypernode[i].partition1++;
			}
			else
			{
				hypernode[i].partition2++;	
			}
			temp = temp->next;
		}
		//cout<<"Hypernode "<<i<<"Partition"<<hypernode[i].partition1<<endl;
	}
	p1count =0;
	p2count =0;
	for( i = 1; i <=number_of_vertices; i++)
	{
		if ( vertex[i].partition ==1)
		{
			p1count++;
		}
		else
		{
			p2count++;
		}
	}
}


/*Updates the verices in the Bucket data structure*/
void UpdateBucket(long newgain,long oldgain,long verno)
{
	long part,old_index,new_index;
	old_index=oldgain + maxweight;
	new_index=newgain + maxweight;
	
	part = vertex[verno].partition;

	if(part == 1) 
        {
		 bucket1[old_index].Delete(verno);
                 bucket1[new_index].AppendBucket(verno);
        }
	
     else if (part == 2) 
        {
	     	 bucket2[old_index].Delete(verno);
	         bucket2[new_index].AppendBucket(verno);
        }
}


/*Appends New vertices to the vertex list*/
void AppendToListofVertices(List_Of_Vertices **vlist, long num)
{
	
	List_Of_Vertices *temp = new List_Of_Vertices;
	List_Of_Vertices *temp1;
	temp->Vertex_No = num;
	temp->next = NULL;
	if(*vlist == NULL)
	{
		*vlist = temp ;
	}
	else
	{
		temp1= *vlist;
		while(temp1->next!=NULL)
		{
			temp1 = temp1->next;
			
		}
		temp1->next = temp;
	}
}


/* Returns the K best moves for the iteration*/
long K_Best_Moves(long gateCount)
{
	long i, max =0, k; 
	A =new long[gateCount];
	for( i=0; i <gateCount; i++)
	{
		if( i==0)
		{
			A[i] = vertex[gainArray[i]].gain;
		}
		else
		{
			A[i] = vertex[gainArray[i]].gain+ A[i-1];
		}
	}
	
	for( i=0; i <gateCount; i++)
	{
		if(A[i]>A[max])
		{
			max  = i;
		}	
	}
	return max;
	
}


/*Computes the elements in each partition*/
void Size_Of_Partitions()
{
	long i;
	p1count = 0;
	p2count = 0;
	for ( i = 1; i <=number_of_vertices;i++)
	{
		if ( vertex[i].partition ==0)
		{
			p1count++;		
		}
		else
		{
			p2count++;
		}
	}
}


/*Computes the Maximum gain of all in each of the partitions */
void Compute_Maxgain()
{
	long i;
	gain1 = -1;
	gain2 = -1;
	for( i= (2*maxweight); i>=0; i--)
	{
		if ( bucket1[i].blist != NULL)
		{
			gain1 = i;
			break;
		}		
	}
	
	for( i= (2*maxweight); i>=0; i--)
	{
		if ( bucket2[i].blist != NULL)
		{
			gain2 = i;
			break;
		}		
	}
}

/*Computes the Cut Size of the circuit*/
long cutSize()
{
	long i, w=0;	
	Update_Hypernode_Partition();
	for ( i = 1;i<=number_of_hyperedges ;i++)
	{
		if( hypernode[i].partition1 != 0 && hypernode[i].partition2!=0)
		{
			w+= hypernode[i].weight;
		}
	}
	return w;
}

/*Computes the Best cut size of the partition*/
void BestCutSize(long cut)
{
	long i=1;
	if( component[0]==-1)
	{
		while(i<=number_of_vertices)
		{
			component[i]=vertex[i].partition;
			i++;
		}
		component[0] = cut;
	}
	else if( component[0]>cut)
	{
		while(i<=number_of_vertices)
		{
			component[i]=vertex[i].partition;
			i++;
		}
		component[0] = cut;
	}
	
	
			
}

/*Write the output to a file*/
void filewrite(char *filename)
{
	FILE *fp;
	long i=1;
	fp=fopen(filename,"w");
	fprintf(fp,"%d\n",component[0]);
	
	while(i<=number_of_vertices)
	{
		fprintf(fp,"%d\t%d\n",i,component[i]); 
		i++;
	}
	fclose(fp);
	return;
}

/* The MAIN Function*/
int main(int argc, char* argv[])
{
	
	long i,select,bfactor,no_of_times=0,times=0,nedit ,lock,Count;
	long K_Best_Moves(long GateCount);
	long moves, count;
	char ch;
	HypernodeList * temp = new HypernodeList;
	List_Of_Vertices * temp1= new List_Of_Vertices;
	BucketList *buclist;
	if(argc != 5)
	{
		cout<<"Insufficient number of input parameters"<<endl;
		exit(0);
	}
	no_of_times=atol(argv[1]);
	fileread(argv[2]);
	bfactor=atol(argv[4]);
	gainArray = new long[number_of_vertices+1];
	component = new long[number_of_vertices+1];
	component[0] = -1;
	VertexWeight();
	Compute_maxweight();
	bucket1 = new Bucket[2*maxweight+1]; 
	bucket2 = new Bucket[2*maxweight+1]; 
	
	while ( times < no_of_times)
	{
		InitialPartition(times);
		while(1)
		{
			initializeBucket(maxweight);
			Update_Hypernode_Partition();
			Compute_cell_Gains();
			count = 0;
			while(1)
			{
				Compute_Maxgain();
				long z= Select_Basecell(bfactor);		
				if(z== -1)
				{
					break;
				}
			
				gainArray[count] = z;
				count++;
				Updategain(z);
				updateh(z);
				vertex[z].locked = 1;
			
			}
			if (count != 0)
			{
				moves = K_Best_Moves(count);
			}
			else 
			{
				break;
			}
			if( A[moves] <=0)
			{
				break;
			}
			for( i = 0; i <=moves;i++)
			{

				if ( vertex[gainArray[i]].partition == 1)
					vertex[gainArray[i]].partition = 2;
				else if ( vertex[gainArray[i]].partition == 2)
					vertex[gainArray[i]].partition = 1;
			}
			
			for( i=1; i <=number_of_vertices;i++)
			{
				vertex[i].locked = 0;
			}
		}
						
		times++;
		long cut = cutSize();
		BestCutSize(cut);
		cout<<endl<<"The Best cut Size Until pass No "<<times<<" = "<<component[0]<<endl;	
	}
	filewrite(argv[3]);
}