Initial commit

1 files changed, 580 insertions, 0 deletions

diff --git a/nauty/sorttemplates.c b/nauty/sorttemplates.c
new file mode 100644
index 0000000..5f7e100
--- /dev/null
+++ b/nauty/sorttemplates.c
@@ -0,0 +1,580 @@
+/* sorttemplates.c version 2.0, Mar 13, 2018.
+ * Author: Brendan McKay; brendan.mckay@anu.edu.au
+ *
+ * This file contains templates for creating in-place sorting procedures
+ * for different data types.  It cannot be compiled separately but
+ * should be #included after defining a few preprocessor variables.
+ *   SORT_OF_SORT, SORT_NAME and SORT_TYPE1 are always required, and
+ *   SORT_TYPE2 is needed for SORT_OF_SORT = 3,
+ *   SORT_COMPARE is needed for SORT_OF_SORT = 4.
+ * 
+ *   SORT_OF_SORT = 1: Creates a procedure
+ *         static void SORT_NAME(SORT_TYPE1 *x, int n)
+ *     which permutes x[0..n-1] so that x[0] <= ... <= x[n-1].
+ *   SORT_OF_SORT = 2: Creates a procedure
+ *         static void SORT_NAME(SORT_TYPE1 *x, SORT_TYPE2 *y, int n)
+ *     which permutes x[0..n-1] so that x[0] <= ... <= x[n-1]
+ *     and also permutes y[0..n-1] by the same permutation.
+ *   SORT_OF_SORT = 3: Creates a procedure
+ *         static void SORT_NAME(SORT_TYPE1 *x, SORT_TYPE2 *y, int n)
+ *     which permutes x[0..n-1] so that y[x[0]] <= ... <= y[x[n-1]].
+ *   SORT_OF_SORT = 4: Creates a procedure
+ *         static void SORT_NAME(SORT_TYPE1 *x, int n)
+ *     which permutes x[0..n-1] so that
+ *     SORT_COMPARE(x[i],x[j]) <= 0 for i<j.
+ *   SORT_COMPARE(x,y) is an expression <0,0,>0 for x<y,x=y,x>y.
+ * 
+ *   SORT_NAME = the name of the procedure to be created
+ *
+ *   SORT_TYPE1 = type of the first or only array (no default)
+ *       This can be any numeric type for SORT_OF_SORT=1,2, but
+ *       should be an integer type for SORT_OF_SORT=3.
+ *       For SORT_OF_SORT=4, SORT_TYPE1 should be assignable;
+ *         such as a simple type or a structure.
+ *   SORT_TYPE2 = type of the second array if needed (no default)
+ *       This can be any assignable type (including a structure) for
+ *       SORT_OF_SORT=2, but must be a numeric type for SORT_OF_SORT=3.
+ *
+ *   Note that C doesn't like SORT_TYPE1 and SORT_TYPE2 to be defined
+ *   as explicit pointer types like int*.  The simplest work-around
+ *   is to define a type, e.g. typedef intptr int*  then use that.
+ *
+ *   SORT_MINPARTITION = least number of elements for using quicksort
+ *           partitioning, otherwise insertion sort is used (default "11") 
+ *   SORT_MINMEDIAN9 = least number of elements for using the median of 3
+ *           medians of 3 for partitioning (default "320")
+ *   SORT_FUNCTYPE = type of sort function (default "static void")
+ *
+ *   This file can be included any number of times provided the value
+ *   of SORT_NAME is different each time.
+ */
+ 
+#define SORT_MEDIAN_OF_3(a,b,c) \
+ ((a) <= (b) ? ((b) <= (c) ? (b) : (c) <= (a) ? (a) : (c)) \
+             : ((a) <= (c) ? (a) : (c) <= (b) ? (b) : (c)))
+#define F_SORT_MEDIAN_OF_3(f,a,b,c) \
+ (f(a,b) <= 0 ? (f(b,c) <= 0 ? (b) : f(c,a) <= 0 ? (a) : (c)) \
+             : (f(a,c) <= 0 ? (a) : f(c,b) <= 0 ? (b) : (c)))
+
+#if !defined(SORT_OF_SORT) || !defined(SORT_NAME)
+ #error Either SORT_OF_SORT or SORT_NAME is undefined
+#endif
+
+#if (SORT_OF_SORT < 1) || (SORT_OF_SORT > 4)
+ #error Unknown value of SORT_OF_SORT
+#endif
+
+#ifndef SORT_TYPE1
+ #error "SORT_TYPE1 must be defined before including sorttemplates.c"
+#endif
+
+#ifndef SORT_MINPARTITION
+#define SORT_MINPARTITION 11
+#endif
+
+#ifndef SORT_MINMEDIAN9
+#define SORT_MINMEDIAN9 320
+#endif
+
+#ifndef SORT_FUNCTYPE
+#define SORT_FUNCTYPE static void
+#endif
+
+#define SORT_SWAP1(x,y) tmp1 = x; x = y; y = tmp1;
+#define SORT_SWAP2(x,y) tmp2 = x; x = y; y = tmp2;
+
+/*******************************************************************/
+
+#if SORT_OF_SORT == 1
+SORT_FUNCTYPE
+SORT_NAME(SORT_TYPE1 *x, int n)
+{
+    int i,j;
+    int a,d,ba,dc,s,nn;
+    SORT_TYPE1 tmp1,v,v1,v2,v3;
+    SORT_TYPE1 *x0,*xa,*xb,*xc,*xd,*xh,*xl;
+    struct {SORT_TYPE1 *addr; int len;} stack[40];
+    int top;
+
+    top = 0;
+    if (n > 1)
+    {
+        stack[top].addr = x;
+        stack[top].len = n;
+        ++top;
+    }
+
+    while (top > 0)
+    {
+        --top;
+        x0 = stack[top].addr;
+        nn = stack[top].len;
+
+        if (nn < SORT_MINPARTITION)
+        {
+            for (i = 1; i < nn; ++i)
+            {
+                tmp1 = x0[i];
+                for (j = i; x0[j-1] > tmp1; )
+                {
+                    x0[j] = x0[j-1];
+                    if (--j == 0) break;
+                }
+                x0[j] = tmp1;
+            }
+            continue;
+        }
+
+        if (nn < SORT_MINMEDIAN9)
+            v = SORT_MEDIAN_OF_3(x0[0],x0[nn/2],x0[nn-1]);
+        else
+        {
+            v1 = SORT_MEDIAN_OF_3(x0[0],x0[1],x0[2]);
+            v2 = SORT_MEDIAN_OF_3(x0[nn/2-1],x0[nn/2],x0[nn/2+1]);
+            v3 = SORT_MEDIAN_OF_3(x0[nn-3],x0[nn-2],x0[nn-1]);
+            v = SORT_MEDIAN_OF_3(v1,v2,v3);
+        }
+
+        xa = xb = x0;  xc = xd = x0+(nn-1);
+        for (;;)
+        {
+            while (xb <= xc && *xb <= v)
+            {
+                if (*xb == v)
+                {
+                    *xb = *xa; *xa = v; ++xa;
+                }
+                ++xb;
+            }
+            while (xc >= xb && *xc >= v)
+            {
+                if (*xc == v)
+                {
+                    *xc = *xd; *xd = v; --xd;
+                }
+                --xc;
+            }
+            if (xb > xc) break;
+            SORT_SWAP1(*xb,*xc);
+            ++xb;
+            --xc;
+        }
+    
+        a = xa - x0;
+        ba = xb - xa;
+        if (ba > a) s = a; else s = ba;
+        for (xl = x0, xh = xb-s; s > 0; --s)
+        {
+            *xl = *xh; *xh = v; ++xl; ++xh;
+        }
+        d = xd - x0;
+        dc = xd - xc;
+        if (dc > nn-1-d) s = nn-1-d; else s = dc;
+        for (xl = xb, xh = x0 + (nn-s); s > 0; --s)
+        {
+            *xh = *xl; *xl = v; ++xl; ++xh;
+        }
+
+        if (ba > dc)
+        {
+            if (ba > 1)
+            {
+                stack[top].addr = x0; stack[top].len = ba; ++top;
+            }
+            if (dc > 1)
+            {
+                stack[top].addr = x0+(nn-dc); stack[top].len = dc; ++top;
+            }
+        }
+        else
+        {
+            if (dc > 1)
+            {
+                stack[top].addr = x0+(nn-dc); stack[top].len = dc; ++top;
+            }
+            if (ba > 1)
+            {
+                stack[top].addr = x0; stack[top].len = ba; ++top;
+            }
+        }
+    }
+}
+#endif
+
+#if SORT_OF_SORT == 2
+#ifndef SORT_TYPE2
+ #error "SORT_TYPE2 must be defined before including sorttemplates.c"
+#endif
+
+SORT_FUNCTYPE
+SORT_NAME(SORT_TYPE1 *x, SORT_TYPE2 *y, int n)
+{
+    int i,j;
+    int a,d,ba,dc,s,nn;
+    SORT_TYPE2 tmp2,*y0,*ya,*yb,*yc,*yd,*yl,*yh;
+    SORT_TYPE1 tmp1,v,v1,v2,v3;
+    SORT_TYPE1 *x0,*xa,*xb,*xc,*xd,*xh,*xl;
+    struct {SORT_TYPE1 *addr; int len;} stack[40];
+    int top;
+
+    top = 0;
+    if (n > 1)
+    {
+        stack[top].addr = x;
+        stack[top].len = n;
+        ++top;
+    }
+
+    while (top > 0)
+    {
+        --top;
+        x0 = stack[top].addr;
+        y0 = y + (x0-x);
+        nn = stack[top].len;
+
+        if (nn < SORT_MINPARTITION)
+        {
+            for (i = 1; i < nn; ++i)
+            {
+                tmp1 = x0[i];
+                tmp2 = y0[i];
+                for (j = i; x0[j-1] > tmp1; )
+                {
+                    x0[j] = x0[j-1];
+                    y0[j] = y0[j-1];
+                    if (--j == 0) break;
+                }
+                x0[j] = tmp1;
+                y0[j] = tmp2;
+            }
+            continue;
+        }
+
+        if (nn < SORT_MINMEDIAN9)
+            v = SORT_MEDIAN_OF_3(x0[0],x0[nn/2],x0[nn-1]);
+        else
+        {
+            v1 = SORT_MEDIAN_OF_3(x0[0],x0[1],x0[2]);
+            v2 = SORT_MEDIAN_OF_3(x0[nn/2-1],x0[nn/2],x0[nn/2+1]);
+            v3 = SORT_MEDIAN_OF_3(x0[nn-3],x0[nn-2],x0[nn-1]);
+            v = SORT_MEDIAN_OF_3(v1,v2,v3);
+        }
+
+        xa = xb = x0;  xc = xd = x0+(nn-1);
+        ya = yb = y0;  yc = yd = y0+(nn-1);
+        for (;;)
+        {
+            while (xb <= xc && *xb <= v)
+            {
+                if (*xb == v)
+                {
+                    *xb = *xa; *xa = v; ++xa;
+                    SORT_SWAP2(*ya,*yb); ++ya;
+                }
+                ++xb; ++yb;
+            }
+            while (xc >= xb && *xc >= v)
+            {
+                if (*xc == v)
+                {
+                    *xc = *xd; *xd = v; --xd;
+                    SORT_SWAP2(*yc,*yd); --yd;
+                }
+                --xc; --yc;
+            }
+            if (xb > xc) break;
+            SORT_SWAP1(*xb,*xc);
+            SORT_SWAP2(*yb,*yc);
+            ++xb; ++yb;
+            --xc; --yc;
+        }
+    
+        a = xa - x0;
+        ba = xb - xa;
+        if (ba > a) s = a; else s = ba;
+        for (xl = x0, xh = xb-s, yl = y0, yh = yb-s; s > 0; --s)
+        {
+            *xl = *xh; *xh = v; ++xl; ++xh;
+            SORT_SWAP2(*yl,*yh); ++yl; ++yh;
+        }
+        d = xd - x0;
+        dc = xd - xc;
+        if (dc > nn-1-d) s = nn-1-d; else s = dc;
+        for (xl = xb, xh = x0+(nn-s), yl = yb, yh = y0+(nn-s); s > 0; --s)
+        {
+            *xh = *xl; *xl = v; ++xl; ++xh;
+            SORT_SWAP2(*yl,*yh); ++yl; ++yh;
+        }
+
+        if (ba > dc)
+        {
+            if (ba > 1)
+            {
+                stack[top].addr = x0; stack[top].len = ba; ++top;
+            }
+            if (dc > 1)
+            {
+                stack[top].addr = x0+(nn-dc); stack[top].len = dc; ++top;
+            }
+        }
+        else
+        {
+            if (dc > 1)
+            {
+                stack[top].addr = x0+(nn-dc); stack[top].len = dc; ++top;
+            }
+            if (ba > 1)
+            {
+                stack[top].addr = x0; stack[top].len = ba; ++top;
+            }
+        }
+    }
+}
+#endif
+
+#if SORT_OF_SORT == 3
+#ifndef SORT_TYPE2
+ #error "SORT_TYPE2 must be defined before including sorttemplates.c"
+#endif
+
+SORT_FUNCTYPE
+SORT_NAME(SORT_TYPE1 *x, SORT_TYPE2 *y, int n)
+{
+    int i,j;
+    int a,d,ba,dc,s,nn;
+    SORT_TYPE2 tmp2,v,v1,v2,v3;
+    SORT_TYPE1 tmp1,*x0,*xa,*xb,*xc,*xd,*xh,*xl;
+    struct {SORT_TYPE1 *addr; int len;} stack[40];
+    int top;
+
+    top = 0;
+    if (n > 1)
+    {
+        stack[top].addr = x;
+        stack[top].len = n;
+        ++top;
+    }
+
+    while (top > 0)
+    {
+        --top;
+        x0 = stack[top].addr;
+        nn = stack[top].len;
+
+        if (nn < SORT_MINPARTITION)
+        {
+            for (i = 1; i < nn; ++i)
+            {
+                tmp1 = x0[i];
+                tmp2 = y[tmp1];
+                for (j = i; y[x0[j-1]] > tmp2; )
+                {
+                    x0[j] = x0[j-1];
+                    if (--j == 0) break;
+                }
+                x0[j] = tmp1;
+            }
+            continue;
+        }
+
+        if (nn < SORT_MINMEDIAN9)
+            v = SORT_MEDIAN_OF_3(y[x0[0]],y[x0[nn/2]],y[x0[nn-1]]);
+        else
+        {
+            v1 = SORT_MEDIAN_OF_3(y[x0[0]],y[x0[1]],y[x0[2]]);
+            v2 = SORT_MEDIAN_OF_3(y[x0[nn/2-1]],y[x0[nn/2]],y[x0[nn/2+1]]);
+            v3 = SORT_MEDIAN_OF_3(y[x0[nn-3]],y[x0[nn-2]],y[x0[nn-1]]);
+            v = SORT_MEDIAN_OF_3(v1,v2,v3);
+        }
+
+        xa = xb = x0;  xc = xd = x0+(nn-1);
+        for (;;)
+        {
+            while (xb <= xc && y[*xb] <= v)
+            {
+                if (y[*xb] == v)
+                {
+                    SORT_SWAP1(*xa,*xb); ++xa;
+                }
+                ++xb;
+            }
+            while (xc >= xb && y[*xc] >= v)
+            {
+                if (y[*xc] == v)
+                {
+                    SORT_SWAP1(*xc,*xd); --xd;
+                }
+                --xc;
+            }
+            if (xb > xc) break;
+            SORT_SWAP1(*xb,*xc);
+            ++xb;
+            --xc;
+        }
+    
+        a = xa - x0;
+        ba = xb - xa;
+        if (ba > a) s = a; else s = ba;
+        for (xl = x0, xh = xb-s; s > 0; --s)
+        {
+            SORT_SWAP1(*xl,*xh); ++xl; ++xh;
+        }
+        d = xd - x0;
+        dc = xd - xc;
+        if (dc > nn-1-d) s = nn-1-d; else s = dc;
+        for (xl = xb, xh = x0 + (nn-s); s > 0; --s)
+        {
+            SORT_SWAP1(*xl,*xh); ++xl; ++xh;
+        }
+
+        if (ba > dc)
+        {
+            if (ba > 1)
+            {
+                stack[top].addr = x0; stack[top].len = ba; ++top;
+            }
+            if (dc > 1)
+            {
+                stack[top].addr = x0+(nn-dc); stack[top].len = dc; ++top;
+            }
+        }
+        else
+        {
+            if (dc > 1)
+            {
+                stack[top].addr = x0+(nn-dc); stack[top].len = dc; ++top;
+            }
+            if (ba > 1)
+            {
+                stack[top].addr = x0; stack[top].len = ba; ++top;
+            }
+        }
+    }
+}
+#endif
+
+#if SORT_OF_SORT == 4
+#ifndef SORT_COMPARE
+ #error "SORT_COMPARE must be defined before including sorttemplates.c"
+#endif
+
+SORT_FUNCTYPE
+SORT_NAME(SORT_TYPE1 *x, int n)
+{
+    int i,j;
+    int a,d,ba,dc,s,nn;
+    SORT_TYPE1 tmp2,v,v1,v2,v3;
+    SORT_TYPE1 tmp1,*x0,*xa,*xb,*xc,*xd,*xh,*xl;
+    struct {SORT_TYPE1 *addr; int len;} stack[40];
+    int top;
+
+    top = 0;
+    if (n > 1)
+    {
+        stack[top].addr = x;
+        stack[top].len = n;
+        ++top;
+    }
+
+    while (top > 0)
+    {
+        --top;
+        x0 = stack[top].addr;
+        nn = stack[top].len;
+
+        if (nn < SORT_MINPARTITION)
+        {
+            for (i = 1; i < nn; ++i)
+            {
+                tmp1 = x0[i];
+                for (j = i; SORT_COMPARE(tmp1,x0[j-1]) < 0; )
+                {
+                    x0[j] = x0[j-1];
+                    if (--j == 0) break;
+                }
+                x0[j] = tmp1;
+            }
+            continue;
+        }
+
+        if (nn < SORT_MINMEDIAN9)
+            v = F_SORT_MEDIAN_OF_3(SORT_COMPARE,x0[0],x0[nn/2],x0[nn-1]);
+        else
+        {
+            v1 = F_SORT_MEDIAN_OF_3(SORT_COMPARE,x0[0],x0[1],x0[2]);
+            v2 = F_SORT_MEDIAN_OF_3(SORT_COMPARE,x0[nn/2-1],x0[nn/2],x0[nn/2+1]);
+            v3 = F_SORT_MEDIAN_OF_3(SORT_COMPARE,x0[nn-3],x0[nn-2],x0[nn-1]);
+            v = F_SORT_MEDIAN_OF_3(SORT_COMPARE,v1,v2,v3);
+        }
+
+        xa = xb = x0;  xc = xd = x0+(nn-1);
+        for (;;)
+        {
+            while (xb <= xc && SORT_COMPARE(*xb,v) <= 0)
+            {
+                if (SORT_COMPARE(*xb,v) == 0)
+                {
+                    SORT_SWAP1(*xa,*xb); ++xa;
+                }
+                ++xb;
+            }
+            while (xc >= xb && SORT_COMPARE(*xc,v) >= 0)
+            {
+                if (SORT_COMPARE(*xc,v) == 0)
+                {
+                    SORT_SWAP1(*xc,*xd); --xd;
+                }
+                --xc;
+            }
+            if (xb > xc) break;
+            SORT_SWAP1(*xb,*xc);
+            ++xb;
+            --xc;
+        }
+    
+        a = xa - x0;
+        ba = xb - xa;
+        if (ba > a) s = a; else s = ba;
+        for (xl = x0, xh = xb-s; s > 0; --s)
+        {
+            SORT_SWAP1(*xl,*xh); ++xl; ++xh;
+        }
+        d = xd - x0;
+        dc = xd - xc;
+        if (dc > nn-1-d) s = nn-1-d; else s = dc;
+        for (xl = xb, xh = x0 + (nn-s); s > 0; --s)
+        {
+            SORT_SWAP1(*xl,*xh); ++xl; ++xh;
+        }
+
+        if (ba > dc)
+        {
+            if (ba > 1)
+            {
+                stack[top].addr = x0; stack[top].len = ba; ++top;
+            }
+            if (dc > 1)
+            {
+                stack[top].addr = x0+(nn-dc); stack[top].len = dc; ++top;
+            }
+        }
+        else
+        {
+            if (dc > 1)
+            {
+                stack[top].addr = x0+(nn-dc); stack[top].len = dc; ++top;
+            }
+            if (ba > 1)
+            {
+                stack[top].addr = x0; stack[top].len = ba; ++top;
+            }
+        }
+    }
+}
+#endif
+
+#undef SORT_NAME
+#undef SORT_OF_SORT
+#undef SORT_TYPE1
+#undef SORT_TYPE2
+#undef SORT_COMPARE