--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/anagram/agcore/binsort.cpp	Sat Dec 22 17:52:45 2007 -0500
@@ -0,0 +1,143 @@
+/*
+ * 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 */