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 {
51 typedef struct _category {
58 typedef struct _mnemon {
63 category_t *categories;
82 fprintf (stderr, "Error: out of memory\n");
90 xrealloc (void *ptr, size_t size)
94 ret = realloc (ptr, size);
96 fprintf (stderr, "Error: out of memory\n");
104 xstrdup (const char *s)
110 fprintf (stderr, "Error: out of memory\n");
118 xasprintf (char **strp, const char *fmt, ...)
124 ret = vasprintf (strp, fmt, ap);
128 fprintf (stderr, "Error: out of memory\n");
134 item_init (item_t *item,
136 const char *challenge,
137 const char *response)
141 item->challenge = xmalloc (strlen (challenge) + 1 +
142 strlen (response) + 1);
143 item->response = item->challenge + strlen (challenge) + 1;
145 strcpy (item->challenge, challenge);
146 strcpy (item->response, response);
150 item_fini (item_t *item)
152 /* item->response shares allocation with item->challenge, so
153 * doesn't require a separate call to free */
154 free (item->challenge);
158 category_init (category_t *category,
161 category->name = xstrdup (name);
163 category->items_size = 0;
164 category->num_items = 0;
165 category->items = NULL;
169 category_fini (category_t *category)
173 for (i = 0; i < category->num_items; i++)
174 item_fini (&category->items[i]);
176 free (category->items);
178 free (category->name);
182 category_grow (category_t *category)
184 if (category->items_size)
185 category->items_size *= 2;
187 category->items_size = 1;
189 category->items = xrealloc (category->items,
190 category->items_size * sizeof (item_t));
194 category_add_item (category_t *category,
196 const char *challenge,
197 const char *response)
201 if (category->num_items == category->items_size)
202 category_grow (category);
204 item = &category->items[category->num_items++];
206 item_init (item, score, challenge, response);
212 category_print (category_t *category,
218 for (i = 0; i < category->num_items; i++) {
219 item = &category->items[i];
221 fprintf (file, "\n");
222 fprintf (file, "%d\n%s\n%s\n",
230 bin_init (bin_t *bin,
241 bin_fini (bin_t *bin)
247 bin_grow (bin_t *bin)
250 bin->items_size *= 2;
254 bin->items = xrealloc (bin->items,
255 bin->items_size * sizeof (item_t*));
259 bin_add_item (bin_t *bin,
262 assert (item->score == bin->score);
264 if (bin->num_items == bin->items_size)
267 bin->items[bin->num_items++] = item;
271 bin_remove_item (bin_t *bin,
274 /* Replace the current item with the last item, (no need to shift
275 * any more than that since we don't care about the order of the
276 * items within a bin). */
279 bin->items[item_index] = bin->items[bin->num_items];
283 mnemon_init (mnemon_t *mnemon)
287 home = getenv ("HOME");
291 xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
293 mnemon->categories_size = 0;
294 mnemon->num_categories = 0;
295 mnemon->categories = NULL;
297 mnemon->bins_size = 0;
298 mnemon->num_bins = 0;
301 mnemon->to_introduce = 3;
302 mnemon->to_master = 10;
303 mnemon->unlearned = 0;
304 mnemon->mastered = 0;
308 mnemon_fini (mnemon_t *mnemon)
312 for (i = 0; i < mnemon->num_bins; i++)
313 bin_fini (&mnemon->bins[i]);
316 for (i = 0; i < mnemon->num_categories; i++)
317 category_fini (&mnemon->categories[i]);
318 free (mnemon->categories);
320 free (mnemon->dir_name);
324 mnemon_categories_grow (mnemon_t *mnemon)
326 if (mnemon->categories_size)
327 mnemon->categories_size *= 2;
329 mnemon->categories_size = 1;
331 mnemon->categories = xrealloc (mnemon->categories,
332 mnemon->categories_size * sizeof (category_t));
336 mnemon_get_category (mnemon_t *mnemon,
340 category_t *category;
342 for (i = 0; i < mnemon->num_categories; i++)
343 if (strcmp (mnemon->categories[i].name, name) == 0)
344 return &mnemon->categories[i];
346 mnemon_categories_grow (mnemon);
348 category = &mnemon->categories[mnemon->num_categories++];
350 category_init (category, name);
356 mnemon_bins_grow (mnemon_t *mnemon)
358 if (mnemon->bins_size)
359 mnemon->bins_size *= 2;
361 mnemon->bins_size = 1;
363 mnemon->bins = xrealloc (mnemon->bins,
364 mnemon->bins_size * sizeof (bin_t));
368 mnemon_get_bin (mnemon_t *mnemon,
374 for (i = 0; i < mnemon->num_bins; i++)
375 if (mnemon->bins[i].score == score)
376 return &mnemon->bins[i];
377 else if (mnemon->bins[i].score > score)
380 if (mnemon->num_bins == mnemon->bins_size)
381 mnemon_bins_grow (mnemon);
383 bin = &mnemon->bins[i];
385 /* Make room to insert new bin at its sorted location. */
386 if (i < mnemon->num_bins)
387 memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
390 bin_init (bin, score);
396 mnemon_remove_bin (mnemon_t *mnemon,
399 int i = bin - mnemon->bins;
403 memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
410 int len = strlen (s);
413 if (s[len - 1] == '\n')
418 mnemon_load_category (mnemon_t *mnemon,
422 char *line = NULL, *end;
423 size_t line_size = 0;
427 category_t *category;
430 path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
431 sprintf (path, "%s/%s", mnemon->dir_name, name);
433 file = fopen (path, "r");
435 fprintf (stderr, "Error: Failed to open %s: %s\n",
436 path, strerror (errno));
440 category = mnemon_get_category (mnemon, name);
444 char *challenge, *response;
446 /* Read bin number (ignoring blank separator lines) */
448 bytes_read = getline (&line, &line_size, file);
449 if (bytes_read == -1)
453 } while (*line == '\0');
455 score = strtol (line, &end, 10);
457 fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
458 line, path, line_count);
463 bytes_read = getline (&line, &line_size, file);
464 if (bytes_read == -1)
468 challenge = strdup (line);
471 bytes_read = getline (&line, &line_size, file);
472 if (bytes_read == -1)
478 category_add_item (category, score, challenge, response);
488 /* Resize category items to fit exactly. */
489 category->items_size = category->num_items;
490 category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
492 /* Now that the category is completely loaded, with stable
493 * pointers to every item, we can add each item to its appropriate
495 for (i = 0; i < category->num_items; i++) {
496 item_t *item = &category->items[i];
497 bin_t *bin = mnemon_get_bin (mnemon, item->score);
499 bin_add_item (bin, item);
504 mnemon_load (mnemon_t *mnemon)
507 struct dirent *dirent;
509 dir = opendir (mnemon->dir_name);
511 fprintf (stderr, "Error: Failed to open directory %s: %s\n",
512 mnemon->dir_name, strerror (errno));
517 dirent = readdir (dir);
521 if (dirent->d_type == DT_REG) {
522 /* Ignore files matching *~, (yes, this shouldn't be
523 * hard-coded in such an ad-hoc way, but there you go. */
524 if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
525 mnemon_load_category (mnemon, dirent->d_name);
533 mnemon_save (mnemon_t *mnemon)
536 char *filename, *lock_filename;
538 category_t *category;
540 for (i = 0; i < mnemon->num_categories; i++) {
541 category = &mnemon->categories[i];
543 xasprintf (&filename, "%s/%s",
544 mnemon->dir_name, category->name);
545 xasprintf (&lock_filename, "%s/.#%s",
546 mnemon->dir_name, category->name);
548 file = fopen (lock_filename, "w");
550 fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
551 lock_filename, strerror (errno));
555 category_print (category, file);
559 err = rename (lock_filename, filename);
561 fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
562 lock_filename, filename, strerror (errno));
567 free (lock_filename);
571 /* Return a uniformly-distributed pseudo-random integer within the
574 * 0 <= result < num_values
577 rand_within (int num_values)
579 return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
582 /* Return an exponentially-distributed pseudo-random integer within
585 * 0 <= result < num_values
587 * The distribution is such that each successively larger value will
588 * occur with a probability of half of the previous value.
591 rand_within_exponential (int num_values)
594 static uint32_t mask = 0;
598 /* Optimize the constant case. */
608 while (mask > RAND_MAX)
615 if (ones == num_values)
624 mnemon_select_item (mnemon_t *mnemon,
631 bin_index = rand_within_exponential (mnemon->num_bins);
633 bin = &mnemon->bins[bin_index];
636 *item_index_ret = rand_within (bin->num_items);
640 #define HISTOGRAM_ROW_FORMAT "%3d: %3d"
641 #define HISTOGRAM_BAR_WIDTH 63
644 print_histogram_bar (double size,
647 int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
648 static char const *boxes[8] = {
653 while (size > units_per_cell) {
655 size -= units_per_cell;
658 size /= units_per_cell;
662 else if (size > 6.5/8.0)
664 else if (size > 5.5/8.0)
666 else if (size > 4.5/8.0)
668 else if (size > 3.5/8.0)
670 else if (size > 2.5/8.0)
672 else if (size > 1.5/8.0)
674 else if (size > 0.5/8.0)
681 mnemon_print_histogram (mnemon_t *mnemon)
683 int i, last_score, max;
686 if (mnemon->num_bins == 0)
689 max = mnemon->bins[0].num_items;
690 for (i = 1; i < mnemon->num_bins; i++)
691 if (mnemon->bins[i].num_items > max)
692 max = mnemon->bins[i].num_items;
694 for (i = 0; i < mnemon->num_bins; i++) {
695 bin = &mnemon->bins[i];
697 while (bin->score - last_score > 1)
698 printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
699 printf (HISTOGRAM_ROW_FORMAT " ", bin->score, bin->num_items);
700 print_histogram_bar (bin->num_items, max);
701 last_score = bin->score;
706 mnemon_handle_command (mnemon_t *mnemon,
709 switch (command[0]) {
711 mnemon_print_histogram (mnemon);
714 printf ("Unknown command: %s\n", command);
720 mnemon_handle_response (mnemon_t *mnemon,
724 const char *response)
728 correct = (strcmp (response, item->response) == 0);
730 bin_remove_item (bin, item_index);
732 /* If the bin is now empty, we must remove it. Also if we just
733 * picked the last word we'll ever pick from the bin with
734 * score 0, then we can remove that as well. */
735 if (bin->num_items == 0 ||
736 (bin->score == 0 && mnemon->to_introduce == 0))
738 mnemon_remove_bin (mnemon, bin);
743 /* We reserve an item score of 0 for an item that has
744 * never been asked. */
745 if (item->score == 0) {
748 printf ("You got it!");
749 } else if (item->score < 0) {
750 printf ("Yes---just give me %d more.",
752 } else if (item->score == 1) {
753 printf ("On your first try, no less!");
755 printf ("Masterful (%dx).", item->score);
758 printf (" %s is the correct answer.",
760 /* Penalize an incorrect response by forcing the score
762 if (item->score >= 0) {
764 printf ( " Oops, you knew that, right?\n ");
766 mnemon->mastered = 0;
767 /* We go to -2 to force a little extra reinforcement
768 * when re-learning an item, (otherwise, it will often
769 * get asked again immediately where it is easy to get
770 * a correct response without any learning). */
778 if (mnemon->to_introduce)
779 printf ("%d to come.", mnemon->to_introduce);
780 if (mnemon->to_introduce && mnemon->unlearned)
782 if (mnemon->unlearned)
783 printf ("%d still unlearned.", mnemon->unlearned);
784 if (mnemon->to_introduce == 0 && mnemon->unlearned == 0) {
785 if (mnemon->mastered < mnemon->to_master)
786 printf ("%d items to master",
787 mnemon->to_master - mnemon->mastered);
789 printf ("Great job!");
794 bin = mnemon_get_bin (mnemon, item->score);
796 bin_add_item (bin, item);
800 mnemon_do_challenges (mnemon_t *mnemon)
808 /* Count the number of items with negative scores. */
809 mnemon->unlearned = 0;
810 for (i = 0; i < mnemon->num_bins; i++) {
811 bin = &mnemon->bins[i];
814 mnemon->unlearned += bin->num_items;
817 mnemon->to_introduce -= mnemon->unlearned;
818 if (mnemon->to_introduce < 0)
819 mnemon->to_introduce = 0;
821 /* Get rid of bin with score of 0 if we aren't going to be
822 * introducing anything from it. */
823 if (mnemon->to_introduce == 0) {
824 bin = mnemon_get_bin (mnemon, 0);
825 mnemon_remove_bin (mnemon, bin);
828 if (mnemon->unlearned) {
829 printf ("You've got %d items to learn already. ", mnemon->unlearned);
830 if (mnemon->to_introduce)
831 printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
834 printf ("Introducing %d new items.\n", mnemon->to_introduce);
839 mnemon_select_item (mnemon, &bin, &item_index);
840 item = bin->items[item_index];
843 mnemon->to_introduce--;
846 printf ("%s\n", item->challenge);
848 response = readline ("> ");
849 /* Terminate on EOF */
850 if (response == NULL) {
855 if (response[0] == '/')
856 mnemon_handle_command (mnemon, response + 1);
861 mnemon_handle_response (mnemon, bin, item_index,
863 } while (mnemon->mastered <= mnemon->to_master);
867 main (int argc, char *argv[])
873 mnemon_init (&mnemon);
875 mnemon_load (&mnemon);
877 mnemon_do_challenges (&mnemon);
879 mnemon_save (&mnemon);
881 mnemon_fini (&mnemon);