home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / games / volume12 / ag / part01 / anagram.c next >
C/C++ Source or Header  |  1991-05-20  |  16KB  |  676 lines
  1. /**********************************************************
  2.  *                                                        *
  3.  *                                                        *
  4.  *                                                        *   
  5.  *            A program to generate anagrams              *
  6.  *              Based on an idea in Byte, Nov 1987        *
  7.  *                                                        *
  8.  *                     Written by                         *      
  9.  *                                                        *
  10.  *                Morten Lerskau Ronseth                  *
  11.  *                 morten@cs.qmw.ac.uk                    *
  12.  *                                                        *
  13.  *                       9|3|1988                         *
  14.  *                                                        *
  15.  *                                                        *
  16.  **********************************************************/                     
  17.  
  18.  
  19. /*
  20.  * Jan. 30, 1991
  21.  * rewrote the dictionary loader, now uses a pool for allocation.
  22.  */
  23.  
  24. /*
  25.  * Sept. 28, 1990
  26.  * removed "islower" & "isupper" - they didn't work...
  27.  */
  28.      
  29. /*
  30.  * Sept. 26, 1990
  31.  * wrote my own "toupper" & "tolower" so as to be compatible 
  32.  * with any system.
  33.  */
  34.      
  35. #include <stdio.h>
  36. #include <signal.h>
  37.  
  38. extern char *xmalloc (), *xrealloc ();
  39. extern void  xfree ();
  40. extern char *cat_strings ();
  41. extern char *xindex ();
  42. extern void fatal ();
  43. extern void _abort ();
  44.  
  45.  
  46. /* various definitions */
  47.  
  48. #define STD_DICTIONARY "/usr/dict/words"
  49. #define MAX_LINELEN    70
  50. #define MAX_WORDLEN    32
  51. #define MAXMASKS 3
  52. #define bitmask long
  53. #define maskwidth  (8 * sizeof (bitmask))
  54. #define large_pool_space 8192
  55. #define large_word_space 80
  56. #define large_stack_space 200
  57. #define tolower(c) hi2lo[c - 65]
  58. #define toupper(c) lo2hi[c - 65]
  59.  
  60. /* some systems cannot handle lowercase in tolower
  61.    and vice versa...use my own table for fast lookup */
  62.  
  63. char hi2lo[] = {
  64.     'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o',
  65.     'p','q','r','s','t','u','v','w','x','y','z',0,0,0,0,0,0,
  66.     'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o',
  67.     'p','q','r','s','t','u','v','w','x','y','z'
  68. };
  69.  
  70. char lo2hi[] = {
  71.     'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
  72.     'P','Q','R','S','T','U','V','W', 'X','Y','Z', 0,0,0,0,0,0,
  73.     'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
  74.     'P','Q','R','S','T','U','V','W', 'X','Y','Z'
  75. };
  76.  
  77.  
  78. char *program;
  79. char *usage = "[-d `dictionary'] [-a] [-v] [-V] [-w] [-W] [-s `SIZE'] [-o `outfile'] [phrase(s)]";
  80.  
  81. /* 1 if only action is to print out the ellegible words [-W]*/
  82.  
  83. int words_only = 0;
  84.  
  85. /* 1 if the ellegible words are to be printed out [-w]*/
  86.  
  87. int words_out = 0;
  88.  
  89. /* size of smallest word in an angram.
  90.    i.e. -s 2 would prevent angrams with singlelettered words [-s]*/
  91.    
  92. int min_size = 2;
  93.  
  94. /* should we count `a' and `i' as complete words? [-a]*/
  95.  
  96. int do_ai = 0;
  97.  
  98. /* speak up! [-v] */
  99.  
  100. int verbose = 0;
  101.  
  102. /* 1 if write out version info [-V] */
  103.  
  104. int version = 0;
  105.  
  106. /* file to write anagrams to, if any */
  107.  
  108. char *outfile = NULL;
  109. char *infile = STD_DICTIONARY;
  110.  
  111. char version_string[] = "Anagram Finder v. 1.0b3";
  112.  
  113. int no_of_phrases = 0;
  114.  
  115.  
  116. /* phrase variables */
  117.  
  118. typedef bitmask bitsig[MAXMASKS];
  119. int freqs[26], letmask[26], letbit[26], letwidth[26], lastmask;
  120. bitsig uflosig;
  121. char *phrase;
  122. bitmask phrasesig[MAXMASKS];
  123.  
  124. /* pool information */
  125.  
  126. char *pool = NULL;
  127.  
  128. /* dictionary information */
  129.  
  130. char **wordlist = NULL;
  131. int wordcount = 0;
  132. bitmask *wordsigs;
  133.  
  134. /* for printing anagrams */
  135.  
  136. char **analist;
  137. long anacount = 0;
  138. long total = 0;
  139.  
  140.  
  141. /*************************************************************************/
  142.  
  143. #define IS_NUM(X) ((X) >= '0' && (X) <= '9')
  144. #define IS_LETTER(c) (((c) >= 'A' && (c) <= 'Z') || ((c) >= 'a' && (c) <= 'z'))
  145.  
  146. int
  147. str_to_num (s)
  148.     char *s;
  149. {
  150.     int result = 0;
  151.     
  152.     while (*s) {
  153.         if (IS_NUM(*s))
  154.             result = (result * 10) + *s++ - '0';
  155.     }
  156.     return result;
  157. }
  158.  
  159. int
  160. candidate (word)
  161.     register char *word;
  162. {
  163.     register char c;
  164.     register int count = 0;
  165.     
  166.     if (strlen (word) < min_size && !do_ai) return 0;
  167.     while (c = word[count++]) {
  168.         if (!IS_LETTER (c) ||
  169.             (!xindex (phrase, tolower (c)) && 
  170.              !xindex (phrase, toupper (c))))
  171.             return 0;
  172.     }
  173.     if (do_ai && !word[1])
  174.         return (xindex ("aAiI", word[0]) != 0);
  175.     return 1;
  176. }
  177.  
  178.  
  179.  
  180. /* prints out all the anagrams found so far, if any */
  181.  
  182. void
  183. printlist (list, no)
  184.     char **list;
  185.     int no;
  186. {
  187.     register int count;
  188.     register int linelen = 0;
  189.     
  190.     for (count = 0; count < no; count++) {
  191.         linelen += strlen (list[count]) + 1;
  192.         if (linelen >= MAX_LINELEN) {
  193.             linelen = 0;
  194.             (void)fprintf (stdout, "\n");
  195.         }
  196.         (void)fprintf (stdout, "%s ", list[count]);
  197.     }
  198.     (void)fprintf (stdout, "\n");
  199.     (void)fflush (stdout);
  200. }
  201.  
  202. /* old version using log didn't work too well...
  203.    use smalltalk's version of highBit instead */
  204. int
  205. fieldwidth (v)
  206.     int v;
  207. {
  208.     int i = 1, bit = 1;
  209.  
  210.     if (v < 0) _abort ("Fieldwidth: negative number");
  211.     if (!v) return 2;
  212.     while (v > bit) {
  213.         i++; bit += bit + 1;
  214.     }
  215.     return (i + 2);
  216. }
  217.  
  218. void
  219. makefreqs (str, freq)
  220.     register char *str;
  221.     register int freq[];
  222. {
  223.     register char c;
  224.     register int f;
  225.     
  226.     for (f = 0; f < 26; f++) 
  227.         freq[f] = 0;
  228.     while (c = *(str++)) {
  229.         freq[tolower (c) - 97] += 1;
  230.     }
  231. }
  232.  
  233. void
  234. choosefields (frq)
  235.     int frq[];
  236. {
  237.     int letter;
  238.     int curmask = 0,curbit = 0;
  239.     int width;
  240.     
  241.     for (letter = 0; letter < 26; letter++)
  242.         if (frq[letter] != 0) {
  243.             width = fieldwidth (frq[letter]);
  244.             if ((curbit + width) > maskwidth) {
  245.                 if (++curmask >= MAXMASKS)
  246.                     _abort ("Phrase too long to handle.");
  247.                 curbit = 0;
  248.             }
  249.             letmask[letter] = curmask;
  250.             letbit[letter] = curbit;
  251.             letwidth[letter] = width;
  252.             curbit += width;
  253.         }
  254.     lastmask = curmask;
  255. }
  256.  
  257. void
  258. makeonesig (str, sig)
  259.     register char *str;
  260.     register bitmask sig[];
  261. {
  262.     register int i, j = 0;
  263.     int sfreqs[26];
  264.     register bitmask fr;
  265.     
  266.     makefreqs (str, sfreqs);
  267.     for (i = 0; i <= lastmask; i++)
  268.         sig[i] = 0;
  269.     for (i = 0; i < 26; i++)
  270.         if (sfreqs[i]) {
  271.             fr = ((bitmask)sfreqs[i]) << letbit[i];
  272.             sig[letmask[i]] += fr;
  273.             j += fr;
  274.         }
  275. }
  276.  
  277. void
  278. makeuf (frq)
  279.     int frq[];
  280. {
  281.     int i, bnum, bwidth;
  282.     
  283.     for (i = 0; i < MAXMASKS; i++)
  284.         uflosig[i] = 0;
  285.     for (i = 0; i < 26; i++)
  286.         if (frq[i]) {
  287.             bnum = letbit[i];
  288.             bwidth = letwidth[i];
  289.             uflosig[letmask[i]] += (1L << (bnum + bwidth - 1));
  290.         }
  291. }
  292.  
  293. #define DOMASK(MASK) {                           \
  294.     newmask = curnode[MASK] - cursig[MASK];      \
  295.     if (newmask & uflosig[MASK]) break;          \
  296.     newsig[MASK] = newmask;                      \
  297.     bitsleft |= newmask;                         \
  298. }
  299.     
  300.  
  301. void
  302. findanagrams (curword, curnode)
  303.     register int curword;
  304.     register bitmask *curnode;
  305. {
  306.     bitsig newsig;
  307.     register bitmask newmask, *cursig;
  308.     register long bitsleft;
  309.     int bsize = large_stack_space;
  310.     
  311.     cursig = &wordsigs[curword * (lastmask + 1)];
  312.     while (curword < wordcount) {
  313.         bitsleft = 0;
  314.         switch (lastmask) {
  315.             case 2:DOMASK(2)
  316.             case 1:DOMASK(1)
  317.             case 0:DOMASK(0)
  318.             
  319.             if (anacount == bsize) {
  320.                 bsize *= 2;
  321.                 analist = (char **)xrealloc (analist, bsize * sizeof (char *));
  322.             }
  323.             analist[anacount++] = wordlist[curword];
  324.             if (!bitsleft) {
  325.                 printlist (analist, anacount);
  326.                 total++;
  327.             }
  328.             else findanagrams (curword, newsig);
  329.             --anacount;
  330.         }
  331.         curword++;
  332.         cursig += (lastmask + 1);
  333.     }
  334. }
  335.  
  336.  
  337. /* If realloc moves the list around in memory (not very likely, but still...)
  338.  * then update all pointers in the wordlist.
  339.  */
  340.  
  341. void
  342. adjust_list (list, offset, count)
  343.     char **list;
  344.     int offset, count;
  345. {
  346.     register int i;
  347.  
  348.     for (i = 0; i < count; i++)
  349.         list[i] += offset;
  350. }
  351.  
  352.  
  353. void
  354. read_dict (name)
  355.     char *name;
  356. {
  357.     FILE *dict;
  358.     int psize = large_pool_space;
  359.     int bsize = large_stack_space;
  360.     int msize = large_stack_space * MAXMASKS;
  361.     char *pend, *next_slot;
  362.     
  363.     if (!(dict = fopen (name, "r"))) {
  364.         char *s = cat_strings ("Couldn't open <", name, ">");
  365.         _abort (s);
  366.     }
  367.     if (verbose) {
  368.         (void)fprintf (stderr, "\nLoading dictionary...");
  369.         (void)fflush (stderr);
  370.     }
  371.     
  372.     /* analist has to be set up here, as "findanagrams" is recursive */
  373.     analist = (char **)xmalloc (bsize * sizeof (char *));
  374.     wordlist = (char **) xmalloc (bsize * sizeof (char *));
  375.     wordsigs = (bitmask *) xmalloc (msize * sizeof (bitmask));
  376.     pool = (char *)xmalloc (psize * sizeof (char));
  377.     pend = pool + psize;
  378.     next_slot = pool;
  379.     
  380.     while (fscanf (dict, "%s", next_slot) != EOF) {
  381.         if (candidate (next_slot)) {
  382.         
  383.             /* if this entry would overflow stack, expand it */
  384.             
  385.             if (wordcount == bsize) {
  386.                 bsize *= 2; msize *= 2;
  387.                 wordlist = (char **)xrealloc (wordlist, bsize * sizeof (char *));
  388.                 wordsigs = (bitmask *)xrealloc (wordsigs, msize * sizeof (bitmask));
  389.             }
  390.             wordlist[wordcount] = next_slot;
  391.             makeonesig (next_slot, &wordsigs[wordcount * (lastmask + 1)]);
  392.  
  393.             next_slot += strlen (next_slot) + 1;
  394.             if ((next_slot + MAX_WORDLEN) >= pend) {
  395.                 char *old_pool = pool;
  396.  
  397.                 psize *= 2;
  398.                 pool = (char *)xrealloc (pool, psize * sizeof (char));
  399.                 if (old_pool != pool)
  400.                     adjust_list (wordlist, pool - old_pool, wordcount);
  401.                 pend = pool + psize;
  402.             }
  403.             wordcount++;
  404.         }
  405.     }
  406.     if (verbose) {
  407.         (void)fprintf (stderr, "done\n"); 
  408.         (void)fflush (stderr);
  409.     }
  410.     (void)fclose (dict);
  411. }
  412.  
  413. void
  414. clean_up ()
  415. {
  416.     /* first, free all strings allocated */
  417.     
  418.     xfree (pool);
  419.         
  420.     /* then, free the array of pointers to these strings */
  421.         
  422.     xfree (wordlist);
  423.     
  424.     /* then, free the array of pointers to the anagrams */
  425.     
  426.     xfree (analist);
  427.     
  428.     /* At last, free the array `wordsigs' */
  429.     
  430.     xfree (wordsigs);
  431. }
  432.  
  433. void
  434. parse_flags (argc, argv)
  435.     int argc;
  436.     char *argv[];
  437. {
  438.     int i;
  439.  
  440.     for (i = 1; i < argc; i++) {
  441.         if (argv[i][0] == '-' && argv[i][1] != 0) {
  442.         
  443.             register char *str = argv[i] + 1;
  444.             
  445.             switch (str[0]) {
  446.                 case 'd':
  447.                     if (argv[i + 1] != NULL) {
  448.                         infile = argv[i + 1];
  449.                         argv[i + 1] = NULL;
  450.                     }
  451.                     break;
  452.  
  453.                 case 's':
  454.                     if (argv[i + 1] != NULL) {
  455.                         min_size = str_to_num (argv[i + 1]);
  456.                         argv[i + 1] = NULL;
  457.                     }
  458.                     else
  459.                         _abort ("No size specified.");
  460.                     break;
  461.  
  462.                 case 'o':
  463.                     if (outfile != NULL)
  464.                         _abort ("Outfile specified twice");
  465.                     if (argv[i + 1] != NULL) {
  466.                         outfile = argv[i + 1];
  467.                         if (!strncmp (outfile, "-", 1))
  468.                             outfile = "";
  469.                         else
  470.                             argv[i + 1] = NULL;
  471.                     }
  472.                     else
  473.                         _abort ("No outfile specified.");
  474.                     break;
  475.  
  476.                 case 'a':
  477.                     do_ai = 1;
  478.                     break;
  479.  
  480.                 case 'v':
  481.                     verbose = 1;
  482.                     break;
  483.  
  484.                 case 'V':
  485.                     version = 1;
  486.                     break;
  487.  
  488.                 case 'w':
  489.                     words_out = 1;
  490.                     break;
  491.  
  492.                 case 'W':
  493.                     words_only = 1;
  494.                     break;
  495.  
  496.                 case '-':
  497.                 case '\n':
  498.                     if (outfile == NULL)
  499.                         outfile = "";
  500.                     argv[i] = NULL;
  501.                     break;
  502.  
  503.                 default : {
  504.                     char *s = cat_strings ("Unrecognized flag: \"", str, "\"");
  505.                     _abort (s);
  506.                 }
  507.             }
  508.         }
  509.         else if (argv[i] != NULL && ++no_of_phrases != i) {
  510.             argv[no_of_phrases] = argv[i];
  511.             argv[i] = NULL;
  512.         }
  513.     }
  514. }
  515.  
  516. void
  517. do_all (argv)
  518.     char *argv[];
  519. {
  520.     int i, j;
  521.  
  522.     for (i = 1; i <= no_of_phrases; i++) {
  523.     
  524.         phrase = argv[i];
  525.         wordcount = 0;
  526.         anacount = 0;
  527.         total = 0;
  528.  
  529.         makefreqs (phrase, freqs);
  530.         choosefields (freqs);
  531.         makeonesig (phrase, phrasesig);
  532.         makeuf (freqs);
  533.         read_dict (infile);
  534.         if (words_out || words_only) {
  535.              (void)fprintf (stdout, "number of words read : %d\n", 
  536.                             wordcount); 
  537.              (void)fflush (stdout);
  538.              printlist (wordlist, wordcount);
  539.         }
  540.         if (words_only)
  541.             continue;
  542.         if (verbose) {
  543.             (void)fprintf (stderr, "\nStarting generator...");
  544.                 
  545.             (void)fprintf (stdout, "\n Anagrams generated from \"%s\" :", phrase);
  546.             (void)fprintf (stdout, "\n--------------------------");
  547.             for (j = 0; j < strlen (phrase); j++)
  548.                 (void)fprintf (stdout, "-");
  549.             (void)fprintf (stdout, "---\n");
  550.             (void)fflush (stdout);
  551.         }
  552.  
  553.         /* Find all anagrams asociated with the specified pattern */
  554.         
  555.         findanagrams (0, phrasesig);
  556.         if (verbose) {
  557.             (void)fprintf (stdout, "\nNo. of anagrams : %ld\n", total);
  558.             (void)fprintf (stderr, "done\n");
  559.         }
  560.         clean_up ();
  561.     }
  562.     
  563. }
  564.  
  565. main (argc, argv)
  566.     int argc;
  567.     char **argv;
  568. {
  569.     /* set up interrupt handler */
  570.     if (signal (SIGINT, SIG_IGN) != SIG_IGN)
  571.         signal (SIGINT, fatal);
  572.     if (signal (SIGKILL, SIG_IGN) != SIG_IGN)
  573.         signal (SIGKILL, fatal);
  574.  
  575.  
  576.     program = argv[0];
  577.  
  578.     if (argc == 1)
  579.         _abort (usage);
  580.  
  581.     parse_flags (argc, argv);
  582.         
  583.     if (version) {
  584.         (void)fprintf (stderr, "%s\n", version_string);
  585.         if (no_of_phrases == 0)
  586.             exit (0);
  587.     }
  588.     if (no_of_phrases == 0)
  589.         _abort ("No pattern(s) specified");
  590.  
  591.     if (!outfile || !strcmp (outfile, ""))
  592.         outfile = "stdout";
  593.     else if (!freopen (outfile, "w", stdout)) {
  594.         char *s = cat_strings ("Couldn't open ", outfile, "");
  595.         _abort (s);
  596.     }
  597.     do_all (argv);
  598.     return (0);
  599. }
  600.      
  601.  
  602.      
  603. char *
  604. xrealloc (ptr, size)
  605.     char *ptr;
  606.     int size;
  607. {
  608.     register char *result = (char *)realloc (ptr, size);
  609.     if (!result)
  610.         _abort ("Virtual memory exhausted.");
  611.     return result;
  612. }
  613.  
  614. char *
  615. xmalloc (size)
  616.     int size;
  617. {
  618.     register char *result = (char *)calloc (1, size);
  619.     if (!result)
  620.         _abort ("Virtual memory exhausted.");
  621.     return result;
  622. }
  623.  
  624. void
  625. xfree (ptr)
  626.     char *ptr;
  627. {
  628.     if (ptr) free (ptr);
  629. }
  630.  
  631. void
  632. fatal (signum)
  633.     int signum;
  634. {
  635.   signal (signum, SIG_DFL);
  636. }
  637.  
  638. char *
  639. cat_strings (s1, s2, s3)
  640.     char *s1, *s2, *s3;
  641. {
  642.     int len1 = strlen (s1), len2 = strlen (s2), len3 = strlen (s3);
  643.     char *s = (char *) xmalloc (len1 + len2 + len3 + 1);
  644.  
  645.     (void)strcpy (s, s1);
  646.     (void)strcpy (s + len1, s2);
  647.     (void)strcpy (s + len1 + len2, s3);
  648.     *(s + len1 + len2 + len3) = 0;
  649.     
  650.     return s;
  651. }
  652.  
  653. /* BSD and SYSV use different names, so use my own */
  654.  
  655. char *
  656. xindex (s, c)
  657.     register char *s, c;
  658. {
  659.     while (*s) {
  660.         if (*s == c) return (s);
  661.         s++;
  662.     }
  663.     return 0;
  664. }
  665.  
  666. void
  667. _abort (arg)
  668.     char *arg;
  669. {
  670.     (void)fprintf (stderr, "%s: ", program);
  671.     (void)fprintf (stderr, arg);
  672.     (void)fprintf (stderr, "\n");
  673.     (void)fflush (stderr);
  674.     exit (-1);
  675. }
  676.