1 files changed, 88 insertions, 0 deletions
diff --git a/tdq.c b/tdq.c
new file mode 100644
index 0000000..d66f9f4
--- /dev/null
+++ b/tdq.c
@@ -0,0 +1,88 @@
+/*
+ * tdq.c: implement a 'to-do queue', a simple de-duplicating to-do
+ * list mechanism.
+ */
+
+#include <assert.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);
+}