/*
 * AnaGram, A System for Syntax Directed Programming
 * Copyright 1993-1999 Parsifal Software. All Rights Reserved.
 * See the file COPYING for license and usage terms.
 *
 * binsort.cpp - Bin sort module (also known as radix sort)
 */

#include <string.h>
#include "port.h"

#include "binsort.h"
#include "minmax.h"
#include "myalloc.h"
#include "tsd.h"


static long *bin_sort_tuples(
  unsigned char *ss,
  unsigned w,
  long *x,
  unsigned nt,
  unsigned *cp
) {
  unsigned bin_tail[256];
  unsigned bin_a[256];
  unsigned bin_b[256];
  unsigned *bins[2];
  unsigned *new_bin_head;
  unsigned *old_bin_head;
  int m;
  unsigned i,j,k;
  unsigned bin,old_bin;
  unsigned *link;
  long *y, *yp;
  unsigned char *sp;

  yp = y = ALLOCATE(nt, long);
  ALLOCATE_ST(link, nt);
  //link = ALLOCATE(nt, unsigned);
  bins[0] = bin_a;
  bins[1] = bin_b;
  m = 0;
  new_bin_head = bins[m];
  m ^= 1;
  memset(new_bin_head, 0xff, 256*sizeof(*new_bin_head));
  memset(bin_tail, 0xff, 256*sizeof(*bin_tail));
  sp = ss + *cp++;
  for (i = 0; i<nt; i++) {
    bin = sp[(int) x[i]];
    if ((k = bin_tail[bin]) == (unsigned) -1) {
      new_bin_head[bin] = i;
    }
    else {
      link[k] = i;
    }
    bin_tail[bin] = i;
    link[i] = (unsigned) -1;
  }
  while (--w) {
    sp = ss + *cp++;
    old_bin_head = new_bin_head;
    new_bin_head = bins[m];
    m ^= 1;
    memset(new_bin_head, 0xff, 256*sizeof(*new_bin_head));
    memset(bin_tail, 0xff, 256*sizeof(*bin_tail));
    for (old_bin = 0; old_bin < 256; old_bin++) {
      j = old_bin_head[old_bin];
      while (j != (unsigned) -1) {
        j = link[i=j];
	bin = sp[(int) x[i]];
        if ((k = bin_tail[bin]) == (unsigned) -1){
          new_bin_head[bin] = i;
        }
        else {
          link[k] = i;
        }
        bin_tail[bin] = i;
        link[i] = (unsigned) -1;
      }
    }
  }
  for (i = 256; i-- > 0;) {
    j = *new_bin_head++;
    while (j != (unsigned) -1){
      *yp++ = j;
      j = link[j];
    }
  }
  DEALLOCATE(link);
  return y;
}

void sort_tuples(tsd *ts, unsigned nc) {
  long *x,p, *y;
  unsigned nt;
  unsigned i,j;
  unsigned wb,sw;
  unsigned char *data, *newdata;
  unsigned tw;
  unsigned pv[100];

  ok_ptr(ts);
  nt = ts->nt;
  tw = ts->tw;
  if (nt == 0 || nc == 0 || tw == 0) {
    return;
  }
  p = 0;
  i = min(nc,tw);
  sw = i*sizeof(*ts->sb);
  wb = tw * sizeof(*ts->sb);
  j = 0;
  while (i--) {
    unsigned k;
    for (k = 0; k < sizeof(*ts->sb); k++) {
      pv[j++] = i*sizeof(*ts->sb) + k;
    }
  }

  ALLOCATE_ST(x, nt);
/*  x = allocate(nt, long); */
  for (i = 0; i< nt; i++) {
    x[i] = p;
    p += wb;
  }
  data = (unsigned char *) ts->sb;
  y = bin_sort_tuples(data, sw, x, nt,pv);
  newdata = (unsigned char *)(ALLOCATE_ST(ts->sb, nt * tw));
/*
  ts->sb = allocate(nt*tw, int);
  newdata = (unsigned char *) ts->sb;
*/
  ts->na = nt;
  for (i = 0; i < nt; i++) {
    memmove(newdata + (int) x[i], data + (int) x[(int) y[i]], wb);
  }
  DEALLOCATE(x);
  DEALLOCATE(data);
  DEALLOCATE(y);
}

/* End BINSORT.C */