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