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