/*************************************************************
	Satish P Bhat

	Implementation of Fiduccia-Matheyses Heuristic
/*************************************************************/

/* This is the Header file " FM-Algo.h" */

/*  Standard Header Files being included */
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>

/*Declaration and Initialization of the class which holds the list of
  Vertices/cells */
class List_Of_Vertices {
public:
	long Vertex_No;
	 List_Of_Vertices *next;
	List_Of_Vertices(){Vertex_No=0;next=NULL;}
	~List_Of_Vertices(){}	
};

/*Declaration and Initialization of the class which holds the hypernodes*/
class Hypernode {
public:
	long weight;
	long counter;
        long partition1;
        long partition2;
	List_Of_Vertices *list_of_vertices;
	void AppendVertex(long);/*Appends the vertices/cells into the list of vertices*/
	Hypernode(){weight = 0; counter=0;partition1=0,partition2=0,list_of_vertices = NULL;}
	~Hypernode(){}
};

/*Declaration and Initialization of the class which holds the list of hypernodes*/
class HypernodeList
{
	public:
	long hypernode_no;
	HypernodeList *next;
	HypernodeList(){hypernode_no = 0; next=NULL;}
	~HypernodeList();
	
};

/*Declaration and Initialization of the class which holds the Vertices and its
  details*/
class Vertex {
public:
	long partition;
	long gain;
	long locked;
	long counter;
	long weight;
	HypernodeList *hypernodelist;
	void AppendHypernode(long);/*Appends the hypernode into the hypernode list*/
	Vertex(){partition=1;gain=0;locked=0;counter=0;weight =0;
	          hypernodelist= NULL;}
	~Vertex(){}
};

/*Declaration and Initialization of the class which is the list of vertices in the given gain
  bucket data structure */
class BucketList{
public:
	long vertex_no;
	BucketList *next;
	BucketList *prev;
	BucketList(){vertex_no=0;next=NULL;prev = NULL;}
	~BucketList(){}
};

/*Declaration and Initialization of the class which holds the gains of the vertices implemented 
  as a doubly linked list */
class Bucket{
public:
	long gain;
	BucketList *blist;
	void AppendBucket(long);/* Appends vertices into bucket data structure*/
	void Delete(long);	/* Deletes vertices from the bucket data structure*/
	Bucket(){gain = 0; blist=NULL;}
	~Bucket(){}
};

/* Global Variables Used in the Implementation of the Algorithm */
Hypernode *hypernode;		/*pointer to the Hypernode class*/
HypernodeList *hypernodelist;	/*pointer to the HypernodeList class*/
List_Of_Vertices *list_of_vertices; /*pointer to the List_Of_Vertices class*/
Vertex *vertex;	          /*pointer to the Vertex class*/
Bucket *bucket1;          /*pointer to the Bucket class*/
Bucket *bucket2;	  /*pointer to the Bucket class*/
BucketList *blist1;       /*pointer to the BucketList class*/
BucketList *blist2;       /*pointer to the BucketList class*/
long * gainArray;	  /*Array to hold the gains of the vertices*/	
long * A;		  /*Array to hold the gains of the vertices*/
long number_of_vertices;  /*Variable to hold the total number of vertices/cell*/
long number_of_hyperedges;/*Variable to hold the total number of hyperedges*/
long maxweight=0;         /*Variable to hold the Maximum Weight of the vertices*/ 
long gain1,gain2;         /*Variables that hold the Maximum gains in the 2 partitions*/
double p1count=0.0,p2count=0.0;/* Variables that have the count of elements in the 2 partitions*/
long bfactor;             /*Variable to hold the balance factor read from the command line*/
long *component;	  /*Records the component number the ith vertex belongs to*/

/* Global Functions Used in the Implementation of the Algorithm */
void InitialPartition(long);	/*Computes the Intial Partition of the vertices*/
void Compute_cell_Gains();	/*Computes the gains of the vertices*/
void display(HypernodeList * temp); /*Computes the weight of each vertex */
void Size_Of_Partitions();	/*Computes the elements in each partition*/
void initializeBucket(long maxweight);/*Initialises the gain bucket data structure*/
void DisplayBucket();		/*Displays the elemnts contained in the bucket data structure*/
void VertexWeight();            /*Computes the weight of each vertex */
void Update_Hypernode_();	/*Updates the hypernodes*/
void Compute_maxweight();	/*Computes the Maximum weight of the vertices*/
void displayPartition();	/*Displays the vertices in each of the partitions*/ 
long Select_Basecell(long balance_factor);/*Returns the Base cell which satisfies the required criteria*/
void Compute_Maxgain();         /*Computes the Maximum gain of all in each of the partitions */
void Updategain(long vertex);	/*Updates the gains of the vertices */
long cutSize();			/*Computes the Cut Size of the circuit*/
void UpdateBucket(long,long,long);/*Updates the verices in the Bucket data structure*/
void fileread(char* filename);  /*Reads the File and puts the vertices in a list*/  
void AppendToListofVertices(List_Of_Vertices **vlist, long num);/*Appends New vertices to the vertex list*/
void updateh(long );		/*Updates the Hypernodes*/
void BestCutSize(long cut);	/*Computes the Best Cut Size*/
void filewrite(char *filename); /*Writes the output to the file specified*/