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>
33 #include <readline/readline.h>
34 #include <readline/history.h>
38 typedef struct _item {
52 CATEGORY_ORDER_RANDOM,
53 CATEGORY_ORDER_SEQUENTIAL
56 typedef struct _category {
62 /* Support sequential introduction of items from bin 0 */
63 category_order_t order;
67 typedef struct _mnemon {
72 category_t *categories;
91 fprintf (stderr, "Error: out of memory\n");
99 xrealloc (void *ptr, size_t size)
103 ret = realloc (ptr, size);
105 fprintf (stderr, "Error: out of memory\n");
113 xstrdup (const char *s)
119 fprintf (stderr, "Error: out of memory\n");
127 xstrndup (const char *s, size_t n)
131 ret = strndup (s, n);
133 fprintf (stderr, "Error: out of memory\n");
141 xasprintf (char **strp, const char *fmt, ...)
147 ret = vasprintf (strp, fmt, ap);
151 fprintf (stderr, "Error: out of memory\n");
157 item_init (item_t *item,
159 const char *challenge,
160 const char *response)
164 item->challenge = xmalloc (strlen (challenge) + 1 +
165 strlen (response) + 1);
166 item->response = item->challenge + strlen (challenge) + 1;
168 strcpy (item->challenge, challenge);
169 strcpy (item->response, response);
173 item_fini (item_t *item)
175 /* item->response shares allocation with item->challenge, so
176 * doesn't require a separate call to free */
177 free (item->challenge);
181 category_init (category_t *category,
184 category->name = xstrdup (name);
186 category->items_size = 0;
187 category->num_items = 0;
188 category->items = NULL;
189 category->order = CATEGORY_ORDER_RANDOM;
190 category->bin_zero_head = 0;
194 category_fini (category_t *category)
198 for (i = 0; i < category->num_items; i++)
199 item_fini (&category->items[i]);
201 free (category->items);
203 free (category->name);
207 category_grow (category_t *category)
209 if (category->items_size)
210 category->items_size *= 2;
212 category->items_size = 1;
214 category->items = xrealloc (category->items,
215 category->items_size * sizeof (item_t));
219 category_add_item (category_t *category,
221 const char *challenge,
222 const char *response)
226 if (category->num_items == category->items_size)
227 category_grow (category);
229 item = &category->items[category->num_items++];
231 item_init (item, score, challenge, response);
237 category_next_bin_zero_item (category_t *category)
239 int *i = &category->bin_zero_head;
241 for ( ; *i < category->num_items; *i = *i + 1)
242 if (category->items[*i].score == 0)
243 return &category->items[*i];
249 category_print (category_t *category,
255 fprintf (file, "order = %s\n\n",
256 category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
258 for (i = 0; i < category->num_items; i++) {
259 item = &category->items[i];
261 fprintf (file, "\n");
262 fprintf (file, "%d\n%s\n%s\n",
270 bin_init (bin_t *bin,
281 bin_fini (bin_t *bin)
287 bin_grow (bin_t *bin)
290 bin->items_size *= 2;
294 bin->items = xrealloc (bin->items,
295 bin->items_size * sizeof (item_t*));
299 bin_add_item (bin_t *bin,
302 assert (item->score == bin->score);
304 if (bin->num_items == bin->items_size)
307 bin->items[bin->num_items++] = item;
311 bin_remove_item (bin_t *bin,
314 /* Replace the current item with the last item, (no need to shift
315 * any more than that since we don't care about the order of the
316 * items within a bin). */
319 bin->items[item_index] = bin->items[bin->num_items];
322 /* Find the index for an item within a bin.
324 * XXX: This is currently a linear search, so is a potential
325 * performance problem.
328 bin_item_index (bin_t *bin,
333 for (i = 0; i < bin->num_items; i++)
334 if (bin->items[i] == item)
340 typedef int (item_match_predicate_t) (void *closure, item_t *item);
342 /* Return the number of items in the bin from the given category (or
343 * from all categories if category == NULL) */
345 bin_num_items_matching (bin_t *bin,
346 item_match_predicate_t *predicate,
349 int i, num_items = 0;
351 if (predicate == NULL)
352 return bin->num_items;
354 for (i = 0; i < bin->num_items; i++)
355 if ((predicate) (closure, bin->items[i]))
362 mnemon_init (mnemon_t *mnemon)
366 home = getenv ("HOME");
370 xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
372 mnemon->categories_size = 0;
373 mnemon->num_categories = 0;
374 mnemon->categories = NULL;
376 mnemon->bins_size = 0;
377 mnemon->num_bins = 0;
380 mnemon->to_introduce = 10;
381 mnemon->to_master = 0;
382 mnemon->unlearned = 0;
383 mnemon->mastered = -1;
387 mnemon_fini (mnemon_t *mnemon)
391 for (i = 0; i < mnemon->num_bins; i++)
392 bin_fini (&mnemon->bins[i]);
395 for (i = 0; i < mnemon->num_categories; i++)
396 category_fini (&mnemon->categories[i]);
397 free (mnemon->categories);
399 free (mnemon->dir_name);
403 mnemon_categories_grow (mnemon_t *mnemon)
405 if (mnemon->categories_size)
406 mnemon->categories_size *= 2;
408 mnemon->categories_size = 1;
410 mnemon->categories = xrealloc (mnemon->categories,
411 mnemon->categories_size * sizeof (category_t));
414 /* Get a category by name if it exists */
416 mnemon_get_category_if_exists (mnemon_t *mnemon,
421 for (i = 0; i < mnemon->num_categories; i++)
422 if (strcmp (mnemon->categories[i].name, name) == 0)
423 return &mnemon->categories[i];
428 /* Get a category by name, creating new one if necessary. */
430 mnemon_get_category (mnemon_t *mnemon,
433 category_t *category;
435 category = mnemon_get_category_if_exists (mnemon, name);
439 mnemon_categories_grow (mnemon);
441 category = &mnemon->categories[mnemon->num_categories++];
443 category_init (category, name);
449 mnemon_bins_grow (mnemon_t *mnemon)
451 if (mnemon->bins_size)
452 mnemon->bins_size *= 2;
454 mnemon->bins_size = 1;
456 mnemon->bins = xrealloc (mnemon->bins,
457 mnemon->bins_size * sizeof (bin_t));
461 mnemon_get_bin (mnemon_t *mnemon,
467 for (i = 0; i < mnemon->num_bins; i++)
468 if (mnemon->bins[i].score == score)
469 return &mnemon->bins[i];
470 else if (mnemon->bins[i].score > score)
473 if (mnemon->num_bins == mnemon->bins_size)
474 mnemon_bins_grow (mnemon);
476 bin = &mnemon->bins[i];
478 /* Make room to insert new bin at its sorted location. */
479 if (i < mnemon->num_bins)
480 memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
483 bin_init (bin, score);
489 mnemon_remove_bin (mnemon_t *mnemon,
492 int i = bin - mnemon->bins;
496 memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
503 int len = strlen (s);
506 if (s[len - 1] == '\n')
511 trim_space (char *string)
516 while (*s && isspace (*s))
521 s = string + strlen (string) - 1;
522 while (s > string && isspace (*s)) {
531 mnemon_load_category (mnemon_t *mnemon,
535 char *line = NULL, *end;
536 size_t line_size = 0;
540 category_t *category;
543 path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
544 sprintf (path, "%s/%s", mnemon->dir_name, name);
546 file = fopen (path, "r");
548 fprintf (stderr, "Error: Failed to open %s: %s\n",
549 path, strerror (errno));
553 category = mnemon_get_category (mnemon, name);
555 #define READ_LINE do { \
556 bytes_read = getline (&line, &line_size, file); \
557 if (bytes_read == -1) \
565 char *name, *equal, *value;
567 /* Ignore blank lines */
572 /* An initial digit means we hit an item. Trigger the
573 * spaghetti machine. */
574 if (*line >= '0' && *line <= '9')
577 equal = strchr (line, '=');
579 fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
580 line, path, line_count);
588 name = trim_space (name);
589 value = trim_space (value);
591 if (strcmp (name, "order") == 0) {
592 if (strcmp (value, "sequential") == 0) {
593 category->order = CATEGORY_ORDER_SEQUENTIAL;
594 } else if (strcmp (value, "random") == 0) {
595 category->order = CATEGORY_ORDER_RANDOM;
597 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
598 value, path, line_count);
602 fprintf (stderr, "Unknown option %s at %s:%d\n",
603 name, path, line_count);
611 char *challenge, *response;
613 /* Ignore blank lines */
618 /* Read bin number */
620 score = strtol (line, &end, 10);
622 fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
623 line, path, line_count);
629 challenge = strdup (line);
635 category_add_item (category, score, challenge, response);
645 /* Resize category items to fit exactly. */
646 category->items_size = category->num_items;
647 category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
649 /* Now that the category is completely loaded, with stable
650 * pointers to every item, we can add each item to its appropriate
652 for (i = 0; i < category->num_items; i++) {
653 item_t *item = &category->items[i];
654 bin_t *bin = mnemon_get_bin (mnemon, item->score);
656 bin_add_item (bin, item);
661 mnemon_load (mnemon_t *mnemon)
664 struct dirent *dirent;
666 dir = opendir (mnemon->dir_name);
668 fprintf (stderr, "Error: Failed to open directory %s: %s\n",
669 mnemon->dir_name, strerror (errno));
674 dirent = readdir (dir);
678 if (dirent->d_type == DT_REG) {
679 /* Ignore files matching *~, (yes, this shouldn't be
680 * hard-coded in such an ad-hoc way, but there you go. */
681 if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
682 mnemon_load_category (mnemon, dirent->d_name);
690 mnemon_save (mnemon_t *mnemon)
693 char *filename, *lock_filename;
695 category_t *category;
697 for (i = 0; i < mnemon->num_categories; i++) {
698 category = &mnemon->categories[i];
700 xasprintf (&filename, "%s/%s",
701 mnemon->dir_name, category->name);
702 xasprintf (&lock_filename, "%s/.#%s",
703 mnemon->dir_name, category->name);
705 file = fopen (lock_filename, "w");
707 fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
708 lock_filename, strerror (errno));
712 category_print (category, file);
716 err = rename (lock_filename, filename);
718 fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
719 lock_filename, filename, strerror (errno));
724 free (lock_filename);
728 /* Return a uniformly-distributed pseudo-random integer within the
731 * 0 <= result < num_values
734 rand_within (int num_values)
736 return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
739 /* Return an exponentially-distributed pseudo-random integer within
742 * 0 <= result < num_values
744 * The distribution is such that each successively larger value will
745 * occur with a probability of half of the previous value.
748 rand_within_exponential (int num_values)
751 static uint32_t mask = 0;
755 /* Optimize the constant case. */
765 while (mask > RAND_MAX)
772 if (ones == num_values)
780 /* Find the category to which an item belongs. */
782 mnemon_item_category (mnemon_t *mnemon,
785 category_t *category;
788 for (i = 0; i < mnemon->num_categories; i++) {
789 category = &mnemon->categories[i];
790 item_index = item - category->items;
791 if (item_index >= 0 && item_index < category->num_items)
798 typedef struct _item_in_category_closure
801 category_t *category;
802 } item_in_category_closure_t;
805 mnemon_item_in_category (void *closure, item_t *item)
807 item_in_category_closure_t *iicc = closure;
808 mnemon_t *mnemon = iicc->mnemon;
809 category_t *category = iicc->category;
811 return (mnemon_item_category (mnemon, item) == category);
814 typedef struct _item_in_category_of_length_closure
817 category_t *category;
819 } item_in_category_of_length_closure_t;
822 mnemon_item_in_category_of_length (void *closure, item_t *item)
824 item_in_category_of_length_closure_t *iicolc = closure;
825 mnemon_t *mnemon = iicolc->mnemon;
826 category_t *category = iicolc->category;
827 int length = iicolc->length;
829 if (mnemon_item_category (mnemon, item) != category)
832 return strlen (item->challenge) == length;
836 mnemon_select_item (mnemon_t *mnemon,
840 int bin_index, item_index;
843 bin_index = rand_within_exponential (mnemon->num_bins);
845 bin = &mnemon->bins[bin_index];
847 item_index = rand_within (bin->num_items);
849 if (bin->score == 0) {
850 category_t *category;
853 item = bin->items[item_index];
855 category = mnemon_item_category (mnemon, item);
857 if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
858 item = category_next_bin_zero_item (category);
860 item_index = bin_item_index (bin, item);
865 *item_index_ret = item_index;
869 #define HISTOGRAM_ROW_FORMAT "%3d: %3d"
870 #define HISTOGRAM_BAR_WIDTH 63
873 print_histogram_bar (double size,
876 int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
877 static char const *boxes[8] = {
882 while (size > units_per_cell) {
884 size -= units_per_cell;
887 size /= units_per_cell;
891 else if (size > 6.5/8.0)
893 else if (size > 5.5/8.0)
895 else if (size > 4.5/8.0)
897 else if (size > 3.5/8.0)
899 else if (size > 2.5/8.0)
901 else if (size > 1.5/8.0)
903 else if (size > 0.5/8.0)
910 mnemon_print_histogram (mnemon_t *mnemon,
911 const char *category_name,
914 int i, last_score, max;
915 category_t *category = NULL;
918 item_match_predicate_t *predicate = NULL;
919 void *closure = NULL;
920 item_in_category_closure_t item_in_category;
921 item_in_category_of_length_closure_t item_in_category_of_length;
923 if (mnemon->num_bins == 0)
927 category = mnemon_get_category_if_exists (mnemon, category_name);
930 predicate = mnemon_item_in_category_of_length;
931 item_in_category_of_length.mnemon = mnemon;
932 item_in_category_of_length.category = category;
933 item_in_category_of_length.length = length;
934 closure = &item_in_category_of_length;
936 predicate = mnemon_item_in_category;
937 item_in_category.mnemon = mnemon;
938 item_in_category.category = category;
939 closure = &item_in_category;
944 for (i = 0; i < mnemon->num_bins; i++) {
945 num_items = bin_num_items_matching (&mnemon->bins[i],
947 if (i == 0 || num_items > max)
951 for (i = 0; i < mnemon->num_bins; i++) {
952 bin = &mnemon->bins[i];
954 while (bin->score - last_score > 1)
955 printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
956 num_items = bin_num_items_matching (bin,
958 printf (HISTOGRAM_ROW_FORMAT " ", bin->score, num_items);
959 print_histogram_bar (num_items, max);
960 last_score = bin->score;
965 mnemon_handle_command (mnemon_t *mnemon,
970 switch (command[0]) {
973 char *category = NULL;
977 arg += strspn (arg, " \t");
978 len = strcspn (arg, " \t");
980 category = xstrndup (arg, len);
982 arg += strspn (arg, " \t");
986 mnemon_print_histogram (mnemon, category, length);
990 printf ("Unknown command: %s\n", command);
996 mnemon_handle_response (mnemon_t *mnemon,
1000 const char *response)
1004 correct = (strcmp (response, item->response) == 0);
1006 bin_remove_item (bin, item_index);
1008 /* If the bin is now empty, we must remove it. Also if we just
1009 * picked the last word we'll ever pick from the bin with
1010 * score 0, then we can remove that as well. */
1011 if (bin->num_items == 0 ||
1012 (bin->score == 0 && mnemon->to_introduce == 0))
1014 mnemon_remove_bin (mnemon, bin);
1019 /* We reserve an item score of 0 for an item that has
1020 * never been asked. */
1021 if (item->score == 0) {
1023 mnemon->unlearned--;
1024 printf ("You got it!");
1025 } else if (item->score < 0) {
1026 printf ("Yes---just give me %d more.",
1028 } else if (item->score == 1) {
1029 printf ("On your first try, no less!");
1031 printf ("Masterful (%dx).", item->score);
1032 if (mnemon->to_master)
1036 printf (" %s is the correct answer.",
1038 /* Penalize an incorrect response by forcing the score
1040 if (item->score >= 0) {
1041 if (item->score > 0)
1042 printf ( " Oops, you knew that, right?\n ");
1043 mnemon->unlearned++;
1044 /* We go to -2 to force a little extra reinforcement
1045 * when re-learning an item, (otherwise, it will often
1046 * get asked again immediately where it is easy to get
1047 * a correct response without any learning). */
1054 if (mnemon->to_introduce == 0 &&
1055 mnemon->unlearned == 0 &&
1056 mnemon->to_master == 0)
1058 mnemon->to_master = 10;
1059 mnemon->mastered = 0;
1063 if (mnemon->to_introduce)
1064 printf ("%d to come. ", mnemon->to_introduce);
1065 if (mnemon->unlearned)
1066 printf ("%d still unlearned. ", mnemon->unlearned);
1067 if (mnemon->to_master) {
1068 if (mnemon->mastered < mnemon->to_master)
1069 printf ("%d items to master",
1070 mnemon->to_master - mnemon->mastered);
1072 printf ("Great job!");
1076 bin = mnemon_get_bin (mnemon, item->score);
1078 bin_add_item (bin, item);
1082 mnemon_do_challenges (mnemon_t *mnemon)
1090 /* Count the number of items with negative scores. */
1091 mnemon->unlearned = 0;
1092 for (i = 0; i < mnemon->num_bins; i++) {
1093 bin = &mnemon->bins[i];
1094 if (bin->score >= 0)
1096 mnemon->unlearned += bin->num_items;
1099 mnemon->to_introduce -= mnemon->unlearned;
1100 if (mnemon->to_introduce < 0)
1101 mnemon->to_introduce = 0;
1103 /* Get rid of bin with score of 0 if we aren't going to be
1104 * introducing anything from it. */
1105 if (mnemon->to_introduce == 0) {
1106 bin = mnemon_get_bin (mnemon, 0);
1107 mnemon_remove_bin (mnemon, bin);
1110 if (mnemon->unlearned) {
1111 printf ("You've got %d items to learn already. ", mnemon->unlearned);
1112 if (mnemon->to_introduce)
1113 printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
1116 printf ("Introducing %d new items.\n", mnemon->to_introduce);
1121 mnemon_select_item (mnemon, &bin, &item_index);
1122 item = bin->items[item_index];
1124 if (bin->score == 0)
1125 mnemon->to_introduce--;
1128 printf ("%s\n", item->challenge);
1130 response = readline ("> ");
1131 /* Terminate on EOF */
1132 if (response == NULL) {
1137 if (response[0] == '/')
1138 mnemon_handle_command (mnemon, response + 1);
1143 mnemon_handle_response (mnemon, bin, item_index,
1145 } while (mnemon->mastered < mnemon->to_master);
1149 main (int argc, char *argv[])
1153 srand (time (NULL));
1155 mnemon_init (&mnemon);
1157 mnemon_load (&mnemon);
1159 mnemon_do_challenges (&mnemon);
1161 mnemon_save (&mnemon);
1163 mnemon_fini (&mnemon);