#ifndef lint
static char sccsid[] = "@(#)anagram.c (U of Maryland) FLB 4-Sep-1987";
static char RCSid[] = "@(#)$Header: anagram.c,v 1.1 87/09/11 02:19:33 fred Exp $";
#endif

/*
 * anagram - search a dictionary for anagrams of a given string
 *
 *     Anagram takes each of its arguments in turn and searches
 *     a dictionary file for anagrams, printing any it finds to
 *     the standard output.
 *
 *     Options:
 *
 *             -d <dictionary-file>
 *                     Specifies a file other than the default,
 *                     to read the word list from.
 *
 *             -m <n>
 *                     Indicates the minimum number of characters
 *                     in an anagram, which will be acceptable.
 *                     The default is 2.
 *
 *             -l
 *                     Permits partial matches with 'leftover'
 *                     letters which will be printed between
 *                     square brackets.
 *
 *             -r
 *                     Recursive mode: anagram will find
 *                     partial mathces and then attempt to
 *                     find matches for the remaning letters.
 *
 *     Fred Blonder <fred@mimsy.umd.edu>, September 4, 1987
 *
 * To compile:
 %     cc -s -O anagram.c -o anagram
 */

#include <stdio.h>
#include <sysexits.h>
#include <ctype.h>

char *index();

#define        DICTIONARY      "/usr/dict/words"       /* Default dictionary */
#define        LETTERS_IN_ALPHABET     26      /* This shouldn't change much. ;-) */

typedef char histogram[LETTERS_IN_ALPHABET];

/* Program arguments and defaults. */
char *dictionary = DICTIONARY;
int leftovers_flag = 0, min_letters = 2, recurse_flag = 0;

/*****************************************************************************/

main(argc, argv)
int argc;
char *argv[];
{

#define        SHIFT   argc--; argv++

SHIFT;

while (argc > 0 && **argv == '-') {    /* Munch on flag arguments. */
       register char *cp;

       for (cp = &argv[0][1]; *cp; cp++)
               switch (*cp) {
                       case 'd':       /* User-specified dictionary */
                               SHIFT;
                               dictionary = *argv;
                               break;

                       case 'l':       /* Allow 'leftover' letters */
                               leftovers_flag++;
                               break;

                       case 'm':       /* Specify minimum word length */
                               SHIFT;
                               min_letters = atoi(*argv);
                               break;

                       case 'r':       /* Recursive mode */
                               recurse_flag++;
                               break;

                       default:
                               fprintf(stderr,
                                       "anagram: unknown flag: %c\n", *cp);
                       }
       SHIFT;
       }

if (argc < 1) {
       fprintf(stderr,
           "usage: anagram [ -d <dictionary> ] [ -m <number> ] [ -l ] ");
       fprintf(stderr, "[ -r ] string1 [ string2 . . . ]\n");
       exit(EX_USAGE);
       }

do {
       unscramble(*argv);
       SHIFT;
       if (argc > 0)
               putchar('\n');
       } while(argc > 0);

exit (EX_OK);
}

/*****************************************************************************/

unscramble(word)
char word[];
{
histogram w_h, d_h, diff_h;
register FILE *dict_f;
char dict_buff[BUFSIZ];
register int diff;
long p_loc = 0L;

make_hist(word, w_h);

if ((dict_f = fopen(dictionary, "r")) == NULL) {
       perror(dictionary);
       exit(EX_OSFILE);
       }

while (p_loc = ftell(dict_f), fgets(dict_buff, BUFSIZ, dict_f) != NULL) {
       register char *cp;

       if (cp = index(dict_buff, '\n'))
               *cp = '\0';

       if (strlen(dict_buff) < min_letters)
               continue;

       {
       register char *cp;

       for (cp = dict_buff; *cp && isalpha(*cp); cp++);
       if (*cp)
               continue;
       }

       make_hist(dict_buff, d_h);
       diff = cmp_hist(w_h, d_h, diff_h);

       if (!diff) {
               printf("%s\n", dict_buff);
               continue;
               }

       if (diff > 0) {
               long f_loc;

               f_loc = ftell(dict_f);
               if (fseek(dict_f, p_loc, 0) < 0) {
                       perror("Seek error on dictionary file");
                       exit(EX_IOERR);
                       }
               remainder(dict_buff, dict_f, diff_h);
               if (fseek(dict_f, f_loc, 0) < 0) {
                       perror("Seek error on dictionary file");
                       exit(EX_IOERR);
                       }
               }
       }

(void)fclose(dict_f);
}

/*****************************************************************************/

remainder(p_line, file, hist)
char p_line[];
register FILE *file;
histogram hist;
{
histogram d_h, diff_h;
char dict_buff[BUFSIZ];
register int diff, found_match = 0;
long p_loc = 0L;

if (recurse_flag)
       while (p_loc = ftell(file), fgets(dict_buff, BUFSIZ, file) != NULL) {
               register char *cp;

               if (cp = index(dict_buff, '\n'))
                       *cp = '\0';

               if (strlen(dict_buff) < min_letters)
                       continue;

               {
               register char *cp;

               for (cp = dict_buff; *cp && isalpha(*cp); cp++);
               if (*cp)
                       continue;
               }

               make_hist(dict_buff, d_h);
               diff = cmp_hist(hist, d_h, diff_h);

               if (!diff) {
                       printf("%s %s\n", p_line, dict_buff);
                       found_match++;
                       continue;
                       }

               if (diff > 0) {
                       long f_loc;
                       char t_buf[BUFSIZ];

                       f_loc = ftell(file);
                       if (fseek(file, p_loc, 0) < 0) {
                               perror("Seek error on dictionary file");
                               exit(EX_IOERR);
                               }
                       (void)sprintf(t_buf, "%s %s", p_line, dict_buff);
                       remainder(t_buf, file, diff_h);
                       found_match++;
                       if (fseek(file, f_loc, 0) < 0) {
                               perror("Seek error on dictionary file");
                               exit(EX_IOERR);
                               }
                       }
               }

if (!found_match && leftovers_flag) {
       printf("%s ", p_line);
       print_hist(hist);
       putchar('\n');
       }
}

/*****************************************************************************/

make_hist(word, w_hist)
char word[];
histogram w_hist;
{
register char *cp;

for (cp = (char *)w_hist; cp < (char *)&w_hist[LETTERS_IN_ALPHABET]; cp++)
       *cp = (char)0;

for (cp = word; *cp; cp++)
       if (isalpha(*cp))
               if (isupper(*cp))
                       w_hist[tolower(*cp)-'a']++;
               else
                       w_hist[*cp-'a']++;
}

/*****************************************************************************/

cmp_hist(h1, h2, h3)
histogram h1, h2, h3;
{
register char *cp1, *cp2, *cp3;
register int c = LETTERS_IN_ALPHABET;
int ret_val = 0;

for (cp1 = (char *)h1, cp2 = (char *)h2, cp3 = (char *)h3;
                                       c-- > 0; cp1++, cp2++, cp3++)
       if (*cp3 = (*cp1 - *cp2))
               if (*cp3 > 0)
                       ret_val++;
               else
                       return -1;

return ret_val;
}

/*****************************************************************************/

print_hist(h)
histogram h;
{
register int k;

putchar('[');

for (k = 0; k < LETTERS_IN_ALPHABET; k++) {
       register int i;

       for (i = h[k]; i > 0; i--)
               putchar('a'+k);
       }

putchar(']');
}

/*****************************************************************************/