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
58 typedef struct _category {
64 /* Support sequential introduction of items from bin 0 */
65 category_order_t order;
66 /* Support categories where responses are timed (0.0 == disable). */
71 typedef struct _mnemon {
76 category_t *categories;
95 fprintf (stderr, "Error: out of memory\n");
103 xrealloc (void *ptr, size_t size)
107 ret = realloc (ptr, size);
109 fprintf (stderr, "Error: out of memory\n");
117 xstrdup (const char *s)
123 fprintf (stderr, "Error: out of memory\n");
131 xstrndup (const char *s, size_t n)
135 ret = strndup (s, n);
137 fprintf (stderr, "Error: out of memory\n");
145 xasprintf (char **strp, const char *fmt, ...)
151 ret = vasprintf (strp, fmt, ap);
155 fprintf (stderr, "Error: out of memory\n");
161 item_init (item_t *item,
163 const char *challenge,
164 const char *response)
168 item->challenge = xmalloc (strlen (challenge) + 1 +
169 strlen (response) + 1);
170 item->response = item->challenge + strlen (challenge) + 1;
172 strcpy (item->challenge, challenge);
173 strcpy (item->response, response);
177 item_fini (item_t *item)
179 /* item->response shares allocation with item->challenge, so
180 * doesn't require a separate call to free */
181 free (item->challenge);
185 category_init (category_t *category,
188 category->name = xstrdup (name);
190 category->items_size = 0;
191 category->num_items = 0;
192 category->items = NULL;
193 category->order = CATEGORY_ORDER_RANDOM;
194 category->time_limit = 0.0;
195 category->bin_zero_head = 0;
199 category_fini (category_t *category)
203 for (i = 0; i < category->num_items; i++)
204 item_fini (&category->items[i]);
206 free (category->items);
208 free (category->name);
212 category_grow (category_t *category)
214 if (category->items_size)
215 category->items_size *= 2;
217 category->items_size = 1;
219 category->items = xrealloc (category->items,
220 category->items_size * sizeof (item_t));
224 category_add_item (category_t *category,
226 const char *challenge,
227 const char *response)
231 if (category->num_items == category->items_size)
232 category_grow (category);
234 item = &category->items[category->num_items++];
236 item_init (item, score, challenge, response);
242 category_next_bin_zero_item (category_t *category)
244 int *i = &category->bin_zero_head;
246 for ( ; *i < category->num_items; *i = *i + 1)
247 if (category->items[*i].score == 0)
248 return &category->items[*i];
254 category_print (category_t *category,
260 fprintf (file, "order = %s\n\n",
261 category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
262 fprintf (file, "time = %f\n\n",
263 category->time_limit);
265 for (i = 0; i < category->num_items; i++) {
266 item = &category->items[i];
268 fprintf (file, "\n");
269 fprintf (file, "%d\n%s\n%s\n",
277 bin_init (bin_t *bin,
288 bin_fini (bin_t *bin)
294 bin_grow (bin_t *bin)
297 bin->items_size *= 2;
301 bin->items = xrealloc (bin->items,
302 bin->items_size * sizeof (item_t*));
306 bin_add_item (bin_t *bin,
309 assert (item->score == bin->score);
311 if (bin->num_items == bin->items_size)
314 bin->items[bin->num_items++] = item;
318 bin_remove_item (bin_t *bin,
321 /* Replace the current item with the last item, (no need to shift
322 * any more than that since we don't care about the order of the
323 * items within a bin). */
326 bin->items[item_index] = bin->items[bin->num_items];
329 /* Find the index for an item within a bin.
331 * XXX: This is currently a linear search, so is a potential
332 * performance problem.
335 bin_item_index (bin_t *bin,
340 for (i = 0; i < bin->num_items; i++)
341 if (bin->items[i] == item)
347 typedef int (item_match_predicate_t) (void *closure, item_t *item);
349 /* Return the number of items in the bin from the given category (or
350 * from all categories if category == NULL) */
352 bin_num_items_matching (bin_t *bin,
353 item_match_predicate_t *predicate,
356 int i, num_items = 0;
358 if (predicate == NULL)
359 return bin->num_items;
361 for (i = 0; i < bin->num_items; i++)
362 if ((predicate) (closure, bin->items[i]))
369 mnemon_init (mnemon_t *mnemon)
373 home = getenv ("HOME");
377 xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
379 mnemon->categories_size = 0;
380 mnemon->num_categories = 0;
381 mnemon->categories = NULL;
383 mnemon->bins_size = 0;
384 mnemon->num_bins = 0;
387 mnemon->to_introduce = 10;
388 mnemon->to_master = 10;
389 mnemon->unlearned = 0;
390 mnemon->mastered = -1;
394 mnemon_fini (mnemon_t *mnemon)
398 for (i = 0; i < mnemon->num_bins; i++)
399 bin_fini (&mnemon->bins[i]);
402 for (i = 0; i < mnemon->num_categories; i++)
403 category_fini (&mnemon->categories[i]);
404 free (mnemon->categories);
406 free (mnemon->dir_name);
410 mnemon_categories_grow (mnemon_t *mnemon)
412 if (mnemon->categories_size)
413 mnemon->categories_size *= 2;
415 mnemon->categories_size = 1;
417 mnemon->categories = xrealloc (mnemon->categories,
418 mnemon->categories_size * sizeof (category_t));
421 /* Get a category by name if it exists */
423 mnemon_get_category_if_exists (mnemon_t *mnemon,
428 for (i = 0; i < mnemon->num_categories; i++)
429 if (strcmp (mnemon->categories[i].name, name) == 0)
430 return &mnemon->categories[i];
435 /* Get a category by name, creating new one if necessary. */
437 mnemon_get_category (mnemon_t *mnemon,
440 category_t *category;
442 category = mnemon_get_category_if_exists (mnemon, name);
446 mnemon_categories_grow (mnemon);
448 category = &mnemon->categories[mnemon->num_categories++];
450 category_init (category, name);
456 mnemon_bins_grow (mnemon_t *mnemon)
458 if (mnemon->bins_size)
459 mnemon->bins_size *= 2;
461 mnemon->bins_size = 1;
463 mnemon->bins = xrealloc (mnemon->bins,
464 mnemon->bins_size * sizeof (bin_t));
468 mnemon_get_bin (mnemon_t *mnemon,
474 for (i = 0; i < mnemon->num_bins; i++)
475 if (mnemon->bins[i].score == score)
476 return &mnemon->bins[i];
477 else if (mnemon->bins[i].score > score)
480 if (mnemon->num_bins == mnemon->bins_size)
481 mnemon_bins_grow (mnemon);
483 bin = &mnemon->bins[i];
485 /* Make room to insert new bin at its sorted location. */
486 if (i < mnemon->num_bins)
487 memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
490 bin_init (bin, score);
496 mnemon_remove_bin (mnemon_t *mnemon,
499 int i = bin - mnemon->bins;
503 memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
510 int len = strlen (s);
513 if (s[len - 1] == '\n')
518 trim_space (char *string)
523 while (*s && isspace (*s))
528 s = string + strlen (string) - 1;
529 while (s > string && isspace (*s)) {
538 mnemon_load_category (mnemon_t *mnemon,
542 char *line = NULL, *end;
543 size_t line_size = 0;
547 category_t *category;
550 path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
551 sprintf (path, "%s/%s", mnemon->dir_name, name);
553 file = fopen (path, "r");
555 fprintf (stderr, "Error: Failed to open %s: %s\n",
556 path, strerror (errno));
560 category = mnemon_get_category (mnemon, name);
562 #define READ_LINE do { \
563 bytes_read = getline (&line, &line_size, file); \
564 if (bytes_read == -1) \
572 char *name, *equal, *value;
574 /* Ignore blank lines */
579 /* An initial digit means we hit an item. Trigger the
580 * spaghetti machine. */
581 if (*line >= '0' && *line <= '9')
584 equal = strchr (line, '=');
586 fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
587 line, path, line_count);
595 name = trim_space (name);
596 value = trim_space (value);
598 if (strcmp (name, "order") == 0) {
599 if (strcmp (value, "sequential") == 0) {
600 category->order = CATEGORY_ORDER_SEQUENTIAL;
601 } else if (strcmp (value, "random") == 0) {
602 category->order = CATEGORY_ORDER_RANDOM;
604 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
605 value, path, line_count);
608 } else if (strcmp (name, "time") == 0) {
611 limit = strtod (value, &end);
612 while (isspace (*end))
615 category->time_limit = limit;
617 fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
618 value, path, line_count);
622 fprintf (stderr, "Unknown option %s at %s:%d\n",
623 name, path, line_count);
631 char *challenge, *response;
633 /* Ignore blank lines */
638 /* Read bin number */
640 score = strtol (line, &end, 10);
642 fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
643 line, path, line_count);
649 challenge = strdup (line);
655 category_add_item (category, score, challenge, response);
665 /* Resize category items to fit exactly. */
666 category->items_size = category->num_items;
667 category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
669 /* Now that the category is completely loaded, with stable
670 * pointers to every item, we can add each item to its appropriate
672 for (i = 0; i < category->num_items; i++) {
673 item_t *item = &category->items[i];
674 bin_t *bin = mnemon_get_bin (mnemon, item->score);
676 bin_add_item (bin, item);
681 mnemon_load (mnemon_t *mnemon)
684 struct dirent *dirent;
686 dir = opendir (mnemon->dir_name);
688 fprintf (stderr, "Error: Failed to open directory %s: %s\n",
689 mnemon->dir_name, strerror (errno));
694 dirent = readdir (dir);
698 if (dirent->d_type == DT_REG) {
699 /* Ignore files matching *~, (yes, this shouldn't be
700 * hard-coded in such an ad-hoc way, but there you go. */
701 if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
702 mnemon_load_category (mnemon, dirent->d_name);
710 mnemon_save (mnemon_t *mnemon)
713 char *filename, *lock_filename;
715 category_t *category;
717 for (i = 0; i < mnemon->num_categories; i++) {
718 category = &mnemon->categories[i];
720 xasprintf (&filename, "%s/%s",
721 mnemon->dir_name, category->name);
722 xasprintf (&lock_filename, "%s/.#%s",
723 mnemon->dir_name, category->name);
725 file = fopen (lock_filename, "w");
727 fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
728 lock_filename, strerror (errno));
732 category_print (category, file);
734 fsync (fileno (file));
737 err = rename (lock_filename, filename);
739 fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
740 lock_filename, filename, strerror (errno));
745 free (lock_filename);
749 /* Return a uniformly-distributed pseudo-random integer within the
752 * 0 <= result < num_values
755 rand_within (int num_values)
757 return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
760 /* Return an exponentially-distributed pseudo-random integer within
763 * 0 <= result < num_values
765 * The distribution is such that each successively larger value will
766 * occur with a probability of half of the previous value.
769 rand_within_exponential (int num_values)
772 static uint32_t mask = 0;
776 /* Optimize the constant case. */
786 while (mask > RAND_MAX)
793 if (ones == num_values)
801 /* Find the category to which an item belongs. */
803 mnemon_item_category (mnemon_t *mnemon,
806 category_t *category;
809 for (i = 0; i < mnemon->num_categories; i++) {
810 category = &mnemon->categories[i];
811 item_index = item - category->items;
812 if (item_index >= 0 && item_index < category->num_items)
819 typedef struct _item_in_category_closure
822 category_t *category;
823 } item_in_category_closure_t;
826 mnemon_item_in_category (void *closure, item_t *item)
828 item_in_category_closure_t *iicc = closure;
829 mnemon_t *mnemon = iicc->mnemon;
830 category_t *category = iicc->category;
832 return (mnemon_item_category (mnemon, item) == category);
835 typedef struct _item_in_category_of_length_closure
838 category_t *category;
840 } item_in_category_of_length_closure_t;
843 mnemon_item_in_category_of_length (void *closure, item_t *item)
845 item_in_category_of_length_closure_t *iicolc = closure;
846 mnemon_t *mnemon = iicolc->mnemon;
847 category_t *category = iicolc->category;
848 int length = iicolc->length;
850 if (mnemon_item_category (mnemon, item) != category)
853 return strlen (item->challenge) == length;
857 mnemon_select_item (mnemon_t *mnemon,
860 category_t **category_ret)
862 int bin_index, item_index;
865 category_t *category;
867 bin_index = rand_within_exponential (mnemon->num_bins);
868 bin = &mnemon->bins[bin_index];
870 /* The most intuitive understanding of the to_introduce counter is
871 * that it's tracking never-before-learned items as they are
872 * pulled from the bin with score 0. But that bin can become
873 * empty. So the refined rule is that we decrement to_introduce
874 * whenever we pull from the lowest-indexed bin with a
875 * non-negative score. */
876 if (mnemon->to_introduce && bin->score >=0 &&
877 (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
879 mnemon->to_introduce--;
882 item_index = rand_within (bin->num_items);
884 item = bin->items[item_index];
885 category = mnemon_item_category (mnemon, item);
887 if (bin->score == 0) {
888 if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
889 item = category_next_bin_zero_item (category);
891 item_index = bin_item_index (bin, item);
896 *item_index_ret = item_index;
897 *category_ret = category;
901 #define HISTOGRAM_ROW_FORMAT "%3d: %3d"
902 #define HISTOGRAM_BAR_WIDTH 63
905 print_histogram_bar (double size,
908 int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
909 static char const *boxes[8] = {
914 while (size > units_per_cell) {
916 size -= units_per_cell;
919 size /= units_per_cell;
923 else if (size > 6.5/8.0)
925 else if (size > 5.5/8.0)
927 else if (size > 4.5/8.0)
929 else if (size > 3.5/8.0)
931 else if (size > 2.5/8.0)
933 else if (size > 1.5/8.0)
935 else if (size > 0.5/8.0)
942 mnemon_print_histogram (mnemon_t *mnemon,
943 const char *category_name,
946 int i, last_score, max;
947 category_t *category = NULL;
950 item_match_predicate_t *predicate = NULL;
951 void *closure = NULL;
952 item_in_category_closure_t item_in_category;
953 item_in_category_of_length_closure_t item_in_category_of_length;
955 if (mnemon->num_bins == 0)
959 category = mnemon_get_category_if_exists (mnemon, category_name);
962 predicate = mnemon_item_in_category_of_length;
963 item_in_category_of_length.mnemon = mnemon;
964 item_in_category_of_length.category = category;
965 item_in_category_of_length.length = length;
966 closure = &item_in_category_of_length;
968 predicate = mnemon_item_in_category;
969 item_in_category.mnemon = mnemon;
970 item_in_category.category = category;
971 closure = &item_in_category;
976 for (i = 0; i < mnemon->num_bins; i++) {
977 num_items = bin_num_items_matching (&mnemon->bins[i],
979 if (i == 0 || num_items > max)
983 for (i = 0; i < mnemon->num_bins; i++) {
984 bin = &mnemon->bins[i];
986 while (bin->score - last_score > 1)
987 printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
988 num_items = bin_num_items_matching (bin,
990 printf (HISTOGRAM_ROW_FORMAT " ", bin->score, num_items);
991 print_histogram_bar (num_items, max);
992 last_score = bin->score;
997 mnemon_handle_command (mnemon_t *mnemon,
1002 switch (command[0]) {
1005 char *category = NULL;
1009 arg += strspn (arg, " \t");
1010 len = strcspn (arg, " \t");
1012 category = xstrndup (arg, len);
1014 arg += strspn (arg, " \t");
1016 length = atoi (arg);
1018 mnemon_print_histogram (mnemon, category, length);
1022 printf ("Unknown command: %s\n", command);
1028 mnemon_handle_response (mnemon_t *mnemon,
1032 const char *response,
1033 double response_time,
1038 correct = (strcmp (response, item->response) == 0);
1040 bin_remove_item (bin, item_index);
1042 /* If the bin is now empty, we must remove it. Also if we just
1043 * picked the last word we'll ever pick from the bin with
1044 * score 0, then we can remove that as well. */
1045 if (bin->num_items == 0 ||
1046 (bin->score == 0 && mnemon->to_introduce == 0))
1048 mnemon_remove_bin (mnemon, bin);
1052 (time_limit == 0.0 || response_time < time_limit))
1055 mnemon->to_master--;
1056 /* We reserve an item score of 0 for an item that has
1057 * never been asked. */
1058 if (item->score == 0) {
1060 mnemon->unlearned--;
1061 mnemon->to_master--;
1062 printf ("You got it!");
1063 } else if (item->score < 0) {
1064 printf ("Yes---just give me %d more.",
1066 } else if (item->score == 1) {
1067 printf ("On your first try, no less!");
1069 printf ("Masterful (%dx).", item->score);
1073 printf (" %s is the correct answer.",
1076 printf ("Correct, but not quite quick enough (%0.2f seconds---needed %0.2f seconds)\n",
1077 response_time, time_limit);
1078 /* Penalize an incorrect response by forcing the score
1080 if (item->score >= 0) {
1081 if (item->score > 0)
1082 printf (" Oops, you knew that, right? (%dx)\n ",
1084 mnemon->unlearned++;
1085 /* We add three here, (rather than just 2 to track the
1086 * change in the item's score below), as an extra
1087 * penalty. If the user is forgetting stuff learned
1088 * previously, then more time should be spent on mastering
1089 * than learning new items. */
1090 mnemon->to_master += item->score + 3;
1091 /* We go to -2 to force a little extra reinforcement
1092 * when re-learning an item, (otherwise, it will often
1093 * get asked again immediately where it is easy to get
1094 * a correct response without any learning). */
1098 mnemon->to_master++;
1103 if (mnemon->to_introduce)
1104 printf ("%d to come. ", mnemon->to_introduce);
1105 if (mnemon->unlearned)
1106 printf ("%d still unlearned. ", mnemon->unlearned);
1107 if (mnemon->to_introduce == 0 && mnemon->to_master > 0)
1108 printf ("%d items to master", mnemon->to_master);
1111 bin = mnemon_get_bin (mnemon, item->score);
1113 bin_add_item (bin, item);
1117 mnemon_do_challenges (mnemon_t *mnemon)
1122 category_t *category;
1126 /* Count the number of items with negative scores. */
1127 mnemon->unlearned = 0;
1128 for (i = 0; i < mnemon->num_bins; i++) {
1129 bin = &mnemon->bins[i];
1130 if (bin->score >= 0)
1132 mnemon->unlearned += bin->num_items;
1135 mnemon->to_introduce -= mnemon->unlearned;
1136 if (mnemon->to_introduce < 0)
1137 mnemon->to_introduce = 0;
1139 /* Get rid of bin with score of 0 if we aren't going to be
1140 * introducing anything from it. */
1141 if (mnemon->to_introduce == 0) {
1142 bin = mnemon_get_bin (mnemon, 0);
1143 mnemon_remove_bin (mnemon, bin);
1146 if (mnemon->unlearned) {
1147 printf ("You've got %d items to learn already. ", mnemon->unlearned);
1148 if (mnemon->to_introduce)
1149 printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
1152 printf ("Introducing %d new items.\n", mnemon->to_introduce);
1157 struct timeval start, end;
1159 mnemon_select_item (mnemon, &bin, &item_index, &category);
1160 item = bin->items[item_index];
1163 if (category->time_limit > 0.0) {
1164 response = readline ("The next one is timed. Press enter when ready:");
1168 printf ("%s\n", item->challenge);
1170 gettimeofday (&start, NULL);
1171 response = readline ("> ");
1172 gettimeofday (&end, NULL);
1174 /* Terminate on EOF */
1175 if (response == NULL) {
1180 if (response[0] == '/') {
1181 mnemon_handle_command (mnemon, response + 1);
1188 mnemon_handle_response (mnemon, bin, item_index,
1190 (end.tv_sec + end.tv_usec / 1e6) -
1191 (start.tv_sec + start.tv_usec / 1e6),
1192 category->time_limit);
1194 } while (mnemon->to_introduce ||
1195 mnemon->unlearned ||
1196 mnemon->to_master > 0);
1200 main (int argc, char *argv[])
1205 srand (time (NULL));
1207 mnemon_init (&mnemon);
1209 mnemon_load (&mnemon);
1211 mnemon_do_challenges (&mnemon);
1213 mnemon_save (&mnemon);
1215 mnemon_fini (&mnemon);
1217 mnemon_init (&mnemon);
1218 mnemon_load (&mnemon);
1220 printf ("Great job.\nHere are your current results:\n");
1221 mnemon_print_histogram (&mnemon, NULL, 0);
1222 response = readline ("Press enter to quit.\n");
1225 mnemon_fini (&mnemon);