/* anaphrase -- return all phrases made up of letters from a string
 *
 * Usage: anaphrase [-i] string dictionary
 *
 * 


 */

#include <wchar.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <assert.h>
#include <err.h>
#include <sysexits.h>
#include <wctype.h>
#include <locale.h>
#include <unistd.h>


#define INCR 1000		/* Used in realloc() below */

typedef struct _List {
  int n;
  struct _List *next;
} *List;

static wchar_t **dict = NULL;	/* List of words */
static int dictsize = 0;	/* Size of dict */
static int nwords = 0;		/* # of words in the dict */
static int case_insensitive = 0; /* Option -i */
static int minsize = 1;		 /* Only use words at least this size */


/* getlinews -- read a line into a string of wide characters */
static ssize_t getlinews(wchar_t **line, size_t *n, FILE *f)
{
  wint_t c;
  ssize_t i = 0;
  wchar_t *h;

  if (!line || !n || !f || (*n && !(*line))) {errno = EINVAL; return -1;}
  do {
    if (i + 2 > *n) {
      *n = i + 2 + INCR;
      if ((h = realloc(*line, *n * sizeof(**line)))) *line = h;
      else {if (*n > i) (*line)[i] = L'\0'; return -1;} /* Out of memory */
    }
    c = fgetwc(f);
    if (c != WEOF) (*line)[i++] = c;
  } while (c != WEOF && c != L'\n');
  (*line)[i] = L'\0';
  return c == WEOF ? -1 : i;	/* -1 on error or EOF; >= 0 on success */
}


/* subtract -- return pool without all chars from word, or NULL on failure */
static wchar_t *subtract(wchar_t *pool, const wchar_t const *word)
{
  wchar_t c, h;
  size_t i, j, n;

  assert(pool);
  assert(word);
  n = wcslen(pool);
  for (j = 0; word[j]; j++) {
    c = case_insensitive ? towlower(word[j]) : word[j];
    for (i = 0; i < n && pool[i] != c; i++);
    if (i == n) return NULL;	/* Character not found */
    if (i != 0) {h = pool[i]; pool[i] = pool[0]; pool[0] = h;}
    pool++; n--;
  }
  return pool;			/* Success */
}


/* find_all -- recursively find and print words from dict that make up pool */
static void find_all(wchar_t *pool, const List seen)
{
  int i;
  wchar_t *pool2;
  List seen2, h;

  assert(pool);
  if (pool[0] != L'\0') {	/* Still letters in the pool */
    for (i = 0; i < nwords; i++) {
      if ((pool2 = subtract(pool, dict[i]))) {
	if (!(seen2 = malloc(sizeof(*seen2)))) err(EX_UNAVAILABLE, NULL);
	seen2->n = i;
	seen2->next = seen;
	find_all(pool2, seen2);	/* Continue with this smaller pool */
	free(seen2);
      }
    }
  } else if (seen) {		/* Pool is empty and we have a result */
    for (h = seen; h; h = h->next) printf("%ls ", dict[h->n]);
    putchar('\n');
  }
}


/* usage -- print usage message on stderr and exit */
static void usage(const char const *prog)
{
  fprintf(stderr, "Usage: %s [-i] <string> <dictionary>\n", prog);
  exit(EX_USAGE);
}


/* main -- main body */
int main(int argc, char *argv[])
{
  wchar_t *pool;
  size_t n = 0, len;
  ssize_t r;
  FILE *f;
  char c;
  int i;

  (void)setlocale(LC_ALL, "");

  /* Check command line options */
  while ((c = getopt(argc, argv, ":m:i")) != -1) {
    switch (c) {
    case 'i': case_insensitive = 1; break;
    case 'm': minsize = atoi(optarg); break;
    default: usage(argv[0]);
    }
  }
  if (minsize < 1) errx(EX_DATAERR, "minimum word size must be > 0");
  if (argc != optind + 2) usage(argv[0]);

  /* Convert first argument to wide-character and normalize */
  if ((n = mbstowcs(NULL, argv[optind], 0)) == -1) err(EX_DATAERR, NULL);
  if (!(pool = calloc(n + 1, sizeof(*pool)))) err(EX_UNAVAILABLE, NULL);
  if (mbstowcs(pool, argv[optind], n + 1) == -1) err(EX_DATAERR, NULL);
  if (case_insensitive) for (i = 0; pool[i]; i++) pool[i] = towlower(pool[i]);

  /* Open dictionary for reading */
  if (!(f = fopen(argv[optind+1], "r"))) err(EX_NOINPUT, "%s", argv[optind]);

  /* Read all words from the dictionary */
  do {
    if (nwords == dictsize) {	/* Make dict array longer */
      dictsize += INCR;
      dict = realloc(dict, dictsize * sizeof(*dict));
      if (!dict) err(EX_UNAVAILABLE, NULL);
    }
    dict[nwords] = NULL;
    n = 0;
    r = getlinews(&dict[nwords], &n, f);
    if (r != -1) {		/* Got a line */
      len = wcslen(dict[nwords]);
      dict[nwords][len-1] = L'\0'; /* Remove newline */
      if (len > minsize) nwords++; /* Word is long enough? */
    }
  } while (r != -1);

  if (!feof(f)) err(EX_IOERR, "%s", argv[optind+1]);
  fclose(f);

  find_all(pool, NULL);

  return EXIT_SUCCESS;
}