From 640321106d0b60f1f9ed408537691b90a768a651 Mon Sep 17 00:00:00 2001
From: Carl Worth <cworth@cworth.org>
Date: Tue, 17 Apr 2007 10:37:40 -0700
Subject: [PATCH] Add interactive querying of items

We select a bin with an expoentially-distributed pseudo-random number,
(so the items that have been misses the most get the most repetition),
then select an item within that bin with a uniformly distributed
random number. After querying the user, the item's count is adjusted
to the next higher/lower positive/negative number if the user's
response is correct/incorrect. And the item is moved into the new
bin based on its count.
---
 Makefile |   3 +-
 mnemon.c | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 136 insertions(+), 1 deletion(-)

diff --git a/Makefile b/Makefile
index dbb41d5..238afe1 100644
--- a/Makefile
+++ b/Makefile
@@ -1,10 +1,11 @@
 MY_CFLAGS=-Wall -Wextra -Wmissing-prototypes -Wno-unused-parameter -Wno-sign-compare
+MY_LDFLAGS=-lreadline
 
 PROGRAMS=mnemon
 all: $(PROGRAMS)
 
 %: %.o 
-	$(CC) $(CFLAGS) $(MY_CFLAGS) $(LDFLAGS) -o $@ $^
+	$(CC) $(CFLAGS) $(MY_CFLAGS) $(LDFLAGS) $(MY_LDFLAGS) -o $@ $^
 
 %.o: %.c
 	$(CC) $(CFLAGS) $(MY_CFLAGS) -c -o $@ $<
diff --git a/mnemon.c b/mnemon.c
index 039f0ca..c0efa69 100644
--- a/mnemon.c
+++ b/mnemon.c
@@ -21,6 +21,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <stdarg.h>
+#include <stdint.h>
 
 #include <sys/types.h>
 #include <dirent.h>
@@ -28,6 +29,11 @@
 #include <string.h>
 #include <assert.h>
 
+#include <readline/readline.h>
+#include <readline/history.h>
+
+typedef int bool_t;
+
 typedef struct _item {
     int count;
     char *challenge;
@@ -255,6 +261,18 @@ bin_add_item (bin_t 	*bin,
     bin->items[bin->num_items++] = item;
 }
 
+static void
+bin_remove_item (bin_t	*bin,
+		 int	 item_index)
+{
+    /* Replace the current item with the last item, (no need to shift
+     * any more than that since we don't care about the order of the
+     * items within a bin). */
+    bin->num_items--;
+    if (bin->num_items)
+	bin->items[item_index] = bin->items[bin->num_items];
+}
+
 static void
 mnemon_init (mnemon_t *mnemon)
 {
@@ -525,15 +543,131 @@ mnemon_save (mnemon_t *mnemon)
     }
 }
 
+/* Return a uniformly-distributed pseudo-random integer within the
+ * range:
+ *
+ *	0 <= result < num_values
+ */
+static int
+rand_within (int num_values)
+{
+    return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
+}
+
+/* Return an exponentially-distributed pseudo-random integer within
+ * the range:
+ *
+ *	0 <= result < num_values
+ *
+ * The distribution is such that each successively larger value will
+ * occur with a probability of half of the previous value.
+ */
+static int
+rand_within_exponential (int num_values)
+{
+    static int r;
+    static uint32_t mask = 0;
+    int ones;
+    int bit;
+
+    /* Optimize the constant case. */
+    if (num_values == 1)
+	return 0;
+
+    ones = 0;
+
+    do {
+	if (mask == 0) {
+	    r = rand ();
+	    mask = 1 << 31;
+	    while (mask > RAND_MAX)
+		mask >>= 1;
+	}
+	bit = r & mask;
+	mask >>= 1;
+	if (bit) {
+	    ones++;
+	    if (ones == num_values)
+		ones = 0;
+	}
+    } while (bit);
+
+    return ones;
+}
+
+static void
+mnemon_select_item (mnemon_t	 *mnemon,
+		    bin_t	**bin_ret,
+		    int		 *item_index_ret)
+{
+    int bin_index;
+    bin_t *bin;
+
+    bin_index = rand_within_exponential (mnemon->num_bins);
+
+    bin = &mnemon->bins[bin_index];
+
+    *bin_ret = bin;
+    *item_index_ret = rand_within (bin->num_items);
+}
+
+static void
+mnemon_do_challenges (mnemon_t *mnemon)
+{
+    bin_t *bin;
+    int item_index;
+    item_t *item;
+    char *response;
+    bool_t correct;
+
+    while (1) {
+	mnemon_select_item (mnemon, &bin, &item_index);
+	item = bin->items[item_index];
+
+	printf ("%s\n", item->challenge);
+
+	response = readline ("> ");
+	if (response == NULL)
+	    break;
+
+	correct = (strcmp (response, item->response) == 0);
+
+	bin_remove_item (bin, item_index);
+
+	if (correct) {
+	    printf ("Correct!\n\n");
+	    if (item->count < 0)
+		item->count = 1;
+	    else
+		item->count++;
+	} else {
+	    printf ("  %s is the correct answer.\n\n",
+		    item->response);
+	    if (item->count > 0)
+		item->count = -1;
+	    else
+		item->count--;
+	}
+
+	bin = mnemon_get_bin (mnemon, item->count);
+
+	bin_add_item (bin, item);
+    }
+}
+
 int
 main (int argc, char *argv[])
 {
     mnemon_t mnemon;
 
+    srand (time (NULL));
+
     mnemon_init (&mnemon);
 
     mnemon_load (&mnemon);
 
+    mnemon_do_challenges (&mnemon);
+
     mnemon_save (&mnemon);
 
     mnemon_fini (&mnemon);
-- 
2.43.0