// Compute the frequency of each word in the input stream.  An example
// program for binary array sets, as in
// <https://www.nayuki.io/page/binary-array-set>.  This version
// associates a value with each key.
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

enum { max_levels = 64 };
typedef struct {
  struct entry {
    char *word;
    int freq;
  } *values[max_levels];
} bas;

static bas *new_bas()
{
  bas *rv = malloc(sizeof(*rv));
  if (!rv) abort();

  for (int i = 0; i < max_levels; i++) {
    rv->values[i] = NULL;
  }

  return rv;
}

static void increment(bas *set, char *word)
{
  // generate a new one-element array;
  // do an N-way merge among the various entry arrays up to the first empty spot;
  // stick it in the empty spot;
  // then discard the old entry arrays (or reuse them I guess?)
}

static void iterate(bas *set,
                    void (*f)(void *userdata, char *word, int freq),
                    void *userdata)
{
  // do an N-way merge among the various entry arrays, 
  // without destroying them
}

static void delete(bas *set)
{
  for (int i = 0; i < max_levels; i++) {
    free(set->values[i]);
  }
  free(set);
}

static void print_freq(void *userdata, char *word, int freq)
{
  printf("%8d %s\n", freq, word);
}

int main()
{
  bas *set = new_bas();
  char word[256];
  int wordlen = 0, c;

  while ((c = getchar()) != EOF) {
    if (isspace(c)) {
      if (wordlen) {
        word[wordlen] = '\0';
        increment(set, word);
        wordlen = 0;
      }
    } else {
      word[wordlen++] = c;
      assert(wordlen < sizeof(word));
    }
  }

  iterate(set, print_freq, NULL);

  delete(set);

  return 0;
}