git.cworth.org Git - mnemon/blob - mnemon.c

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