-/*
- * Copyright © 2006 Carl Worth
+/* mnemon - A memory training library
+ *
+ * Copyright © 2006,2011 Carl Worth
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2, or (at your option)
+ * the Free Software Foundation; either version 3, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful,
* Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
*/
+#include "mnemon.h"
+
/* for asprintf */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
+#include <stdint.h>
+#include <math.h>
#include <sys/types.h>
+#include <sys/time.h>
+#include <sys/stat.h>
+#include <unistd.h>
#include <dirent.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
-typedef struct _item {
- int count;
- char *challenge;
- char *response;
-} item_t;
-
-typedef struct _bin {
- int count;
- int items_size;
- int num_items;
- item_t **items;
-} bin_t;
-
-typedef struct _category {
- char *name;
- int items_size;
- int num_items;
- item_t *items;
-} category_t;
-
-typedef struct _mnemon {
- char *dir_name;
-
- int categories_size;
- int num_categories;
- category_t *categories;
-
- int bins_size;
- int num_bins;
- bin_t *bins;
-} mnemon_t;
+#include <readline/readline.h>
+#include <readline/history.h>
+
+#define ASSERT_NOT_REACHED \
+do { \
+ static const int NOT_REACHED = 0; \
+ assert (NOT_REACHED); \
+} while (0)
static void *
xmalloc (size_t size)
char *ret;
ret = strdup (s);
- if (s == NULL) {
+ if (ret == NULL) {
fprintf (stderr, "Error: out of memory\n");
exit (1);
}
static void
item_init (item_t *item,
- int count,
+ int score,
const char *challenge,
const char *response)
{
- item->count = count;
+ item->score = score;
item->challenge = xmalloc (strlen (challenge) + 1 +
strlen (response) + 1);
category->items_size = 0;
category->num_items = 0;
category->items = NULL;
+ category->order = CATEGORY_ORDER_RANDOM;
+ category->time_limit = 0.0;
+ category->bin_zero_head = 0;
+ category->challenge_type = xstrdup("");
+ category->repeat = 0;
}
static void
category_fini (category_t *category)
{
- int i;
+ unsigned int i;
for (i = 0; i < category->num_items; i++)
item_fini (&category->items[i]);
free (category->items);
free (category->name);
+
+ free (category->challenge_type);
}
static void
static item_t *
category_add_item (category_t *category,
- int count,
+ int score,
const char *challenge,
const char *response)
{
item = &category->items[category->num_items++];
- item_init (item, count, challenge, response);
+ item_init (item, score, challenge, response);
return item;
}
+static item_t *
+category_next_bin_zero_item (category_t *category)
+{
+ unsigned 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)
{
- int i;
+ unsigned int i;
item_t *item;
+ fprintf (file, "order = %s\n\n",
+ category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
+ fprintf (file, "time = %f\n\n",
+ category->time_limit);
+
+ fprintf (file, "challenge = %s\n\n", category->challenge_type);
+
+ fprintf (file, "repeat = %d\n\n", category->repeat);
+
for (i = 0; i < category->num_items; i++) {
item = &category->items[i];
if (i != 0)
fprintf (file, "\n");
fprintf (file, "%d\n%s\n%s\n",
- item->count,
+ item->score,
item->challenge,
item->response);
}
static void
bin_init (bin_t *bin,
- int count)
+ int score)
{
- bin->count = count;
+ bin->score = score;
bin->items_size = 0;
bin->num_items = 0;
bin_add_item (bin_t *bin,
item_t *item)
{
- assert (item->count == bin->count);
+ assert (item->score == bin->score);
if (bin->num_items == bin->items_size)
bin_grow (bin);
}
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];
+}
+
+/* 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)
+{
+ unsigned int i;
+
+ for (i = 0; i < bin->num_items; i++)
+ if (bin->items[i] == item)
+ return i;
+
+ assert (0);
+}
+
+void
mnemon_init (mnemon_t *mnemon)
{
char *home;
mnemon->bins = NULL;
}
-static void
+void
mnemon_fini (mnemon_t *mnemon)
{
int i;
mnemon->categories_size * sizeof (category_t));
}
-static category_t *
-mnemon_get_category (mnemon_t *mnemon,
- const char *name)
+/* Get a category by name if it exists */
+category_t *
+mnemon_get_category_if_exists (mnemon_t *mnemon,
+ const char *name)
{
int i;
- category_t *category;
for (i = 0; i < mnemon->num_categories; i++)
if (strcmp (mnemon->categories[i].name, name) == 0)
return &mnemon->categories[i];
+ return NULL;
+}
+
+/* Get a category by name, creating new one if necessary. */
+static category_t *
+mnemon_get_category (mnemon_t *mnemon,
+ const char *name)
+{
+ category_t *category;
+
+ category = mnemon_get_category_if_exists (mnemon, name);
+ if (category)
+ return category;
+
mnemon_categories_grow (mnemon);
category = &mnemon->categories[mnemon->num_categories++];
static bin_t *
mnemon_get_bin (mnemon_t *mnemon,
- int count)
+ int score)
{
int i;
bin_t *bin;
for (i = 0; i < mnemon->num_bins; i++)
- if (mnemon->bins[i].count == count)
+ if (mnemon->bins[i].score == score)
return &mnemon->bins[i];
- else if (mnemon->bins[i].count > count)
+ else if (mnemon->bins[i].score > score)
break;
- mnemon_bins_grow (mnemon);
+ if (mnemon->num_bins == mnemon->bins_size)
+ mnemon_bins_grow (mnemon);
bin = &mnemon->bins[i];
/* Make room to insert new bin at its sorted location. */
- memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
+ if (i < mnemon->num_bins)
+ memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
mnemon->num_bins++;
- bin_init (bin, count);
+ bin_init (bin, score);
return bin;
}
+void
+mnemon_remove_bin (mnemon_t *mnemon, int bin_number)
+{
+ bin_t *bin = mnemon_get_bin (mnemon, bin_number);
+ int i;
+
+ if (bin == NULL)
+ return;
+
+ i = bin - mnemon->bins;
+
+ bin_fini (bin);
+
+ memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
+ mnemon->num_bins--;
+}
+
static void
chomp (char *s)
{
s[len - 1] = '\0';
}
-static void
+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;
+}
+
+void
mnemon_load_category (mnemon_t *mnemon,
const char *name)
{
char *path;
category_t *category;
int i;
+ struct stat st;
path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
sprintf (path, "%s/%s", mnemon->dir_name, name);
exit (1);
}
+ fstat (fileno(file), &st);
+ if (! S_ISREG(st.st_mode)) {
+ fprintf (stderr, "Error: File %s is not a regular file.\n", path);
+ exit (1);
+ }
+
category = mnemon_get_category (mnemon, name);
+#define READ_LINE do { \
+ bytes_read = getline (&line, &line_size, file); \
+ if (bytes_read == -1) \
+ goto END_OF_FILE; \
+ line_count++; \
+ 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') || *line == '-')
+ 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 if (strcmp (name, "time") == 0) {
+ double limit;
+ char *end;
+ limit = strtod (value, &end);
+ while (isspace (*end))
+ end++;
+ if (*end == '\0') {
+ category->time_limit = limit;
+ } else {
+ fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
+ value, path, line_count);
+ exit (1);
+ }
+ } else if (strcmp (name, "challenge") == 0) {
+ /* XXX: Need to switch to talloc here. */
+ free (category->challenge_type);
+ category->challenge_type = xstrdup (value);
+ } else if (strcmp (name, "repeat") == 0) {
+ if (strcmp (value, "0") == 0)
+ category->repeat = 0;
+ else
+ category->repeat = 1;
+ } else {
+ fprintf (stderr, "Unknown option %s at %s:%d\n",
+ name, path, line_count);
+ exit (1);
+ }
+ }
+
+ /* Parse items */
while (1) {
- int count;
+ int score;
char *challenge, *response;
- /* Read bin number (ignoring blank separator lines) */
- do {
- bytes_read = getline (&line, &line_size, file);
- if (bytes_read == -1)
- goto END_OF_FILE;
- line_count++;
- chomp (line);
- } while (*line == '\0');
+ /* Ignore blank lines */
+ READ_LINE;
+ if (*line == '\0')
+ continue;
- count = strtol (line, &end, 10);
+ /* 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",
line, path, line_count);
}
/* Read challenge */
- bytes_read = getline (&line, &line_size, file);
- if (bytes_read == -1)
- break;
- line_count++;
- chomp (line);
+ READ_LINE;
challenge = strdup (line);
/* Read response */
- bytes_read = getline (&line, &line_size, file);
- if (bytes_read == -1)
- break;
- line_count++;
- chomp (line);
+ READ_LINE;
response = line;
- category_add_item (category, count, challenge, response);
+ category_add_item (category, score, challenge, response);
free (challenge);
}
* bin. */
for (i = 0; i < category->num_items; i++) {
item_t *item = &category->items[i];
- bin_t *bin = mnemon_get_bin (mnemon, item->count);
+ bin_t *bin = mnemon_get_bin (mnemon, item->score);
bin_add_item (bin, item);
}
}
-static void
+void
mnemon_load (mnemon_t *mnemon)
{
DIR *dir;
closedir (dir);
}
-static void
+void
mnemon_save (mnemon_t *mnemon)
{
int i, err;
category_print (category, file);
+ fsync (fileno (file));
fclose (file);
err = rename (lock_filename, filename);
if (err < 0) {
- fprintf (stderr, "Error: Failes to rename %s to %s: %s\n",
+ fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
lock_filename, filename, strerror (errno));
continue;
}
}
}
-int
-main (int argc, char *argv[])
+/* 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;
+}
+
+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);
+}
+
+void
+mnemon_select_item (mnemon_t *mnemon,
+ bin_t **bin_ret,
+ int *item_index_ret,
+ category_t **category_ret,
+ int *introduced_ret)
+{
+ int bin_index, item_index;
+ bin_t *bin;
+ item_t *item;
+ category_t *category;
+
+ bin_index = rand_within_exponential (mnemon->num_bins);
+ bin = &mnemon->bins[bin_index];
+
+ /* The most intuitive understanding of the introduced flag that
+ * it's tracking never-before-learned items as they are pulled
+ * from the bin with score 0. But that bin can become empty. So
+ * the refined rule is that we also set introduced whenever we
+ * pull from the lowest-indexed bin with a non-negative score. */
+ if (bin->score >=0 &&
+ (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
+ {
+ *introduced_ret = 1;
+ }
+ else
+ {
+ *introduced_ret = 0;
+ }
+
+ item_index = rand_within (bin->num_items);
+
+ item = bin->items[item_index];
+ category = mnemon_item_category (mnemon, item);
+
+ if (bin->score == 0) {
+ 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 = item_index;
+ *category_ret = category;
+}
+
+void
+mnemon_score_item (mnemon_t *mnemon,
+ bin_t *bin,
+ unsigned int item_index,
+ bool_t correct)
{
- mnemon_t mnemon;
+ item_t *item;
+
+ if (item_index >= bin->num_items)
+ return;
- mnemon_init (&mnemon);
+ item = bin->items[item_index];
+ bin_remove_item (bin, item_index);
- mnemon_load (&mnemon);
+ /* If the bin is now empty, we must remove it. */
+ if (bin->num_items == 0)
+ {
+ mnemon_remove_bin (mnemon, bin->score);
+ }
- mnemon_save (&mnemon);
+ if (correct)
+ {
+ item->score++;
+ /* We reserve an item score of 0 for an item that has
+ * never been asked. */
+ if (item->score == 0)
+ item->score = 1;
+ }
+ else
+ {
+ /* Penalize an incorrect response by forcing the score
+ * negative. */
+ if (item->score >= 0) {
+ /* We go to -2 to force a little extra reinforcement
+ * when re-learning an item, (otherwise, it will often
+ * get asked again immediately where it is easy to get
+ * a correct response without any learning). */
+ item->score = -2;
+ } else {
+ item->score--;
+ }
+ }
- mnemon_fini (&mnemon);
+ bin = mnemon_get_bin (mnemon, item->score);
- return 0;
+ bin_add_item (bin, item);
}