#include <stdlib.h>
#include <stdio.h>
#include <errno.h>

#define TRUE  1
#define FALSE 0
#define MXFS 100
#define N    6
#define MAXR 20
/* #define DEBUG */
/* #define PRINTF(x) printf("%s\n",x) */
#define PRINTF(x)

/*extern int getopt(int argc, char **argv, char *optstring);*/
extern char *optarg;
extern int optind, opterr;

char *errmsg=
"usage: usage-sort [-n <count>] [-s <seed>] [-hv] [-p<perm> [-d<step>]]\n";
int verbose=0;

int count=1000;
int seed=1;
int preset=0;
char presetstr[N];
int preb[N];
int liveness=0;
int bitmap[N];


void my_random()
{
  srand(1000);
}

int irnd(int a,int b)
{
  int i, my_range=b-a+1, j;
  i = 0x1fffffff / my_range;
  i *= my_range;
  while ((j = rand()) >= i) continue;
/*  printf("i=%d,j=%d,my_range=%d\n",i,j,my_range); */
  return (j % my_range)+a;
}

int b[N];
int cc, minc, maxc;
inline void move(int from, int to)
{
  int j,f, *p, *q;
  q=&(b[to]);p=&(b[from]);f=*p;
  if (from>to)
    for(;q!=p;p--) *p = *(p-1);
  else if (from<to)
    for(;q!=p;p++) *p = *(p+1);
  *q=f;
}
inline void movea(int a[],int from, int to)
{
  int j,f, *p, *q;
  q=&(a[to]);p=&(a[from]);f=*p;
  if (from>to)
    for(;q!=p;p--) *p = *(p-1);
  else if (from<to)
    for(;q!=p;p++) *p = *(p+1);
  *q=f;
}

inline int sorted()
{
  int *p;
  for(p=b;p!=(b+N-1);p++)
    if (*p>*(p+1)) return FALSE;
  return TRUE;
}

void initbooks()
{
  int a,i,j;
  if (preset) {
    for(i=0;i<N;i++) b[i]=preb[i];
  }
  else {
    for(i=0;i<N;i++) b[i]=i;
    for(i=0;i<N-1;i++) {
      j=irnd(i,N-1);
      a=b[j];b[j]=b[i];b[i]=a;
    }
  }
  cc=0;minc=100;maxc=0;
}
  

  void dostat(int c)
{
  cc+=c;if (c<minc) minc=c;
  if (c>maxc) maxc=c;
}

void prarrp(int a[])
{
  int i;
  printf("[");
  for(i=0;i<N;i++) printf("%d ",a[i]);
  printf("]");
}

void prarr()
{
  int i;
  printf("[");
  for(i=0;i<N;i++) printf("%d ",b[i]);
  printf("]");
}

void verbosecheck(int i)
{
  if (verbose) {
    printf("%d ",i);
    prarr();printf("\n");
  }
}

int longestSubsequence(int start,int ss[],int out, int last)
{
  int i,j, cur, l;

  if (start==N || start==N-1 && last==N-1) return 0;
  
  cur= -1;
  for(i=start;i<N;i++)
    if (i != out) {
      if (b[i]>last) {
	ss[i]=1;
	l=longestSubsequence(i+1,ss,out,b[i]);
	if (l>cur) {j=i;cur=l;}
	ss[i]=0;
      }
    }
  if (cur>-1) {
    ss[j]=1;longestSubsequence(j+1,ss,out,b[j]);return 1+cur;
  }
  else {return 0;}
}

int inversions(int d[])
{
  int a[N],i,j,k=0, s;
  for(i=0;i<N;i++) a[i]=d[i];
  for(i=N-1;i>0;i--) {
    for(j=0;j<i;j++) {
      if (a[j]>a[j+1]) {
	s=a[j];a[j]=a[j+1];a[j+1]=s;k++;/*prarrp(a);*/
      }
    }
  }
  return k;
}

const char s1[] = "Place the book at its position";
void sort1()
{
  int i,c=0;
  while (! sorted()) {
    i=irnd(0,N-1);
    move(i,b[i]);
    verbosecheck(i);
    c++;
  }
  dostat(c);
}

const char s2[] = "Longest subsequence";
void sort2()
{
  int ss[N],i,j,c=0;

  while (!sorted()) {
    for(i=0;i<N;i++) ss[i]=0;
    i=irnd(0,N-1);
    longestSubsequence(0,ss,i,-1);
    for(j=0;j<N;j++)
      if(ss[j] && b[i]<b[j]) break;
    if (i>j) move(i,j);
    else move(i,j-1);
    verbosecheck(i);
    c++;
  }
  dostat(c);
}

const char s3[] = "Maximize correct numbers";
void sort3()
{
  int i,j,k,s,l,s1,c=0;

  while (!sorted()) {
    i=irnd(0,N-1);
    s=N-1-i;k=0;l=0;s1=s;
    for(j=0;j<N;j++)
      if (j!=i) {
	l++;
	if (b[j]<b[i]) s++;
	else s--;
	if (s>s1) {
	  s1=s;k=l;
	}
      }
    move(i,k);
    verbosecheck(i);
    c++;
  }
  dostat(c);
}

const char s4[]="Minimize inversions";
void sort4()
{
  int i,j,k,s,s1,c=0,a[N],l;
   while (!sorted()) {
    i=irnd(0,N-1);
    s=100;
    for(j=0;j<N;j++) {
      for (k=0;k<N;k++) a[k]=b[k];
      movea(a,i,j);
      s1=inversions(a);
      if (s1<s) {
	s=s1;l=j;
      }
    }
    move(i,l);
    verbosecheck(i);
    c++;
  }
  dostat(c);
}

const char s5[]="Move due left of next number";
void sort5()
{
  int i,j,k,s,s1,c=0,a[N],l;
   while (!sorted()) {
    i=irnd(0,N-1);
    if (b[i]==N-1) l=N-1;
    else {
      l=0;
      for(j=0;j<N-1;j++)
	if (j!=i) {
	  if (b[i]+1==b[j]) break;
	  l++;
	}
    }
      
    move(i,l);
    verbosecheck(i);
    c++;
  }
  dostat(c);
}

 

void   ( (*sortarr[])() )  = {sort1,sort2,sort3,sort4,sort5,NULL};
		    
const char *sat[]  = {&s1[0],&s2[0],&s3[0],&s4[0],&s5[0],NULL};

void setpreset()
{
  int i;

  if (preset)
    for(i=0;i<N;i++)
      preb[i]=presetstr[i]-'0';
}

void update_bitmap(char *s)
{
  int i;
  for(i=0;i<N;i++) bitmap[i]=0;
  while (*s) {
    i=*s-'0';
    if (i>=0 &&i<N) bitmap[i]=1;
    s++;
  }
}
    

void PrintHelp()
{
   int i;

   
   printf("\nusage-sort [options] \n\n");
   printf("Options: h       : display this message.\n");
   printf("         n<count>: number of times to run, default: %d.\n",
                              count);
   printf("         v       : verbose (sideeffect: count=1)\n");
   printf("         s<seed> : integer random seed, default:%d\n",seed);
   printf("         p<perm> : initial permutation, default is random\n");
   printf("         d<step> : print liveness information\n");
   printf("         b<seq>  : which algorithms to include\n\n");

   printf("Possible algorthms\n");
   for (i=0;sat[i]!=NULL;i++) {
     printf("%2d %s\n",i,sat[i]);
   }
 }

int GetOptions(int argc, char *argv[])
{
   int c, *cp;
   int i, errflg=0;
 
   opterr=0;

   while ((c=getopt(argc,argv,"n:s:vhp:d:b:")) != -1) 
      switch (c) {
      case 'v': 
         verbose++;
	 count=1;
         break;
       case 'h':
         PrintHelp();
         exit(0);
         break;
       case 'n':
         count=atoi(optarg);
         break;
       case 's':
         seed=atoi(optarg);
         break;
      case 'p':
	strncpy(presetstr,optarg,N);
	preset++;
	break;
      case 'd':
	liveness=atoi(optarg);
	break;
      case 'b':
	update_bitmap(optarg);
	break;
       case '?':
         errflg++;
       }
   if (errflg) {
      (void) fprintf(stderr, errmsg);
      exit(2);
    }

   return 0;   

}

void main(int argc, char *argv[])
{
  int j, i, from, to, bigcc[MAXR], high[MAXR], low[MAXR], saveseed;
  float av;
  int ss[N];
  void (*sap)() ;

  for(i=0;i<N;i++) bitmap[i]=1;
  GetOptions(argc,argv);
  setpreset();
  srand(seed);

/*   initbooks();prarr(); */
/*   printf("Inversions: %d\n",inversions(b));cc=0; */
  /*  sort2();prarr();printf(" runder: %d\n",cc);*/
  /*  return;*/


/*   initbooks();for(i=0;i<N;i++) ss[i]=0; */
/*   j=longestSubsequence(0,ss,atoi(argv[optind]),-1); */
/*   prarr();for(i=0;i<N;i++) printf(" %d",ss[i]); */
/*   printf(", lengde=%d\n",j); */
/*   return; */
  
   for(j=0;sat[j]!=NULL;j++) {
     bigcc[j]=0;high[j]=0;low[j]=1000;
   }
   for(i=0;i<count;i++) {
     saveseed=rand();
     for(j=0;sat[j]!=NULL;j++)
       if (bitmap[j]) {
	 srand(saveseed);
	 initbooks();
	 if (verbose) {
	   printf("\n%s\n",sat[j]);
	   prarr();
	   printf("\n");
	 }
	 (*(sortarr[j]))();
	 bigcc[j]+=cc;
	 if(high[j]<maxc) high[j]=maxc;
	 if(low[j]>minc) low[j]=minc;
	 if (verbose) {printf("Count=%d\n",cc); }
       }
     if (liveness && ((i % liveness) == 0)) {
       printf("%10d\r",i);
       fflush(stdout);
     }
     
   }
   
   printf("   Algorithm                                 count   mean max min\n");
   for(j=0;sat[j]!=NULL;j++)
     if (bitmap[j]) {
     av=(float) bigcc[j] / (float) count;
     printf("%2d %-40s %6d %6.2f %3d %3d\n",j,sat[j],bigcc[j],av,high[j],low[j]);
   }
   printf("\nEach algorithm has sorted the same %d sequences.\n",count);
   if (preset) printf("The random sequence was preset to %s.\n",presetstr);

   
/*    for(i=0;i<N;i++) b[i]=i; */
/*    from=atoi(argv[optind]); */
/*    to=atoi(argv[optind+1]); */
/*    move(from,to); */

/*    printf("Move fra %d til %d: ",from,to); */
/*    for(i=0;i<N;i++) printf("%d ",b[i]); */
/*    printf(", sortert: %d\n",sorted()); */

}