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

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