2 * Copyright © 2006 Carl Worth
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2, or (at your option)
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software Foundation,
16 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
27 #include <sys/types.h>
35 #include <readline/readline.h>
36 #include <readline/history.h>
40 typedef struct _item {
54 CATEGORY_ORDER_RANDOM,
55 CATEGORY_ORDER_SEQUENTIAL
63 typedef struct _category {
69 /* Support sequential introduction of items from bin 0 */
70 category_order_t order;
71 /* Support categories where responses are timed (0.0 == disable). */
74 /* Support challenges of non-text types (image, audio, etc.) */
75 challenge_type_t challenge_type;
78 typedef struct _mnemon {
83 category_t *categories;
102 fprintf (stderr, "Error: out of memory\n");
110 xrealloc (void *ptr, size_t size)
114 ret = realloc (ptr, size);
116 fprintf (stderr, "Error: out of memory\n");
124 xstrdup (const char *s)
130 fprintf (stderr, "Error: out of memory\n");
138 xstrndup (const char *s, size_t n)
142 ret = strndup (s, n);
144 fprintf (stderr, "Error: out of memory\n");
152 xasprintf (char **strp, const char *fmt, ...)
158 ret = vasprintf (strp, fmt, ap);
162 fprintf (stderr, "Error: out of memory\n");
168 item_init (item_t *item,
170 const char *challenge,
171 const char *response)
175 item->challenge = xmalloc (strlen (challenge) + 1 +
176 strlen (response) + 1);
177 item->response = item->challenge + strlen (challenge) + 1;
179 strcpy (item->challenge, challenge);
180 strcpy (item->response, response);
184 item_fini (item_t *item)
186 /* item->response shares allocation with item->challenge, so
187 * doesn't require a separate call to free */
188 free (item->challenge);
192 category_init (category_t *category,
195 category->name = xstrdup (name);
197 category->items_size = 0;
198 category->num_items = 0;
199 category->items = NULL;
200 category->order = CATEGORY_ORDER_RANDOM;
201 category->time_limit = 0.0;
202 category->bin_zero_head = 0;
203 category->challenge_type = CHALLENGE_TYPE_TEXT;
207 category_fini (category_t *category)
211 for (i = 0; i < category->num_items; i++)
212 item_fini (&category->items[i]);
214 free (category->items);
216 free (category->name);
220 category_grow (category_t *category)
222 if (category->items_size)
223 category->items_size *= 2;
225 category->items_size = 1;
227 category->items = xrealloc (category->items,
228 category->items_size * sizeof (item_t));
232 category_add_item (category_t *category,
234 const char *challenge,
235 const char *response)
239 if (category->num_items == category->items_size)
240 category_grow (category);
242 item = &category->items[category->num_items++];
244 item_init (item, score, challenge, response);
250 category_next_bin_zero_item (category_t *category)
252 int *i = &category->bin_zero_head;
254 for ( ; *i < category->num_items; *i = *i + 1)
255 if (category->items[*i].score == 0)
256 return &category->items[*i];
262 category_print (category_t *category,
268 fprintf (file, "order = %s\n\n",
269 category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
270 fprintf (file, "time = %f\n\n",
271 category->time_limit);
273 fprintf (file, "challenge = ");
274 switch (category->challenge_type) {
275 case CHALLENGE_TYPE_TEXT:
276 fprintf (file, "text");
278 case CHALLENGE_TYPE_IMAGE:
279 fprintf (file, "image");
282 fprintf (file, "\n\n");
284 for (i = 0; i < category->num_items; i++) {
285 item = &category->items[i];
287 fprintf (file, "\n");
288 fprintf (file, "%d\n%s\n%s\n",
296 bin_init (bin_t *bin,
307 bin_fini (bin_t *bin)
313 bin_grow (bin_t *bin)
316 bin->items_size *= 2;
320 bin->items = xrealloc (bin->items,
321 bin->items_size * sizeof (item_t*));
325 bin_add_item (bin_t *bin,
328 assert (item->score == bin->score);
330 if (bin->num_items == bin->items_size)
333 bin->items[bin->num_items++] = item;
337 bin_remove_item (bin_t *bin,
340 /* Replace the current item with the last item, (no need to shift
341 * any more than that since we don't care about the order of the
342 * items within a bin). */
345 bin->items[item_index] = bin->items[bin->num_items];
348 /* Find the index for an item within a bin.
350 * XXX: This is currently a linear search, so is a potential
351 * performance problem.
354 bin_item_index (bin_t *bin,
359 for (i = 0; i < bin->num_items; i++)
360 if (bin->items[i] == item)
366 typedef int (item_match_predicate_t) (void *closure, item_t *item);
368 /* Return the number of items in the bin from the given category (or
369 * from all categories if category == NULL) */
371 bin_num_items_matching (bin_t *bin,
372 item_match_predicate_t *predicate,
375 int i, num_items = 0;
377 if (predicate == NULL)
378 return bin->num_items;
380 for (i = 0; i < bin->num_items; i++)
381 if ((predicate) (closure, bin->items[i]))
388 mnemon_init (mnemon_t *mnemon)
392 home = getenv ("HOME");
396 xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
398 mnemon->categories_size = 0;
399 mnemon->num_categories = 0;
400 mnemon->categories = NULL;
402 mnemon->bins_size = 0;
403 mnemon->num_bins = 0;
406 mnemon->to_introduce = 10;
407 mnemon->to_master = 10;
408 mnemon->unlearned = 0;
409 mnemon->mastered = -1;
413 mnemon_fini (mnemon_t *mnemon)
417 for (i = 0; i < mnemon->num_bins; i++)
418 bin_fini (&mnemon->bins[i]);
421 for (i = 0; i < mnemon->num_categories; i++)
422 category_fini (&mnemon->categories[i]);
423 free (mnemon->categories);
425 free (mnemon->dir_name);
429 mnemon_categories_grow (mnemon_t *mnemon)
431 if (mnemon->categories_size)
432 mnemon->categories_size *= 2;
434 mnemon->categories_size = 1;
436 mnemon->categories = xrealloc (mnemon->categories,
437 mnemon->categories_size * sizeof (category_t));
440 /* Get a category by name if it exists */
442 mnemon_get_category_if_exists (mnemon_t *mnemon,
447 for (i = 0; i < mnemon->num_categories; i++)
448 if (strcmp (mnemon->categories[i].name, name) == 0)
449 return &mnemon->categories[i];
454 /* Get a category by name, creating new one if necessary. */
456 mnemon_get_category (mnemon_t *mnemon,
459 category_t *category;
461 category = mnemon_get_category_if_exists (mnemon, name);
465 mnemon_categories_grow (mnemon);
467 category = &mnemon->categories[mnemon->num_categories++];
469 category_init (category, name);
475 mnemon_bins_grow (mnemon_t *mnemon)
477 if (mnemon->bins_size)
478 mnemon->bins_size *= 2;
480 mnemon->bins_size = 1;
482 mnemon->bins = xrealloc (mnemon->bins,
483 mnemon->bins_size * sizeof (bin_t));
487 mnemon_get_bin (mnemon_t *mnemon,
493 for (i = 0; i < mnemon->num_bins; i++)
494 if (mnemon->bins[i].score == score)
495 return &mnemon->bins[i];
496 else if (mnemon->bins[i].score > score)
499 if (mnemon->num_bins == mnemon->bins_size)
500 mnemon_bins_grow (mnemon);
502 bin = &mnemon->bins[i];
504 /* Make room to insert new bin at its sorted location. */
505 if (i < mnemon->num_bins)
506 memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
509 bin_init (bin, score);
515 mnemon_remove_bin (mnemon_t *mnemon,
518 int i = bin - mnemon->bins;
522 memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
529 int len = strlen (s);
532 if (s[len - 1] == '\n')
537 trim_space (char *string)
542 while (*s && isspace (*s))
547 s = string + strlen (string) - 1;
548 while (s > string && isspace (*s)) {
557 mnemon_load_category (mnemon_t *mnemon,
561 char *line = NULL, *end;
562 size_t line_size = 0;
566 category_t *category;
569 path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
570 sprintf (path, "%s/%s", mnemon->dir_name, name);
572 file = fopen (path, "r");
574 fprintf (stderr, "Error: Failed to open %s: %s\n",
575 path, strerror (errno));
579 category = mnemon_get_category (mnemon, name);
581 #define READ_LINE do { \
582 bytes_read = getline (&line, &line_size, file); \
583 if (bytes_read == -1) \
591 char *name, *equal, *value;
593 /* Ignore blank lines */
598 /* An initial digit means we hit an item. Trigger the
599 * spaghetti machine. */
600 if ((*line >= '0' && *line <= '9') || *line == '-')
603 equal = strchr (line, '=');
605 fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
606 line, path, line_count);
614 name = trim_space (name);
615 value = trim_space (value);
617 if (strcmp (name, "order") == 0) {
618 if (strcmp (value, "sequential") == 0) {
619 category->order = CATEGORY_ORDER_SEQUENTIAL;
620 } else if (strcmp (value, "random") == 0) {
621 category->order = CATEGORY_ORDER_RANDOM;
623 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
624 value, path, line_count);
627 } else if (strcmp (name, "time") == 0) {
630 limit = strtod (value, &end);
631 while (isspace (*end))
634 category->time_limit = limit;
636 fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
637 value, path, line_count);
640 } else if (strcmp (name, "challenge") == 0) {
641 if (strcmp (value, "text") == 0) {
642 category->challenge_type = CHALLENGE_TYPE_TEXT;
643 } else if (strcmp (value, "image") == 0) {
644 category->challenge_type = CHALLENGE_TYPE_IMAGE;
646 fprintf (stderr, "Unknown value for \"challenge\" option \"%s\" at %s:%d\n",
647 value, path, line_count);
651 fprintf (stderr, "Unknown option %s at %s:%d\n",
652 name, path, line_count);
660 char *challenge, *response;
662 /* Ignore blank lines */
667 /* Read bin number */
669 score = strtol (line, &end, 10);
671 fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
672 line, path, line_count);
678 challenge = strdup (line);
684 category_add_item (category, score, challenge, response);
694 /* Resize category items to fit exactly. */
695 category->items_size = category->num_items;
696 category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
698 /* Now that the category is completely loaded, with stable
699 * pointers to every item, we can add each item to its appropriate
701 for (i = 0; i < category->num_items; i++) {
702 item_t *item = &category->items[i];
703 bin_t *bin = mnemon_get_bin (mnemon, item->score);
705 bin_add_item (bin, item);
710 mnemon_load (mnemon_t *mnemon)
713 struct dirent *dirent;
715 dir = opendir (mnemon->dir_name);
717 fprintf (stderr, "Error: Failed to open directory %s: %s\n",
718 mnemon->dir_name, strerror (errno));
723 dirent = readdir (dir);
727 if (dirent->d_type == DT_REG) {
728 /* Ignore files matching *~, (yes, this shouldn't be
729 * hard-coded in such an ad-hoc way, but there you go. */
730 if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
731 mnemon_load_category (mnemon, dirent->d_name);
739 mnemon_save (mnemon_t *mnemon)
742 char *filename, *lock_filename;
744 category_t *category;
746 for (i = 0; i < mnemon->num_categories; i++) {
747 category = &mnemon->categories[i];
749 xasprintf (&filename, "%s/%s",
750 mnemon->dir_name, category->name);
751 xasprintf (&lock_filename, "%s/.#%s",
752 mnemon->dir_name, category->name);
754 file = fopen (lock_filename, "w");
756 fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
757 lock_filename, strerror (errno));
761 category_print (category, file);
763 fsync (fileno (file));
766 err = rename (lock_filename, filename);
768 fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
769 lock_filename, filename, strerror (errno));
774 free (lock_filename);
778 /* Return a uniformly-distributed pseudo-random integer within the
781 * 0 <= result < num_values
784 rand_within (int num_values)
786 return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
789 /* Return an exponentially-distributed pseudo-random integer within
792 * 0 <= result < num_values
794 * The distribution is such that each successively larger value will
795 * occur with a probability of half of the previous value.
798 rand_within_exponential (int num_values)
801 static uint32_t mask = 0;
805 /* Optimize the constant case. */
815 while (mask > RAND_MAX)
822 if (ones == num_values)
830 /* Find the category to which an item belongs. */
832 mnemon_item_category (mnemon_t *mnemon,
835 category_t *category;
838 for (i = 0; i < mnemon->num_categories; i++) {
839 category = &mnemon->categories[i];
840 item_index = item - category->items;
841 if (item_index >= 0 && item_index < category->num_items)
848 typedef struct _item_in_category_closure
851 category_t *category;
852 } item_in_category_closure_t;
855 mnemon_item_in_category (void *closure, item_t *item)
857 item_in_category_closure_t *iicc = closure;
858 mnemon_t *mnemon = iicc->mnemon;
859 category_t *category = iicc->category;
861 return (mnemon_item_category (mnemon, item) == category);
864 typedef struct _item_in_category_of_length_closure
867 category_t *category;
869 } item_in_category_of_length_closure_t;
872 mnemon_item_in_category_of_length (void *closure, item_t *item)
874 item_in_category_of_length_closure_t *iicolc = closure;
875 mnemon_t *mnemon = iicolc->mnemon;
876 category_t *category = iicolc->category;
877 int length = iicolc->length;
879 if (mnemon_item_category (mnemon, item) != category)
882 return strlen (item->challenge) == length;
886 mnemon_select_item (mnemon_t *mnemon,
889 category_t **category_ret)
891 int bin_index, item_index;
894 category_t *category;
896 bin_index = rand_within_exponential (mnemon->num_bins);
897 bin = &mnemon->bins[bin_index];
899 /* The most intuitive understanding of the to_introduce counter is
900 * that it's tracking never-before-learned items as they are
901 * pulled from the bin with score 0. But that bin can become
902 * empty. So the refined rule is that we decrement to_introduce
903 * whenever we pull from the lowest-indexed bin with a
904 * non-negative score. */
905 if (mnemon->to_introduce && bin->score >=0 &&
906 (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
908 mnemon->to_introduce--;
911 item_index = rand_within (bin->num_items);
913 item = bin->items[item_index];
914 category = mnemon_item_category (mnemon, item);
916 if (bin->score == 0) {
917 if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
918 item = category_next_bin_zero_item (category);
920 item_index = bin_item_index (bin, item);
925 *item_index_ret = item_index;
926 *category_ret = category;
930 #define HISTOGRAM_ROW_FORMAT "%3d: %3d"
931 #define HISTOGRAM_BAR_WIDTH 63
934 print_histogram_bar (double size,
937 int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
938 static char const *boxes[8] = {
943 while (size > units_per_cell) {
945 size -= units_per_cell;
948 size /= units_per_cell;
952 else if (size > 6.5/8.0)
954 else if (size > 5.5/8.0)
956 else if (size > 4.5/8.0)
958 else if (size > 3.5/8.0)
960 else if (size > 2.5/8.0)
962 else if (size > 1.5/8.0)
964 else if (size > 0.5/8.0)
971 mnemon_print_histogram (mnemon_t *mnemon,
972 const char *category_name,
975 int i, last_score, max;
976 category_t *category = NULL;
979 item_match_predicate_t *predicate = NULL;
980 void *closure = NULL;
981 item_in_category_closure_t item_in_category;
982 item_in_category_of_length_closure_t item_in_category_of_length;
984 if (mnemon->num_bins == 0)
988 category = mnemon_get_category_if_exists (mnemon, category_name);
991 predicate = mnemon_item_in_category_of_length;
992 item_in_category_of_length.mnemon = mnemon;
993 item_in_category_of_length.category = category;
994 item_in_category_of_length.length = length;
995 closure = &item_in_category_of_length;
997 predicate = mnemon_item_in_category;
998 item_in_category.mnemon = mnemon;
999 item_in_category.category = category;
1000 closure = &item_in_category;
1005 for (i = 0; i < mnemon->num_bins; i++) {
1006 num_items = bin_num_items_matching (&mnemon->bins[i],
1007 predicate, closure);
1008 if (i == 0 || num_items > max)
1012 for (i = 0; i < mnemon->num_bins; i++) {
1013 bin = &mnemon->bins[i];
1015 while (bin->score - last_score > 1)
1016 printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
1017 num_items = bin_num_items_matching (bin,
1018 predicate, closure);
1019 printf (HISTOGRAM_ROW_FORMAT " ", bin->score, num_items);
1020 print_histogram_bar (num_items, max);
1021 last_score = bin->score;
1026 mnemon_handle_command (mnemon_t *mnemon,
1027 const char *command)
1031 switch (command[0]) {
1034 char *category = NULL;
1038 arg += strspn (arg, " \t");
1039 len = strcspn (arg, " \t");
1041 category = xstrndup (arg, len);
1043 arg += strspn (arg, " \t");
1045 length = atoi (arg);
1047 mnemon_print_histogram (mnemon, category, length);
1051 printf ("Unknown command: %s\n", command);
1057 mnemon_handle_response (mnemon_t *mnemon,
1061 const char *response,
1062 double response_time,
1067 correct = (strcmp (response, item->response) == 0);
1069 bin_remove_item (bin, item_index);
1071 /* If the bin is now empty, we must remove it. Also if we just
1072 * picked the last word we'll ever pick from the bin with
1073 * score 0, then we can remove that as well. */
1074 if (bin->num_items == 0 ||
1075 (bin->score == 0 && mnemon->to_introduce == 0))
1077 mnemon_remove_bin (mnemon, bin);
1081 (time_limit == 0.0 || response_time < time_limit))
1084 mnemon->to_master--;
1085 /* We reserve an item score of 0 for an item that has
1086 * never been asked. */
1087 if (item->score == 0) {
1089 mnemon->unlearned--;
1090 mnemon->to_master--;
1091 printf ("You got it!");
1092 } else if (item->score < 0) {
1093 printf ("Yes---just give me %d more.",
1095 } else if (item->score == 1) {
1096 printf ("On your first try, no less!");
1098 printf ("Masterful (%dx).", item->score);
1102 printf (" %s is the correct answer.",
1105 printf ("Correct, but not quite quick enough (%0.2f seconds---needed %0.2f seconds)\n",
1106 response_time, time_limit);
1107 /* Penalize an incorrect response by forcing the score
1109 if (item->score >= 0) {
1110 if (item->score > 0)
1111 printf (" Oops, you knew that, right? (%dx)\n ",
1113 mnemon->unlearned++;
1114 /* We add three here, (rather than just 2 to track the
1115 * change in the item's score below), as an extra
1116 * penalty. If the user is forgetting stuff learned
1117 * previously, then more time should be spent on mastering
1118 * than learning new items. */
1119 mnemon->to_master += item->score + 3;
1120 /* We go to -2 to force a little extra reinforcement
1121 * when re-learning an item, (otherwise, it will often
1122 * get asked again immediately where it is easy to get
1123 * a correct response without any learning). */
1127 mnemon->to_master++;
1132 if (mnemon->to_introduce)
1133 printf ("%d to come. ", mnemon->to_introduce);
1134 if (mnemon->unlearned)
1135 printf ("%d still unlearned. ", mnemon->unlearned);
1136 if (mnemon->to_introduce == 0 && mnemon->to_master > 0)
1137 printf ("%d items to master", mnemon->to_master);
1140 bin = mnemon_get_bin (mnemon, item->score);
1142 bin_add_item (bin, item);
1146 mnemon_show_image (mnemon_t *mnemon, const char *filename)
1150 /* XXX: Yes, shelling out to system is total cheese. The planned
1151 * fix here is to bring graphical display in process, (or at least
1152 * have a custom external program that accepts image filenames on
1155 xasprintf (&command, "xli -gamma 2.2 %s >/dev/null 2>&1 &",
1162 mnemon_hide_image (mnemon_t *mnemon)
1166 /* XXX: And this is just embarrassing (obviously wrong in several
1167 * ways). Hopefully I'll amend away any commit that includes this.
1169 xasprintf (&command, "killall xli");
1175 mnemon_do_challenges (mnemon_t *mnemon)
1180 category_t *category;
1184 /* Count the number of items with negative scores. */
1185 mnemon->unlearned = 0;
1186 for (i = 0; i < mnemon->num_bins; i++) {
1187 bin = &mnemon->bins[i];
1188 if (bin->score >= 0)
1190 mnemon->unlearned += bin->num_items;
1193 mnemon->to_introduce -= mnemon->unlearned;
1194 if (mnemon->to_introduce < 0)
1195 mnemon->to_introduce = 0;
1197 /* Get rid of bin with score of 0 if we aren't going to be
1198 * introducing anything from it. */
1199 if (mnemon->to_introduce == 0) {
1200 bin = mnemon_get_bin (mnemon, 0);
1201 mnemon_remove_bin (mnemon, bin);
1204 if (mnemon->unlearned) {
1205 printf ("You've got %d items to learn already. ", mnemon->unlearned);
1206 if (mnemon->to_introduce)
1207 printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
1210 printf ("Introducing %d new items.\n", mnemon->to_introduce);
1215 struct timeval start, end;
1217 mnemon_select_item (mnemon, &bin, &item_index, &category);
1218 item = bin->items[item_index];
1221 if (category->time_limit > 0.0) {
1222 response = readline ("The next one is timed. Press enter when ready:");
1226 switch (category->challenge_type) {
1227 case CHALLENGE_TYPE_TEXT:
1228 printf ("%s\n", item->challenge);
1230 case CHALLENGE_TYPE_IMAGE:
1232 char *absolute_filename;
1234 xasprintf (&absolute_filename, "%s/%s",
1235 mnemon->dir_name, item->challenge);
1236 mnemon_show_image (mnemon, absolute_filename);
1237 free (absolute_filename);
1242 gettimeofday (&start, NULL);
1243 response = readline ("> ");
1244 gettimeofday (&end, NULL);
1246 if (category->challenge_type == CHALLENGE_TYPE_IMAGE)
1247 mnemon_hide_image (mnemon);
1249 /* Terminate on EOF */
1250 if (response == NULL) {
1255 if (response[0] == '/') {
1256 mnemon_handle_command (mnemon, response + 1);
1263 mnemon_handle_response (mnemon, bin, item_index,
1265 (end.tv_sec + end.tv_usec / 1e6) -
1266 (start.tv_sec + start.tv_usec / 1e6),
1267 category->time_limit);
1269 } while (mnemon->to_introduce ||
1270 mnemon->unlearned ||
1271 mnemon->to_master > 0);
1275 main (int argc, char *argv[])
1280 srand (time (NULL));
1282 mnemon_init (&mnemon);
1284 mnemon_load (&mnemon);
1286 mnemon_do_challenges (&mnemon);
1288 mnemon_save (&mnemon);
1290 mnemon_fini (&mnemon);
1292 mnemon_init (&mnemon);
1293 mnemon_load (&mnemon);
1295 printf ("Great job.\nHere are your current results:\n");
1296 mnemon_print_histogram (&mnemon, NULL, 0);
1297 response = readline ("Press enter to quit.\n");
1300 mnemon_fini (&mnemon);