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