Add support for sequential introduction of a category

This allows a particular category to be configured so that new items
will be introduced in the order they exist in the file, rather than
randomly, (though once an item leaves bin 0 it gets the same random
treatment as all other items).

The behavior is controlled by a new option at the beginning of the
file that looks like this:

	order = sequential

If there is no option it will be treated as random, (and when written
out the order option will be set to either sequential or random).

diff --git a/mnemon.c b/mnemon.c
index 63ea457f49a18deb3cfb4d034aba9b1a209cfc59..321ab1433a9dd235e738354ba36ecc5f2e029acf 100644 (file)
--- a/mnemon.c
+++ b/mnemon.c
@@ -48,11 +48,20 @@ typedef struct _bin {
     item_t **items;
 } bin_t;
 
+typedef enum {
+    CATEGORY_ORDER_RANDOM,
+    CATEGORY_ORDER_SEQUENTIAL
+} category_order_t;
+
 typedef struct _category {
     char *name;
     int items_size;
     int num_items;
     item_t *items;
+
+    /* Support sequential introduction of items from bin 0 */
+    category_order_t order;
+    int bin_zero_head;
 } category_t;
 
 typedef struct _mnemon {
@@ -163,6 +172,8 @@ category_init (category_t *category,
     category->items_size = 0;
     category->num_items = 0;
     category->items = NULL;
+    category->order = CATEGORY_ORDER_RANDOM;
+    category->bin_zero_head = 0;
 }
 
 static void
@@ -208,6 +219,18 @@ category_add_item (category_t      *category,
     return item;
 }
 
+static item_t *
+category_next_bin_zero_item (category_t        *category)
+{
+    int *i = &category->bin_zero_head;
+
+    for ( ; *i < category->num_items; *i = *i + 1)
+       if (category->items[*i].score == 0)
+           return &category->items[*i];
+
+    return NULL;
+}
+
 static void
 category_print (category_t     *category,
                FILE            *file)
@@ -215,6 +238,9 @@ category_print (category_t  *category,
     int i;
     item_t *item;
 
+    fprintf (file, "order = %s\n\n",
+           category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
+
     for (i = 0; i < category->num_items; i++) {
        item = &category->items[i];
        if (i != 0)
@@ -279,6 +305,24 @@ bin_remove_item (bin_t     *bin,
        bin->items[item_index] = bin->items[bin->num_items];
 }
 
+/* Find the index for an item within a bin.
+ *
+ * XXX: This is currently a linear search, so is a potential
+ * performance problem.
+ */
+static int
+bin_item_index (bin_t  *bin,
+               item_t  *item)
+{
+    int i;
+
+    for (i = 0; i < bin->num_items; i++)
+       if (bin->items[i] == item)
+           return i;
+
+    assert (0);
+}
+
 static void
 mnemon_init (mnemon_t *mnemon)
 {
@@ -414,6 +458,26 @@ chomp (char *s)
        s[len - 1] = '\0';
 }
 
+static char *
+trim_space (char *string)
+{
+    char *s;
+
+    s = string;
+    while (*s && isspace (*s))
+       s++;
+
+    string = s;
+
+    s = string + strlen (string) - 1;
+    while (s > string && isspace (*s)) {
+       *s = '\0';
+       s--;
+    }
+
+    return string;
+}
+
 static void
 mnemon_load_category (mnemon_t         *mnemon,
                      const char        *name)
@@ -447,6 +511,52 @@ mnemon_load_category (mnemon_t             *mnemon,
     chomp (line);                                      \
 } while (0)
 
+    /* Parse options */
+    while (1) {
+       char *name, *equal, *value;
+
+       /* Ignore blank lines */
+       READ_LINE;
+       if (*line == '\0')
+           continue;
+
+       /* An initial digit means we hit an item. Trigger the
+        * spaghetti machine. */
+       if (*line >= '0' && *line <= '9')
+           goto PARSE_BIN;
+
+       equal = strchr (line, '=');
+       if (equal == NULL) {
+           fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
+                    line, path, line_count);
+           exit (1);
+       }
+
+       value = equal + 1;
+       name = line;
+       *equal = '\0';
+
+       name = trim_space (name);
+       value = trim_space (value);
+
+       if (strcmp (name, "order") == 0) {
+           if (strcmp (value, "sequential") == 0) {
+               category->order = CATEGORY_ORDER_SEQUENTIAL;
+           } else if (strcmp (value, "random") == 0) {
+               category->order = CATEGORY_ORDER_RANDOM;
+           } else {
+               fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
+                        value, path, line_count);
+               exit (1);
+           }
+       } else {
+           fprintf (stderr, "Unknown option %s at %s:%d\n",
+                    name, path, line_count);
+           exit (1);
+       }
+    }
+
+    /* Parse items */
     while (1) {
        int score;
        char *challenge, *response;
@@ -457,6 +567,7 @@ mnemon_load_category (mnemon_t              *mnemon,
            continue;
 
        /* Read bin number */
+      PARSE_BIN:
        score = strtol (line, &end, 10);
        if (*end != '\0') {
            fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
@@ -617,20 +728,55 @@ rand_within_exponential (int num_values)
     return ones;
 }
 
+/* Find the category to which an item belongs. */
+static category_t *
+mnemon_item_category (mnemon_t *mnemon,
+                     item_t    *item)
+{
+    category_t *category;
+    int i, item_index;
+
+    for (i = 0; i < mnemon->num_categories; i++) {
+       category = &mnemon->categories[i];
+       item_index = item - category->items;
+       if (item_index >= 0 && item_index < category->num_items)
+           return category;
+    }
+
+    assert (0);
+}
+
 static void
 mnemon_select_item (mnemon_t    *mnemon,
                    bin_t       **bin_ret,
                    int          *item_index_ret)
 {
-    int bin_index;
+    int bin_index, item_index;
     bin_t *bin;
 
     bin_index = rand_within_exponential (mnemon->num_bins);
 
     bin = &mnemon->bins[bin_index];
 
+    item_index = rand_within (bin->num_items);
+
+    if (bin->score == 0) {
+       category_t *category;
+       item_t *item;
+
+       item = bin->items[item_index];
+
+       category = mnemon_item_category (mnemon, item);
+
+       if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
+           item = category_next_bin_zero_item (category);
+           if (item)
+               item_index = bin_item_index (bin, item);
+       }
+    }
+
     *bin_ret = bin;
-    *item_index_ret = rand_within (bin->num_items);
+    *item_index_ret = item_index;
 }