// Comparison of sorting techniques to produce suffix array
// Uses less space that lab2.2.c for radixsort

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <sys/time.h>
#include <sys/resource.h>

double CPUtime()
{
  struct rusage rusage;
  getrusage(RUSAGE_SELF,&rusage);
  return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
    + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

void shellsort(char **a,int N)
{
int group;
int i,j,h,hWork;
char *v;
for (h=1;
     (hWork=3*h+1)<N;
     h=hWork)
  ;

for ( ;h>0;h/=3)
{
  for (group=0; group<h; group++)
     for (i=group+h; i<N; i+=h)
     {
       v=a[i];
       j=i;
       //while (j>=h && a[j-h]>v)
       while (j>=h && strcmp(a[j-h],v)>0)
       {
         a[j]=a[j-h];
         j -= h;
       }
       a[j]=v;
     }
}
}

int pstrcmp(const void* p, const void* q)
{   return strcmp(*((char**) p), *((char**) q)); }

#define MAXN 10000000
char c[MAXN], *a[MAXN];
int n=0;

int msd1[500000]; // Input to start of radix pass
int msd2[500000],pos2[500000]; // From LSD subpass
int msd3[500000],pos3[500000]; // from MSD subpass
int count[500000];

#define lsd1(j) ((j)>=n-i ? 0 : msd1[(j)+i])
#define lsd2(j) (lsd1(pos2[j]))
#define lsd3(j) (lsd1(pos3[j]))

void radixsort(char **a,int n)
{
int i,j,k,lastMSD,lastLSD;
int radix=257;

if (n>radix)
  radix=n;

for (i=0;i<n;i++)
  msd1[i]=1 + (unsigned char) c[i];

for (i=1; ;i+=i)
{
  printf("radixsort i=%d\n",i);
  printf("POS                  MSD  LSD - start of pass\n");
  for (j=0;j<n;j++)
    printf("%3d %.15s %3d  %3d\n",j,&c[j],msd1[j],lsd1(j));
  // Counting sort on LSD
  for (j=0;j<radix;j++)
    count[j]=0;
  for (j=0;j<n;j++)
    count[lsd1(j)]++;
  for (j=1;j<radix;j++)
    count[j]+=count[j-1];
  for (j=n-1;j>=0;j--)
  {
    count[lsd1(j)]--;
    msd2[count[lsd1(j)]]=msd1[j];
    pos2[count[lsd1(j)]]=j;
  }
  // Counting sort on MSD
  for (j=0;j<radix;j++)
    count[j]=0;
  for (j=0;j<n;j++)
    count[msd2[j]]++;
  for (j=1;j<radix;j++)
    count[j]+=count[j-1];
  for (j=n-1;j>=0;j--)
  {
    count[msd2[j]]--;
    msd3[count[msd2[j]]]=msd2[j];
    pos3[count[msd2[j]]]=pos2[j];
  }
  printf("POS                  MSD  LSD - after radix sort\n");
  for (j=0;j<n;j++)
    printf("%3d %.15s %3d  %3d\n",pos3[j],&c[pos3[j]],msd3[j],lsd3(j));
  // Renumber MSD
  lastMSD=msd3[0];
  lastLSD=lsd3(0);
  k=0;
  for (j=0;j<n;j++)
  {
    if (lastMSD!=msd3[j] || lastLSD!=lsd3(j))
    {
      k++;
      lastMSD=msd3[j];
      lastLSD=lsd3(j);
    }
    msd3[j]=k;
  }
  printf("%d buckets\n",k+1);
  printf("POS                  MSD  LSD - after renumbering\n");
/*
  for (j=0;j<n;j++)
    printf("%3d %c %3d\n",pos3[j],c[pos3[j]],msd3[j]);
*/
  for (j=0;j<n;j++)
    printf("%3d %.15s %3d\n",pos3[j],&c[pos3[j]],msd3[j]);
  //if (msd3[n-1]==n-1)
  if (k+1==n)
    break;
  // Reorder by position
  for (j=0;j<n;j++)
    msd1[pos3[j]]=msd3[j];
}

for (i=0;i<n;i++)
  a[i]= &c[pos3[i]];
}

int main()
{   int i, j, ch, maxi, maxlen = -1;
    double startCPU;
    char filename[80];
    FILE* book;

    printf("Enter filename: ");
    fflush(stdout);
    scanf("%s",filename);
    book=fopen(filename,"r");
    while ((ch = getc(book)) != EOF && ch!=10 && ch!=11 && ch!=12) {
        a[n] = &c[n];
        c[n++] = ch;
    }
    c[n] = 0;
    a[n]=&c[n];
    n++;
    fclose(book);
    printf("File read %d symbols\n",n);

    startCPU=CPUtime();
    shellsort(a,n);
    printf("shellsort CPU %f\n",CPUtime()-startCPU);
    for (i=0;i<n;i+=500)
      printf("%d %.10s\n",i,a[i]);

    for (i=0;i<n;i++)
      a[i]= &c[i];

    startCPU=CPUtime();
    qsort((void*) a, n, sizeof(char *), pstrcmp);
    printf("qsort CPU %f\n",CPUtime()-startCPU);
    for (i=0;i<n;i+=500)
      printf("%d %.10s\n",i,a[i]);

    for (i=0;i<n;i++)
      a[i]= &c[i];

    startCPU=CPUtime();
    radixsort(a,n);
    printf("radix sort CPU %f\n",CPUtime()-startCPU);
    for (i=0;i<n;i+=500)
      printf("%d %.10s\n",i,a[i]);

    return 0;
}