add split out cantor library file

diff --git a/lib/cantor.c b/lib/cantor.c
new file mode 100644 (file)
index 0000000..0f7cb31
--- /dev/null
+++ b/lib/cantor.c
@@ -0,0 +1,100 @@
+#include "hexagon.h"
+
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+
+static int inversenatcantor(int cantor, int *x, int *y) {
+       int w, t, py;
+
+       cantor -= 1;
+
+       w = (int)floor((sqrt(8.0 * cantor + 1.0) - 1.0)/2.0);
+       t = (w * w + w)/2;
+
+       py = cantor - t;
+
+       if (y) *y = py;
+       if (x) *x = w - py;
+
+       return cantor;
+}
+
+
+static int inversecantor(int cantor, int *x, int *y) {
+       if (cantor < 0) {
+               inversenatcantor(-cantor, x, y);
+               if (x) {
+                       if (*x % 2) {
+                               *x = -(*x+1)/2;
+                       } else {
+                               *x = *x / 2;
+                       }
+               }
+               if (y) {
+                       if (*y % 2) {
+                               *y =  -(*y+1)/2;
+                       } else {
+                               *y = *y/2;
+                       }
+               }
+       } else {
+               inversenatcantor(cantor, x, y);
+       }
+
+       return cantor;
+}
+/*
+ * map non negative integer pairs to their cantor pairing function
+ * number, plus one.  We add one so that the result is never zero,
+ * leaving zero to be "invalid" or "none" or what have you.
+ */
+
+static int natcantor(int x, int y) {
+       return (x+y) * (x + y + 1) / 2 + y+1;
+}
+
+/* See http://en.wikipedia.org/wiki/Cantor_pairing_function */
+/* see also http://szudzik.com/ElegantPairing.pdf */
+/*
+ * if either coordinate is negative, map the integers onto the
+ * whole numbers, and then return the negative of the adjusted
+ * cantor number.  As for most grids negative coordinates will
+ * be invalid, this will allow for a <= 0 test for invalid
+ * or out of bounds (on the negative side anyway, you'll
+ * still have to test for out of range on the positive side).
+ *
+ * TODO figure out what the maximum supported coordinates are
+ * for given integer sizes.
+ */
+int HL_cantor_xy(int x, int y) {
+       if (x < 0 || y < 0) {
+               x = abs(2 * x) - (x < 0);
+               y = abs(2 * y) - (y < 0);
+               return -natcantor(x, y);
+       }
+       return natcantor(x,y);
+}
+
+int HL_cantor(struct HL_hex h) {
+       int x, y;
+
+       x = h.x;
+       y = h.y;
+
+       if (x < 0 || y < 0) {
+               x = abs(2 * x) - (x < 0);
+               y = abs(2 * y) - (y < 0);
+               return -natcantor(x, y);
+       }
+       return natcantor(x,y);
+}
+
+struct HL_hex HL_uncantor(int cantor) {
+       struct HL_hex h;
+
+       inversecantor(cantor, &h.x, &h.y);
+
+       return h;
+}