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 xasprintf (char **strp, const char *fmt, ...)
133 ret = vasprintf (strp, fmt, ap);
137 fprintf (stderr, "Error: out of memory\n");
143 item_init (item_t *item,
145 const char *challenge,
146 const char *response)
150 item->challenge = xmalloc (strlen (challenge) + 1 +
151 strlen (response) + 1);
152 item->response = item->challenge + strlen (challenge) + 1;
154 strcpy (item->challenge, challenge);
155 strcpy (item->response, response);
159 item_fini (item_t *item)
161 /* item->response shares allocation with item->challenge, so
162 * doesn't require a separate call to free */
163 free (item->challenge);
167 category_init (category_t *category,
170 category->name = xstrdup (name);
172 category->items_size = 0;
173 category->num_items = 0;
174 category->items = NULL;
175 category->order = CATEGORY_ORDER_RANDOM;
176 category->bin_zero_head = 0;
180 category_fini (category_t *category)
184 for (i = 0; i < category->num_items; i++)
185 item_fini (&category->items[i]);
187 free (category->items);
189 free (category->name);
193 category_grow (category_t *category)
195 if (category->items_size)
196 category->items_size *= 2;
198 category->items_size = 1;
200 category->items = xrealloc (category->items,
201 category->items_size * sizeof (item_t));
205 category_add_item (category_t *category,
207 const char *challenge,
208 const char *response)
212 if (category->num_items == category->items_size)
213 category_grow (category);
215 item = &category->items[category->num_items++];
217 item_init (item, score, challenge, response);
223 category_next_bin_zero_item (category_t *category)
225 int *i = &category->bin_zero_head;
227 for ( ; *i < category->num_items; *i = *i + 1)
228 if (category->items[*i].score == 0)
229 return &category->items[*i];
235 category_print (category_t *category,
241 fprintf (file, "order = %s\n\n",
242 category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
244 for (i = 0; i < category->num_items; i++) {
245 item = &category->items[i];
247 fprintf (file, "\n");
248 fprintf (file, "%d\n%s\n%s\n",
256 bin_init (bin_t *bin,
267 bin_fini (bin_t *bin)
273 bin_grow (bin_t *bin)
276 bin->items_size *= 2;
280 bin->items = xrealloc (bin->items,
281 bin->items_size * sizeof (item_t*));
285 bin_add_item (bin_t *bin,
288 assert (item->score == bin->score);
290 if (bin->num_items == bin->items_size)
293 bin->items[bin->num_items++] = item;
297 bin_remove_item (bin_t *bin,
300 /* Replace the current item with the last item, (no need to shift
301 * any more than that since we don't care about the order of the
302 * items within a bin). */
305 bin->items[item_index] = bin->items[bin->num_items];
308 /* Find the index for an item within a bin.
310 * XXX: This is currently a linear search, so is a potential
311 * performance problem.
314 bin_item_index (bin_t *bin,
319 for (i = 0; i < bin->num_items; i++)
320 if (bin->items[i] == item)
327 mnemon_init (mnemon_t *mnemon)
331 home = getenv ("HOME");
335 xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
337 mnemon->categories_size = 0;
338 mnemon->num_categories = 0;
339 mnemon->categories = NULL;
341 mnemon->bins_size = 0;
342 mnemon->num_bins = 0;
345 mnemon->to_introduce = 10;
346 mnemon->to_master = 0;
347 mnemon->unlearned = 0;
348 mnemon->mastered = -1;
352 mnemon_fini (mnemon_t *mnemon)
356 for (i = 0; i < mnemon->num_bins; i++)
357 bin_fini (&mnemon->bins[i]);
360 for (i = 0; i < mnemon->num_categories; i++)
361 category_fini (&mnemon->categories[i]);
362 free (mnemon->categories);
364 free (mnemon->dir_name);
368 mnemon_categories_grow (mnemon_t *mnemon)
370 if (mnemon->categories_size)
371 mnemon->categories_size *= 2;
373 mnemon->categories_size = 1;
375 mnemon->categories = xrealloc (mnemon->categories,
376 mnemon->categories_size * sizeof (category_t));
379 /* Get a category by name if it exists */
381 mnemon_get_category_if_exists (mnemon_t *mnemon,
386 for (i = 0; i < mnemon->num_categories; i++)
387 if (strcmp (mnemon->categories[i].name, name) == 0)
388 return &mnemon->categories[i];
393 /* Get a category by name, creating new one if necessary. */
395 mnemon_get_category (mnemon_t *mnemon,
398 category_t *category;
400 category = mnemon_get_category_if_exists (mnemon, name);
404 mnemon_categories_grow (mnemon);
406 category = &mnemon->categories[mnemon->num_categories++];
408 category_init (category, name);
414 mnemon_bins_grow (mnemon_t *mnemon)
416 if (mnemon->bins_size)
417 mnemon->bins_size *= 2;
419 mnemon->bins_size = 1;
421 mnemon->bins = xrealloc (mnemon->bins,
422 mnemon->bins_size * sizeof (bin_t));
426 mnemon_get_bin (mnemon_t *mnemon,
432 for (i = 0; i < mnemon->num_bins; i++)
433 if (mnemon->bins[i].score == score)
434 return &mnemon->bins[i];
435 else if (mnemon->bins[i].score > score)
438 if (mnemon->num_bins == mnemon->bins_size)
439 mnemon_bins_grow (mnemon);
441 bin = &mnemon->bins[i];
443 /* Make room to insert new bin at its sorted location. */
444 if (i < mnemon->num_bins)
445 memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
448 bin_init (bin, score);
454 mnemon_remove_bin (mnemon_t *mnemon,
457 int i = bin - mnemon->bins;
461 memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
468 int len = strlen (s);
471 if (s[len - 1] == '\n')
476 trim_space (char *string)
481 while (*s && isspace (*s))
486 s = string + strlen (string) - 1;
487 while (s > string && isspace (*s)) {
496 mnemon_load_category (mnemon_t *mnemon,
500 char *line = NULL, *end;
501 size_t line_size = 0;
505 category_t *category;
508 path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
509 sprintf (path, "%s/%s", mnemon->dir_name, name);
511 file = fopen (path, "r");
513 fprintf (stderr, "Error: Failed to open %s: %s\n",
514 path, strerror (errno));
518 category = mnemon_get_category (mnemon, name);
520 #define READ_LINE do { \
521 bytes_read = getline (&line, &line_size, file); \
522 if (bytes_read == -1) \
530 char *name, *equal, *value;
532 /* Ignore blank lines */
537 /* An initial digit means we hit an item. Trigger the
538 * spaghetti machine. */
539 if (*line >= '0' && *line <= '9')
542 equal = strchr (line, '=');
544 fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
545 line, path, line_count);
553 name = trim_space (name);
554 value = trim_space (value);
556 if (strcmp (name, "order") == 0) {
557 if (strcmp (value, "sequential") == 0) {
558 category->order = CATEGORY_ORDER_SEQUENTIAL;
559 } else if (strcmp (value, "random") == 0) {
560 category->order = CATEGORY_ORDER_RANDOM;
562 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
563 value, path, line_count);
567 fprintf (stderr, "Unknown option %s at %s:%d\n",
568 name, path, line_count);
576 char *challenge, *response;
578 /* Ignore blank lines */
583 /* Read bin number */
585 score = strtol (line, &end, 10);
587 fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
588 line, path, line_count);
594 challenge = strdup (line);
600 category_add_item (category, score, challenge, response);
610 /* Resize category items to fit exactly. */
611 category->items_size = category->num_items;
612 category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
614 /* Now that the category is completely loaded, with stable
615 * pointers to every item, we can add each item to its appropriate
617 for (i = 0; i < category->num_items; i++) {
618 item_t *item = &category->items[i];
619 bin_t *bin = mnemon_get_bin (mnemon, item->score);
621 bin_add_item (bin, item);
626 mnemon_load (mnemon_t *mnemon)
629 struct dirent *dirent;
631 dir = opendir (mnemon->dir_name);
633 fprintf (stderr, "Error: Failed to open directory %s: %s\n",
634 mnemon->dir_name, strerror (errno));
639 dirent = readdir (dir);
643 if (dirent->d_type == DT_REG) {
644 /* Ignore files matching *~, (yes, this shouldn't be
645 * hard-coded in such an ad-hoc way, but there you go. */
646 if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
647 mnemon_load_category (mnemon, dirent->d_name);
655 mnemon_save (mnemon_t *mnemon)
658 char *filename, *lock_filename;
660 category_t *category;
662 for (i = 0; i < mnemon->num_categories; i++) {
663 category = &mnemon->categories[i];
665 xasprintf (&filename, "%s/%s",
666 mnemon->dir_name, category->name);
667 xasprintf (&lock_filename, "%s/.#%s",
668 mnemon->dir_name, category->name);
670 file = fopen (lock_filename, "w");
672 fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
673 lock_filename, strerror (errno));
677 category_print (category, file);
681 err = rename (lock_filename, filename);
683 fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
684 lock_filename, filename, strerror (errno));
689 free (lock_filename);
693 /* Return a uniformly-distributed pseudo-random integer within the
696 * 0 <= result < num_values
699 rand_within (int num_values)
701 return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
704 /* Return an exponentially-distributed pseudo-random integer within
707 * 0 <= result < num_values
709 * The distribution is such that each successively larger value will
710 * occur with a probability of half of the previous value.
713 rand_within_exponential (int num_values)
716 static uint32_t mask = 0;
720 /* Optimize the constant case. */
730 while (mask > RAND_MAX)
737 if (ones == num_values)
745 /* Find the category to which an item belongs. */
747 mnemon_item_category (mnemon_t *mnemon,
750 category_t *category;
753 for (i = 0; i < mnemon->num_categories; i++) {
754 category = &mnemon->categories[i];
755 item_index = item - category->items;
756 if (item_index >= 0 && item_index < category->num_items)
763 /* Return the number of items in the bin from the given category (or
764 * from all categories if category == NULL) */
766 mnemon_bin_num_items_in_category (mnemon_t *mnemon,
768 category_t *category)
770 int i, num_items = 0;
772 if (category == NULL)
773 return bin->num_items;
775 for (i = 0; i < bin->num_items; i++)
776 if (mnemon_item_category (mnemon, bin->items[i]) == category)
783 mnemon_select_item (mnemon_t *mnemon,
787 int bin_index, item_index;
790 bin_index = rand_within_exponential (mnemon->num_bins);
792 bin = &mnemon->bins[bin_index];
794 item_index = rand_within (bin->num_items);
796 if (bin->score == 0) {
797 category_t *category;
800 item = bin->items[item_index];
802 category = mnemon_item_category (mnemon, item);
804 if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
805 item = category_next_bin_zero_item (category);
807 item_index = bin_item_index (bin, item);
812 *item_index_ret = item_index;
816 #define HISTOGRAM_ROW_FORMAT "%3d: %3d"
817 #define HISTOGRAM_BAR_WIDTH 63
820 print_histogram_bar (double size,
823 int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
824 static char const *boxes[8] = {
829 while (size > units_per_cell) {
831 size -= units_per_cell;
834 size /= units_per_cell;
838 else if (size > 6.5/8.0)
840 else if (size > 5.5/8.0)
842 else if (size > 4.5/8.0)
844 else if (size > 3.5/8.0)
846 else if (size > 2.5/8.0)
848 else if (size > 1.5/8.0)
850 else if (size > 0.5/8.0)
857 mnemon_print_histogram (mnemon_t *mnemon,
858 const char *category_name)
860 int i, last_score, max;
861 category_t *category = NULL;
865 if (mnemon->num_bins == 0)
869 category = mnemon_get_category_if_exists (mnemon, category_name);
871 for (i = 0; i < mnemon->num_bins; i++) {
872 num_items = mnemon_bin_num_items_in_category (mnemon,
875 if (i == 0 || num_items > max)
879 for (i = 0; i < mnemon->num_bins; i++) {
880 bin = &mnemon->bins[i];
882 while (bin->score - last_score > 1)
883 printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
884 num_items = mnemon_bin_num_items_in_category (mnemon,
886 printf (HISTOGRAM_ROW_FORMAT " ", bin->score, num_items);
887 print_histogram_bar (num_items, max);
888 last_score = bin->score;
893 mnemon_handle_command (mnemon_t *mnemon,
897 switch (command[0]) {
900 while (*arg && isspace (*arg))
904 mnemon_print_histogram (mnemon, arg);
907 printf ("Unknown command: %s\n", command);
913 mnemon_handle_response (mnemon_t *mnemon,
917 const char *response)
921 correct = (strcmp (response, item->response) == 0);
923 bin_remove_item (bin, item_index);
925 /* If the bin is now empty, we must remove it. Also if we just
926 * picked the last word we'll ever pick from the bin with
927 * score 0, then we can remove that as well. */
928 if (bin->num_items == 0 ||
929 (bin->score == 0 && mnemon->to_introduce == 0))
931 mnemon_remove_bin (mnemon, bin);
936 /* We reserve an item score of 0 for an item that has
937 * never been asked. */
938 if (item->score == 0) {
941 printf ("You got it!");
942 } else if (item->score < 0) {
943 printf ("Yes---just give me %d more.",
945 } else if (item->score == 1) {
946 printf ("On your first try, no less!");
948 printf ("Masterful (%dx).", item->score);
949 if (mnemon->to_master)
953 printf (" %s is the correct answer.",
955 /* Penalize an incorrect response by forcing the score
957 if (item->score >= 0) {
959 printf ( " Oops, you knew that, right?\n ");
961 /* We go to -2 to force a little extra reinforcement
962 * when re-learning an item, (otherwise, it will often
963 * get asked again immediately where it is easy to get
964 * a correct response without any learning). */
971 if (mnemon->to_introduce == 0 &&
972 mnemon->unlearned == 0 &&
973 mnemon->to_master == 0)
975 mnemon->to_master = 10;
976 mnemon->mastered = 0;
980 if (mnemon->to_introduce)
981 printf ("%d to come. ", mnemon->to_introduce);
982 if (mnemon->unlearned)
983 printf ("%d still unlearned. ", mnemon->unlearned);
984 if (mnemon->to_master) {
985 if (mnemon->mastered < mnemon->to_master)
986 printf ("%d items to master",
987 mnemon->to_master - mnemon->mastered);
989 printf ("Great job!");
993 bin = mnemon_get_bin (mnemon, item->score);
995 bin_add_item (bin, item);
999 mnemon_do_challenges (mnemon_t *mnemon)
1007 /* Count the number of items with negative scores. */
1008 mnemon->unlearned = 0;
1009 for (i = 0; i < mnemon->num_bins; i++) {
1010 bin = &mnemon->bins[i];
1011 if (bin->score >= 0)
1013 mnemon->unlearned += bin->num_items;
1016 mnemon->to_introduce -= mnemon->unlearned;
1017 if (mnemon->to_introduce < 0)
1018 mnemon->to_introduce = 0;
1020 /* Get rid of bin with score of 0 if we aren't going to be
1021 * introducing anything from it. */
1022 if (mnemon->to_introduce == 0) {
1023 bin = mnemon_get_bin (mnemon, 0);
1024 mnemon_remove_bin (mnemon, bin);
1027 if (mnemon->unlearned) {
1028 printf ("You've got %d items to learn already. ", mnemon->unlearned);
1029 if (mnemon->to_introduce)
1030 printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
1033 printf ("Introducing %d new items.\n", mnemon->to_introduce);
1038 mnemon_select_item (mnemon, &bin, &item_index);
1039 item = bin->items[item_index];
1041 if (bin->score == 0)
1042 mnemon->to_introduce--;
1045 printf ("%s\n", item->challenge);
1047 response = readline ("> ");
1048 /* Terminate on EOF */
1049 if (response == NULL) {
1054 if (response[0] == '/')
1055 mnemon_handle_command (mnemon, response + 1);
1060 mnemon_handle_response (mnemon, bin, item_index,
1062 } while (mnemon->mastered < mnemon->to_master);
1066 main (int argc, char *argv[])
1070 srand (time (NULL));
1072 mnemon_init (&mnemon);
1074 mnemon_load (&mnemon);
1076 mnemon_do_challenges (&mnemon);
1078 mnemon_save (&mnemon);
1080 mnemon_fini (&mnemon);