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

//this is an improved method of the lilei's dictionary-based test data compression.
//but we compress the test data from two directions.
//firstly we compress the test data vertically, and then we compress them from crosswise.
//the main algorithms refer to lilei's dictionary-based test data compression method.

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

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
	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);
	
//read 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","");


//read the original patterns
    char *patterns=new char[width*number]; //the array for the original patterns
    char *ptemp; //the point of the array patterns
    int l; //the length of the subvectors
    int fcare=0; 
    int i,j,k,t,tp1;
    int wfmp; //the width of the formatted test data
    ptemp=patterns;
   

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

//output the array patterns for checking
	fprintf(fp,"%s\n","the test patterns:");
	for ( i=0;i<number;i++ )
	{
		for ( j=0;j<width;j++ )
			fprintf(fp,"%c",patterns[i*width+j]);
		fprintf(fp,"%s\n","");
	}
	fprintf(fp,"%s\n","");


//rebuild the array of the test patterns formatted for multiple scan chains
   
//calculate l first
    if ( width%m==0 )  l=width/m;
    else  
    {   
	    l=width/m+1;
	    fcare=1;//here the flag show whether need or not to pad the don't care in the end.if fcare=1,it means needing
    }

//then format the test patterns and process the patterns one by one 
    t=0;
    wfmp=number*l;
    char *fmatpat=new char[wfmp*m];//the array for the formatted test data
	char *tfmat=new char[wfmp*m];

    tp1=width/l;
	if ( fcare==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<tp1;j++ )
		        for ( k=0;k<l;k++ )
				{
			         fmatpat[j*wfmp+(k+i*l)]=patterns[t];
			         t++;
				}
		    for ( k=0;k<(width-tp1*l);k++ )
			{
			    fmatpat[j*wfmp+(k+i*l)]=patterns[t];
			    t++;
			}
		    for ( k=(width-tp1*l);k<l;k++ )
			    fmatpat[j*wfmp+(k+i*l)]='-';
		    for ( j=tp1+1;j<m;j++ ) //do while l<m
			    for ( k=0;k<l;k++ )
					fmatpat[j*wfmp+(k+i*l)]='-';
		}
	}
  

//output the array fmatpat for checking
	fprintf(fp,"%s\n","the formatted pattern:");
	for ( i=0;i<m;i++ )
	{
		for ( j=0;j<wfmp;j++ )
			fprintf(fp,"%c",fmatpat[i*wfmp+j]);
		fprintf(fp,"%s\n","");
	}
	fprintf(fp,"%s\n","");
   

//find the compatible cliques among rows
//this is the first time to look for the compatible cliques
//the results we need are the positions of the shanchu lines and the compatible array in which the compatible patterns have been deleted
   
   int *scl=new int[m];//the temp array used to save the original position value
   int *tscl=new int[m];//the temp array usd to save the changed position value
   int *graphg=new int[m*m]; //the graph G for the compatible matrix of the famatted data
   int *gg=new int[m*m];//G'
   int *tgg=new int[m*m];//temp G'
   int *ncomp=new int[m];//the degree of every vertex
   int *rcomp=new int[m];//show the compatible relationship
   int fcomp; 
   int t1,t2,tmax;
   int tm;//the number of the vectors in the array in which the compatible patterns have been deleted
   int pgg1,pgg2;
   int temp=0;

//set up the compatible matrix G
//if the two patterns are compatible,the corresponding position in the matrix equals 1;otherwise 0.
//we think the pattern is not compatible to itself

   for ( i=0;i<m;i++ )
   {
	   for ( j=0;j<m;j++ )
	   {
		   fcomp=0;//the flag of the compatible;here if fcomp=1;it means the patterns are not compatible
		   k=0;
		   while ( k<wfmp )
		   {
			   if (((fmatpat[i*wfmp+k]=='0')||(fmatpat[i*wfmp+k]=='1'))&&((fmatpat[j*wfmp+k]=='0')||(fmatpat[j*wfmp+k]=='1')))
			   {
				   if (fmatpat[i*wfmp+k]==fmatpat[j*wfmp+k])  k++;
				   else
				   {
					   graphg[i*m+j]=0;
					   fcomp=1;
					   break;
				   }
			   }
			   else k++;
		   }
		   if ((fcomp==0)&&(i!=j))
		   {
			   graphg[i*m+j]=1;
			   temp++;//the total number of the compatible relationship
		   }
		   if (i==j) graphg[i*m+j]=0;
	   }
   }

//output graph G for checking
   fprintf(fp,"%s\n","the compatible matrix G:");
   for ( i=0;i<m;i++ )
   {
	   for ( j=0;j<m;j++ )
		   fprintf(fp,"%d",graphg[i*m+j]);
	   fprintf(fp,"%s\n","");
   }
   fprintf(fp,"%s\n","");


//greedy algorithm.

//the first cycle is used to confirm the group of compatible vectors
//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)
   
   fprintf(fp,"%s\n","the positions of the shanchu lines:");
   fcomp=0;//count the number of the groups of the compatible vectors    
   while(temp!=0)
   {
	   for ( i=0;i<(m*m);i++ )
	       gg[i]=graphg[i];
           pgg2=m;
	   for ( i=0;i<m;i++ )
	       scl[i]=i;
	   fcomp++;
	   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(fp,"%d ",t);//output the position of the shanchu line
			rcomp[t]=fcomp;//the compatible vectors have the same value in the corresponding positions in the array rcomp.this can be used later.
			for ( i=0;i<m;i++ )
			{
				if(graphg[i*m+t]==1)
				{
					graphg[i*m+t]=0;
					temp--;
				}
				if(graphg[t*m+i]==1)
				{
					graphg[t*m+i]=0;
					temp--;
				}
			}
			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(fp,"%s\n","");
   }
   fprintf(fp,"%s\n","");
   
   delete[]graphg;
   delete[]gg;
   delete[]tgg;
   delete[]ncomp;
   delete[]scl;


//rebuild the array in which the compatible vectors have been deleted
   for ( i=1;i<=fcomp;i++ )
   {
	   t=0;
	   t1=0;
//the compatible vectors belong to same group resave to the array tfmat in order to process easily
	   for ( j=0;j<m;j++ )
	   {
		   if ( rcomp[j]==i )
		   {
			   for ( k=0;k<wfmp;k++ )
			   {
				   tfmat[t]=fmatpat[j*wfmp+k];
				   t++;
			   }
			   tscl[t1]=j;
			   t1++;//the size of the group of the compatible patterns
		   }
	   }

//specify the bits that can be specified
	   for ( j=0;j<wfmp;j++ )
	   {
		   k=0;
		   while ( k<t1 )
		   {
			   if( tfmat[k*wfmp+j]=='-') k++;
			   else
			   {
				   tfmat[j]=tfmat[k*wfmp+j];
				   break;
			   }
		   }

	   }
//rewrite the specified patterns to the first appeared vector in the original formatted array 
//char 2 is rewited to the first cells of the other patterns