git.cworth.org Git - mnemon/blob - 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 <sys/time.h>
  29 #include <unistd.h>
  30 #include <dirent.h>
  31 #include <errno.h>
  32 #include <string.h>
  33 #include <assert.h>
  34
  35 #include <readline/readline.h>
  36 #include <readline/history.h>
  37
  38 #define ASSERT_NOT_REACHED              \
  39 do {                                    \
  40     static const int NOT_REACHED = 0;   \
  41     assert (NOT_REACHED);               \
  42 } while (0)
  43
  44 typedef int bool_t;
  45
  46 typedef struct _item {
  47     int score;
  48     char *challenge;
  49     char *response;
  50 } item_t;
  51
  52 typedef struct _bin {
  53     int score;
  54     int items_size;
  55     int num_items;
  56     item_t **items;
  57 } bin_t;
  58
  59 typedef enum {
  60     CATEGORY_ORDER_RANDOM,
  61     CATEGORY_ORDER_SEQUENTIAL
  62 } category_order_t;
  63
  64 typedef enum {
  65     CHALLENGE_TYPE_TEXT,
  66     CHALLENGE_TYPE_IMAGE,
  67     CHALLENGE_TYPE_AUDIO,
  68     CHALLENGE_TYPE_MIDI
  69 } challenge_type_t;
  70
  71 typedef struct _category {
  72     char *name;
  73     int items_size;
  74     int num_items;
  75     item_t *items;
  76
  77     /* Support sequential introduction of items from bin 0 */
  78     category_order_t order;
  79     /* Support categories where responses are timed (0.0 == disable). */
  80     double time_limit;
  81     int bin_zero_head;
  82     /* Support challenges of non-text types (image, audio, etc.) */
  83     challenge_type_t challenge_type;
  84     /* Whether to repeat afterwards (for a little extra reinforcement) */
  85     bool_t repeat;
  86 } category_t;
  87
  88 typedef struct _mnemon {
  89     char *dir_name;
  90
  91     int categories_size;
  92     int num_categories;
  93     category_t *categories;
  94
  95     int bins_size;
  96     int num_bins;
  97     bin_t *bins;
  98
  99     int to_introduce;
 100     int to_master;
 101     int unlearned;
 102     int mastered;
 103 } mnemon_t;
 104
 105 static void *
 106 xmalloc (size_t size)
 107 {
 108     void *ret;
 109
 110     ret = malloc (size);
 111     if (ret == NULL) {
 112         fprintf (stderr, "Error: out of memory\n");
 113         exit (1);
 114     }
 115
 116     return ret;
 117 }
 118
 119 static void *
 120 xrealloc (void *ptr, size_t size)
 121 {
 122     void *ret;
 123
 124     ret = realloc (ptr, size);
 125     if (ret == NULL) {
 126         fprintf (stderr, "Error: out of memory\n");
 127         exit (1);
 128     }
 129
 130     return ret;
 131 }
 132
 133 static char *
 134 xstrdup (const char *s)
 135 {
 136     char *ret;
 137
 138     ret = strdup (s);
 139     if (ret == NULL) {
 140         fprintf (stderr, "Error: out of memory\n");
 141         exit (1);
 142     }
 143
 144     return ret;
 145 }
 146
 147 static char *
 148 xstrndup (const char *s, size_t n)
 149 {
 150     char *ret;
 151
 152     ret = strndup (s, n);
 153     if (ret == NULL) {
 154         fprintf (stderr, "Error: out of memory\n");
 155         exit (1);
 156     }
 157
 158     return ret;
 159 }
 160
 161 static void
 162 xasprintf (char **strp, const char *fmt, ...)
 163 {
 164     va_list ap;
 165     int ret;
 166
 167     va_start (ap, fmt);
 168     ret = vasprintf (strp, fmt, ap);
 169     va_end (ap);
 170
 171     if (ret < 0) {
 172         fprintf (stderr, "Error: out of memory\n");
 173         exit (1);
 174     }
 175 }
 176
 177 static void
 178 item_init (item_t       *item,
 179            int           score,
 180            const char   *challenge,
 181            const char   *response)
 182 {
 183     item->score = score;
 184
 185     item->challenge = xmalloc (strlen (challenge) + 1 +
 186                                strlen (response) + 1);
 187     item->response = item->challenge + strlen (challenge) + 1;
 188
 189     strcpy (item->challenge, challenge);
 190     strcpy (item->response, response);
 191 }
 192
 193 static void
 194 item_fini (item_t *item)
 195 {
 196     /* item->response shares allocation with item->challenge, so
 197      * doesn't require a separate call to free */
 198     free (item->challenge);
 199 }
 200
 201 static void
 202 category_init (category_t *category,
 203                const char *name)
 204 {
 205     category->name = xstrdup (name);
 206
 207     category->items_size = 0;
 208     category->num_items = 0;
 209     category->items = NULL;
 210     category->order = CATEGORY_ORDER_RANDOM;
 211     category->time_limit = 0.0;
 212     category->bin_zero_head = 0;
 213     category->challenge_type = CHALLENGE_TYPE_TEXT;
 214     category->repeat = 0;
 215 }
 216
 217 static void
 218 category_fini (category_t *category)
 219 {
 220     int i;
 221
 222     for (i = 0; i < category->num_items; i++)
 223         item_fini (&category->items[i]);
 224
 225     free (category->items);
 226
 227     free (category->name);
 228 }
 229
 230 static void
 231 category_grow (category_t *category)
 232 {
 233     if (category->items_size)
 234         category->items_size *= 2;
 235     else
 236         category->items_size = 1;
 237
 238     category->items = xrealloc (category->items,
 239                                 category->items_size * sizeof (item_t));
 240 }
 241
 242 static item_t *
 243 category_add_item (category_t   *category,
 244                    int           score,
 245                    const char   *challenge,
 246                    const char   *response)
 247 {
 248     item_t *item;
 249
 250     if (category->num_items == category->items_size)
 251         category_grow (category);
 252
 253     item = &category->items[category->num_items++];
 254
 255     item_init (item, score, challenge, response);
 256
 257     return item;
 258 }
 259
 260 static item_t *
 261 category_next_bin_zero_item (category_t *category)
 262 {
 263     int *i = &category->bin_zero_head;
 264
 265     for ( ; *i < category->num_items; *i = *i + 1)
 266         if (category->items[*i].score == 0)
 267             return &category->items[*i];
 268
 269     return NULL;
 270 }
 271
 272 static void
 273 category_print (category_t      *category,
 274                 FILE            *file)
 275 {
 276     int i;
 277     item_t *item;
 278
 279     fprintf (file, "order = %s\n\n",
 280             category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
 281     fprintf (file, "time = %f\n\n",
 282              category->time_limit);
 283
 284     fprintf (file, "challenge = ");
 285     switch (category->challenge_type) {
 286     case CHALLENGE_TYPE_TEXT:
 287         fprintf (file, "text");
 288         break;
 289     case CHALLENGE_TYPE_IMAGE:
 290         fprintf (file, "image");
 291         break;
 292     case CHALLENGE_TYPE_AUDIO:
 293         fprintf (file, "audio");
 294         break;
 295     case CHALLENGE_TYPE_MIDI:
 296         fprintf (file, "midi");
 297         break;
 298     }
 299     fprintf (file, "\n\n");
 300
 301     fprintf (file, "repeat = %d\n\n", category->repeat);
 302
 303     for (i = 0; i < category->num_items; i++) {
 304         item = &category->items[i];
 305         if (i != 0)
 306             fprintf (file, "\n");
 307         fprintf (file, "%d\n%s\n%s\n",
 308                  item->score,
 309                  item->challenge,
 310                  item->response);
 311     }
 312 }
 313
 314 static void
 315 bin_init (bin_t *bin,
 316           int    score)
 317 {
 318     bin->score = score;
 319
 320     bin->items_size = 0;
 321     bin->num_items = 0;
 322     bin->items = NULL;
 323 }
 324
 325 static void
 326 bin_fini (bin_t *bin)
 327 {
 328     free (bin->items);
 329 }
 330
 331 static void
 332 bin_grow (bin_t *bin)
 333 {
 334     if (bin->items_size)
 335         bin->items_size *= 2;
 336     else
 337         bin->items_size = 1;
 338
 339     bin->items = xrealloc (bin->items,
 340                            bin->items_size * sizeof (item_t*));
 341 }
 342
 343 static void
 344 bin_add_item (bin_t     *bin,
 345               item_t    *item)
 346 {
 347     assert (item->score == bin->score);
 348
 349     if (bin->num_items == bin->items_size)
 350         bin_grow (bin);
 351
 352     bin->items[bin->num_items++] = item;
 353 }
 354
 355 static void
 356 bin_remove_item (bin_t  *bin,
 357                  int     item_index)
 358 {
 359     /* Replace the current item with the last item, (no need to shift
 360      * any more than that since we don't care about the order of the
 361      * items within a bin). */
 362     bin->num_items--;
 363     if (bin->num_items)
 364         bin->items[item_index] = bin->items[bin->num_items];
 365 }
 366
 367 /* Find the index for an item within a bin.
 368  *
 369  * XXX: This is currently a linear search, so is a potential
 370  * performance problem.
 371  */
 372 static int
 373 bin_item_index (bin_t   *bin,
 374                 item_t  *item)
 375 {
 376     int i;
 377
 378     for (i = 0; i < bin->num_items; i++)
 379         if (bin->items[i] == item)
 380             return i;
 381
 382     assert (0);
 383 }
 384
 385 typedef int (item_match_predicate_t) (void *closure, item_t *item);
 386
 387 /* Return the number of items in the bin from the given category (or
 388  * from all categories if category == NULL) */
 389 static int
 390 bin_num_items_matching (bin_t                   *bin,
 391                         item_match_predicate_t  *predicate,
 392                         void                    *closure)
 393 {
 394     int i, num_items = 0;
 395
 396     if (predicate == NULL)
 397         return bin->num_items;
 398
 399     for (i = 0; i < bin->num_items; i++)
 400         if ((predicate) (closure, bin->items[i]))
 401             num_items++;
 402
 403     return num_items;
 404 }
 405
 406 static void
 407 mnemon_init (mnemon_t *mnemon)
 408 {
 409     char *home;
 410
 411     home = getenv ("HOME");
 412     if (home == NULL)
 413         home = "";
 414
 415     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
 416
 417     mnemon->categories_size = 0;
 418     mnemon->num_categories = 0;
 419     mnemon->categories = NULL;
 420
 421     mnemon->bins_size = 0;
 422     mnemon->num_bins = 0;
 423     mnemon->bins = NULL;
 424
 425     mnemon->to_introduce = 10;
 426     mnemon->to_master = 10;
 427     mnemon->unlearned = 0;
 428     mnemon->mastered = -1;
 429 }
 430
 431 static void
 432 mnemon_fini (mnemon_t *mnemon)
 433 {
 434     int i;
 435
 436     for (i = 0; i < mnemon->num_bins; i++)
 437         bin_fini (&mnemon->bins[i]);
 438     free (mnemon->bins);
 439
 440     for (i = 0; i < mnemon->num_categories; i++)
 441         category_fini (&mnemon->categories[i]);
 442     free (mnemon->categories);
 443
 444     free (mnemon->dir_name);
 445 }
 446
 447 static void
 448 mnemon_categories_grow (mnemon_t *mnemon)
 449 {
 450     if (mnemon->categories_size)
 451         mnemon->categories_size *= 2;
 452     else
 453         mnemon->categories_size = 1;
 454
 455     mnemon->categories = xrealloc (mnemon->categories,
 456                                    mnemon->categories_size * sizeof (category_t));
 457 }
 458
 459 /* Get a category by name if it exists */
 460 static category_t *
 461 mnemon_get_category_if_exists (mnemon_t     *mnemon,
 462                                const char   *name)
 463 {
 464     int i;
 465
 466     for (i = 0; i < mnemon->num_categories; i++)
 467         if (strcmp (mnemon->categories[i].name, name) == 0)
 468             return &mnemon->categories[i];
 469
 470     return NULL;
 471 }
 472
 473 /* Get a category by name, creating new one if necessary. */
 474 static category_t *
 475 mnemon_get_category (mnemon_t   *mnemon,
 476                      const char *name)
 477 {
 478     category_t *category;
 479
 480     category = mnemon_get_category_if_exists (mnemon, name);
 481     if (category)
 482         return category;
 483
 484     mnemon_categories_grow (mnemon);
 485
 486     category = &mnemon->categories[mnemon->num_categories++];
 487
 488     category_init (category, name);
 489
 490     return category;
 491 }
 492
 493 static void
 494 mnemon_bins_grow (mnemon_t *mnemon)
 495 {
 496     if (mnemon->bins_size)
 497         mnemon->bins_size *= 2;
 498     else
 499         mnemon->bins_size = 1;
 500
 501     mnemon->bins = xrealloc (mnemon->bins,
 502                              mnemon->bins_size * sizeof (bin_t));
 503 }
 504
 505 static bin_t *
 506 mnemon_get_bin (mnemon_t        *mnemon,
 507                 int              score)
 508 {
 509     int i;
 510     bin_t *bin;
 511
 512     for (i = 0; i < mnemon->num_bins; i++)
 513         if (mnemon->bins[i].score == score)
 514             return &mnemon->bins[i];
 515         else if (mnemon->bins[i].score > score)
 516             break;
 517
 518     if (mnemon->num_bins == mnemon->bins_size)
 519         mnemon_bins_grow (mnemon);
 520
 521     bin = &mnemon->bins[i];
 522
 523     /* Make room to insert new bin at its sorted location. */
 524     if (i < mnemon->num_bins)
 525         memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
 526     mnemon->num_bins++;
 527
 528     bin_init (bin, score);
 529
 530     return bin;
 531 }
 532
 533 static void
 534 mnemon_remove_bin (mnemon_t     *mnemon,
 535                    bin_t        *bin)
 536 {
 537     int i = bin - mnemon->bins;
 538
 539     bin_fini (bin);
 540
 541     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
 542     mnemon->num_bins--;
 543 }
 544
 545 static void
 546 chomp (char *s)
 547 {
 548     int len = strlen (s);
 549     if (len == 0)
 550         return;
 551     if (s[len - 1] == '\n')
 552         s[len - 1] = '\0';
 553 }
 554
 555 static char *
 556 trim_space (char *string)
 557 {
 558     char *s;
 559
 560     s = string;
 561     while (*s && isspace (*s))
 562         s++;
 563
 564     string = s;
 565
 566     s = string + strlen (string) - 1;
 567     while (s > string && isspace (*s)) {
 568         *s = '\0';
 569         s--;
 570     }
 571
 572     return string;
 573 }
 574
 575 static void
 576 mnemon_load_category (mnemon_t          *mnemon,
 577                       const char        *name)
 578 {
 579     FILE *file;
 580     char *line = NULL, *end;
 581     size_t line_size = 0;
 582     ssize_t bytes_read;
 583     int line_count = 0;
 584     char *path;
 585     category_t *category;
 586     int i;
 587
 588     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
 589     sprintf (path, "%s/%s", mnemon->dir_name, name);
 590
 591     file = fopen (path, "r");
 592     if (file == NULL) {
 593         fprintf (stderr, "Error: Failed to open %s: %s\n",
 594                  path, strerror (errno));
 595         exit (1);
 596     }
 597
 598     category = mnemon_get_category (mnemon, name);
 599
 600 #define READ_LINE do {                                  \
 601     bytes_read = getline (&line, &line_size, file);     \
 602     if (bytes_read == -1)                               \
 603         goto END_OF_FILE;                               \
 604     line_count++;                                       \
 605     chomp (line);                                       \
 606 } while (0)
 607
 608     /* Parse options */
 609     while (1) {
 610         char *name, *equal, *value;
 611
 612         /* Ignore blank lines */
 613         READ_LINE;
 614         if (*line == '\0')
 615             continue;
 616
 617         /* An initial digit means we hit an item. Trigger the
 618          * spaghetti machine. */
 619         if ((*line >= '0' && *line <= '9') || *line == '-')
 620             goto PARSE_BIN;
 621
 622         equal = strchr (line, '=');
 623         if (equal == NULL) {
 624             fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
 625                      line, path, line_count);
 626             exit (1);
 627         }
 628
 629         value = equal + 1;
 630         name = line;
 631         *equal = '\0';
 632
 633         name = trim_space (name);
 634         value = trim_space (value);
 635
 636         if (strcmp (name, "order") == 0) {
 637             if (strcmp (value, "sequential") == 0) {
 638                 category->order = CATEGORY_ORDER_SEQUENTIAL;
 639             } else if (strcmp (value, "random") == 0) {
 640                 category->order = CATEGORY_ORDER_RANDOM;
 641             } else {
 642                 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
 643                          value, path, line_count);
 644                 exit (1);
 645             }
 646         } else if (strcmp (name, "time") == 0) {
 647             double limit;
 648             char *end;
 649             limit = strtod (value, &end);
 650             while (isspace (*end))
 651                 end++;
 652             if (*end == '\0') {
 653                 category->time_limit = limit;
 654             } else {
 655                 fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
 656                          value, path, line_count);
 657                 exit (1);
 658             }
 659         } else if (strcmp (name, "challenge") == 0) {
 660             if (strcmp (value, "text") == 0) {
 661                 category->challenge_type = CHALLENGE_TYPE_TEXT;
 662             } else if (strcmp (value, "image") == 0) {
 663                 category->challenge_type = CHALLENGE_TYPE_IMAGE;
 664             } else if (strcmp (value, "audio") == 0) {
 665                 category->challenge_type = CHALLENGE_TYPE_AUDIO;
 666             } else if (strcmp (value, "midi") == 0) {
 667                 category->challenge_type = CHALLENGE_TYPE_MIDI;
 668             } else {
 669                 fprintf (stderr, "Unknown value for \"challenge\" option \"%s\" at %s:%d\n",
 670                          value, path, line_count);
 671                 exit (1);
 672             }
 673         } else if (strcmp (name, "repeat") == 0) {
 674             if (strcmp (value, "0") == 0)
 675                 category->repeat = 0;
 676             else
 677                 category->repeat = 1;
 678         } else {
 679             fprintf (stderr, "Unknown option %s at %s:%d\n",
 680                      name, path, line_count);
 681             exit (1);
 682         }
 683     }
 684
 685     /* Parse items */
 686     while (1) {
 687         int score;
 688         char *challenge, *response;
 689
 690         /* Ignore blank lines */
 691         READ_LINE;
 692         if (*line == '\0')
 693             continue;
 694
 695         /* Read bin number */
 696       PARSE_BIN:
 697         score = strtol (line, &end, 10);
 698         if (*end != '\0') {
 699             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
 700                      line, path, line_count);
 701             exit (1);
 702         }
 703
 704         /* Read challenge */
 705         READ_LINE;
 706         challenge = strdup (line);
 707
 708         /* Read response */
 709         READ_LINE;
 710         response = line;
 711
 712         category_add_item (category, score, challenge, response);
 713
 714         free (challenge);
 715     }
 716   END_OF_FILE:
 717
 718     free (line);
 719     fclose (file);
 720     free (path);
 721
 722     /* Resize category items to fit exactly. */
 723     category->items_size = category->num_items;
 724     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
 725
 726     /* Now that the category is completely loaded, with stable
 727      * pointers to every item, we can add each item to its appropriate
 728      * bin. */
 729     for (i = 0; i < category->num_items; i++) {
 730         item_t *item = &category->items[i];
 731         bin_t *bin = mnemon_get_bin (mnemon, item->score);
 732
 733         bin_add_item (bin, item);
 734     }
 735 }
 736
 737 static void
 738 mnemon_load (mnemon_t *mnemon)
 739 {
 740     DIR *dir;
 741     struct dirent *dirent;
 742
 743     dir = opendir (mnemon->dir_name);
 744     if (dir == NULL) {
 745         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
 746                  mnemon->dir_name, strerror (errno));
 747         exit (1);
 748     }
 749
 750     while (1) {
 751         dirent = readdir (dir);
 752         if (dirent == NULL)
 753             break;
 754
 755         if (dirent->d_type == DT_REG) {
 756             /* Ignore files matching *~, (yes, this shouldn't be
 757              * hard-coded in such an ad-hoc way, but there you go. */
 758             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
 759                 mnemon_load_category (mnemon, dirent->d_name);
 760         }
 761     }
 762
 763     closedir (dir);
 764 }
 765
 766 static void
 767 mnemon_save (mnemon_t *mnemon)
 768 {
 769     int i, err;
 770     char *filename, *lock_filename;
 771     FILE *file;
 772     category_t *category;
 773
 774     for (i = 0; i < mnemon->num_categories; i++) {
 775         category = &mnemon->categories[i];
 776
 777         xasprintf (&filename, "%s/%s",
 778                    mnemon->dir_name, category->name);
 779         xasprintf (&lock_filename, "%s/.#%s",
 780                    mnemon->dir_name, category->name);
 781
 782         file = fopen (lock_filename, "w");
 783         if (file == NULL) {
 784             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
 785                      lock_filename, strerror (errno));
 786             continue;
 787         }
 788
 789         category_print (category, file);
 790
 791         fsync (fileno (file));
 792         fclose (file);
 793
 794         err = rename (lock_filename, filename);
 795         if (err < 0) {
 796             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
 797                      lock_filename, filename, strerror (errno));
 798             continue;
 799         }
 800
 801         free (filename);
 802         free (lock_filename);
 803     }
 804 }
 805
 806 /* Return a uniformly-distributed pseudo-random integer within the
 807  * range:
 808  *
 809  *      0 <= result < num_values
 810  */
 811 static int
 812 rand_within (int num_values)
 813 {
 814     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
 815 }
 816
 817 /* Return an exponentially-distributed pseudo-random integer within
 818  * the range:
 819  *
 820  *      0 <= result < num_values
 821  *
 822  * The distribution is such that each successively larger value will
 823  * occur with a probability of half of the previous value.
 824  */
 825 static int
 826 rand_within_exponential (int num_values)
 827 {
 828     static int r;
 829     static uint32_t mask = 0;
 830     int ones;
 831     int bit;
 832
 833     /* Optimize the constant case. */
 834     if (num_values == 1)
 835         return 0;
 836
 837     ones = 0;
 838
 839     do {
 840         if (mask == 0) {
 841             r = rand ();
 842             mask = 1 << 31;
 843             while (mask > RAND_MAX)
 844                 mask >>= 1;
 845         }
 846         bit = r & mask;
 847         mask >>= 1;
 848         if (bit) {
 849             ones++;
 850             if (ones == num_values)
 851                 ones = 0;
 852         }
 853     } while (bit);
 854
 855     return ones;
 856 }
 857
 858 /* Find the category to which an item belongs. */
 859 static category_t *
 860 mnemon_item_category (mnemon_t  *mnemon,
 861                       item_t    *item)
 862 {
 863     category_t *category;
 864     int i, item_index;
 865
 866     for (i = 0; i < mnemon->num_categories; i++) {
 867         category = &mnemon->categories[i];
 868         item_index = item - category->items;
 869         if (item_index >= 0 && item_index < category->num_items)
 870             return category;
 871     }
 872
 873     assert (0);
 874 }
 875
 876 typedef struct _item_in_category_closure
 877 {
 878     mnemon_t *mnemon;
 879     category_t *category;
 880 } item_in_category_closure_t;
 881
 882 static int
 883 mnemon_item_in_category (void *closure, item_t *item)
 884 {
 885     item_in_category_closure_t *iicc = closure;
 886     mnemon_t *mnemon = iicc->mnemon;
 887     category_t *category = iicc->category;
 888
 889     return (mnemon_item_category (mnemon, item) == category);
 890 }
 891
 892 typedef struct _item_in_category_of_length_closure
 893 {
 894     mnemon_t *mnemon;
 895     category_t *category;
 896     int length;
 897 } item_in_category_of_length_closure_t;
 898
 899 static int
 900 mnemon_item_in_category_of_length (void *closure, item_t *item)
 901 {
 902     item_in_category_of_length_closure_t *iicolc = closure;
 903     mnemon_t *mnemon = iicolc->mnemon;
 904     category_t *category = iicolc->category;
 905     int length = iicolc->length;
 906
 907     if (mnemon_item_category (mnemon, item) != category)
 908         return 0;
 909
 910     return strlen (item->challenge) == length;
 911 }
 912
 913 static void
 914 mnemon_select_item (mnemon_t     *mnemon,
 915                     bin_t       **bin_ret,
 916                     int          *item_index_ret,
 917                     category_t  **category_ret)
 918 {
 919     int bin_index, item_index;
 920     bin_t *bin;
 921     item_t *item;
 922     category_t *category;
 923
 924     bin_index = rand_within_exponential (mnemon->num_bins);
 925     bin = &mnemon->bins[bin_index];
 926
 927     /* The most intuitive understanding of the to_introduce counter is
 928      * that it's tracking never-before-learned items as they are
 929      * pulled from the bin with score 0. But that bin can become
 930      * empty. So the refined rule is that we decrement to_introduce
 931      * whenever we pull from the lowest-indexed bin with a
 932      * non-negative score. */
 933     if (mnemon->to_introduce && bin->score >=0 &&
 934         (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
 935     {
 936         mnemon->to_introduce--;
 937     }
 938
 939     item_index = rand_within (bin->num_items);
 940
 941     item = bin->items[item_index];
 942     category = mnemon_item_category (mnemon, item);
 943
 944     if (bin->score == 0) {
 945         if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
 946             item = category_next_bin_zero_item (category);
 947             if (item)
 948                 item_index = bin_item_index (bin, item);
 949         }
 950     }
 951
 952     *bin_ret = bin;
 953     *item_index_ret = item_index;
 954     *category_ret = category;
 955 }
 956
 957
 958 #define HISTOGRAM_ROW_FORMAT "%3d: %3d"
 959 #define HISTOGRAM_BAR_WIDTH  63
 960
 961 static void
 962 print_histogram_bar (double     size,
 963                      double     max)
 964 {
 965     int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
 966     static char const *boxes[8] = {
 967         "█", "▉", "▊", "▋",
 968         "▌", "▍", "▎", "▏"
 969     };
 970
 971     while (size > units_per_cell) {
 972         printf(boxes[0]);
 973         size -= units_per_cell;
 974     }
 975
 976     size /= units_per_cell;
 977
 978     if (size > 7.5/8.0)
 979         printf(boxes[0]);
 980     else if (size > 6.5/8.0)
 981         printf(boxes[1]);
 982     else if (size > 5.5/8.0)
 983         printf(boxes[2]);
 984     else if (size > 4.5/8.0)
 985         printf(boxes[3]);
 986     else if (size > 3.5/8.0)
 987         printf(boxes[4]);
 988     else if (size > 2.5/8.0)
 989         printf(boxes[5]);
 990     else if (size > 1.5/8.0)
 991         printf(boxes[6]);
 992     else if (size > 0.5/8.0)
 993         printf(boxes[7]);
 994
 995     printf ("\n");
 996 }
 997
 998 static void
 999 mnemon_print_histogram (mnemon_t    *mnemon,
1000                         const char  *category_name,
1001                         int          length)
1002 {
1003     int i, last_score, max;
1004     category_t *category = NULL;
1005     bin_t *bin;
1006     int num_items;
1007     item_match_predicate_t *predicate = NULL;
1008     void *closure = NULL;
1009     item_in_category_closure_t item_in_category;
1010     item_in_category_of_length_closure_t item_in_category_of_length;
1011
1012     if (mnemon->num_bins == 0)
1013         return;
1014
1015     if (category_name) {
1016         category = mnemon_get_category_if_exists (mnemon, category_name);
1017         if (category) {
1018             if (length) {
1019                 predicate = mnemon_item_in_category_of_length;
1020                 item_in_category_of_length.mnemon = mnemon;
1021                 item_in_category_of_length.category = category;
1022                 item_in_category_of_length.length = length;
1023                 closure = &item_in_category_of_length;
1024             } else {
1025                 predicate = mnemon_item_in_category;
1026                 item_in_category.mnemon = mnemon;
1027                 item_in_category.category = category;
1028                 closure = &item_in_category;
1029             }
1030         }
1031     }
1032
1033     for (i = 0; i < mnemon->num_bins; i++) {
1034         num_items = bin_num_items_matching (&mnemon->bins[i],
1035                                             predicate, closure);
1036         if (i == 0 || num_items > max)
1037             max = num_items;
1038     }
1039
1040     for (i = 0; i < mnemon->num_bins; i++) {
1041         bin = &mnemon->bins[i];
1042         if (i != 0)
1043             while (bin->score - last_score > 1)
1044                 printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
1045         num_items = bin_num_items_matching (bin,
1046                                             predicate, closure);
1047         printf (HISTOGRAM_ROW_FORMAT " ", bin->score, num_items);
1048         print_histogram_bar (num_items, max);
1049         last_score = bin->score;
1050     }
1051 }
1052
1053 static void
1054 mnemon_handle_command (mnemon_t         *mnemon,
1055                        const char       *command)
1056 {
1057     const char *arg;
1058     int len;
1059     switch (command[0]) {
1060         /* 'h' for histogram */
1061         case 'h':
1062         {
1063             char *category = NULL;
1064             int length = 0;
1065
1066             arg = command + 1;
1067             arg += strspn (arg, " \t");
1068             len = strcspn (arg, " \t");
1069             if (len) {
1070                 category = xstrndup (arg, len);
1071                 arg += len;
1072                 arg += strspn (arg, " \t");
1073                 if (*arg)
1074                     length = atoi (arg);
1075             }
1076             mnemon_print_histogram (mnemon, category, length);
1077         }
1078         break;
1079         /* 'r' for repeat */
1080         case 'r':
1081         {
1082             /* Nothing necessary for repeating. */
1083         }
1084         break;
1085         default:
1086             printf ("Unknown command: %s\n", command);
1087             break;
1088     }
1089 }
1090
1091 static void
1092 mnemon_handle_response (mnemon_t        *mnemon,
1093                         bin_t           *bin,
1094                         int              item_index,
1095                         item_t          *item,
1096                         const char      *response,
1097                         double           response_time,
1098                         double           time_limit)
1099 {
1100     bool_t correct;
1101
1102     correct = (strcmp (response, item->response) == 0);
1103
1104     bin_remove_item (bin, item_index);
1105
1106     /* If the bin is now empty, we must remove it. Also if we just
1107      * picked the last word we'll ever pick from the bin with
1108      * score 0, then we can remove that as well. */
1109     if (bin->num_items == 0 ||
1110         (bin->score == 0 && mnemon->to_introduce == 0))
1111     {
1112         mnemon_remove_bin (mnemon, bin);
1113     }
1114
1115     if (correct &&
1116         (time_limit == 0.0 || response_time < time_limit))
1117     {
1118         item->score++;
1119         /* We reserve an item score of 0 for an item that has
1120          * never been asked. */
1121         if (item->score == 0) {
1122             item->score = 1;
1123             mnemon->unlearned--;
1124             printf ("You got it!");
1125         } else if (item->score < 0) {
1126             printf ("Yes---just give me %d more.",
1127                     - item->score);
1128         } else if (item->score == 1) {
1129             printf ("On your first try, no less!");
1130         } else {
1131             printf ("Masterful (%dx).", item->score);
1132             if (mnemon->to_master)
1133                 mnemon->to_master--;
1134         }
1135     } else {
1136         if (! correct)
1137             printf ("  %s is the correct answer.",
1138                     item->response);
1139         else
1140             printf ("Correct, but not quite quick enough (%0.2f seconds---needed %0.2f seconds)\n",
1141                     response_time, time_limit);
1142         /* Penalize an incorrect response by forcing the score
1143          * negative. */
1144         if (item->score >= 0) {
1145             if (item->score > 0)
1146                 printf (" Oops, you knew that, right? (%dx)\n ",
1147                         item->score);
1148             mnemon->unlearned++;
1149             /* We increase to_master here as an extra penalty. If the
1150              * user is forgetting stuff learned previously, then more
1151              * time should be spent on mastering than learning new
1152              * items. Note that we only do this during the initial
1153              * phase while new items are still being introduced. */
1154             if (mnemon->to_introduce)
1155                 mnemon->to_master++;
1156             /* We go to -2 to force a little extra reinforcement
1157              * when re-learning an item, (otherwise, it will often
1158              * get asked again immediately where it is easy to get
1159              * a correct response without any learning). */
1160             item->score = -2;
1161         } else {
1162             item->score--;
1163         }
1164     }
1165
1166     printf (" ");
1167     if (mnemon->to_introduce)
1168         printf ("%d to come. ", mnemon->to_introduce);
1169     if (mnemon->unlearned)
1170         printf ("%d still unlearned. ", mnemon->unlearned);
1171     if (mnemon->to_introduce == 0 && mnemon->to_master > 0)
1172         printf ("%d items to master", mnemon->to_master);
1173     printf ("\n\n");
1174
1175     bin = mnemon_get_bin (mnemon, item->score);
1176
1177     bin_add_item (bin, item);
1178 }
1179
1180 static void
1181 mnemon_show_challenge (mnemon_t *mnemon,
1182                        challenge_type_t challenge_type,
1183                        const char *challenge)
1184 {
1185     const char *program;
1186     char *command;
1187
1188     if (challenge_type == CHALLENGE_TYPE_TEXT) {
1189         printf ("%s\n", challenge);
1190         return;
1191     }
1192
1193     /* XXX: Yes, shelling out to system is total cheese. The planned
1194      * fix here is to bring graphical display in process, (or at least
1195      * have a custom external program that accepts image filenames on
1196      * stdin.
1197      */
1198     switch (challenge_type) {
1199     case CHALLENGE_TYPE_TEXT:
1200         ASSERT_NOT_REACHED;
1201         break;
1202     case CHALLENGE_TYPE_IMAGE:
1203         program = "xli -gamma 2.2";
1204         break;
1205     case CHALLENGE_TYPE_AUDIO:
1206         program = "play";
1207         break;
1208     case CHALLENGE_TYPE_MIDI:
1209         program = "timidity -Os";
1210         break;
1211     }
1212
1213     xasprintf (&command, "%s %s/%s >/dev/null 2>&1 &",
1214                program,
1215                mnemon->dir_name,
1216                challenge);
1217     system (command);
1218     free (command);
1219 }
1220
1221 static void
1222 mnemon_hide_challenge (mnemon_t *mnemon, challenge_type_t challenge_type)
1223 {
1224     char * command;
1225
1226     if (challenge_type != CHALLENGE_TYPE_IMAGE)
1227         return;
1228
1229     /* XXX: And this is just embarrassing (obviously wrong in several
1230      * ways). Hopefully I'll amend away any commit that includes this.
1231      */
1232     xasprintf (&command, "killall xli");
1233     system (command);
1234     free (command);
1235 }
1236
1237 static void
1238 mnemon_do_challenges (mnemon_t *mnemon)
1239 {
1240     bin_t *bin;
1241     int item_index;
1242     item_t *item;
1243     category_t *category;
1244     char *response;
1245     int i;
1246
1247     /* Count the number of items with negative scores. */
1248     mnemon->unlearned = 0;
1249     for (i = 0; i < mnemon->num_bins; i++) {
1250         bin = &mnemon->bins[i];
1251         if (bin->score >= 0)
1252             break;
1253         mnemon->unlearned += bin->num_items;
1254     }
1255
1256     mnemon->to_introduce -= mnemon->unlearned;
1257     if (mnemon->to_introduce < 0)
1258         mnemon->to_introduce = 0;
1259
1260     /* Get rid of bin with score of 0 if we aren't going to be
1261      * introducing anything from it. */
1262     if (mnemon->to_introduce == 0) {
1263         bin = mnemon_get_bin (mnemon, 0);
1264         mnemon_remove_bin (mnemon, bin);
1265     }
1266
1267     if (mnemon->unlearned) {
1268         printf ("You've got %d items to learn already. ", mnemon->unlearned);
1269         if (mnemon->to_introduce)
1270             printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
1271         printf ("\n");
1272     } else {
1273         printf ("Introducing %d new items.\n", mnemon->to_introduce);
1274     }
1275     printf ("\n");
1276
1277     do {
1278         struct timeval start, end;
1279
1280         mnemon_select_item (mnemon, &bin, &item_index, &category);
1281         item = bin->items[item_index];
1282
1283         while (1) {
1284             if (category->time_limit > 0.0) {
1285                 response = readline ("The next one is timed. Press enter when ready:");
1286                 free (response);
1287             }
1288
1289             mnemon_show_challenge (mnemon, category->challenge_type,
1290                                    item->challenge);
1291
1292             gettimeofday (&start, NULL);
1293             response = readline ("> ");
1294             gettimeofday (&end, NULL);
1295
1296             mnemon_hide_challenge (mnemon, category->challenge_type);
1297
1298             /* Terminate on EOF */
1299             if (response == NULL) {
1300                 printf ("\n");
1301                 return;
1302             }
1303
1304             if (response[0] == '/') {
1305                 mnemon_handle_command (mnemon, response + 1);
1306                 free (response);
1307             } else {
1308                 break;
1309             }
1310         }
1311
1312         mnemon_handle_response (mnemon, bin, item_index,
1313                                 item, response,
1314                                 (end.tv_sec + end.tv_usec / 1e6) -
1315                                 (start.tv_sec + start.tv_usec / 1e6),
1316                                 category->time_limit);
1317         free (response);
1318
1319         /* Replay audio challenges for reinforcement. */
1320         if (category->repeat)
1321         {
1322             mnemon_show_challenge (mnemon, category->challenge_type,
1323                                    item->challenge);
1324             printf ("%s\n", item->challenge);
1325             sleep (2);
1326         }
1327     } while (mnemon->to_introduce ||
1328              mnemon->unlearned ||
1329              mnemon->to_master > 0);
1330 }
1331
1332 int
1333 main (int argc, char *argv[])
1334 {
1335     mnemon_t mnemon;
1336     char *response;
1337
1338     srand (time (NULL));
1339
1340     mnemon_init (&mnemon);
1341
1342     mnemon_load (&mnemon);
1343
1344     mnemon_do_challenges (&mnemon);
1345
1346     mnemon_save (&mnemon);
1347
1348     mnemon_fini (&mnemon);
1349
1350     mnemon_init (&mnemon);
1351     mnemon_load (&mnemon);
1352
1353     printf ("Great job.\nHere are your current results:\n");
1354     mnemon_print_histogram (&mnemon, NULL, 0);
1355     response = readline ("Press enter to quit.\n");
1356     free (response);
1357
1358     mnemon_fini (&mnemon);
1359
1360     return 0;
1361 }