]> git.cworth.org Git - mnemon/blob - mnemon.c
Macro-ify some repeated code from parsing
[mnemon] / mnemon.c
1 /*
2  * Copyright © 2006 Carl Worth
3  *
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)
7  * any later version.
8  *
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.
13  *
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."
17  */
18
19 /* for asprintf */
20 #define _GNU_SOURCE
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <stdarg.h>
24 #include <stdint.h>
25 #include <math.h>
26
27 #include <sys/types.h>
28 #include <dirent.h>
29 #include <errno.h>
30 #include <string.h>
31 #include <assert.h>
32
33 #include <readline/readline.h>
34 #include <readline/history.h>
35
36 typedef int bool_t;
37
38 typedef struct _item {
39     int score;
40     char *challenge;
41     char *response;
42 } item_t;
43
44 typedef struct _bin {
45     int score;
46     int items_size;
47     int num_items;
48     item_t **items;
49 } bin_t;
50
51 typedef struct _category {
52     char *name;
53     int items_size;
54     int num_items;
55     item_t *items;
56 } category_t;
57
58 typedef struct _mnemon {
59     char *dir_name;
60
61     int categories_size;
62     int num_categories;
63     category_t *categories;
64
65     int bins_size;
66     int num_bins;
67     bin_t *bins;
68
69     int to_introduce;
70     int to_master;
71     int unlearned;
72     int mastered;
73 } mnemon_t;
74
75 static void *
76 xmalloc (size_t size)
77 {
78     void *ret;
79
80     ret = malloc (size);
81     if (ret == NULL) {
82         fprintf (stderr, "Error: out of memory\n");
83         exit (1);
84     }
85
86     return ret;
87 }
88
89 static void *
90 xrealloc (void *ptr, size_t size)
91 {
92     void *ret;
93
94     ret = realloc (ptr, size);
95     if (ret == NULL) {
96         fprintf (stderr, "Error: out of memory\n");
97         exit (1);
98     }
99
100     return ret;
101 }
102
103 static char *
104 xstrdup (const char *s)
105 {
106     char *ret;
107
108     ret = strdup (s);
109     if (s == NULL) {
110         fprintf (stderr, "Error: out of memory\n");
111         exit (1);
112     }
113
114     return ret;
115 }
116
117 static void
118 xasprintf (char **strp, const char *fmt, ...)
119 {
120     va_list ap;
121     int ret;
122
123     va_start (ap, fmt);
124     ret = vasprintf (strp, fmt, ap);
125     va_end (ap);
126
127     if (ret < 0) {
128         fprintf (stderr, "Error: out of memory\n");
129         exit (1);
130     }
131 }
132
133 static void
134 item_init (item_t       *item,
135            int           score,
136            const char   *challenge,
137            const char   *response)
138 {
139     item->score = score;
140
141     item->challenge = xmalloc (strlen (challenge) + 1 +
142                                strlen (response) + 1);
143     item->response = item->challenge + strlen (challenge) + 1;
144
145     strcpy (item->challenge, challenge);
146     strcpy (item->response, response);
147 }
148
149 static void
150 item_fini (item_t *item)
151 {
152     /* item->response shares allocation with item->challenge, so
153      * doesn't require a separate call to free */
154     free (item->challenge);
155 }
156
157 static void
158 category_init (category_t *category,
159                const char *name)
160 {
161     category->name = xstrdup (name);
162     
163     category->items_size = 0;
164     category->num_items = 0;
165     category->items = NULL;
166 }
167
168 static void
169 category_fini (category_t *category)
170 {
171     int i;
172
173     for (i = 0; i < category->num_items; i++)
174         item_fini (&category->items[i]);
175
176     free (category->items);
177
178     free (category->name);
179 }
180
181 static void
182 category_grow (category_t *category)
183 {
184     if (category->items_size)
185         category->items_size *= 2;
186     else
187         category->items_size = 1;
188
189     category->items = xrealloc (category->items,
190                                 category->items_size * sizeof (item_t));
191 }
192
193 static item_t *
194 category_add_item (category_t   *category,
195                    int           score,
196                    const char   *challenge,
197                    const char   *response)
198 {
199     item_t *item;
200
201     if (category->num_items == category->items_size)
202         category_grow (category);
203
204     item = &category->items[category->num_items++];
205
206     item_init (item, score, challenge, response);
207
208     return item;
209 }
210
211 static void
212 category_print (category_t      *category,
213                 FILE            *file)
214 {
215     int i;
216     item_t *item;
217
218     for (i = 0; i < category->num_items; i++) {
219         item = &category->items[i];
220         if (i != 0)
221             fprintf (file, "\n");
222         fprintf (file, "%d\n%s\n%s\n",
223                  item->score,
224                  item->challenge,
225                  item->response);
226     }
227 }
228
229 static void
230 bin_init (bin_t *bin,
231           int    score)
232 {
233     bin->score = score;
234
235     bin->items_size = 0;
236     bin->num_items = 0;
237     bin->items = NULL;
238 }
239
240 static void
241 bin_fini (bin_t *bin)
242 {
243     free (bin->items);
244 }
245
246 static void
247 bin_grow (bin_t *bin)
248 {
249     if (bin->items_size)
250         bin->items_size *= 2;
251     else
252         bin->items_size = 1;
253
254     bin->items = xrealloc (bin->items,
255                            bin->items_size * sizeof (item_t*));
256 }
257
258 static void
259 bin_add_item (bin_t     *bin,
260               item_t    *item)
261 {
262     assert (item->score == bin->score);
263
264     if (bin->num_items == bin->items_size)
265         bin_grow (bin);
266
267     bin->items[bin->num_items++] = item;
268 }
269
270 static void
271 bin_remove_item (bin_t  *bin,
272                  int     item_index)
273 {
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). */
277     bin->num_items--;
278     if (bin->num_items)
279         bin->items[item_index] = bin->items[bin->num_items];
280 }
281
282 static void
283 mnemon_init (mnemon_t *mnemon)
284 {
285     char *home;
286
287     home = getenv ("HOME");
288     if (home == NULL)
289         home = "";
290
291     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
292
293     mnemon->categories_size = 0;
294     mnemon->num_categories = 0;
295     mnemon->categories = NULL;
296
297     mnemon->bins_size = 0;
298     mnemon->num_bins = 0;
299     mnemon->bins = NULL;
300
301     mnemon->to_introduce = 3;
302     mnemon->to_master = 0;
303     mnemon->unlearned = 0;
304     mnemon->mastered = -1;
305 }
306
307 static void
308 mnemon_fini (mnemon_t *mnemon)
309 {
310     int i;
311
312     for (i = 0; i < mnemon->num_bins; i++)
313         bin_fini (&mnemon->bins[i]);
314     free (mnemon->bins);
315
316     for (i = 0; i < mnemon->num_categories; i++)
317         category_fini (&mnemon->categories[i]);
318     free (mnemon->categories);
319
320     free (mnemon->dir_name);
321 }
322
323 static void
324 mnemon_categories_grow (mnemon_t *mnemon)
325 {
326     if (mnemon->categories_size)
327         mnemon->categories_size *= 2;
328     else
329         mnemon->categories_size = 1;
330
331     mnemon->categories = xrealloc (mnemon->categories,
332                                    mnemon->categories_size * sizeof (category_t));
333 }
334
335 static category_t *
336 mnemon_get_category (mnemon_t   *mnemon,
337                      const char *name)
338 {
339     int i;
340     category_t *category;
341
342     for (i = 0; i < mnemon->num_categories; i++)
343         if (strcmp (mnemon->categories[i].name, name) == 0)
344             return &mnemon->categories[i];
345
346     mnemon_categories_grow (mnemon);
347
348     category = &mnemon->categories[mnemon->num_categories++];
349
350     category_init (category, name);
351
352     return category;
353 }
354
355 static void
356 mnemon_bins_grow (mnemon_t *mnemon)
357 {
358     if (mnemon->bins_size)
359         mnemon->bins_size *= 2;
360     else
361         mnemon->bins_size = 1;
362
363     mnemon->bins = xrealloc (mnemon->bins,
364                              mnemon->bins_size * sizeof (bin_t));
365 }
366
367 static bin_t *
368 mnemon_get_bin (mnemon_t        *mnemon,
369                 int              score)
370 {
371     int i;
372     bin_t *bin;
373
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)
378             break;
379
380     if (mnemon->num_bins == mnemon->bins_size)
381         mnemon_bins_grow (mnemon);
382
383     bin = &mnemon->bins[i];
384
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));
388     mnemon->num_bins++;
389
390     bin_init (bin, score);
391
392     return bin;
393 }
394
395 static void
396 mnemon_remove_bin (mnemon_t     *mnemon,
397                    bin_t        *bin)
398 {
399     int i = bin - mnemon->bins;
400
401     bin_fini (bin);
402
403     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
404     mnemon->num_bins--;
405 }
406
407 static void
408 chomp (char *s)
409 {
410     int len = strlen (s);
411     if (len == 0)
412         return;
413     if (s[len - 1] == '\n')
414         s[len - 1] = '\0';
415 }
416
417 static void
418 mnemon_load_category (mnemon_t          *mnemon,
419                       const char        *name)
420 {
421     FILE *file;
422     char *line = NULL, *end;
423     size_t line_size = 0;
424     ssize_t bytes_read;
425     int line_count = 0;
426     char *path;
427     category_t *category;
428     int i;
429
430     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
431     sprintf (path, "%s/%s", mnemon->dir_name, name);
432
433     file = fopen (path, "r");
434     if (file == NULL) {
435         fprintf (stderr, "Error: Failed to open %s: %s\n",
436                  path, strerror (errno));
437         exit (1);
438     }
439
440     category = mnemon_get_category (mnemon, name);
441
442 #define READ_LINE do {                                  \
443     bytes_read = getline (&line, &line_size, file);     \
444     if (bytes_read == -1)                               \
445         goto END_OF_FILE;                               \
446     line_count++;                                       \
447     chomp (line);                                       \
448 } while (0)
449
450     while (1) {
451         int score;
452         char *challenge, *response;
453
454         /* Ignore blank lines */
455         READ_LINE;
456         if (*line == '\0')
457             continue;
458
459         /* Read bin number */
460         score = strtol (line, &end, 10);
461         if (*end != '\0') {
462             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
463                      line, path, line_count);
464             exit (1);
465         }
466
467         /* Read challenge */
468         READ_LINE;
469         challenge = strdup (line);
470
471         /* Read response */
472         READ_LINE;
473         response = line;
474
475         category_add_item (category, score, challenge, response);
476
477         free (challenge);
478     }
479   END_OF_FILE:
480
481     free (line);
482     fclose (file);
483     free (path);
484
485     /* Resize category items to fit exactly. */
486     category->items_size = category->num_items;
487     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
488
489     /* Now that the category is completely loaded, with stable
490      * pointers to every item, we can add each item to its appropriate
491      * bin. */
492     for (i = 0; i < category->num_items; i++) {
493         item_t *item = &category->items[i];
494         bin_t *bin = mnemon_get_bin (mnemon, item->score);
495
496         bin_add_item (bin, item);
497     }
498 }
499
500 static void
501 mnemon_load (mnemon_t *mnemon)
502 {
503     DIR *dir;
504     struct dirent *dirent;
505
506     dir = opendir (mnemon->dir_name);
507     if (dir == NULL) {
508         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
509                  mnemon->dir_name, strerror (errno));
510         exit (1);
511     }
512
513     while (1) {
514         dirent = readdir (dir);
515         if (dirent == NULL)
516             break;
517
518         if (dirent->d_type == DT_REG) {
519             /* Ignore files matching *~, (yes, this shouldn't be
520              * hard-coded in such an ad-hoc way, but there you go. */
521             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
522                 mnemon_load_category (mnemon, dirent->d_name);
523         }
524     }
525
526     closedir (dir);
527 }
528
529 static void
530 mnemon_save (mnemon_t *mnemon)
531 {
532     int i, err;
533     char *filename, *lock_filename;
534     FILE *file;
535     category_t *category;
536
537     for (i = 0; i < mnemon->num_categories; i++) {
538         category = &mnemon->categories[i];
539
540         xasprintf (&filename, "%s/%s",
541                    mnemon->dir_name, category->name);
542         xasprintf (&lock_filename, "%s/.#%s",
543                    mnemon->dir_name, category->name);
544
545         file = fopen (lock_filename, "w");
546         if (file == NULL) {
547             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
548                      lock_filename, strerror (errno));
549             continue;
550         }
551
552         category_print (category, file);
553
554         fclose (file);
555
556         err = rename (lock_filename, filename);
557         if (err < 0) {
558             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
559                      lock_filename, filename, strerror (errno));
560             continue;
561         }
562
563         free (filename);
564         free (lock_filename);
565     }
566 }
567
568 /* Return a uniformly-distributed pseudo-random integer within the
569  * range:
570  *
571  *      0 <= result < num_values
572  */
573 static int
574 rand_within (int num_values)
575 {
576     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
577 }
578
579 /* Return an exponentially-distributed pseudo-random integer within
580  * the range:
581  *
582  *      0 <= result < num_values
583  *
584  * The distribution is such that each successively larger value will
585  * occur with a probability of half of the previous value.
586  */
587 static int
588 rand_within_exponential (int num_values)
589 {
590     static int r;
591     static uint32_t mask = 0;
592     int ones;
593     int bit;
594
595     /* Optimize the constant case. */
596     if (num_values == 1)
597         return 0;
598
599     ones = 0;
600
601     do {
602         if (mask == 0) {
603             r = rand ();
604             mask = 1 << 31;
605             while (mask > RAND_MAX)
606                 mask >>= 1;
607         }
608         bit = r & mask;
609         mask >>= 1;
610         if (bit) {
611             ones++;
612             if (ones == num_values)
613                 ones = 0;
614         }
615     } while (bit);
616
617     return ones;
618 }
619
620 static void
621 mnemon_select_item (mnemon_t     *mnemon,
622                     bin_t       **bin_ret,
623                     int          *item_index_ret)
624 {
625     int bin_index;
626     bin_t *bin;
627
628     bin_index = rand_within_exponential (mnemon->num_bins);
629
630     bin = &mnemon->bins[bin_index];
631
632     *bin_ret = bin;
633     *item_index_ret = rand_within (bin->num_items);
634 }
635
636
637 #define HISTOGRAM_ROW_FORMAT "%3d: %3d"
638 #define HISTOGRAM_BAR_WIDTH  63
639
640 static void
641 print_histogram_bar (double     size,
642                      double     max)
643 {
644     int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
645     static char const *boxes[8] = {
646         "█", "▉", "▊", "▋",
647         "▌", "▍", "▎", "▏"
648     };
649
650     while (size > units_per_cell) {
651         printf(boxes[0]);
652         size -= units_per_cell;
653     }
654
655     size /= units_per_cell;
656
657     if (size > 7.5/8.0)
658         printf(boxes[0]);
659     else if (size > 6.5/8.0)
660         printf(boxes[1]);
661     else if (size > 5.5/8.0)
662         printf(boxes[2]);
663     else if (size > 4.5/8.0)
664         printf(boxes[3]);
665     else if (size > 3.5/8.0)
666         printf(boxes[4]);
667     else if (size > 2.5/8.0)
668         printf(boxes[5]);
669     else if (size > 1.5/8.0)
670         printf(boxes[6]);
671     else if (size > 0.5/8.0)
672         printf(boxes[7]);
673
674     printf ("\n");
675 }
676
677 static void
678 mnemon_print_histogram (mnemon_t *mnemon)
679 {
680     int i, last_score, max;
681     bin_t *bin;
682
683     if (mnemon->num_bins == 0)
684         return;
685
686     max = mnemon->bins[0].num_items;
687     for (i = 1; i < mnemon->num_bins; i++)
688         if (mnemon->bins[i].num_items > max)
689             max = mnemon->bins[i].num_items;
690
691     for (i = 0; i < mnemon->num_bins; i++) {
692         bin = &mnemon->bins[i];
693         if (i != 0)
694             while (bin->score - last_score > 1)
695                 printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
696         printf (HISTOGRAM_ROW_FORMAT " ", bin->score, bin->num_items);
697         print_histogram_bar (bin->num_items, max);
698         last_score = bin->score;
699     }
700 }
701
702 static void
703 mnemon_handle_command (mnemon_t         *mnemon,
704                        const char       *command)
705 {
706     switch (command[0]) {
707         case 'h':
708             mnemon_print_histogram (mnemon);
709             break;
710         default:
711             printf ("Unknown command: %s\n", command);
712             break;
713     }
714 }
715
716 static void
717 mnemon_handle_response (mnemon_t        *mnemon,
718                         bin_t           *bin,
719                         int              item_index,
720                         item_t          *item,
721                         const char      *response)
722 {
723     bool_t correct;
724
725     correct = (strcmp (response, item->response) == 0);
726
727     bin_remove_item (bin, item_index);
728
729     /* If the bin is now empty, we must remove it. Also if we just
730      * picked the last word we'll ever pick from the bin with
731      * score 0, then we can remove that as well. */
732     if (bin->num_items == 0 ||
733         (bin->score == 0 && mnemon->to_introduce == 0))
734     {
735         mnemon_remove_bin (mnemon, bin);
736     }
737
738     if (correct) {
739         item->score++;
740         /* We reserve an item score of 0 for an item that has
741          * never been asked. */
742         if (item->score == 0) {
743             item->score = 1;
744             mnemon->unlearned--;
745             printf ("You got it!");
746             if (mnemon->to_introduce == 0 &&
747                 mnemon->unlearned == 0 &&
748                 mnemon->to_master == 0)
749             {
750                 mnemon->to_master = 10;
751                 mnemon->mastered = 0;
752             }
753         } else if (item->score < 0) {
754             printf ("Yes---just give me %d more.",
755                     - item->score);
756         } else if (item->score == 1) {
757             printf ("On your first try, no less!");
758         } else {
759             printf ("Masterful (%dx).", item->score);
760             if (mnemon->to_master)
761                 mnemon->mastered++;
762         }
763     } else {
764         printf ("  %s is the correct answer.",
765                 item->response);
766         /* Penalize an incorrect response by forcing the score
767          * negative. */
768         if (item->score >= 0) {
769             if (item->score > 0)
770                 printf ( " Oops, you knew that, right?\n ");
771             mnemon->unlearned++;
772             /* We go to -2 to force a little extra reinforcement
773              * when re-learning an item, (otherwise, it will often
774              * get asked again immediately where it is easy to get
775              * a correct response without any learning). */
776             item->score = -2;
777         } else {
778             item->score--;
779         }
780     }
781
782     printf (" ");
783     if (mnemon->to_introduce)
784         printf ("%d to come. ", mnemon->to_introduce);
785     if (mnemon->unlearned)
786         printf ("%d still unlearned. ", mnemon->unlearned);
787     if (mnemon->to_master) {
788         if (mnemon->mastered < mnemon->to_master)
789             printf ("%d items to master",
790                     mnemon->to_master - mnemon->mastered);
791         else
792             printf ("Great job!");
793     }
794     printf ("\n\n");
795
796     bin = mnemon_get_bin (mnemon, item->score);
797
798     bin_add_item (bin, item);
799 }
800
801 static void
802 mnemon_do_challenges (mnemon_t *mnemon)
803 {
804     bin_t *bin;
805     int item_index;
806     item_t *item;
807     char *response;
808     int i;
809
810     /* Count the number of items with negative scores. */
811     mnemon->unlearned = 0;
812     for (i = 0; i < mnemon->num_bins; i++) {
813         bin = &mnemon->bins[i];
814         if (bin->score >= 0)
815             break;
816         mnemon->unlearned += bin->num_items;
817     }
818
819     mnemon->to_introduce -= mnemon->unlearned;
820     if (mnemon->to_introduce < 0)
821         mnemon->to_introduce = 0;
822
823     /* Get rid of bin with score of 0 if we aren't going to be
824      * introducing anything from it. */
825     if (mnemon->to_introduce == 0) {
826         bin = mnemon_get_bin (mnemon, 0);
827         mnemon_remove_bin (mnemon, bin);        
828     }
829
830     if (mnemon->unlearned) {
831         printf ("You've got %d items to learn already. ", mnemon->unlearned);
832         if (mnemon->to_introduce)
833             printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
834         printf ("\n");
835     } else {
836         printf ("Introducing %d new items.\n", mnemon->to_introduce);
837     }
838     printf ("\n");
839
840     do {
841         mnemon_select_item (mnemon, &bin, &item_index);
842         item = bin->items[item_index];
843
844         if (bin->score == 0)
845             mnemon->to_introduce--;
846
847         while (1) {
848             printf ("%s\n", item->challenge);
849
850             response = readline ("> ");
851             /* Terminate on EOF */
852             if (response == NULL) {
853                 printf ("\n");
854                 return;
855             }
856
857             if (response[0] == '/')
858                 mnemon_handle_command (mnemon, response + 1);
859             else
860                 break;
861         }
862
863         mnemon_handle_response (mnemon, bin, item_index,
864                                 item, response);
865     } while (mnemon->mastered < mnemon->to_master);
866 }
867
868 int
869 main (int argc, char *argv[])
870 {
871     mnemon_t mnemon;
872
873     srand (time (NULL));
874
875     mnemon_init (&mnemon);
876
877     mnemon_load (&mnemon);
878
879     mnemon_do_challenges (&mnemon);
880
881     mnemon_save (&mnemon);
882
883     mnemon_fini (&mnemon);
884
885     return 0;
886 }