From 857d4a226763dd6adf42dbd6ca47ee9df679eaac Mon Sep 17 00:00:00 2001
From: Nathan Wagner <nw@hydaspes.if.org>
Date: Sun, 17 Jun 2018 18:03:44 +0000
Subject: [PATCH] add split out cantor library file

---
 lib/cantor.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
 create mode 100644 lib/cantor.c

diff --git a/lib/cantor.c b/lib/cantor.c
new file mode 100644
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;
+}
-- 
2.40.0