// compression11.cpp : Defines the entry point for the console application.
//


//**************************PROGRAM***********************


#include "stdafx.h"
#include "iostream.h"
#include "stdio.h"
#include "math.h"


//function pronouncement

void patternfmat(char *,char *,int,int,int);

int compgraphset(char *,int *,int,int);
int maxcliquegreedy(FILE *,int *,int *,int,int);
int comppatdelete(char *,int *,int,int,int);
int rowcompalg(FILE *,char *,int,int);//first compression

void matrixoutput(FILE *,char *,int,int);

void distgraphset(char *,int *,int,int);
void patternsort(char *,char *,int *,int,int);
void firstpattern(char *,char *,int,int);
int maxdistfind(char *,char *,int,int);
int log2upl(int);
int positioncao(FILE *,char *,char *,int,int,int,int);
int positionmarkalg(FILE *,FILE *,char *,int,int);//second compression




//***********************main function*************************


int main(int argc, char* argv[])
{

	char sourcename[35];       //filename for input
	char destinationname[35];  //filename for output(related information)
	char resultname[35];       //filename for result
    int width = 0;             //the width of test patterns
    int number = 0;            //the number of test patterns
    int m=0;                   //the number of the scan chains
	int l=0;                   //the length of the subvectors
    int wfmp=0;                //the width of the formatted test data
	int tm=0;                  //the number of the vectors in the array in which the compatible patterns have been deleted
	int nw=0;                  //the width of the new test patterns
	int total;                 //the size of the compressed test set
	int i,j;
	FILE *fpp,*fp,*fr;         //the point of the input file and the output file


//open the file

    cout << "Filename input:";
    cin >> sourcename;
	fpp=fopen(sourcename,"r");
	if (!fpp)
	{
		cout << sourcename << " could not be opened" << endl;
		return 1;
	} 
	
    cout << "Filename output:";
    cin >> destinationname;
    fp=fopen(destinationname,"w");
    if (!fp)
    {
	     cout<< destinationname << "not created" << endl;
         return 1;
	}

	cout << "Filename for result:";
    cin >> resultname;
    fr=fopen(resultname,"w");
    if (!fr)
    {
	     cout<< resultname << "not created" << endl;
         return 1;
	}
 
	
//read the width and the number of the patterns

	fscanf(fpp,"%d", &width);
    if (width==0)
    {
         cout << "no patterns!";
         return 1;
    }
    fscanf(fpp,"%d", &number);
	fprintf(fp,"%s","the width and number of test patterns : ");
    fprintf(fp,"%d ",width);
	fprintf(fp,"%d\n",number);
	fprintf(fp,"%s\n","");

	
//read and output the number of the scan chains

    cout << "please input the number of the scan chains m(<width):";
    cin >> m;
    fprintf(fp,"%s","the number of the scan chains m:");
    fprintf(fp,"%d\n",m);
	fprintf(fp,"%s\n","");


//calculate l and wfmp

    if ( width%m==0 )    	l=width/m;
    else            		l=width/m+1;
    wfmp=number*l;



    char *patterns=new char[width*number];  //the heap for the original patterns
                                            //many times we use the heap as two dimensions array
    char *ptemp;                            //the point of the array patterns
	char *fmatpat=new char[wfmp*m];         //the heap for the formatted test data
	char *tfmat=new char[wfmp*m];           //temp fmatpat
    ptemp=patterns;

   
//read the original patterns

    while(!feof(fpp))
    {
	    fscanf(fpp,"%c",ptemp);
        if(*ptemp!='\n') ptemp++;
    }
    fclose(fpp);
  

//first compression

	patternfmat(patterns,fmatpat,width,number,m);
    tm=rowcompalg(fp,fmatpat,wfmp,m);
    fprintf(fp,"%s ","the number of the vectors after the compatible vectors have been deleted:");
    fprintf(fp,"%d\n",tm);
    fprintf(fp,"%s\n","");


//rearrange the array fmatpat to tfmat(nw,number)

    for ( i=0;i<wfmp;i++ )
	    for ( j=0;j<tm;j++ )
		    tfmat[i*tm+j]=fmatpat[j*wfmp+i];

    nw=tm*l;        //the width of the tfmat,and also the length of the CSR
    fprintf(fp,"%s ","the length of the CSR (the width of the new patterns): ");
    fprintf(fp,"%d\n",nw);
    fprintf(fp,"%s\n","");
/*	fprintf(fp,"%s\n","the rearranged fmatpat:");
    matrixoutput(fp,tfmat,nw,number);*/

   
//second compression.process the new patterns and output the result using position-mark method
	
	total=positionmarkalg(fp,fr,tfmat,nw,number);
	delete[]tfmat;
	total=total+nw;
	fprintf(fp,"%s","the total size of the compressed test set: ");
	fprintf(fp,"%d\n",total);
    

//close the file

    fclose(fp);
	fclose(fr);

	return 0;


}



//**********************function patternfmat********************


//this function formats the test patterns according to the number of scan chains m
//the formatting details refer to lilei's dictionary-based test data compression
//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be formatted
//      fmatpat--the heap room used to save the formatted test patterns
//      width,number--the width and the number of the patterns
//      m--the number of the scan chains


void patternfmat(char *patterns,char *fmatpat,int width,int number,int m)
{

	int i,j,k,p,l,t=0;
	int flag=0;  //here the flag show whether need or not to pad the don't care in the end.if flag=1,it means needing    
    int wfmp=0;  //the width of the fmatpat

	if ( width%m==0 )    l=width/m;
    else
	{
		l=width/m+1;
		flag=1;
	}
    wfmp=number*l;

	p=width/l;
	if ( flag==0 )
	{
		 for ( i=0;i<number;i++ )
		 {
			  for ( j=0;j<m;j++ )
			      for ( k=0;k<l;k++ )
				  {
			            fmatpat[j*wfmp+(k+i*l)]=patterns[t];
			            t++;
				  }
		 }
	}
	else
	{
		for ( i=0;i<number;i++ )
		{
		    for ( j=0;j<p;j++ )
		        for ( k=0;k<l;k++ )
				{
			         fmatpat[j*wfmp+(k+i*l)]=patterns[t];
			         t++;
				}
		    for ( k=0;k<(width-p*l);k++ )
			{
			    fmatpat[j*wfmp+(k+i*l)]=patterns[t];
			    t++;
			}
		    for ( k=(width-p*l);k<l;k++ )
			    fmatpat[j*wfmp+(k+i*l)]='-';
		    for ( j=p+1;j<m;j++ ) //do while width%m>l
			    for ( k=0;k<l;k++ )
					fmatpat[j*wfmp+(k+i*l)]='-';
		}
	}
}




//********************function compgraphset*********************


//this function sets up the compatible graph G of the test patterns
//if the two patterns are compatible,the corresponding position in the graph G equals 1;otherwise 0.
//we think the pattern is not compatible to itself
//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be set up the compatible graph G
//      graphg--the heap room used to save the compatible graph G
//      width,number--the width and the number of the patterns
//this function will return the number of 1 in the graph G


int compgraphset(char *patterns,int *graphg,int width,int number)
{

	int i,j,k,flag;
    int total=0;
	
	for ( i=0;i<number;i++ )
    {
		for ( j=0;j<number;j++ )
		{
			flag=0;//the flag of the compatible;if flag=1;it means the patterns are not compatible
		    k=0;
		    while ( k<width )
			{
			    if ((patterns[i*width+k]!='-')&&(patterns[j*width+k]!='-'))
				{
				    if (patterns[i*width+k]==patterns[j*width+k])  k++;
				    else
					{
					    graphg[i*number+j]=0;
					    flag=1;
					    break;
					}
				}
			    else k++;
			}
		    if ((flag==0)&&(i!=j))
			{
			    graphg[i*number+j]=1;
			    total++;//the total number of the compatible relationship
			}
		    if (i==j) graphg[i*number+j]=0;
		}
	}

	return total;
}




//*******************function maxcliquegreedy********************


//this fuction is the greedy algorithm to find the maximal clique in graph G.

//the first cycle is used to confirm the group of compatible vectors(clique).
//cycle one time comfirms a group of compatible vectors
//here we will output the positions of the compatible vectors(the positions of the shanchu lines)
//the meaning of the function's parameters as follows:
//      f--the point of the file to output the position value
//      graphg--the graph G show the compatible relationship
//      rcomp--a heap room to save compatible mark of every pattern
//      n--the number of the vertices in graph G
//      total--the number of 1 in the graph G
//this function will return the number of the cliques

   
int maxcliquegreedy(FILE *f,int *graphg,int *rcomp,int n,int total)
{

   int *scl=new int[n];   //the temp array used to save the original position value
   int *tscl=new int[n];  //the temp array usd to save the changed position value
   int *gg=new int[n*n];  //G'
   int *tgg=new int[n*n]; //temp G'
   int *ncomp=new int[n]; //the degree of every vertex 
   int i,j,t,t1,t2,tmax,flag,pgg1,pgg2;

   if(gg==NULL)       cout<<"allocate error1"<<endl;
   if(tgg==NULL)      cout<<"allocate error2"<<endl;

   fprintf(f,"%s\n","the positions of the shanchu lines:");

   flag=0;//count the number of the groups(cliques)   
   while(total!=0)
   {
	   for ( i=0;i<(n*n);i++ )
	       gg[i]=graphg[i];
           pgg2=n;
	   for ( i=0;i<n;i++ )
	       scl[i]=i;
	   flag++;
	   do
	   {
            for ( i=0;i<pgg2;i++ )
				ncomp[i]=0;
			for ( i=0;i<pgg2;i++ )
				for ( j=0;j<pgg2;j++ )
				{
					if( gg[i*pgg2+j]==1)
						ncomp[i]++;
				}
		    t2=ncomp[0];
            tmax=0;
            for( t1=1;t1<pgg2;t1++ )
			{
	            if( t2<ncomp[t1] )
				{
		            t2=ncomp[t1];
		            tmax=t1;
				}
			}
			t=scl[tmax];            //the position of the vector in graphg
			fprintf(f,"%d ",t);     //output the position of the shanchu line
			rcomp[t]=flag;          //the compatible vectors have the same value in the corresponding positions in the array rcomp.this can be used later.
			for ( i=0;i<n;i++ )
			{
				if(graphg[i*n+t]==1)
				{
					graphg[i*n+t]=0;
					total--;
				}
				if(graphg[t*n+i]==1)
				{
					graphg[t*n+i]=0;
					total--;
				}
			}
			pgg1=pgg2;
			pgg2=0;
			for ( i=0;i<pgg1;i++ )
			{
				if( gg[tmax*pgg1+i]==1 )
				{
					tscl[pgg2]=i;
					pgg2++;
				}
			}
			for ( i=0;i<pgg2;i++ )
			{
				t1=tscl[i];
				scl[i]=scl[t1];      //t1 increases progressively
				for ( j=0;j<pgg2;j++ )
				{
					t2=tscl[j];
					tgg[i*pgg2+j]=gg[t1*pgg1+t2];
				}
					
			}
			for ( i=0;i<(pgg2*pgg2);i++ )
					gg[i]=tgg[i];			

	   }while(pgg2!=0);
	   
	   fprintf(f,"%s\n","");
   }
   fprintf(f,"%s\n","");

   delete[]gg;
   delete[]tgg;
   delete[]ncomp;
   delete[]scl;
   delete[]tscl;

   return flag;
}




//********************function comppatdelete*******************


//this fuction will delete the compatible vectors in the test patterns according to the rcomp

//first the compatible vectors belong to same clique will be resave to the heap(array) tfmat in order to process easily
//then we will specify the bits that can be specified in a clique
//and rewrite the specified vector to the first appeared position in the original array 
//and char 2 is rewited to the first cells of the other patterns
//at last,scan the array.if the first cell of the vector in array is char 2,delete this vector

//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be processed
//      rcomp--compatible mark array(as above)
//      width,number--the width and the number of the patterns
//      n--the number of the cliques
//this function will return the number of the patterns in which the compatible ones have been deleted.


int comppatdelete(char *patterns,int *rcomp,int width,int number,int n)
{

	int i,j,k,t,t1;
	char *temp1=new char[width*number];   
	int *temp2=new int[number];

	for ( i=1;i<=n;i++ )
    {
	    t=0;