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."
26 #include <sys/types.h>
32 #include <readline/readline.h>
33 #include <readline/history.h>
37 typedef struct _item {
50 typedef struct _category {
57 typedef struct _mnemon {
62 category_t *categories;
76 fprintf (stderr, "Error: out of memory\n");
84 xrealloc (void *ptr, size_t size)
88 ret = realloc (ptr, size);
90 fprintf (stderr, "Error: out of memory\n");
98 xstrdup (const char *s)
104 fprintf (stderr, "Error: out of memory\n");
112 xasprintf (char **strp, const char *fmt, ...)
118 ret = vasprintf (strp, fmt, ap);
122 fprintf (stderr, "Error: out of memory\n");
128 item_init (item_t *item,
130 const char *challenge,
131 const char *response)
135 item->challenge = xmalloc (strlen (challenge) + 1 +
136 strlen (response) + 1);
137 item->response = item->challenge + strlen (challenge) + 1;
139 strcpy (item->challenge, challenge);
140 strcpy (item->response, response);
144 item_fini (item_t *item)
146 /* item->response shares allocation with item->challenge, so
147 * doesn't require a separate call to free */
148 free (item->challenge);
152 category_init (category_t *category,
155 category->name = xstrdup (name);
157 category->items_size = 0;
158 category->num_items = 0;
159 category->items = NULL;
163 category_fini (category_t *category)
167 for (i = 0; i < category->num_items; i++)
168 item_fini (&category->items[i]);
170 free (category->items);
172 free (category->name);
176 category_grow (category_t *category)
178 if (category->items_size)
179 category->items_size *= 2;
181 category->items_size = 1;
183 category->items = xrealloc (category->items,
184 category->items_size * sizeof (item_t));
188 category_add_item (category_t *category,
190 const char *challenge,
191 const char *response)
195 if (category->num_items == category->items_size)
196 category_grow (category);
198 item = &category->items[category->num_items++];
200 item_init (item, score, challenge, response);
206 category_print (category_t *category,
212 for (i = 0; i < category->num_items; i++) {
213 item = &category->items[i];
215 fprintf (file, "\n");
216 fprintf (file, "%d\n%s\n%s\n",
224 bin_init (bin_t *bin,
235 bin_fini (bin_t *bin)
241 bin_grow (bin_t *bin)
244 bin->items_size *= 2;
248 bin->items = xrealloc (bin->items,
249 bin->items_size * sizeof (item_t*));
253 bin_add_item (bin_t *bin,
256 assert (item->score == bin->score);
258 if (bin->num_items == bin->items_size)
261 bin->items[bin->num_items++] = item;
265 bin_remove_item (bin_t *bin,
268 /* Replace the current item with the last item, (no need to shift
269 * any more than that since we don't care about the order of the
270 * items within a bin). */
273 bin->items[item_index] = bin->items[bin->num_items];
277 mnemon_init (mnemon_t *mnemon)
281 home = getenv ("HOME");
285 xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
287 mnemon->categories_size = 0;
288 mnemon->num_categories = 0;
289 mnemon->categories = NULL;
291 mnemon->bins_size = 0;
292 mnemon->num_bins = 0;
297 mnemon_fini (mnemon_t *mnemon)
301 for (i = 0; i < mnemon->num_bins; i++)
302 bin_fini (&mnemon->bins[i]);
305 for (i = 0; i < mnemon->num_categories; i++)
306 category_fini (&mnemon->categories[i]);
307 free (mnemon->categories);
309 free (mnemon->dir_name);
313 mnemon_categories_grow (mnemon_t *mnemon)
315 if (mnemon->categories_size)
316 mnemon->categories_size *= 2;
318 mnemon->categories_size = 1;
320 mnemon->categories = xrealloc (mnemon->categories,
321 mnemon->categories_size * sizeof (category_t));
325 mnemon_get_category (mnemon_t *mnemon,
329 category_t *category;
331 for (i = 0; i < mnemon->num_categories; i++)
332 if (strcmp (mnemon->categories[i].name, name) == 0)
333 return &mnemon->categories[i];
335 mnemon_categories_grow (mnemon);
337 category = &mnemon->categories[mnemon->num_categories++];
339 category_init (category, name);
345 mnemon_bins_grow (mnemon_t *mnemon)
347 if (mnemon->bins_size)
348 mnemon->bins_size *= 2;
350 mnemon->bins_size = 1;
352 mnemon->bins = xrealloc (mnemon->bins,
353 mnemon->bins_size * sizeof (bin_t));
357 mnemon_get_bin (mnemon_t *mnemon,
363 for (i = 0; i < mnemon->num_bins; i++)
364 if (mnemon->bins[i].score == score)
365 return &mnemon->bins[i];
366 else if (mnemon->bins[i].score > score)
369 if (mnemon->num_bins == mnemon->bins_size)
370 mnemon_bins_grow (mnemon);
372 bin = &mnemon->bins[i];
374 /* Make room to insert new bin at its sorted location. */
375 if (i < mnemon->num_bins)
376 memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
379 bin_init (bin, score);
385 mnemon_remove_bin (mnemon_t *mnemon,
388 int i = bin - mnemon->bins;
392 memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
399 int len = strlen (s);
402 if (s[len - 1] == '\n')
407 mnemon_load_category (mnemon_t *mnemon,
411 char *line = NULL, *end;
412 size_t line_size = 0;
416 category_t *category;
419 path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
420 sprintf (path, "%s/%s", mnemon->dir_name, name);
422 file = fopen (path, "r");
424 fprintf (stderr, "Error: Failed to open %s: %s\n",
425 path, strerror (errno));
429 category = mnemon_get_category (mnemon, name);
433 char *challenge, *response;
435 /* Read bin number (ignoring blank separator lines) */
437 bytes_read = getline (&line, &line_size, file);
438 if (bytes_read == -1)
442 } while (*line == '\0');
444 score = strtol (line, &end, 10);
446 fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
447 line, path, line_count);
452 bytes_read = getline (&line, &line_size, file);
453 if (bytes_read == -1)
457 challenge = strdup (line);
460 bytes_read = getline (&line, &line_size, file);
461 if (bytes_read == -1)
467 category_add_item (category, score, challenge, response);
477 /* Resize category items to fit exactly. */
478 category->items_size = category->num_items;
479 category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
481 /* Now that the category is completely loaded, with stable
482 * pointers to every item, we can add each item to its appropriate
484 for (i = 0; i < category->num_items; i++) {
485 item_t *item = &category->items[i];
486 bin_t *bin = mnemon_get_bin (mnemon, item->score);
488 bin_add_item (bin, item);
493 mnemon_load (mnemon_t *mnemon)
496 struct dirent *dirent;
498 dir = opendir (mnemon->dir_name);
500 fprintf (stderr, "Error: Failed to open directory %s: %s\n",
501 mnemon->dir_name, strerror (errno));
506 dirent = readdir (dir);
510 if (dirent->d_type == DT_REG) {
511 /* Ignore files matching *~, (yes, this shouldn't be
512 * hard-coded in such an ad-hoc way, but there you go. */
513 if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
514 mnemon_load_category (mnemon, dirent->d_name);
522 mnemon_save (mnemon_t *mnemon)
525 char *filename, *lock_filename;
527 category_t *category;
529 for (i = 0; i < mnemon->num_categories; i++) {
530 category = &mnemon->categories[i];
532 xasprintf (&filename, "%s/%s",
533 mnemon->dir_name, category->name);
534 xasprintf (&lock_filename, "%s/.#%s",
535 mnemon->dir_name, category->name);
537 file = fopen (lock_filename, "w");
539 fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
540 lock_filename, strerror (errno));
544 category_print (category, file);
548 err = rename (lock_filename, filename);
550 fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
551 lock_filename, filename, strerror (errno));
556 free (lock_filename);
560 /* Return a uniformly-distributed pseudo-random integer within the
563 * 0 <= result < num_values
566 rand_within (int num_values)
568 return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
571 /* Return an exponentially-distributed pseudo-random integer within
574 * 0 <= result < num_values
576 * The distribution is such that each successively larger value will
577 * occur with a probability of half of the previous value.
580 rand_within_exponential (int num_values)
583 static uint32_t mask = 0;
587 /* Optimize the constant case. */
597 while (mask > RAND_MAX)
604 if (ones == num_values)
613 mnemon_select_item (mnemon_t *mnemon,
620 bin_index = rand_within_exponential (mnemon->num_bins);
622 bin = &mnemon->bins[bin_index];
625 *item_index_ret = rand_within (bin->num_items);
629 mnemon_do_challenges (mnemon_t *mnemon,
638 int unlearned, mastered = 0;
641 /* Count the number of items with negative scores. */
643 for (i = 0; i < mnemon->num_bins; i++) {
644 bin = &mnemon->bins[i];
647 unlearned += bin->num_items;
650 to_introduce -= unlearned;
651 if (to_introduce < 0)
654 /* Get rid of bin with score of 0 if we aren't going to be
655 * introducing anything from it. */
656 if (to_introduce == 0) {
657 bin = mnemon_get_bin (mnemon, 0);
658 mnemon_remove_bin (mnemon, bin);
662 printf ("You've got %d items to learn already. ", unlearned);
664 printf ("I'll introduce %d more as we go.", to_introduce);
667 printf ("Introducing %d new items.\n", to_introduce);
672 mnemon_select_item (mnemon, &bin, &item_index);
677 item = bin->items[item_index];
679 printf ("%s\n", item->challenge);
681 response = readline ("> ");
682 if (response == NULL) {
687 correct = (strcmp (response, item->response) == 0);
689 bin_remove_item (bin, item_index);
691 /* If the bin is now empty, we must remove it. Also if we just
692 * picked the last word we'll ever pick from the bin with
693 * score 0, then we can remove that as well. */
694 if (bin->num_items == 0 ||
695 (bin->score == 0 && to_introduce == 0))
697 mnemon_remove_bin (mnemon, bin);
702 /* We reserve an item score of 0 for an item that has
703 * never been asked. */
704 if (item->score == 0) {
707 printf ("You got it!");
708 } else if (item->score < 0) {
709 printf ("Yes---just give me %d more.",
711 } else if (item->score == 1) {
712 printf ("On your first try, no less!");
714 printf ("Masterful (%dx).", item->score);
717 printf (" %s is the correct answer.",
719 /* Penalize an incorrect response by forcing the score
721 if (item->score >= 0) {
723 printf ( " Oops, you knew that, right?\n ");
726 /* We go to -2 to force a little extra reinforcement
727 * when re-learning an item, (otherwise, it will often
728 * get asked again immediately where it is easy to get
729 * a correct response without any learning). */
738 printf ("%d to come.", to_introduce);
739 if (to_introduce && unlearned)
742 printf ("%d still unlearned.", unlearned);
743 if (to_introduce == 0 && unlearned == 0) {
744 if (mastered < to_master)
745 printf ("%d items to master",
746 to_master - mastered);
748 printf ("Great job!");
753 bin = mnemon_get_bin (mnemon, item->score);
755 bin_add_item (bin, item);
756 } while (mastered <= to_master);
760 main (int argc, char *argv[])
763 int to_introduce = 3;
768 mnemon_init (&mnemon);
770 mnemon_load (&mnemon);
772 mnemon_do_challenges (&mnemon,
776 mnemon_save (&mnemon);
778 mnemon_fini (&mnemon);