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

#define TRUE 1 /* "RobboLito.h" */
#define MIN(x, y) ((x) <= (y) ? (x) : (y))
#define MAX(x, y) ((x) >= (y) ? (x) : (y))
#define uint8 unsigned char

#define AuxArrVal(x) (AUX[(IDX[x] + h >= N) ? (IDX[x] + h - N) : (IDX[x] + h)])
#define SwapIdxVal(p, q) { int _x; _x = IDX[p]; IDX[p] = IDX[q]; IDX[q] = _x; }
#define Median3(a, b, c) \
  (AuxArrVal(a) < AuxArrVal(b) ? \
   (AuxArrVal(b) < AuxArrVal(c) ? (b) : \
    AuxArrVal(c) < AuxArrVal(a) ? (a) : (c)) : \
   (AuxArrVal(b) > AuxArrVal(c) ? (b) : \
    AuxArrVal(c) > AuxArrVal(a) ? (a) : (c)))

static void SamePacket(int* IDX, int* AUX, int lo, int hi)
{
  AUX[IDX[lo]] = hi;
  if (lo == hi)
    IDX[lo] = -1; /* negate for packet */
  else
    {
      while (lo < hi)
	AUX[IDX[++lo]] = hi;
    }
}

#define SELECT_LIMIT (9)
#define SMALL_ARRAY_SIZE (9)
#define LARGE_ARRAY_SIZE (81)

static void SelectionSorter(int* IDX, int* AUX, int N, int h, int lo, int hi)
{
  int s, small, val, pack_sz;
  while (lo < hi)
    {
      pack_sz = 1;
      s = lo + pack_sz; /* sentinel */
      small = AuxArrVal (lo);
      while (s <= hi) /* loop */
	{
	  val = AuxArrVal (s);
	  if (val == small)
	    {
	      SwapIdxVal (s, lo + pack_sz); /* pack in loc 0 */
	      pack_sz++;
	    }
	  if (val < small)
	    {
	      small = val;
	      SwapIdxVal (lo, s); /* new small */
	      pack_sz = 1;
	    }
	  s++;
	}
      SamePacket (IDX, AUX, lo, lo + pack_sz - 1); /* packet */
      lo = lo + pack_sz;
    }
  if (lo == hi) /* terminal packet */
    {
      AUX[IDX[lo]] = lo;
      IDX[lo] = -1; /* negate for packet */
    }
}

static int PivotSelectionValue (int* IDX, int* AUX, int N, int h, int w, int sz)
{
  int med;
  if (sz < SMALL_ARRAY_SIZE) /* HACK */
    med = w + (sz / 2);
  else if (sz < LARGE_ARRAY_SIZE)
    med = Median3 (w, w + sz / 2, w + sz - 1);
  else
    {
      int lo, mid, hi, sh, m1, m2, m3;
      lo = w;
      mid = w + (sz / 2);
      hi = w + sz - 1;
      sh = sz / 8;
      m1 = Median3 (lo, lo + sh, lo + 2 * sh);
      m2 = Median3 (mid - sh, mid, mid + sh);
      m3 = Median3 (hi - 2 * sh, hi - sh, hi);
      med = Median3 (m1, m2, m3);
    }
  return AuxArrVal(med);
}

static void MainSorter(int* IDX, int* AUX, int N, int h, int LO, int HI)
{
  int lo, slo, hi, shi, piv, val, s, q;
  if ((HI - LO + 1) < SELECT_LIMIT)
    {
      SelectionSorter (IDX, AUX, N, h, LO, HI);
      return;
    }
   piv = PivotSelectionValue (IDX, AUX, N, h, LO, HI - LO + 1);
   lo = LO;
   hi = HI;
   slo = lo; /* sentinels */
   shi = hi;
   while (TRUE)
     {
       while (slo <= shi && (val = AuxArrVal (slo)) <= piv)
	 {
	   if (val == piv)
	     {
	       SwapIdxVal(lo, slo); /* pack to front */
	       lo++;
	     }
	   slo++;
	 }
       while (shi >= slo && (val = AuxArrVal (shi)) >= piv) /* obverse */
	 {
	   if (val == piv)
	     {
	       SwapIdxVal(hi, shi); /* pack in rearguard */
	       hi--;
	     }
	   shi--;
	 }
      if (slo > shi)
         break;
      SwapIdxVal(slo, shi);
      slo++;
      shi--;
   }
   s = MIN (lo - LO, slo - lo);
   for (q = 0; q < s; q++)
     SwapIdxVal (LO + q, slo - s + q);
   s = MIN (HI - hi, hi - shi);
   for (q = 0; q < s; q++)
     SwapIdxVal (slo + q, HI + 1 - s + q);
   if (slo > lo)
     MainSorter(IDX, AUX, N, h, LO, LO - 1 + slo - lo);
   SamePacket(IDX, AUX, LO + slo - lo, HI - (hi - shi));
   if (hi > shi)
     MainSorter(IDX, AUX, N, h, HI + 1 - (hi - shi), HI);
}

void SuffixSort(int* IDX, int* AUX, int N)
{
  int w, ind, sort_run, h = 1;
  MainSorter (IDX, AUX, N, 0, 0, N - 1);
  while (IDX[0] > -N)
    {
      w = 0;
      sort_run = 0;
      while (w < N)
	{
	  ind = IDX[w];
	  if (ind < 0)
	    {
	      w += -ind;
	      sort_run += -ind;
	    }
	  else
	    {
	      if (sort_run)
		{
		  IDX[w - sort_run] = -sort_run; /* negate for packet */
		  sort_run = 0;
		}
	      MainSorter (IDX, AUX, N, h, w, AUX[ind]);
	      w = AUX[ind] + 1;
	    }
	}
      if (sort_run)
	IDX[w - sort_run] = -sort_run;
      h <<= 1; /* double */
   }
}

void Suffix_fare (uint8* DATA, int* IDX, int N)
{
  int* AUX;
  int i;
  AUX = malloc (N * sizeof (int));
  for (i = 0; i < N; i++)
    {
      AUX[i] = DATA[i]; /* copy */
      IDX[i] = i; /* iniz */
    }
  SuffixSort (IDX, AUX, N);
  for (i = 0; i < N; i++)
    IDX[AUX[i]] = i;
  free (AUX);
}
