/* the american flag sort from Computing Systems vol 6, no 1, Winter 1993 */
/* modified by tridge October 1995 to move elements directly instead
   of using pointers to strings, and to use fixed record lengths, with
   nulls not considered special 

   This results in a N bit inplace integer sorting routine which works
   well for a wide range of values of N
 */

#include <stdlib.h>
#include "element.h"

enum {SIZE = 512, THRESHOLD = 16};

typedef struct {element *sa; int sn,si;} stack_t;
void simplesort(element *,int,int);

static int comp(element *s1,element *s2,int b)
{
  int d;
  do {
    if ((d=s1->c[b] - s2->c[b])) return(d);
  } while (++b<ELSIZE);
  return(0);
}


/* a simple insertion sort */
static void insertionsort(element *base,int n,int b)
{
  element t;
  element *lo,*max,*x;

  for (max = base + n - 1;base < max;base++) 
    {      
      for (lo = x = base;x++ < max;) 
	if (comp(lo,x,b)>0) lo = x;

      if (lo != base) {
	for (t = *lo; lo > base;lo--) *lo = *(lo-1);
	*base = t;
      }
    }
}


static void rsorta(element *a,int n,int b)
{
#define push(a,n,i) sp->sa = a, sp->sn = n, (sp++)->si = i
#define pop(a,n,i) a = (--sp)->sa, n = sp->sn, i = sp->si
#define stackempty() (sp <= stack)
#define swap(p,q,r) r = p, p = q, q = r
  stack_t stack[SIZE], *sp = stack, stmp, *oldsp, *bigsp;
  element *pile[256], *ak, *an, r, t;
  static int count[256], cmin, nc=0;
  int *cp, c, cmax;

  if (nc == 0)
    bzero(count,sizeof(count[0])*256);

  push(a,n,b);

  while (!stackempty()) {
    pop(a,n,b);
    if (n < THRESHOLD) {
      insertionsort(a,n,b);
      continue;
    }

    an = a + n;
    if (nc == 0) {
      cmin = 255;
      for (ak=a;ak<an;) {
	c = (*ak++).c[b];
	if (++count[c] == 1) {
	  if (c < cmin) cmin = c;
	  nc++;
	}
      }
      if (sp+nc > stack+SIZE) {
	rsorta(a,n,b);
	continue;
      }
    }
    oldsp = bigsp = sp, c = 2;
    cmax = 0; ak = a;
    for (cp= count+cmin;nc>0; cp++, nc--) {
      while (*cp == 0) cp++;
      if (*cp > 1 && (b<(ELSIZE-1))) {
	if (*cp > c) c = *cp, bigsp = sp;
	push(ak, *cp, b+1);
      }
      pile[cmax = cp - count] = ak += *cp;
    }
    swap(*oldsp, *bigsp, stmp);
    an -= count[cmax];
    count[cmax] = 0;
    for (ak = a; ak < an; ak += count[c], count[c] = 0) {
      r = *ak;
      while (--pile[c = r.c[b]] > ak)
	swap(*pile[c], r, t);
      *ak = r;
    }
  }
}

void rsort(element *a, int n) 
{
  rsorta(a,n,0);
}