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