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