[WIP] Port of Simon Tatham's Puzzle Collectionpuzzles

Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9

MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.

The following games are at least partially broken for various reasons:

Cube:     crash with certain settings
Galaxies: crash
Inertia:  crash
Keen:     input issues
Loopy:    weird stuff happens
Map:      crash on input
Mines:    weird stuff happens on target
Palisade: input issues
Signpost: crash on input
Solo:     input issues
Towers:   input and drawing issues
Train Tracks: drawing issues
Twiddle:  weird animation on target
Undead:   input and drawing issues
Unequal:  input and drawing issues
Untangle: input issues

All in all, about 40% of the games are at least partially broken.

Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368

1 files changed, 88 insertions, 0 deletions

diff --git a/apps/plugins/puzzles/tdq.c b/apps/plugins/puzzles/tdq.c
new file mode 100644
index 0000000..43c9c35
--- /dev/null
+++ b/apps/plugins/puzzles/tdq.c
@@ -0,0 +1,88 @@
+/*
+ * tdq.c: implement a 'to-do queue', a simple de-duplicating to-do
+ * list mechanism.
+ */
+
+#include "rbassert.h"
+
+#include "puzzles.h"
+
+/*
+ * Implementation: a tdq consists of a circular buffer of size n
+ * storing the integers currently in the queue, plus an array of n
+ * booleans indicating whether each integer is already there.
+ *
+ * Using a circular buffer of size n to store between 0 and n items
+ * inclusive has an obvious failure mode: if the input and output
+ * pointers are the same, how do you know whether that means the
+ * buffer is full or empty?
+ *
+ * In this application we have a simple way to tell: in the former
+ * case, the flags array is all 1s, and in the latter case it's all
+ * 0s. So we could spot that case and check, say, flags[0].
+ *
+ * However, it's even easier to simply determine whether the queue is
+ * non-empty by testing flags[buffer[op]] - that way we don't even
+ * _have_ to compare ip against op.
+ */
+
+struct tdq {
+    int n;
+    int *queue;
+    int ip, op;                        /* in pointer, out pointer */
+    char *flags;
+};
+
+tdq *tdq_new(int n)
+{
+    int i;
+    tdq *tdq = snew(struct tdq);
+    tdq->queue = snewn(n, int);
+    tdq->flags = snewn(n, char);
+    for (i = 0; i < n; i++) {
+        tdq->queue[i] = 0;
+        tdq->flags[i] = 0;
+    }
+    tdq->n = n;
+    tdq->ip = tdq->op = 0;
+    return tdq;
+}
+
+void tdq_free(tdq *tdq)
+{
+    sfree(tdq->queue);
+    sfree(tdq->flags);
+    sfree(tdq);
+}
+
+void tdq_add(tdq *tdq, int k)
+{
+    assert((unsigned)k < (unsigned)tdq->n);
+    if (!tdq->flags[k]) {
+        tdq->queue[tdq->ip] = k;
+        tdq->flags[k] = 1;
+        if (++tdq->ip == tdq->n)
+            tdq->ip = 0;
+    }
+}
+
+int tdq_remove(tdq *tdq)
+{
+    int ret = tdq->queue[tdq->op];
+
+    if (!tdq->flags[ret])
+        return -1;
+
+    tdq->flags[ret] = 0;
+    if (++tdq->op == tdq->n)
+        tdq->op = 0;
+
+    return ret;
+}
+
+void tdq_fill(tdq *tdq)
+{
+    int i;
+    for (i = 0; i < tdq->n; i++)
+        tdq_add(tdq, i);
+}