/*Prog2 CSE5311
Name: Anan Tongprasith
compile: cc prog2.c
inputfile: randomnumber
random number generator: random.c
usage: a.out
limitation: 8750 input max please

Make sure "randomnumber" file exists when running the program
*/

#include <stdio.h>
#include <sys/timers.h>

void myread();
int bruteforce(int x[],int y[],int xsize,int ysize,int result[],int resultsize);
int strictlyinc(int x[],int size);
int comp(int *a,int *b);
int LCSLength(int x[],int y[],int maxsize,int bsize,int *result);
int memoizing(int x[],int y[],int maxsize,int bsize,int *result);
int LookupArray(int x[],int y[], int **c,int i,int j);

void main()
{  int *a,*b;		// original and sorted array
   int maxsize,i,bsize,choice;
   int *result,resultsize;
   struct timespec tp1,tp2;
   double timeuse;

///////////// Reading input
   printf("\nHow many input do you want to read ?:");
   scanf("%d",&maxsize);
   if(maxsize>8750)
   {maxsize=8750;printf("\nLimit maximum to 8750.\n");
   }
   printf("\nReading from randomnumber file...\n\n");

   a=(int *)malloc(sizeof(int)*maxsize);
   myread(a,maxsize); 

//////////// Select calculation technique
   printf("Available algorithm:\n");
   printf("1) BruteForce\n");
   printf("2) Bottom-up Dynamic Programming\n");
   printf("3) Memoizing Dynamic Programming\n");
   printf("Select you choice(1,2,3):");
   scanf("%d",&choice);

   getclock(TIMEOFDAY,&tp1);               /* start timing */
   if(choice==1)
   {
//////////// Calling Bruteforce
   	resultsize=0;
   	result=(int *)malloc(sizeof(int)*maxsize);
   	resultsize=bruteforce(a,b,maxsize,0,result,resultsize);
   	printf("Bruteforce found longest sequence size to be %d.\n",resultsize);
   	printf("The sequence is:\n");
   	for(i=0;i<resultsize;i++)
        	printf("%d ",result[i]);
   	printf("\n");
   	free(result);
   }
   if(choice==2)
   {
//////////// Calling Bottom-up dynamic programming
   	resultsize=0;
	//// Create a second array (sorted and no redundant value)
   	b=(int *)malloc(sizeof(int)*maxsize);
   	for(i=0;i<maxsize;i++)
           b[i]=a[i];
   	qsort(b,maxsize,sizeof(i), &comp);   // sort
   	bsize=1;
   	for(i=1;i<maxsize;i++)               // eliminate redundancy
   	{  if(b[i]!=b[i-1])
           {	b[bsize]=b[i];
           	bsize++;
           }
   	}

   	result=(int *)malloc(sizeof(int)*bsize);
   	resultsize=LCSLength(a,b,maxsize,bsize,result); 

   	printf("Bottomup DP found longest sequence size to be %d.\n",resultsize);
   	printf("The sequence is:\n");
   	for(i=resultsize-1;i>=0;i--)
           printf("%d ",result[i]);
   	printf("\n");
   	free(b);
   	free(result);
   }
   if(choice==3)
   {
//////////// Memoizing
	resultsize=0;
       	//// Create a second array (sorted and no redundant value)
   	b=(int *)malloc(sizeof(int)*maxsize);
   	for(i=0;i<maxsize;i++)
           b[i]=a[i];
   	qsort(b,maxsize,sizeof(i), &comp);   // sort
   	bsize=1;
   	for(i=1;i<maxsize;i++)               // eliminate redundancy
   	{  if(b[i]!=b[i-1])
           {	b[bsize]=b[i];
          	bsize++;
           }
   	}

   	result=(int *)malloc(sizeof(int)*bsize);
   	resultsize=memoizing(a,b,maxsize,bsize,result);

   	printf("Memoizing DP found longest sequence size to be %d.\n",resultsize);
   	printf("The sequence is:\n");
   	for(i=resultsize-1;i>=0;i--)
           printf("%d ",result[i]);
   	printf("\n");
   	free(b);
   	free(result);
   }
   getclock(TIMEOFDAY,&tp2);               /* stop timing */
///////////////////////
   free(a);
   timeuse=(tp2.tv_sec - tp1.tv_sec)*1000000000 + (tp2.tv_nsec - tp1.tv_nsec);
   printf("Time used is %2.4f milliseconds.\n",timeuse/1000000);
}

void myread(int *a,int maxsize)
{ int i,buf;FILE *fp;

   fp=fopen("randomnumber","r");

   for(i=0;i<maxsize;i++)
   {
	fscanf(fp,"%d\n",&buf);
	a[i]=buf;
   }
   fclose(fp);
}

/////////// brute force

int bruteforce(int x[],int y[],int xsize,int ysize,int result[],int resultsize)
{  int *u,*v;
   int i;

   if(xsize==0)
   {
	if(ysize>resultsize)	// check if it is longer than current result
	{
 	   if(strictlyinc(y,ysize))	// check if it is strictly increasing 
	   {
		resultsize=ysize;
		for(i=0;i<ysize;i++)
		   result[i]=y[i];
	   }
	}
   }
   else
   {
   	u=(int *)malloc(sizeof(int)*(xsize-1));
	for(i=1;i<xsize;i++)
	   u[i-1]=x[i];		//extract first item out of x
	v=(int *)malloc(sizeof(int)*(ysize+1));
	
	for(i=0;i<ysize;i++)		//attach that item to v
	   v[i]=y[i];
	v[ysize]=x[0];	

	resultsize=bruteforce(u,y,xsize-1,ysize,result,resultsize);
	resultsize=bruteforce(u,v,xsize-1,ysize+1,result,resultsize);	
	free(u);
	free(v);
   }
   return resultsize;
}
/////////// check if an array is strictly increasing or not
int strictlyinc(int x[],int size)
{  
   int i;

   if(size==0)
	return 0;
   for(i=1;i<size;i++)
   {
	if(x[i]<x[i-1]||x[i]==x[i-1])
	   return 0;
   }
   return 1;
}

//////////////// Comparison function for qsort

int comp(int *a,int *b)
{ int x;
        if(*a<*b)
                return -1;
        if(*a==*b)
                return 0;
        else
                return 1;
}

/////////////// Bottomup LCS

int LCSLength(int x[],int y[],int maxsize,int bsize,int *result)
{
   int **c,i,j,k;
   int isize=maxsize+1,jsize=bsize+1;

   c=(int **)malloc(sizeof(&i)*isize);  // allocate memory
   for(i=0;i<isize;i++)
        c[i]=(int *)malloc(sizeof(int)*jsize);

////////// empty first row and column (shift the array 1 block further)

   for(i=1;i<isize;i++)
        c[i][0]=0;
   for(j=0;j<jsize;j++)
        c[0][j]=0;

///////// create c array

   for(i=1;i<isize;i++)
   {
        for(j=1;j<jsize;j++)
        {
	   if(x[i-1]==y[j-1])           // we shifted the arrays 1 block
           {    c[i][j]=c[i-1][j-1]+1;
           }
           else
           {
                if(c[i-1][j]>=c[i][j-1])
                   c[i][j]=c[i-1][j];
                else
                   c[i][j]=c[i][j-1];
           }
        }
   }

/*
// show c array
   for(i=0;i<isize;i++)
   {    for(j=0;j<jsize;j++)
           printf("%d ",c[i][j]);
        printf("\n");
   }
*/

/////////////// now get answer from c array
   j=jsize-1;
   i=isize-1;
   k=0;
   while(c[i][j]>0)
   {    if(x[i-1]==y[j-1])      // don't forget! we shifted the arrays 1 block
        {
           result[k]=x[i-1];
           k=k+1;
           i=i-1;
           j=j-1;
        }
        else
        {  if(c[i-1][j]>=c[i][j-1])
                i=i-1;
           else
                j=j-1;
        }
   }
   for(i=0;i<isize;i++)         // free memory
        free(c[i]);
   free(c);
   return k;			// resultsize = k
}
		
/////////////////// Memoizing
int memoizing(int x[],int y[],int maxsize,int bsize,int *result)
{  int **c,i,j,k;
   int isize=maxsize+1,jsize=bsize+1;

   c=(int **)malloc(sizeof(&i)*isize);  // allocate memory
   for(i=0;i<isize;i++)
        c[i]=(int *)malloc(sizeof(int)*jsize);

///////// setup c[][] to negative value which indicates untouch

   for(i=1;i<isize;i++)
        for(j=1;j<jsize;j++)
                c[i][j]=-1;

////////// empty first row and column (shift the array 1 block further)

   for(i=1;i<isize;i++)
        c[i][0]=0;
   for(j=0;j<jsize;j++)
        c[0][j]=0;

///////// call recursive lookup
   LookupArray(x,y,c,isize-1,jsize-1);

/////////////// now get answer from c array
   j=jsize-1;
   i=isize-1;
   k=0;
   while(c[i][j]>0)
   {    if(x[i-1]==y[j-1])      // don't forget! we shifted the arrays 1 block
        {
           result[k]=x[i-1];
           k=k+1;
           i=i-1;
           j=j-1;
        }
        else
        {  if(c[i-1][j]>=c[i][j-1])
                i=i-1;
           else
                j=j-1;
        }
   }
   return k;
}
///////// lookup recursive
int LookupArray(int x[],int y[], int **c,int i,int j)
{
   if(c[i][j]>=0)
	return c[i][j];
   else
   {
	if(x[i-1]==y[j-1])
	   c[i][j]=1+LookupArray(x,y,c,i-1,j-1);
	else
	{  if(LookupArray(x,y,c,i-1,j)>=LookupArray(x,y,c,i,j-1))
		c[i][j]=c[i-1][j];
	   else
		c[i][j]=c[i][j-1];
	}
   }
   return c[i][j];
}