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