/* Compiled with g++.
 * This is the program written to calculate the opt size of the monotone 
 * function up to 6 variables. 
*/
# include <stdio.h>
# include <math.h>
# include <stdlib.h>
# include <fstream.h>
# include <iostream.h>

#define Nterm 4
#define SFT3 8 // 2^3 
#define SFT4 16 // 2^4 
#define SFT5 32 // 2^5 
#define N_3 20 //the number of monotone functions for 3 vars
#define N_4 168 //the number of monotone functions for 4 vars
#define N_5 7581 //the number of monotone functions for 5 vars
#define N_6 7828354 //the number of monotone functions for 5 vars
#define MAX 10000 //just a large number


void nrerror(char error_text[])
	/*Numerical Recipes standard error handler*/
{
	int i;
	printf("\n\n");
	fprintf(stderr,"Numerical Recipes run-time error...\n");
	fprintf(stderr,"%s\n",error_text);
	fprintf(stderr,"...now exiting to system...\n");
	exit(1);
}


int * inf_cal(unsigned long mfv,int n,int t2n,int * mindex) 

       //mfv: monotone function's value; n: number of variables in the function; t2n: number equal to 2^n.
{
	//to calculate the inf using the naive method, which defines the inf as a ratio of the numb of changed f(v)|v:0->1, 	
	//with the total 2^n numbers. And here the inf is defined without normalized by 2^n since one only cares the relative inf
	int i,j;
	unsigned long tmp;
	int indxf;
	long  max=-1;
//        for (i=0;i<n;i++)
//            mindex[i]=n;//initialize; the real index for each variable is in the range of 0 to n-1; 
	int vinf[n];//stores this variable's unnormalized influnce.
				//for monotone function value from bit 0 to bit 15
				/*
				 * x0 00000000 | 11111111
				 * x1 00001111 | 00001111
				 * x2 00110011 | 00110011
				 * x3 01010101 | 01010101
				 * -----------------------
				 * f  00000001 | 00000011 this is just one of 168 functions of 4 vars
				 * bit0---------------->bit 15
				 */


	//cal the inf for each varible
	for(j=0;j<n;j++)//for each var
	{
		vinf[j]=0; //initialize 
		for(i=0;i<t2n;i++)//go through the whole list
			          //namely 0,1,.....,2^n-1
		{
		  if(!((i>>(n-1-j))&1))//if the var_j is 0 
			               //this definition of j is consistent with elsewhere in this program
		  {
			  if((t2n-1-i)<32){
				  tmp=1&(mfv>>(t2n-1-i)); //get the fvalue of bit n-1-i   
			  }
			  else{ tmp=1&(mfv>>16>>16>>(t2n-1-i-32));}
			  indxf=(i|(1<<(n-1-j))); //flip the var_j from 0 to 1

			  if((t2n-1-indxf)<32){
				  if(tmp!=(1&(mfv>>(t2n-1-indxf))))//if the DNF changes
					  vinf[j]++; 
			  }
			  else{
				  if(tmp!=(1&(mfv>>16>>16>>(t2n-1-32-indxf))))//if the DNF changes
					  vinf[j]++;

			  }
		  }
		}//end of the list
	} //end of each var loop 

	for(j=0;j<n;j++) //for each var
	{
		//printf("vinf[%d] is %d\n",j,vinf[j]);
		if(max <= vinf[j])
		{
			mindex[j]=j;
			//if(n==5) printf("mindex[%d] is %d\n",j,mindex[j]);
			max=vinf[j];
		}
	}

	//now return the index of the max influce var 
//	cout<<"the mindex[%d] is "<<j<<"\n\n";
	return mindex;
}

//the following method search an array of m var function lish and returns its 
//optsize of that monotone function
int srch_opts(unsigned long *flist, int *optlist, unsigned long  fvalue, int length)
	//the flist is an array of monotone functions
	//optlist is an array of optsize of the monotone functions
	//fvalue is the searching key and length is the size of the array
{
//	printf("length is %d\n",length);
        //if(length==7581) printf("optlist[%d] is %d\n",fvalue,optlist[fvalue]);
	int L=0, R=length-1;
	int M; //the left index rightmost index and middle index
	int found=0;
	while(L!=R&&!found)
	{
		if((R-L)==1)
		{
			if(fvalue==flist[L])
			{
				M=L;
				found=1;
			}
			else if(fvalue==flist[R])
			{
				M=R;
				found=1;
			}
			else
			{ }
		}
		else
		{
			M=(L+R)/2;

			if(fvalue>flist[M])
			{
				L=M;
			}
			else if(fvalue<flist[M])
			{
				R=M;
			}
			else //equal values
			{
				found=1;
			}
		}
	}
	return optlist[M];
}

int srch_opts2(unsigned long *flist, int *optlist, unsigned long  fvalue, int length)
	//the flist is an array of monotone functions
	//optlist is an array of optsize of the monotone functions
	//fvalue is the searching key and length is the size of the array
{
	int L=0, R=length-1;
	int i; //the left index rightmost index and middle index
        for(i=0;i<length;i++)	
	{
		if(flist[i]==fvalue)
			break;
	}
	return optlist[i];
}

int  gen_mnt(unsigned long *mntf_pre, unsigned long *mntf_nxt,int N_pre,int N_nxt,int sft)
	/*
	 * this function generate the mnt_function of n var from mnt_function of n-1 var
	 * mntf_pre is the list of mnt functions of n-1 var
	 * mnt_nxt is the list of mnt functions of n var
	 * int N_pre is the number of mntf of n-1 var
	 * and the int N_nxt is the number of mntf of n var
	 * sft is the shift numbre and equals 2^(n-1)
	 */
{
	int i,j;
	//construct the 4 var monotone function
	for(i=0;i<N_nxt;i++)
	{
		mntf_nxt[i]=0;
	}
	
	int cnt=0; //the counter 
	for(i=0;i<N_pre;i++)
	{
		for(j=i;j<N_pre;j++)
		{
			//generate the 4 var monotone functions from the N_3 3 var functions
                        if(sft==16 and cnt==7580)
                          printf("let's check the value of the 7580th function of 5 variable now");
			if((mntf_pre[i]|mntf_pre[j])==mntf_pre[j])
			{
				mntf_nxt[cnt]=(mntf_pre[i]<<1<<(sft-1))|mntf_pre[j];//incase sft==32, the << can not handle >=32
				cnt++;
			}
		}
	}
	return cnt;
}

void left_right(unsigned long &left, unsigned long &right,int NV, int nv,unsigned long mf,int N1,int N2)
	/*
	 * suppose that the N1=2^3 is the number of inputs of 3 var, and the N2=2^4=16 is now the number of inputs of 4 var; then
	 * left, right;  each stores the left and right subtree 3 vars monotone function
	 *  value, which is the key to find the optsize from the 3 var stored result
	 *  The nv is the nth var. For N2=16, nv=0,1,2,or 3.
         *  NV is the # of variables in the MF
         * mf is the MF's value.
	 */
{
	int i,j, l,r;
	unsigned long temp;	
	i=nv;
	left=0; //need to double check the position of these two lines
	right=0;
	l=0; r=0; //the left and right counter are set to zero in the beginning
	for(j=0;j<N2;j++)
	{
		//for 4 vars for i=0 to 3
		//for monotone function value from bit 0 to bit 15
		/*
		 * x0 00000000 | 11111111
		 * x1 00001111 | 00001111
		 * x2 00110011 | 00110011
		 * x3 01010101 | 01010101
		 * -----------------------
		 * f  00000001 | 00000011 this is just one of 168 functions of 4 vars
		 * bit0---------------->bit 15
		 */
		//cout<<"j "<<j<<"\n";
		if((j>>(NV-i-1))&1)
		{
			//right
                        if(j>=32) temp=mf>>N2-j-1;
                        else temp=mf>>N2-(j+32)-1>>16>>16;
			if(temp&1)
			{
				right|=(1<<(N1-1-r)); //mask that bit to 1
				r++;
			}
			else
			{
				//right&=(0<<(N1-1-r)); //mask that bit to 0
				r++;
			}
		}
		else
		{
			//left
                        if(j>=32) temp=mf>>N2-j-1;
                        else temp=mf>>N2-(j+32)-1>>16>>16;
			if(temp&1)
			{
				left|=(1<<(N1-1-l)); //mask that bit to 1
				l++;
			}
			else
			{
				//left&=(0<<(N1-1-l)); //mask that bit to 0
				l++;
			}
		}
		//cout<<"left is "<<left<<"\n";
		//cout<<"right is "<<right<<"\n";
	}
}

 void opt_size_cal(unsigned long* mntnf_pre,unsigned long* mntnf,int* optsz_pre, int* optsz,int Nf_pre, int Nf, int nv)
	/*
	 * This is the function to calculate the opt size of each monotone function for
	 * a given number of vars, i.e., 3 vars, 4 vars, 5 vars, 6 vars etc.
	 * Nf= 168 monotone functions for nv=4 vars
	 * Nf_pre is 20 then since 3 var is used to cal 4 vars
	 * nv is the number of variables in the monotone function
         */
{
	unsigned long left, right;  //each stores the left and right subtree 3 vars monotone function
	                  //value, which is the key to find the optsize from the 3 var stored result
        int k, l, r, i;	
	int tree_size, trszl, trszr; //size of trees
	int min;
	int *index_opt=new (int [nv]),min_index_opt;
	int nterm; //the number of total input terms, e.g. when nv=4 nterm=2^4=16
	int hfnt;
	unsigned long  tmp1=0,tmp2=Nf;
	nterm=(int) pow(2.0, nv);
	hfnt=nterm/2;
        for (i=0;i<nv;i++)
	{
		index_opt[i]=nv;
	}
	   
	
//	for(k=0;k<Nf;k++) //N_4 number of monotone function of 4 vars
        //if(nv==5) printf("Nf_pre is %d\n",Nf_pre);
	for(k=tmp1;k<tmp2;k++) //N_4 number of monotone function of 4 vars
	{
		min=1000;
	      // if (nv==6)	printf("k is %d\n",k);
		index_opt=inf_cal(mntnf[k],nv,nterm,index_opt);//get the index of the variable with the largest influence
               // cout<<"index_opt is %f"<<index_opt<<"\n";
                for(i=0;i<nv;i++)
		{
                        if( k%1000==0){
			cout<<"the ith variable\t"<<i<<"\n";
       		        cout<<"mntnf["<<k<<"] of 6 variables "<<mntnf[k]<<"\n";}
			left_right(left,right,nv,i,mntnf[k],hfnt,nterm);

			//part I, find min optsize w/o considering the influence
			//after one gets the left and right subtree value for a give var as the root
			//then calculate the optsize tree for each var as a root.
			//Finally one chooses the min optsize tree
			if(nv==6 && k== 7580){
                        cout<<"left "<<left<<"\n";
			cout<<"right "<<right<<"\n";}
                        //if(nv== 5){
                        //printf("left is %d\n",left);
		//	printf("right is %d\n",right);}
		        //cout<<"in the else\n";
			trszl=srch_opts(mntnf_pre,optsz_pre,left,Nf_pre);
			//if(nv==5)
			//{printf("left tree size is %d\n",trszl);
			// printf("right tree size is %d\n",trszr);}
			trszr=srch_opts(mntnf_pre,optsz_pre,right,Nf_pre);
			if(left == right)
                          tree_size=trszl;   //the tree size is just one sub-tree's size 
                        else
                          tree_size=trszl+trszr+1;
                      //  printf("tree_size of variable %d is %d\n",i,tree_size);
		        if(min>=tree_size)
				{
					min=tree_size;
                                        min_index_opt=i;
				}			
			//Part II, find min optsize by considering the influence of a var
         		//if the above part I and part II give two different answer, there is a conter example found.
                 }
		//send the results to storage
                int count=0;
		for(i=0;i<nv;i++)
//                   cout<<"index_opt is"<<i<<index_opt[i]<<"\n";
		{    //printf("index_opt[%d] w/influ.of(%d) is %d \n",i,mntnf[k],index_opt[i]);
                     if(index_opt[i] < nv && min_index_opt == index_opt[i]) count=1;
		}
		     if(count == 0)	 
                       {	
//			cout<<"\n**********mntnf["<<k<<"] "<<mntnf[k]<<"\n";
			printf("\n**********mntnf[%d] is %d\n ",k,mntnf[k]);
//			cout<<" nv is "<<nv<<"\n";
			printf(" nv is %d\n",nv);
//			cout<<"the counter example is found now\n"
			printf("the counter example is found now\n");
//			cout<<"the optimal root w/o influence(min_index_opt) is "<<min_index_opt<<"\n";
			printf("the optimal root w/o influence(min_index_opt) is%d\n ",min_index_opt);
//			cout<<"the true min is "<<min<<"\n";
			printf("the true min is %d\n ",min);
                        break;
                        }
		optsz[k]=min;
	}
	delete [] index_opt;
}

int main(int argv, char *argc[])
{
	int i=0,cnt;
	unsigned long monotf; //the monotone function f
	int opts; //the optsize of the fuction f
	unsigned long * mntnf4= new (unsigned long [N_4]); 
	if(mntnf4==NULL) nrerror("some thing is wrong with the allocation of mntnf4\n");
	int * optsz4= new (int [N_4]);
	if(optsz4==NULL) nrerror("some thing is wrong with the allocation of optsz4\n");
	unsigned long * mntnf5= new (unsigned long [N_5]); 
	if(mntnf5==NULL) nrerror("some thing is wrong with the allocation of mntnf5\n");
	int * optsz5= new (int [N_5]);
	if(optsz5==NULL) nrerror("some thing is wrong with the allocation of optsz5\n");
	unsigned long * mntnf6= new (unsigned long [N_6]); 
	if(mntnf6==NULL) nrerror("some thing is wrong with the allocation of mntnf6\n");
	int * optsz6= new (int [N_6]);
	if(optsz6==NULL) nrerror("some thing is wrong with the allocation of optsz6\n");
	
	unsigned long mntnf[N_3];  int optsz[N_3];
	if(argv<2)
	{
	  printf("syntax: <inf_cal.out> <txt file> \n");
	  exit(0);
	}
	//the following reads a  3 variable monotone function from a file and
	//stores in an array
        ifstream fin;
	fin.open(argc[1],ifstream::in);
	while(!fin.eof())
	{
		fin >>monotf>>opts; 
		mntnf[i]=monotf;
		optsz[i]=opts;
		i++;
		if(i>=20) break;
	}
	fin.close(); //finishing reading the  file

	//construct the 4 var monotone function and calculate the opt size
	for(i=0;i<N_4;i++){
		optsz4[i]=0;
	}
        cnt=gen_mnt(mntnf,mntnf4,N_3,N_4,SFT3); 

	//after successfully generate the monotone function of 4 vars
	//lets calculate the optimal size for each function
	opt_size_cal(mntnf,mntnf4,optsz,optsz4,N_3,N_4,4);

	
	
	//construct the 5 var monotone function and calculate the opt size
	for(i=0;i<N_5;i++){
		optsz5[i]=0;
	}
        cnt=gen_mnt(mntnf4,mntnf5,N_4,N_5,SFT4); 

	//after successfully generate the monotone function of 5 vars
	//lets calculate the optimal size for each function
	opt_size_cal(mntnf4,mntnf5,optsz4,optsz5,N_4,N_5,5);
	
	//construct the 6 var monotone function and calculate the opt size
	for(i=0;i<N_6;i++){
		optsz6[i]=0;
	}
        cnt=gen_mnt(mntnf5,mntnf6,N_5,N_6,SFT5); 

	//after successfully generate the monotone function of 6 vars
	//lets calculate the optimal size for each function
	opt_size_cal(mntnf5,mntnf6,optsz5,optsz6,N_5,N_6,6);

	//clean the space
        delete [] mntnf4;
	delete [] optsz4;

        delete [] mntnf5;
	delete [] optsz5;

        delete [] mntnf6;
	delete [] optsz6;

	return 0;
}