home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 2 / FFMCD02.bin / new / dev / misc / cweb / examples / wordtest.w < prev    next >
Text File  |  1993-12-21  |  21KB  |  540 lines
  1. \datethis
  2. @* Introduction. This program is a simple filter that sorts and outputs all
  3. lines of input that do not appear in a given set of sorted files. It is called
  4. {\tt wordtest} because each line of input is considered to be a `word' and
  5. each of the sorted files is considered to be a 'dictionary'. Words are
  6. output when they don't appear in any given dictionary.
  7.  
  8. The character set and alphabetic order are flexible. Every 8-bit
  9. character is mapped into an integer called its {\it ord}. A character
  10. is called a {\it null\/} if its ord is zero; such characters are
  11. discarded from the input. A character is called a {\it break\/} if
  12. its ord is negative; such characters break the input into so-called words.
  13. Otherwise a character's ord is positive, and the character is called a
  14. {\it letter}. One letter precedes another in alphabetic order if and only
  15. if it has a smaller ord. Two letters are considered identical, for
  16. purposes of sorting, if their ords are the same.
  17.  
  18. The null character |'\n'| must have ord~0; thus, it must remain null.
  19. Otherwise the ord mapping is arbitrary. If the user doesn't specify
  20. any special mapping, the default ord table simply maps every 8-bit
  21. character code into itself, considering characters to be unsigned char
  22. values in the range 0--255, except that ASCII codes {\tt a-z} are
  23. mapped into the corresponding codes for {\tt A-Z}, and newline is a
  24. break character. Optional command-line arguments, described below, can
  25. change this default mapping to any other desired scheme.
  26.  
  27. A word is any nonempty sequence of letters that is immediately preceded
  28. and followed by break characters, when nulls are ignored. Technically
  29. speaking, we pretend that a break character is present at the beginning of a
  30. file but not at the end; thus, all letters following the final break character
  31. of a file are ignored, if any such letters are present. Two words are
  32. {\it equivalent\/} to each other if their letters have the same sequence
  33. of ord values. If two or more words of the input are equivalent, only
  34. the first will be output, and it will be output only if it is not
  35. equivalent to any word in the given dictionary files. Words in each
  36. dictionary are assumed to be in lexicographic order and to contain no
  37. nulls. Words in the output file will satisfy these conditions; therefore
  38. {\tt wordtest} can be used to generate and update the dictionaries it needs.
  39. Notice that if no dictionaries are given, {\tt wordtest} will act as a
  40. sorting routine that simply discards nulls and duplicate lines.
  41.  
  42. @ The \UNIX/ command line `{\tt wordtest} {\tt [options]} {\tt [dictionaries]}'
  43. is interpreted by executing option commands from left to right and then by
  44. regarding any remaining arguments as the names of dictionary files.
  45.  
  46. Most of the option commands are designed to specify the |ord| table.
  47. Initially |ord[c]=c| for each unsigned char code~|c|. The command
  48. $$\line{\hskip5em\tt-b\it string\hfil}$$
  49. makes every character in the string a break character. If the string is
  50. empty, {\tt-b} makes every nonnull character a break (i.e., it sets
  51. |ord[c]=-1| for |1<=c<=255|). The command
  52. $$\line{\hskip5em\tt-n\it string\hfil}$$
  53. makes every character in the string a null character. If the string is
  54. empty, {\tt-n} makes every character null. The command
  55. $$\line{\hskip5em\tt-a\it string\hfil}$$
  56. sets the ord of the $k$th element of the string equal to $\delta+k$,
  57. where $\delta$ is an offset value (normally zero). The command
  58. $$\line{\hskip5em\tt-d\it offset\hfil}$$
  59. sets the value of $\delta$; the offset should be a decimal integer between
  60. 0 and 255.
  61.  
  62. There is also an option that has no effect on the |ord| table:
  63. $$\line{\hskip5em\tt-m\it length\hfil}$$
  64. defines the length of the longest word. If any word of a file has
  65. more than this many characters, a break is artificially inserted
  66. so that a word of this maximum length is obtained. The default value is 50.
  67. The maximum legal value is 1000.
  68.  
  69. If the given options do not specify at least one break character,
  70. {\tt wordtest} applies the option commands
  71. $$\vbox{\line{\hskip5em\.{-b"\\}\hfil}
  72. \line{\.{" -d64 -a"abcdefghijklmnopqrstuvwxyz"}\hfil}}$$
  73. which generate the default mapping mentioned above (unless other ords were
  74. changed).
  75.  
  76. The program is designed to run fastest when there are at most two
  77. dictionary files (usually one large system dictionary and another
  78. personalized one), although it places no limit on the actual number of
  79. dictionaries that can be mentioned on the command line. Users who want
  80. to specify a multitude of dictionaries should ask themselves why they
  81. wouldn't prefer to merge their dictionaries together first (using
  82. {\tt wordtest}).
  83.  
  84. @d MAX_LENGTH_DEFAULT 50
  85. @d MAX_LENGTH_LIMIT 1000
  86.  
  87. @ The general organization of {\tt wordtest} is typical of applications
  88. written in \CEE/, and its approach is quite simple. If any errors are
  89. detected, an indication of the error is sent to the |stderr| file and
  90. a nonzero value is returned.
  91.  
  92. @p
  93. #include <stdio.h>
  94. @#
  95. @<Typedefs@>@;
  96. int main(argc,argv)
  97.   int argc; /* the number of command-line arguments */
  98.   char *argv[]; /* the arguments themselves */
  99. {
  100.   @<Local variables@>;
  101.   @<Scan the command line arguments@>;
  102.   @<Sort the input into memory@>;
  103.   @<Output all input words that aren't in dictionaries@>;
  104.   return 0;
  105. }
  106.  
  107. @ @<Typedefs@>=
  108. typedef unsigned char byte; /* our bytes will range from 0 to 255 */
  109.  
  110. @ @<Local variables@>=
  111. int targc; /* temporary modifications to |argc| */
  112. byte **targv; /* pointer to the current argument of interest */
  113. unsigned delta; /* the offset used in the \.{-a} and \.{-d} options */
  114. unsigned max_length=MAX_LENGTH_DEFAULT; /* longest allowable word */
  115. byte breakchar; /* break character to use in the output */
  116. int ord[256]; /* table of ord values */
  117. register int c; /* an all-purpose index */
  118. register byte *u,*v; /* pointer to current string characters */
  119.  
  120. @ We try to use newline as the output break character, if possible.
  121.  
  122. @<Scan the command line arguments@>=
  123. for (c=0;c<256;c++) ord[c]=c;
  124. delta=0;
  125. targc=argc-1;@+targv=(byte**)argv+1;
  126. while (targc && **targv=='-') {
  127.   @<Execute the option command |targv|@>;
  128.   targc--;@+targv++;
  129. }
  130. if (ord['\n']<0) breakchar='\n';
  131. else {
  132.   breakchar='\0';
  133.   for (c=255;c;c--) if (ord[c]<0) breakchar=c;
  134.   if (!breakchar) @<Set up the default ords@>;
  135. }
  136. @<Allocate data structures for a total of |targc| files@>;
  137. for (;targc;targc--,targv++) @<Open the dictionary file named |*targv|@>;
  138.  
  139. @ @<Execute the option...@>=
  140. switch((*targv)[1]) {
  141. case 'a': for (c=delta,u=*targv+2;*u;u++) ord[*u]=++c;@+break;
  142. case 'b': if ((*targv)[2]) for (u=*targv+2;*u;u++) ord[*u]=-1;
  143.   else for (c=1;c<256;c++) ord[c]=-1;
  144.   break;
  145. case 'n': if ((*targv)[2]) for (u=*targv+2;*u;u++) ord[*u]=0;
  146.   else for (c=1;c<256;c++) ord[c]=0;
  147.   break;
  148. case 'd': if (sscanf((char*)*targv+2,"%u",&delta)==1 && delta<256) break;
  149.   goto print_usage;
  150. case 'm': if (sscanf((char*)*targv+2,"%u",&max_length)==1 &
  151.     max_length<=MAX_LENGTH_LIMIT) break;
  152.   goto print_usage;
  153. default: print_usage: fprintf(stderr,
  154.   "Usage: %s {-{{a|b|n}string|{d|m}number}}* dictionaryname*\n",*argv);
  155.   return-1;
  156. }
  157.  
  158. @ @<Set up the default ords@>=
  159. {
  160.   ord['\n']=-1; /* newline is break character */
  161.   breakchar='\n';
  162.   for (c=1;c<=26;c++) ord['a'-1+c]='A'-1+c;
  163. }
  164.  
  165. @*Treaps. The most interesting part of this program is its sorting algorithm,
  166. which is based on the ``treap'' data structure of Aragon and Seidel
  167. [{\sl 30th IEEE Symposium on Foundations of Computer Science\/} (1989),
  168. 540--546].
  169. @^Aragon, Cecilia Rodriguez@>@^Seidel, Raimund@>
  170. A treap is a binary tree whose nodes have two key fields. The primary
  171. key, which in our application is a word from the input, obeys
  172. tree-search order: All descendants of the left child of node~$p$ have
  173. a primary key that is less than the primary key of~$p$, and all descendants
  174. of its right child have a primary key that is greater. The secondary key,
  175. which in our application is a unique pseudorandom integer attached to
  176. each input word, obeys heap order: The secondary key of~$p$'s children
  177. is greater than $p$'s own secondary key.
  178.  
  179. A given set of nodes with distinct primary keys and distinct secondary
  180. keys can be made into a treap in exactly one way. This unique treap
  181. can be obtained, for example, by