/* anagram -- find all permutations of a given string in a dictionary
 *
 * Usage: anagram [-i] string dictionary
 *
 * The dictionary must be a simple list of strings, one per line. The
 * strings need not be words, they may contain spaces and other
 * characters (but no newlines).
 *
 * With option -i, the string and the dictionary are compared
 * case-insensitively. Set the proper locale before calling the
 * program, otherwise the comparison is in the "C" locale. E.g.:
 *
 *   LC_ALL=en_US.UTF-8 anagram sword wordlist.txt
 *
 * Copyright © 2015 World Wide Web Consortium
 * See http://www.w3.org/Consortium/Legal/2002/copyright-software-20021231
 *
 * Author: Bert Bos <bert@w3.org>
 * Created: 14 August 2015
 */

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

#define INCR 100		/* Used with realloc() below */


/* compare -- compare two wide characters, return <0, 0 or >0 */
static int compare(const void *a, const void *b)
{
  assert(a && b);
  return (int)(*((wchar_t*)a) - *((wchar_t*)b));
}


/* normalize -- lowercase and sort the characters, remove newline */
static wchar_t* normalize(const wchar_t const *s, int case_insensitive)
{
  size_t n;
  wchar_t *result;

  assert(s);
  if (!(result = wcsdup(s))) return NULL; /* Out of memory */
  if (case_insensitive)
    for (n = 0; result[n]; n++) result[n] = towlower(result[n]);
  else
    n = wcslen(result);
  if (n != 0 && result[n-1] == L'\n') {n--; result[n] = L'\0';}
  qsort(result, n, sizeof(*result), compare);
  return result;
}


/* 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 */
}


/* 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);
}


int main(int argc, char *argv[])
{
  FILE *f;
  size_t n = 0;
  ssize_t len;
  char c;
  int case_insensitive = 0;
  wchar_t *s1, *s, *t;
  wchar_t *line;

  (void)setlocale(LC_ALL, "");

  /* Check command line options */
  while ((c = getopt(argc, argv, ":i")) != -1) {
    switch (c) {
    case 'i': case_insensitive = 1; break;
    default: usage(argv[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 (!(s1 = calloc(n + 1, sizeof(*s1)))) err(EX_UNAVAILABLE, NULL);
  if (mbstowcs(s1, argv[optind], n + 1) == -1) err(EX_DATAERR, NULL);
  if (!(s = normalize(s1, case_insensitive))) err(EX_UNAVAILABLE, NULL);
  free(s1);

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

  /* Loop over lines from dictionary; normalize and compare */
  n = 0;
  line = NULL;
  while ((len = getlinews(&line, &n, f)) >= 0) {
    if (!(t = normalize(line, case_insensitive))) err(EX_UNAVAILABLE, NULL);
    if (wcscmp(s, t) == 0) fputws(line, stdout);
    free(t);
  }
  if (!feof(f)) err(EX_IOERR, "%s", argv[optind+1]);

  free(line);
  free(s);
  fclose(f);
  return EXIT_SUCCESS;
}