home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1515 < prev    next >
Encoding:
Internet Message Format  |  1990-12-28  |  47.5 KB
  1. From: gtoal@tharr.UUCP (Graham Toal)
  2. Newsgroups: alt.sources
  3. Subject: Spelling utilities in C (Part 3 of 3)
  4. Message-ID: <809@tharr.UUCP>
  5. Date: 28 Jun 90 07:09:57 GMT
  6.  
  7. #!/bin/sh-----cut here-----cut here-----cut here-----cut here-----
  8. # shar:    Shell Archiver
  9. #    Run the following text with /bin/sh to create:
  10. #    dawg.c #    dwgcheck.c #    pack.c #    pckcheck.c #    pdawg.c #    ppack.c #    proot.c #    sample.c #    tell.c 
  11. cat - << \SHAR_EOF > dawg.c
  12. /* The first three #define's are to repair mangling by BITNET mailers */
  13. #define EOR ^
  14.               /* This should be Caret (hat, up arrow) -- C Ex-or */
  15. #define MOD %
  16.               /* This should be Percent -- C Modulus             */
  17. #define NOT ~
  18.               /* This should be Tilde (twiddle) -- C unary Not   */
  19. #include "copyr.h"
  20. /*****************************************************************************/
  21. /*                                                                           */
  22. /*      FILE : DAWG.C                                                        */
  23. /*                                                                           */
  24. /*      Convert an alphabetically-ordered dictionary file in text format     */
  25. /*      (one word per line) into a Directed Acyclic Word Graph. The command  */
  26. /*      syntax is                                                            */
  27. /*                                                                           */
  28. /*              DAWG <text file (inc .ext)> <output file (no ext)>           */
  29. /*                                                                           */
  30. /*      The first 4 bytes of the output file form a 24-bit number containing */
  31. /*      the number of edges in the dawg. The rest of the file contains the   */
  32. /*      dawg itself (see "The World's Fastest Scrabble Program" by Appel     */
  33. /*      and Jacobson for a description of a dawg).                           */
  34. /*                                                                           */
  35. /*****************************************************************************/
  36.  
  37. #include "grope.h"
  38. #ifndef grope_h
  39. /* If you don't have grope.h, create an empty one.
  40.    These will do for a basic system: */
  41. #undef KNOWS_VOID
  42. #undef STDLIBS
  43. #undef PROTOTYPES
  44. #define SYS_ANY 1
  45. #define COMPILER_ANY 1
  46. #define SMALL_MEMORY 1
  47.                        /*  To be defined if you have to generate
  48.                            the data structure in bits. This will
  49.                            certainly be true for any non-trivial
  50.                            dictionary on MSDOS, or most home
  51.                            micros with 1Mb Ram or under. */
  52. #endif
  53. /* Portability notes:
  54.  
  55.    0) KISS! Keep It Simple, Stupid!
  56.  
  57.    1) No typedef's
  58.    2) No bitfields
  59.    3) No structs
  60.    4) No #if defined()
  61.    5) No complex #if's
  62.    6) No procedure variables
  63.    7) Don't trust tolower() as some libs don't range check
  64.    8) Stay character-set independent (EBCDIC should work?)
  65.    9) Assume sizeof(long) >= 32 bits, but sizeof(int) just >= 16
  66.   10) Note use of ABS in preference to unsigned longs.
  67.   11) Assume 8-bit char set
  68.   12) Don't use k&r reserved words for variables, even if not
  69.       in ANSI.  Such as 'entry'.
  70.   13) Unix people; no sys/ or machine/ files please unless under a
  71.       suitable #ifdef, and generic code supplied for everyone else...
  72.   14) this is byte-sex independant at the moment. KEEP IT THAT WAY!
  73.       Don't assume dawgs are stored in a fixed form, such as so-called
  74.       'net-order'.
  75.   15) Since C doesn't range-check arrays, we'll do it. If possible,
  76.       leave the running systems with range checking on if you can
  77.       afford it!
  78.   16) No nested include files.
  79.   17) Don't pull in any include files twice. (*Kills* the Atari!)
  80.   18) Don't use 'register' -- trust the compiler; the compiler is your friend.
  81.  */
  82. /*#define RCHECK 1*/      /* We want range-checking of array accesses */
  83.  
  84. #include <stdio.h>
  85.  
  86. #ifdef LIB_STRINGS
  87. #include <strings.h>    /* Some unixes, Mac? */
  88. #else
  89. #include <string.h>
  90. #endif
  91.  
  92. #ifdef SYS_MAC
  93. /* To compile with THINK C 4.0, place the files dawg.h grope.h,
  94.    dawg.c and utils.c in a folder.  Create a project that contains
  95.    dawg.c and the libraries unix and ANSI.
  96. */
  97. #include <unix.h>
  98. #include <stdlib.h>
  99. #include <console.h>
  100. /* Assume a 1Mb mac for the moment. Someday I'll add dynamic RAM sizing */
  101. #define SMALL_MEMORY 1
  102. #endif
  103.  
  104. #include "dawg.h"   /* main system constants */
  105.  
  106. #include "utils.c"  /* utils.c pulls in header file for malloc/free & exit */
  107.  
  108. #define ABS(x) ((x) < 0 ? -(x) : (x))
  109.  
  110. /**
  111. *  The following constant, HASH_TABLE_SIZE, can be changed according to
  112. *  dictionary size.  The two values shown will be fine for both large
  113. *  and small systems.  It MUST be prime.
  114. **/
  115.  
  116. #ifdef SMALL_MEMORY
  117. #define HASH_TABLE_SIZE 30011
  118.  
  119. #ifdef SYS_MAC
  120. /* boy, you guys must be *really* tight on space...
  121.    are you sure you can handle a reasonable size of dictionary with
  122.    such a small table? Bump this back up as soon as you get everything
  123.    else working... 
  124.    (I was given this info by a Mac site while they were first porting
  125.    this stuff; maybe now it works on macs we can put the buffer size
  126.    back up to something reasonable)
  127.  */
  128. #undef HASH_TABLE_SIZE
  129. #define HASH_TABLE_SIZE 17389
  130. #endif
  131.  
  132. #else
  133. /* pick one about 20% larger than needed */
  134. #define HASH_TABLE_SIZE 240007
  135.  
  136. /* Suitable prime numbers if you want to tune it:
  137.      30011
  138.     150001  <-- probably a good compromise. OK for dicts to about 1Mb text
  139.     200003
  140.     220009
  141.     240007
  142.  
  143.    If you try any others, for goodness sake CHECK THAT THEY ARE PRIME!!!
  144.  
  145.  */
  146. #endif
  147. #define MAX_EDGES (HASH_TABLE_SIZE-1)
  148.  
  149. static FILE *fpin, *fpout;     /* Input/output files */
  150. static char current_word[(MAX_LINE+1)];  /* The last word read from fpin */
  151. static int first_diff, save_first_diff;
  152.                                 /* The position of the first letter at which */
  153.                                 /* current_word differs from the previous    */
  154.                                 /* word read                                 */
  155. static NODE PCCRAP *hash_table;
  156. static int first_time = TRUE;
  157. static int this_char = '?', lastch;
  158. static NODE PCCRAP *dawg;
  159.  
  160. static int FILE_ENDED = FALSE;  /* I'm having real problems getting
  161.  merged dawgs to work on the PC; this is yet another filthy hack. Sorry. */
  162.  
  163. static INDEX nwords, nnodes, total_edges;
  164.  
  165. #ifdef SMALL_MEMORY
  166. #define MAX_SUBDAWG 30000 /* Big enough for largest dict,
  167.                              even on small systems */
  168. static NODE PCCRAP *merge;
  169.  
  170. static INDEX dawgsize[256];
  171. static INDEX dawgstart[256];
  172. static INDEX dawgentry[256];
  173.  
  174. static int nextslot;  /* Dawgs are packed in sequentially - not in their
  175.                          'proper' indexed position */
  176. #endif
  177. /*
  178.                 Shorthand macros for array accesses with checking
  179.      If RCHECK isn't defined, these don't contribute any overhead. I suggest
  180.      leaving RCHECK on except for production code.
  181.  */
  182.  
  183. #define EDGE_LIST(idx) \
  184.   edge_list[RANGECHECK(idx, MAX_CHARS)]
  185. #define CURRENT_WORD(idx) \
  186.   current_word[RANGECHECK(idx, MAX_LINE+1)]
  187. #define DAWG(idx) \
  188.   dawg[RANGECHECK(idx, MAX_EDGES)]
  189. #define HASH_TABLE(idx) \
  190.   hash_table[RANGECHECK(idx, HASH_TABLE_SIZE)]
  191.  
  192. /*
  193.                 Forward references
  194.  */
  195.  
  196. #ifdef PROTOTYPES
  197. static INDEX build_node(int depth);
  198. static INDEX add_node(NODE  *edge_list, INDEX nedges);
  199. static void read_next_word(VOID);
  200. static INDEX compute_hashcode(NODE *edge_list, INDEX nedges);
  201. static void report_size(VOID);
  202. #else
  203. static INDEX build_node();
  204. static INDEX add_node();
  205. static void read_next_word();
  206. static INDEX compute_hashcode();
  207. static void report_size();
  208. #endif
  209.  
  210. #ifdef SMALL_MEMORY
  211.  
  212. #ifdef PROTOTYPES
  213. static void merge_dawg (char *filename);
  214. #else
  215. static void merge_dawg ();
  216. #endif
  217.  
  218. #endif
  219.  
  220. /**
  221. *       main
  222. *
  223. *       Program entry point
  224. **/
  225.  
  226. long words; /* dirty communication variable -- the multi-pass stuff
  227.                was hacked in at the last minute. */
  228.  
  229. int
  230. #ifdef PROTOTYPES
  231. main(int argc, char **argv)
  232. #else
  233. main(argc, argv)
  234. int argc;
  235. char **argv;
  236. #endif
  237. {
  238.   INDEX i;
  239.   char fname[128];
  240.  
  241. #ifdef SYS_MAC
  242.   argc = ccommand(&argv);
  243. #endif
  244.  
  245.   if (argc != 3) {
  246.     fprintf(stderr,
  247.       "usage: dawg dictfile.ext dawgfile\n");
  248.     exit(EXIT_ERROR);
  249.   }
  250.  
  251.   /**
  252.   *  Allocate the memory for the dawg
  253.   **/
  254.  
  255.   if ((dawg = MALLOC(MAX_EDGES, sizeof(NODE PCCRAP *))) == NULL) {
  256.     fprintf(stderr, "Can\'t allocate dictionary memory\n");
  257. #ifndef SMALL_MEMORY
  258.     fprintf(stderr, "-- try recompiling with -DSMALL_MEMORY\n");
  259. #endif
  260.     exit(EXIT_ERROR);
  261.   }
  262.   for (i = 0; i < (INDEX)MAX_EDGES; i++) dawg[i] = 0L;
  263.   /**
  264.   *  Allocate the hash table.
  265.   *  Fill it with zeroes later just before use.  Don't trust calloc etc.
  266.   *  - not portable enough.  Anyway, in the multi-pass version we don't
  267.   *  want to continually free/claim...
  268.   **/
  269.  
  270.   if ((hash_table =
  271.       MALLOC((HASH_TABLE_SIZE+1), sizeof(NODE))) == NULL) {
  272.     fprintf(stderr, "Can\'t allocate memory for hash table\n");
  273.     exit(EXIT_ERROR);
  274.   }
  275.   /**
  276.   *  Open the input/output files
  277.   **/
  278.  
  279.   fpin = fopen(argv[1], READ_TEXT);
  280.   if (fpin == NULL) {
  281.     fprintf(stderr, "Can\'t open text file \"%s\"\n", argv[1]);
  282.     /* Could print out error string but it's not portable... */
  283.     exit(EXIT_ERROR);
  284.   }
  285.  
  286.   /**
  287.   *  Read the first word from the dictionary
  288.   **/
  289.  
  290.   first_time = TRUE;
  291.   nwords = 0;
  292.   current_word[0] = 0;
  293.   read_next_word();
  294.   lastch = *current_word;
  295.   /**
  296.   *  Initialise the counters, taking account of the root node (which is
  297.   *  a special case)
  298.   **/
  299.  
  300.   nnodes = 1; total_edges = MAX_CHARS;
  301.  
  302.   /**
  303.   *  Build the dawg and report the outcome
  304.   **/
  305.  
  306.   /* Now, in the dim & distant past, this code supported the concept
  307.      of a restricted character set - ie a..z & A..Z were packed into 6 bits;
  308.      this caused awful problems in the loop below, where we had to try to
  309.      keep the loop-control variable and the character code in synch; nowadays
  310.      chars are 8 bits or else, so I'm starting to tidy up the places
  311.      where these hacks were necessary... */
  312.      
  313. #ifdef SMALL_MEMORY
  314.   for (this_char = 0; this_char < MAX_CHARS; this_char++) {
  315.   if (FILE_ENDED) break; /* Don't waste time in this loop... */
  316. #endif
  317.   /* Explicitly initialise hash table to all zeros */
  318.   {INDEX a; for (a = 0; a <= HASH_TABLE_SIZE; a++) hash_table[a] = 0;}
  319.   words = 0;
  320.   (void) build_node(0);
  321. #ifdef SMALL_MEMORY
  322. #ifdef DEBUG
  323.   fprintf(stderr,
  324.     "Char %d done. %ld Words, %ld Nodes\n", *current_word, words, total_edges);
  325. #endif
  326.   if (total_edges /* words */ == 0) continue;
  327. #endif
  328.  
  329.   /**
  330.   *  Save the dawg to file
  331.   **/
  332. #ifdef SMALL_MEMORY
  333.   sprintf(fname, "%s%c%d", argv[2], EXT_CHAR, lastch);
  334. #else
  335.   sprintf(fname, "%s%cdwg", argv[2], EXT_CHAR);
  336. #endif
  337.   fpout = fopen(fname, WRITE_BIN);
  338.   if (fpout == NULL) {
  339.     fprintf(stderr, "Can\'t open output file \"%s\"\n", fname);
  340.     exit(EXIT_ERROR);
  341.   }
  342. #ifdef DEBUG
  343.   fprintf(stderr, "Writing to %s\n", fname);
  344. #endif
  345.  
  346.   *dawg = total_edges;
  347.   total_edges = sizeof(NODE) * (total_edges + 1); /* Convert to byte count */
  348.  
  349.   {
  350.     long cnt;
  351.     if ((cnt = putwords(dawg, (long)total_edges, fpout)) != total_edges) {
  352.       fprintf(stderr, "%ld bytes written instead of %ld\n.", cnt, total_edges);
  353.       exit(EXIT_ERROR);
  354.     }
  355.   }
  356.   fclose(fpout);
  357.  
  358.   /**
  359.   *  Read the first word from the dictionary
  360.   **/
  361.  
  362.   first_diff = save_first_diff;
  363.   first_time = FALSE;
  364.   nwords = 0;
  365.   /**
  366.   *  Initialise the counters, taking account of the root node (which is
  367.   *  a special case)
  368.   **/
  369.  
  370.   nnodes = 1; total_edges = MAX_CHARS;
  371.  
  372.   lastch = *current_word;
  373.   /**
  374.   *  Build the dawg and report the outcome
  375.   **/
  376.  
  377. #ifdef SMALL_MEMORY
  378.   }
  379. #endif
  380.   fclose(fpin);
  381.   fprintf(stderr, "Dawg generated\n");
  382. #ifdef SMALL_MEMORY
  383.   merge_dawg(argv[2]);
  384. #endif
  385.   exit(EXIT_OK);
  386. }
  387.  
  388. /**
  389. *       BUILD_NODE
  390. *
  391. *       Recursively build the next node and all its sub-nodes
  392. **/
  393.  
  394. static INDEX
  395. #ifdef PROTOTYPES
  396. build_node(int depth)
  397. #else
  398. build_node(depth)
  399. int depth;
  400. #endif
  401. {
  402.   INDEX nedges = 0;
  403.   INDEX i;
  404.   NODE *edge_list;
  405.  
  406.   edge_list = NULL;
  407.   if (CURRENT_WORD(depth) == 0) {
  408.     /**
  409.     *  End of word reached. If the next word isn't a continuation of the
  410.     *  current one, then we've reached the bottom of the recursion tree.
  411.     **/
  412.  
  413.     read_next_word();
  414.     if (first_diff < depth) return(0);
  415.   }
  416.  
  417.   edge_list = (NODE *)malloc(MAX_CHARS*sizeof(NODE));
  418.                      /* Note this is a 'near' array */
  419.   if (edge_list == NULL) {
  420.     fprintf(stderr, "Stack full (depth %d)\n", depth);
  421.     exit(EXIT_ERROR);
  422.   }
  423.   for (i = 0; i < MAX_CHARS; i++) EDGE_LIST(i) = 0L;
  424.  
  425.   /**
  426.   *  Loop through all the sub-nodes until a word is read which can't
  427.   *  be reached via this node
  428.   **/
  429.  
  430.   do
  431.     {
  432.     /* Construct the edge. Letter.... */
  433.     EDGE_LIST(nedges) = (NODE) (((NODE)CURRENT_WORD(depth)))
  434.                         << (NODE)V_LETTER;
  435.     /* ....end-of-word flag.... */
  436.     if (CURRENT_WORD(depth+1L) == 0) EDGE_LIST(nedges) |= M_END_OF_WORD;
  437.     /* ....and node pointer. */
  438.     EDGE_LIST(nedges) |= build_node(depth+1); nedges++;
  439.                                                    /* (don't ++ in a macro) */
  440.     } while (first_diff == depth);
  441.  
  442.   if (first_diff > depth) {
  443.     fprintf(stderr, "Internal error -- first_diff = %d, depth = %d\n",
  444.       first_diff, depth);
  445.     exit(EXIT_ERROR);
  446.   }
  447.  
  448.   EDGE_LIST(nedges-1) |= M_END_OF_NODE;
  449.                                   /* Flag the last edge in the node */
  450.  
  451.   /**
  452.   *  Add the node to the dawg
  453.   **/
  454.  
  455.   if (depth) {
  456.     NODE result = add_node(edge_list, nedges);
  457.     free(edge_list);
  458.     return(result);
  459.   }
  460.  
  461.   /**
  462.   *  depth is zero, so the root node (as a special case) goes at the start
  463.   **/
  464.  
  465.   edge_list[MAX_CHARS-1] |= M_END_OF_NODE;      /* For backward searches */
  466.   for (i = 0; i < MAX_CHARS; i++)
  467.     {
  468.     dawg[i+1] = edge_list[i];
  469.     }
  470.   free(edge_list);
  471.   return(0);
  472. }
  473.  
  474. /**
  475. *       ADD_NODE
  476. *
  477. *       Add a node to the dawg if it isn't already there. A hash table is
  478. *       used to speed up the search for an identical node.
  479. **/
  480.  
  481. static INDEX
  482. #ifdef PROTOTYPES
  483. add_node(NODE *edge_list, INDEX nedges)
  484. #else
  485. add_node(edge_list, nedges)
  486. NODE *edge_list;
  487. INDEX nedges;
  488. #endif
  489. {
  490.   NODE hash_entry;
  491.   INDEX inc;
  492.   INDEX a, first_a;
  493.   INDEX i;
  494.  
  495.   /**
  496.   *  Look for an identical node. A quadratic probing algorithm is used
  497.   *  to traverse the hash table.
  498.   **/
  499.  
  500.   first_a = compute_hashcode(edge_list, nedges);
  501.   first_a = ABS(first_a) MOD HASH_TABLE_SIZE;
  502.   a = first_a;
  503.   inc = 9;
  504.  
  505.   for (;;)
  506.     {
  507.     hash_entry = HASH_TABLE(a) & M_NODE_POINTER;
  508.  
  509.     if (hash_entry == 0) break;   /* Node not found, so add it to the dawg */
  510.  
  511.     for (i = 0; i < nedges; i++)
  512.       if (DAWG((hash_entry+i) MOD HASH_TABLE_SIZE) != EDGE_LIST(i)) break;
  513.  
  514. /* On the 1.6M dictionary, this gave a rangecheck with < 0. Now fixed
  515.    I think - it was a problem with MOD giving unexpected results. */
  516.  
  517.       if (i == nedges) {
  518.         return(hash_entry);        /* Node found */
  519.       }
  520.       /**
  521.       *  Node not found here. Look in the next spot
  522.       **/
  523.  
  524.       a += inc;
  525.       inc += 8;
  526.       if (a >= HASH_TABLE_SIZE) a -= HASH_TABLE_SIZE;
  527.       if (inc >= HASH_TABLE_SIZE) inc -= HASH_TABLE_SIZE;
  528.       if (a == first_a) {
  529.         fprintf(stderr, "Hash table full\n");
  530.         exit(EXIT_ERROR);
  531.       }
  532.     }
  533.  
  534.   /**
  535.   *  Add the node to the dawg
  536.   **/
  537.  
  538.   if (total_edges + nedges >= MAX_EDGES) {
  539.     fprintf(stderr,
  540.       "Error -- dictionary full - total edges = %ld\n", total_edges);
  541.     exit(EXIT_ERROR);
  542.   }
  543.  
  544.   HASH_TABLE(a) |= total_edges + 1;
  545.   nnodes++;
  546.   for (i = 0; i < nedges; i++) {
  547.     DAWG((total_edges + 1 + i) MOD HASH_TABLE_SIZE) = EDGE_LIST(i);
  548.   }
  549.   total_edges += nedges;
  550.   return(total_edges - nedges + 1);
  551. }
  552.  
  553. /**
  554. *       READ_NEXT_WORD
  555. *
  556. *       Read the next word from the input file, setting first_diff accordingly
  557. **/
  558.  
  559. static void
  560. #ifdef PROTOTYPES
  561. read_next_word(VOID)
  562. #else
  563. read_next_word()
  564. #endif
  565. {
  566.   /* This stuff imposes the limitation of not allowing '\0' in a word;
  567.      not yet a problem but the dawg structure itself could probably cope
  568.      if the feature were wanted. (Maybe with a little teweaking)       */
  569.   char linebuff[(MAX_LINE+1)];
  570.   int length;
  571.   for (;;)
  572.     {
  573.     int next = 0, c;
  574.     for (;;) {
  575.       c = fgetc(fpin);
  576.       if (FILE_ENDED || c == EOF || ferror(fpin) || feof(fpin)) {
  577.         /* for some reason, we always get a blank line at the end of files */
  578.         current_word[0] = 0;
  579.         first_diff = -1;
  580.         linebuff[next] = '\0';
  581.         FILE_ENDED = TRUE;
  582.         return;
  583.       }
  584.       c &= 255;
  585.       if (next == 0 && c == '\n') continue; /* skip blank lines... */
  586.       linebuff[next++] = c;
  587.       if (c == '\n') break;
  588.     }
  589.     linebuff[next] = '\0';
  590.  
  591.     words++;
  592.  
  593.     length = strlen(linebuff);
  594.  
  595.     if (linebuff[length-1] == '\n') linebuff[length-1] = '\0';
  596.     if (linebuff[length] == '\n') linebuff[length] = '\0';
  597.  
  598.     if (length < 2 || length > MAX_LINE-1)
  599.       {
  600.       fprintf(stderr, "\n%s - invalid length\n", linebuff);
  601.       continue;    /* Previously exit()ed, but now ignore so that
  602.                       test sites without my pddict can use /usr/dict/words */
  603.       }
  604.     break;
  605.     }
  606.   for (length = 0; current_word[length] == linebuff[length]; length++) {
  607.     /* Get common part of string to check order */
  608.   }
  609.   if (current_word[length] > linebuff[length]) {
  610.     fprintf(stderr, "Error -- %s (word out of sequence)\n", linebuff);
  611.     exit(EXIT_ERROR);
  612.   }
  613.   first_diff = length;
  614.  
  615.   nwords++;
  616.   strcpy(current_word, linebuff);
  617.  
  618.   if ((nwords > 1) && (!(nwords & 0x3FF))) report_size();
  619. #ifdef SMALL_MEMORY
  620.   if (current_word[0] != lastch) {
  621.     save_first_diff = first_diff;
  622.     first_diff = -1;
  623.     report_size();
  624.   }
  625. #else
  626.   this_char = current_word[0]; /* for diagnostics... */
  627. #endif
  628. }
  629. /**
  630. *       COMPUTE_HASHCODE
  631. *
  632. *       Compute the hash code for a node
  633. **/
  634.  
  635. static INDEX
  636. #ifdef PROTOTYPES
  637. compute_hashcode(NODE *edge_list, INDEX nedges)
  638. #else
  639. compute_hashcode(edge_list, nedges)
  640. NODE *edge_list;
  641. INDEX nedges;
  642. #endif
  643. {
  644.   INDEX i;
  645.   INDEX res = 0L;
  646.  
  647.   for (i = 0; i < nedges; i++)
  648.     res = ((res << 1) | (res >> 31)) EOR EDGE_LIST(i);
  649.   return(res);
  650. }
  651.  
  652. /**
  653. *       REPORT_SIZE
  654. *
  655. *       Report the current size etc
  656. **/
  657.  
  658. static void
  659. #ifdef PROTOTYPES
  660. report_size(VOID)
  661. #else
  662. report_size()
  663. #endif
  664. {
  665.  
  666.   if (first_time)
  667.     {
  668.     fprintf(stderr, "      Words    Nodes    Edges    Bytes    BPW\n");
  669.     fprintf(stderr, "      -----    -----    -----    -----    ---\n");
  670.     first_time = FALSE;
  671.     }
  672.   if (*current_word) fprintf(stderr, "%c:", *current_word);
  673.   else fprintf(stderr, "Total:");
  674.   
  675.   /* THE FOLLOWING IS RATHER GRATUITOUS USE OF FLOATING POINT - REMOVE
  676.      IT AND REPLACE WITH INTEGER ARITHMETIC * 100 */
  677.  
  678.   /* (hey - I already did this in the copy I sent to Richard; so how
  679.       come its missing? Oh no, not again: I've got out of synch and
  680.       used an old copy, haven't I? :-(   ) */ 
  681.  
  682.   fprintf(stderr, "  %7ld  %7ld  %7ld  %7ld  %5.2f\n",
  683.     nwords, nnodes, total_edges, sizeof(NODE PCCRAP *)*(total_edges+1),
  684.       (float)(sizeof(NODE PCCRAP *)*(total_edges+1))/(float)nwords);
  685. }
  686.  
  687. #ifdef SMALL_MEMORY
  688. static void
  689. #ifdef PROTOTYPES
  690. merge_dawg (char *filename)
  691. #else
  692. merge_dawg (filename)
  693. char *filename;
  694. #endif
  695. {
  696.   FILE *fp, *outfile;
  697.   NODE data, edge;
  698.   INDEX nedges, nextfree, i, dentry;
  699.   INDEX count, lastnode;
  700.   int dictch, padding;
  701.   char fname[128];
  702.  
  703.   nedges = (INDEX)MAX_SUBDAWG;
  704.   if ((merge = MALLOC((SIZE_T)nedges, sizeof(INDEX))) == 0) {
  705.      fprintf(stderr, "Memory allocation error -- %ld wanted\n",
  706.        nedges*sizeof(INDEX));
  707.      exit(EXIT_ERROR);
  708.   }
  709.  
  710.   nextfree = MAX_CHARS; /* 0 is special, 1..26 are root nodes for a..z */
  711.   nextslot = 0;
  712.   for (dictch = 0; dictch < MAX_CHARS; dictch++) {
  713.     /***
  714.     *   Open the file and find out the size of the dawg
  715.     ***/
  716.     sprintf(fname, "%s%c%d", filename, EXT_CHAR, dictch);
  717.     if ((fp = fopen(fname, READ_BIN)) == NULL) {
  718.       continue;
  719.     }
  720.     nedges = getword(fp);
  721.     dawgstart[nextslot] = nextfree;
  722.     dawgsize[nextslot] = nedges-MAX_CHARS;
  723.  
  724.     /* the first entry is (erroneously) the pointer to the chunk */
  725.     dentry = getword(fp);
  726.     dawgentry[nextslot] = dentry - MAX_CHARS + nextfree;
  727.  
  728.     nextfree += nedges - MAX_CHARS;
  729.     nextslot++;
  730.  
  731.     fclose(fp);
  732.   }
  733.  
  734. /* Now output total edges, and starts[a..z] */
  735. /* Then set nextfree to start of each block  */
  736.   sprintf(fname, "%s%cdwg", filename, EXT_CHAR);
  737.   outfile = fopen(fname, WRITE_BIN);
  738.   if (outfile == NULL) {
  739.     fprintf(stderr, "Cannot open output dawg file %s\n", fname);
  740.     exit(EXIT_ERROR);
  741.   }
  742.   putword(nextfree, outfile);
  743.   nextfree = 1; nextslot = 0; padding = 0;
  744.   lastnode = MAX_CHARS-1;
  745.   for (;;) {
  746.     if (dawgentry[lastnode] != 0) break; /* Leave with 'lastnode' set */
  747.     lastnode -= 1;
  748.   }
  749.   for (dictch = 0; dictch < MAX_CHARS; dictch++) {
  750.     NODE edge = dawgentry[nextslot];
  751.     if (edge == 0) {
  752.       padding++;
  753.       continue;
  754.     }
  755.     if (dictch == lastnode) {
  756.       edge |= M_END_OF_NODE;
  757.     } else {
  758.       edge &= (NOT M_END_OF_NODE);
  759.     }
  760.     putword(edge, outfile);
  761.     nextfree++; nextslot++;
  762.   }
  763.   nextfree += padding;
  764.   while (padding > 0) {
  765.     putword(0L, outfile); padding -= 1;
  766.   }
  767.   /* nextslot = 0; ???? This one not used? */
  768.   for (dictch = 0; dictch < MAX_CHARS; dictch++) {
  769.     sprintf(fname, "%s%c%d", filename, EXT_CHAR, dictch);
  770.     if ((fp = fopen(fname, READ_BIN)) == NULL) {
  771.       continue;
  772.     }
  773.  
  774.     nedges = getword(fp);
  775.  
  776.     for (i = 0; i < MAX_CHARS; i++) {
  777.       (void) getword(fp);
  778.       /* Skip root pointers */
  779.     }
  780.  
  781.     nedges -= MAX_CHARS;
  782.     count = getwords(&merge[1], (long)(nedges*sizeof(NODE)), fp);
  783.     if (count != nedges*sizeof(NODE)) {
  784.       fprintf(stderr, "Dictionary read error - %ld wanted - %ld got\n",
  785.         nedges*sizeof(NODE), count);
  786.       exit(EXIT_ERROR);
  787.     }
  788.     fclose(fp);
  789.  
  790.     DELETE(fname);    /* On floppy systems, we can almost get away with
  791.                          little more space than the final files would take! */
  792.  
  793.     /* relocate all nodes */
  794.     for (i = 1; i <= nedges; i++) {
  795.       data = merge[i];
  796.       edge = data & M_NODE_POINTER;
  797.       if (edge > MAX_CHARS) {
  798.         data &= (NOT M_NODE_POINTER);
  799.         data |= edge - MAX_CHARS - 1 + nextfree;
  800.         merge[i] = data;
  801.       }
  802.       putword(merge[i], outfile);
  803.     }
  804.     nextfree += nedges;
  805.     /*  nextslot++;   this one not used??? */
  806.   }
  807.   fclose(outfile);
  808.   FREE(merge);
  809. }
  810. #endif
  811. SHAR_EOF
  812. cat - << \SHAR_EOF > dwgcheck.c
  813. /*
  814.  
  815.     File:          dwgcheck.c
  816.     Author:        Graham Toal
  817.     Purpose:       check correct spelling using dict.dwg
  818.     Creation date: 22/06/90
  819.     Lastedit:      23/06/90 01:10:12
  820.  
  821.     Description:
  822.  
  823.        This can be expanded to be like the unix 'spell' command.
  824.     This demo file simply checks words passed on the command line.
  825.     note how it remembers words so that the second time it sees
  826.     them, it will call them correct.  This is how you should
  827.     implement the 'ignore' feature of an interactive checker.
  828.  
  829.     This code uses the dawg data structure, which I recommend
  830.     you stick with; however for *extremely* fast checking in
  831.     special circumstances you can use the 'pack' versions of
  832.     check() et al.
  833.  
  834. */
  835.  
  836.  
  837. /* Manadatory header files */
  838. #include <stdio.h>
  839. #include "dawg.h"
  840. #include "grope.h"
  841.  
  842. /*#define RCHECK*/     /* Enable for internal range checks... */
  843.  
  844. #include "utils.c"
  845.  
  846. /* Headers here as needed on per-program basis */
  847. #include <ctype.h>  /* eg, for isalpha() */
  848.  
  849. /* Spelling library utilities */
  850. #include "init.c"      /* Loading dicts */
  851. #include "dyntrie.c"   /* Creating dicts at run-time */
  852. #include "print.c"     /* Printing dicts */
  853. #include "check.c"     /* Checking words */
  854. #include "locate.c"    /* Finding words by their stems */
  855.  
  856. #include "soundex.c"   /* Soundex algorithm for word-likeness comparison */
  857. #include "similcmp.c"  /* Closeness-metric for correction */
  858. #include "correct.c"   /* Hack code to attempt error correction (uses above) */
  859.  
  860. /* Let's be friendly to these guys... */
  861. #ifdef SYS_MAC
  862. /* To compile with THINK C 4.0, place all the relevant .h and .c
  863.    files in a folder.  Then create a project which contains this main.c
  864.    and the libraries unix and ANSI.
  865. */
  866. #include <unix.h>
  867. #include <stdlib.h>
  868. #include <console.h>
  869. #endif
  870.  
  871. /* Your own header files go here, for instance:
  872.                #include "readword.h"
  873.  */
  874.  
  875.  
  876.  
  877. int
  878. #ifdef PROTOTYPES
  879. main(int argc, char **argv)
  880. #else
  881. main(argc, argv)
  882. int argc;
  883. char **argv;
  884. #endif
  885. {
  886. NODE PCCRAP *dawg;      /* precompiled dictionary (dict.dwg) */
  887. INDEX edges;            /* size of above */
  888.  
  889. NODE PCCRAP *userdict;  /* run-time dictionary, added to dynamically */
  890.  
  891. char *word;
  892. int each;
  893.  
  894. #ifdef SYS_MAC
  895.   argc = ccommand(&argv);  /* Mac users have my sympathy */
  896. #endif
  897.  
  898.   /* Your program goes here... */
  899.   if (argc == 1) {
  900.     fprintf(stderr, "usage: %s possibly mispeled wurdz\n", argv[0]);
  901.     exit(EXIT_ERROR);
  902.   }
  903.   if (!dawg_init("", &dawg, &edges)) exit(EXIT_ERROR);
  904.  
  905.   if (!trie_new(&userdict)) exit(EXIT_ERROR);
  906.  
  907.   for (each = 1; each < argc; each++) {
  908.     word = argv[each];
  909.     fprintf(stderr, "* %s:\n", word);
  910.     if (dawg_check(dawg, word) || dawg_check(userdict, word)) {
  911.       fprintf(stderr, "Correct\n");
  912.     } else {
  913.       fprintf(stderr, "Wrong\n");
  914.       (void)trie_add(&userdict, word);
  915.     }
  916.     if (each+1 != argc) fprintf(stderr, "\n");
  917.   }
  918.  
  919.   exit(EXIT_OK);
  920. }
  921. SHAR_EOF
  922. cat - << \SHAR_EOF > pack.c
  923. /* The line below is to protect against Bitnet mailer damage */
  924. #define MOD %
  925.              /* This should be a Percent (for C Modulus) */ 
  926.  
  927. /* Blech. This file is a mess. Make it the first rewrite... */
  928. #include "copyr.h"
  929. /*****************************************************************************/
  930. /*                                                                           */
  931. /*      FILE : PACK.C                                                        */
  932. /*                                                                           */
  933. /*      Re-pack a dawg/trie data structure using Franklin Liang's            */
  934. /*      algorithm for sparse matrix storage.  Final structure allows         */
  935. /*      direct indexing into trie nodes, so is exceedingly fast at checking. */
  936. /*      Unfortunately the trade off is that any algorithms which walk        */
  937. /*      the data structure and generate words will take much longer          */
  938. /*                                                                           */
  939. /*              PACK <dawg file (inc .ext)> <pack file (inc .ext)>           */
  940. /*                                                                           */
  941. /*****************************************************************************/
  942.  
  943. /* Pending:
  944.  
  945.    see what closest gap between dawgptr + freenode is, and see whether we
  946.    can save space by overlapping input & output arrays with a window between
  947.    them.  Should get almost 50% of memory back.  Also, because of hacking
  948.    around a bug some time back, I'm using an extra array (new_loc) for
  949.    relocation of pointers, when in fact I could (and have in the past)
  950.    managed to relocate them in situ with not much extra overhead.
  951.       As I said, it needs a rewrite...
  952.  
  953.  */
  954.  
  955. /* Note: I tried one implementation of this which used bitsets to test
  956.    whether two nodes were compatible.  In fact, it wasn't sufficiently
  957.    faster to justify the extra space it used for the arrays of flags.
  958.    Now I check for compatibility on the fly with lots of comparisons.
  959.    I do however have a seperate byte array to flag whether a trie
  960.    is based at any address.  There's probably a way of removing this.
  961. */
  962.  
  963. #include "grope.h"
  964. #ifndef grope_h
  965. /* If you don't have grope.h, create an empty one.
  966.    These will do for a basic system: */
  967. #undef KNOWS_VOID
  968. #undef STDLIBS
  969. #undef PROTOTYPES
  970. #define SYS_ANY 1
  971. #define COMPILER_ANY 1
  972. #define SMALL_MEMORY 1 /*  To be defined if you have to generate
  973.                            the data structure in bits. This will
  974.                            certainly be true for any non-trivial
  975.                            dictionary on MSDOS, or most home
  976.                            micros with 1Mb Ram or under. */
  977. #endif
  978.  
  979. #include <stdio.h>
  980.  
  981. /*#define RCHECK*/  /* Turn this back on if you have any problems. */
  982.  
  983. #include "dawg.h"
  984. #include "utils.c"
  985. #include "init.c"
  986. #include "print.c"
  987.  
  988. #ifdef SYS_MAC
  989. /* To compile with THINK C 4.0, place the files dawg.h grope.h,
  990.    pack.c and utils.c in a folder.  Create a project that contains
  991.    pack.c and the libraries unix and ANSI.
  992. */
  993. #include <unix.h>
  994. #include <stdlib.h>
  995. #include <console.h>
  996. /* Assume a 1Mb mac for the moment. Someday I'll add dynamic RAM sizing */
  997. #define SMALL_MEMORY
  998. #endif
  999.  
  1000. #define TRUE (0==0)
  1001. #define FALSE (0!=0)
  1002. #define MAX_WORD_LENGTH 32
  1003.  
  1004. /* These two magic numbers alter a very hacky heuristic employed in
  1005.    the packing algorithm.  Tweaking them judiciously ought to speed
  1006.    it up significantly (at the expense of a slightly sparser packing */
  1007. #define DENSE_LOWER 100
  1008. #define DENSE_UPPER 200
  1009.  
  1010. /*###########################################################################*/
  1011. INDEX ptrie_size = 0;
  1012. static NODE PCCRAP *ptrie;
  1013. #ifdef RCHECK
  1014. /* can't use the standard range_check macro because these are slightly
  1015.    non-standard. */
  1016. #define PTRIE(x) ptrie[RANGECHECK((x), ptrie_size)]
  1017. #define DATA(x) (((x) >> 12) == 0xf2f1 ? toosmall((x), 0, __LINE__) : (x))
  1018. #else
  1019. /* so supply an explicit base case */
  1020. #define PTRIE(x) ptrie[x]
  1021. #define DATA(x) (x)
  1022. #endif
  1023. static char PCCRAP *trie_at;  /* save some time by caching this info --
  1024.                           previously it was a function called on each test */
  1025. static INDEX freenode, lowest_base = 1, highest_base = -1;
  1026. static int debug = FALSE;
  1027.  
  1028. int
  1029. #ifdef PROTOTYPES
  1030. compatible(NODE *node, INDEX i) /* Can a node be overlaid here? */
  1031. #else
  1032. compatible(node, i)
  1033. NODE *node;
  1034. INDEX i;
  1035. /* Can a node be overlaid here? */
  1036. #endif
  1037. {
  1038. int c;
  1039.  for (c = 0; c < MAX_CHARS; c++) {
  1040.    if ((node[c]&M_FREE) == 0) { /* Something to slot in... */
  1041.     if ((PTRIE(i+c) & M_FREE) == 0) return(FALSE); /* but no slot for it */
  1042.    }
  1043.  }
  1044.  return(TRUE);
  1045. }
  1046.  
  1047. INDEX
  1048. #ifdef PROTOTYPES
  1049. find_slot(NODE *node)
  1050. #else
  1051. find_slot(node)
  1052. NODE *node;
  1053. #endif
  1054. {               /* Try each position until we can overlay this node */
  1055. INDEX i;
  1056.   for (i = lowest_base; i < freenode; i++) {
  1057.     if ((!trie_at[i]) && (compatible(node, i))) {
  1058.        /* nothing here already */
  1059.                          /* and this one will fit */
  1060.       return(i);
  1061.     }
  1062.   }
  1063.   fprintf(stderr, "Should never fail to find a slot!\n");
  1064.                      /* because the output array is larger than the input... */
  1065.   exit(5);
  1066.   /* NOT REACHED */
  1067.   return(0);
  1068. }
  1069.  
  1070. static int changes;
  1071.  
  1072. INDEX
  1073. #ifdef PROTOTYPES
  1074. pack(NODE *node)
  1075. #else
  1076. pack(node)
  1077. NODE *node;
  1078. #endif
  1079. {
  1080. int c;
  1081. INDEX slot;
  1082. NODE value;
  1083.  
  1084.   slot = find_slot(node);  /* slot is also returned as the result,
  1085.                               to be used in relocation */
  1086.   /* Place node at slot */
  1087.   changes = 0;
  1088.   for (c = 0; c < MAX_CHARS; c++) {
  1089.     value = node[c];
  1090.     if ((value&M_FREE) == 0) { /* Something to fit? */
  1091.       if (((value>>V_LETTER)&M_LETTER) == (INDEX)c+BASE_CHAR) {
  1092.                   /* Just a consistency check - could safely be removed */
  1093.         PTRIE(slot+c) = DATA(value);
  1094.         changes++;
  1095.       }
  1096.     }
  1097.   }
  1098.   /* The hack heuristics below keep a N^2 operation down to linear time! */
  1099.   if ((slot == lowest_base) || (slot >= lowest_base+DENSE_LOWER)) {
  1100.     /* Heuristic is: we increase the initial search position if the
  1101.        array is packed solid up to this point or we're finding it *very*
  1102.        hard to find suitable slots */
  1103.     int found = FALSE;
  1104.     for (;;) {
  1105.       INDEX c;
  1106.       while (trie_at[lowest_base]) lowest_base++;
  1107.       for (c = lowest_base; c < lowest_base+MAX_CHARS; c++) {
  1108.         if ((PTRIE(c)&M_FREE) != 0) {found = TRUE; break;}
  1109.       }
  1110.       if (found && (slot < lowest_base+DENSE_UPPER)) break;
  1111.                   /* ^ Skip hard slots to fill */
  1112.       lowest_base++; /* although nothing is based here, the next N slots
  1113.                       are filled with data from the last N tries. */
  1114.  
  1115.       /* Actually I'm not sure if 256 sequential trees each with the
  1116.          same element used would actually block the next 256 slots
  1117.          without a trie_at[] flag being set for them.  However it
  1118.          does no harm to believe this... I must formally check this
  1119.          someday once all the other stuff is in order. */
  1120.     }
  1121.   }
  1122.  
  1123.   if (slot > highest_base) highest_base = slot;
  1124.      /* This is info for when we try to overlap input & output
  1125.         arrays, -- with the output sitting some large number of
  1126.         bytes lower down than the input. */
  1127.   trie_at[slot] = TRUE;
  1128.   return(slot);
  1129. }
  1130. /*###########################################################################*/
  1131.  
  1132. static NODE PCCRAP *dawg;
  1133. static INDEX PCCRAP *new_loc;
  1134. static INDEX nedges;
  1135.  
  1136. NODE this_node[MAX_CHARS];
  1137.  
  1138. INDEX
  1139. #ifdef PROTOTYPES
  1140. take_node(INDEX ptr)
  1141. #else
  1142. take_node(ptr)
  1143. INDEX ptr;
  1144. #endif
  1145. {
  1146. NODE data;
  1147. INDEX edge;
  1148. int let;
  1149. int endsword;
  1150. int endsnode;
  1151. char ch;
  1152. int changes = 0;
  1153.   for (let = 0; let < MAX_CHARS; let++) this_node[let] = M_FREE;
  1154.   for (;;) {
  1155.     data = dawg[ptr++];
  1156.     if (data == 0) {
  1157.       return(-1);
  1158.     } else {
  1159.       endsword = ((data & M_END_OF_WORD) != 0);
  1160.       endsnode = ((data & M_END_OF_NODE) != 0);
  1161.       edge = data & M_NODE_POINTER;
  1162.       let = (int) ((data >> V_LETTER) & M_LETTER);
  1163.       ch = let + BASE_CHAR;
  1164.   
  1165.       this_node[let] = edge & M_NODE_POINTER;
  1166.       if (endsword) this_node[let] |= M_END_OF_WORD;
  1167.       this_node[let] |= (NODE)ch<<V_LETTER;
  1168.   
  1169.       changes++;
  1170.       if (endsnode) break;
  1171.     }
  1172.   }
  1173.   if (changes != 0) {
  1174.     return(ptr);
  1175.   } else {
  1176.     fprintf(stderr, "Fatal error\n");
  1177.     return(0);
  1178.   }
  1179. }
  1180.  
  1181. NODE
  1182. #ifdef PROTOTYPES
  1183. redirect_node(NODE ptr)
  1184. #else
  1185. redirect_node(ptr)
  1186. NODE ptr;
  1187. #endif
  1188. {
  1189. NODE data;
  1190. INDEX edge;
  1191. int endsword;
  1192. char ch;
  1193.   data = DATA(PTRIE(ptr));
  1194.  
  1195.   endsword = ((data & M_END_OF_WORD) != 0);
  1196.   edge = data & M_NODE_POINTER;
  1197.   ch = (int) ((data >> V_LETTER) & M_LETTER);
  1198.  
  1199.   /*edge = dawg[edge] & M_NODE_POINTER;*/
  1200.   edge = new_loc[edge];
  1201.  
  1202.   ptr = edge;
  1203.   ptr |= (NODE)ch<<V_LETTER;
  1204.   if (endsword) ptr |= M_END_OF_WORD;
  1205.  
  1206.   return(ptr);
  1207. }
  1208.  
  1209. int
  1210. #ifdef PROTOTYPES
  1211. main(int argc, char **argv)
  1212. #else
  1213. main(argc, argv)
  1214. int argc;
  1215. char **argv;
  1216. #endif
  1217. {
  1218. INDEX dawgptr = 1, trieptr, newdawgptr, i, nodes = 0;
  1219. FILE *triefile;
  1220.  
  1221. #ifdef SYS_MAC
  1222.   argc = ccommand(&argv);
  1223. #endif
  1224.  
  1225.   if (argc != 3) {
  1226.     fprintf(stderr, "pack: wrong parameters - should be infile outfile\n");
  1227.     exit(EXIT_ERROR);
  1228.   }
  1229.  
  1230.   if (!dawg_init((argc >= 2 ? argv[1]: ""), &dawg, &nedges)) exit(EXIT_ERROR);
  1231.   if (debug) dawg_print(dawg, (INDEX)ROOT_NODE); /* assume small test file! */
  1232.  
  1233.   freenode = ((nedges*16)/15)+(4*MAX_CHARS);
  1234.                                /* Minimal slop for pathological packing? */
  1235.   ptrie_size = freenode;
  1236.   ptrie = MALLOC((SIZE_T)freenode, sizeof(NODE));
  1237.   if (ptrie == NULL) {
  1238.     fprintf(stderr, "Cannot claim %ld bytes for ptrie[]\n",
  1239.             sizeof(NODE)*freenode);
  1240.     exit(EXIT_ERROR);
  1241.   }
  1242.   new_loc = MALLOC((SIZE_T)freenode, sizeof(NODE));
  1243.   if (new_loc == NULL) {
  1244.     fprintf(stderr, "Cannot claim %ld bytes for new_loc[]\n",
  1245.             sizeof(NODE)*freenode);
  1246.     exit(EXIT_ERROR);
  1247.   }
  1248.   trie_at = (char PCCRAP *)MALLOC((SIZE_T)freenode, sizeof(char));
  1249.   if (trie_at == NULL) {
  1250.     fprintf(stderr, "Cannot claim %ld bytes for trie_at[]\n", freenode);
  1251.     exit(EXIT_ERROR);
  1252.   }
  1253.   for (i = 0; i < freenode; i++) {
  1254.     ptrie[i] = M_FREE; new_loc[i] = 0; trie_at[i] = FALSE;
  1255.   }
  1256.  
  1257.   dawg[0] = 0; /* 1st entry is never looked at, and maps to itself */
  1258.  
  1259.   dawgptr = 1;
  1260.  
  1261. /* Relocate initial node at 1 seperately */
  1262.  
  1263.     newdawgptr = take_node(dawgptr /* 1 */);
  1264.     trieptr = pack(this_node);
  1265.     /*dawg[dawgptr] = trieptr;*/
  1266.       /* What the hell does this do??? I've forgotten!!! - oh yes, this
  1267.          was relocating in situ, without new_loc... */
  1268.     new_loc[dawgptr] = trieptr;
  1269.     dawgptr = MAX_CHARS+1;
  1270.  
  1271. {INDEX maxdiff = 0, diff;
  1272.   for (;;) {
  1273.     if (highest_base > dawgptr) {
  1274.       diff = highest_base - dawgptr;
  1275.       if (diff > maxdiff) maxdiff = diff;
  1276.     }
  1277.     newdawgptr = take_node(dawgptr);
  1278.     if (newdawgptr == -1) {
  1279.       dawgptr++;
  1280.       continue;
  1281.     }
  1282.     trieptr = pack(this_node);
  1283.     /*dawg[dawgptr] = trieptr;*/
  1284.     new_loc[dawgptr] = trieptr;
  1285.     dawgptr = newdawgptr;
  1286.     if (dawgptr > nedges) {
  1287.       break;  /* AHA!!! I was doing this in the
  1288.                  wrong order & lost last entry! *AND* had '>=' for '>' */
  1289.     }
  1290.     nodes++;
  1291.     if ((nodes MOD 1000) == 0) fprintf(stderr, "%ld nodes\n", nodes);
  1292.   }
  1293.   if (debug) fprintf(stderr, "wavefront gets up to %ld\n", maxdiff);
  1294. }
  1295.   if (debug) fprintf(stderr, "All packed - used %ld nodes\n", highest_base);
  1296.   for (trieptr = 1; trieptr < freenode; trieptr++) {
  1297.     /*
  1298.       extract edge from ptrie[trieptr],
  1299.       look it up via dawg[edge], slot it back in
  1300.       (while preserving other bits)
  1301.      */
  1302.     PTRIE(trieptr) = redirect_node(trieptr);
  1303.   }
  1304.   /* Finally, remember to bump up highest_base in case last node is only
  1305.      one edge and 25 others are missing! */
  1306.   if (debug) fprintf(stderr, "Redirected...\n");
  1307.  
  1308.   triefile = fopen((argc >= 3 ? argv[2] : DEFAULT_PACK), WRITE_BIN);
  1309.   if (triefile == NULL) {
  1310.     fprintf(stderr, "Cannot write to packed trie file\n");
  1311.     exit(1);
  1312.   }
  1313.   if (debug) fprintf(stderr, "File opened...\n");
  1314.  
  1315.   ptrie[0] = highest_base+MAX_CHARS-1;/* File size in words
  1316.                                      (-1 because doesn't include itself)  */
  1317.   if (debug) fprintf(stderr, "Dumping... (0..%ld)\n", highest_base+MAX_CHARS-1);
  1318.   for (i = 0; i < highest_base+MAX_CHARS; i++) {/* dump packed DAG */
  1319.   NODE n;
  1320.     n = DATA(PTRIE(i));
  1321.     putword(n, triefile);
  1322.     if (ferror(triefile)) {
  1323.       fprintf(stderr, "*** TROUBLE: Writing DAG -- disk full?\n");
  1324.       fclose(triefile);
  1325.       exit(1);
  1326.     }
  1327.   }
  1328.   if (debug) fprintf(stderr, "Dumped...\n");
  1329.   fclose(triefile);
  1330.   if (debug) fprintf(stderr, "Done.\n");
  1331. }
  1332. SHAR_EOF
  1333. cat - << \SHAR_EOF > pckcheck.c
  1334. /*
  1335.  
  1336.     File:          pckcheck.c
  1337.     Author:        Graham Toal
  1338.     Purpose:       check correct spelling using dict.pck
  1339.     Creation date: 22/06/90
  1340.     Lastedit:      23/06/90 01:15:39
  1341.  
  1342.     Description:
  1343.  
  1344.        This can be expanded to be like the unix 'spell' command.
  1345.     This demo file simply checks words passed on the command line.
  1346.     note how it remembers words so that the second time it sees
  1347.     them, it will call them correct.  This is how you should
  1348.     implement the 'ignore' feature of an interactive checker.
  1349.  
  1350.     This version used the fast 'packed' data structure.  This is
  1351.     approximately 3 times faster, but not all utilities support
  1352.     the packed versions.  Also utilities which walk the trie are
  1353.     considerably slower (say by a factor of 100) -- so chose when
  1354.     to used 'dawg' and when to use 'pack'ed versions carefully!
  1355.  
  1356. */
  1357.  
  1358.  
  1359. /* Manadatory header files */
  1360. #include <stdio.h>
  1361. #include "dawg.h"
  1362. #include "grope.h"
  1363.  
  1364. /*#define RCHECK*/     /* Enable for internal range checks... */
  1365.  
  1366. #include "utils.c"
  1367.  
  1368. /* Headers here as needed on per-program basis */
  1369. #include <ctype.h>  /* eg, for isalpha() */
  1370.  
  1371. /* Spelling library utilities */
  1372. #include "init.c"      /* Loading dicts */
  1373. #include "dyntrie.c"   /* Creating dicts at run-time */
  1374. #include "print.c"     /* Printing dicts */
  1375. #include "check.c"     /* Checking words */
  1376. #include "locate.c"    /* Finding words by their stems */
  1377.  
  1378. #include "soundex.c"   /* Soundex algorithm for word-likeness comparison */
  1379. #include "similcmp.c"  /* Closeness-metric for correction */
  1380. #include "correct.c"   /* Hack code to attempt error correction (uses above) */
  1381.  
  1382. /* Let's be friendly to these guys... */
  1383. #ifdef SYS_MAC
  1384. /* To compile with THINK C 4.0, place all the relevant .h and .c
  1385.    files in a folder.  Then create a project which contains this main.c
  1386.    and the libraries unix and ANSI.
  1387. */
  1388. #include <unix.h>
  1389. #include <stdlib.h>
  1390. #include <console.h>
  1391. #endif
  1392.  
  1393. /* Your own header files go here, for instance:
  1394.                #include "readword.h"
  1395.  */
  1396.  
  1397.  
  1398.  
  1399. int
  1400. #ifdef PROTOTYPES
  1401. main(int argc, char **argv)
  1402. #else
  1403. main(argc, argv)
  1404. int argc;
  1405. char **argv;
  1406. #endif
  1407. {
  1408. NODE PCCRAP *ptrie;     /* precompiled dictionary (dict.pck) */
  1409. INDEX edges;            /* size of above */
  1410.  
  1411. NODE PCCRAP *userdict;  /* run-time dictionary, added to dynamically */
  1412.  
  1413. char *word;
  1414. int each;
  1415.  
  1416. #ifdef SYS_MAC
  1417.   argc = ccommand(&argv);  /* Mac users have my sympathy */
  1418. #endif
  1419.  
  1420.   /* Your program goes here... */
  1421.   if (argc == 1) {
  1422.     fprintf(stderr, "usage: %s possibly mispeled wurdz\n", argv[0]);
  1423.     exit(EXIT_ERROR);
  1424.   }
  1425.  
  1426.   if (!pack_init("", &ptrie, &edges)) exit(EXIT_ERROR);
  1427.  
  1428.   if (!trie_new(&userdict)) exit(EXIT_ERROR);
  1429.  
  1430.   for (each = 1; each < argc; each++) {
  1431.     word = argv[each];
  1432.     fprintf(stderr, "* %s:\n", word);
  1433.     if (pack_check(ptrie, word) || dawg_check(userdict, word)) {
  1434.       fprintf(stderr, "Correct\n");
  1435.     } else {
  1436.       fprintf(stderr, "Wrong\n");
  1437.       (void)trie_add(&userdict, word);
  1438.     }
  1439.     if (each+1 != argc) fprintf(stderr, "\n");
  1440.   }
  1441.  
  1442.   exit(EXIT_OK);
  1443. }
  1444. SHAR_EOF
  1445. cat - << \SHAR_EOF > pdawg.c
  1446. /* Manadatory headers */
  1447. /*#define RCHECK*/
  1448. /*#define DEBUG*/
  1449. #include <stdio.h>
  1450. #include "dawg.h"
  1451. #include "grope.h"
  1452. #include "utils.c"
  1453.  
  1454. /* Headers here as needed on per-program basis */
  1455. #include <ctype.h>  /* for isalpha() */
  1456.  
  1457. /* Spelling library utilities */
  1458. #include "init.c"
  1459. #include "print.c"
  1460. /*
  1461. #include "check.c"
  1462. #include "locate.c"
  1463. #include "similcmp.c"
  1464. #include "soundex.c"
  1465. #include "correct.c"
  1466. */
  1467. /*#include "dyntrie.c"*/
  1468.  
  1469. int
  1470. #ifdef PROTOTYPES
  1471. main(int argc, char **argv)
  1472. #else
  1473. main(argc, argv)
  1474. int argc;
  1475. char **argv;
  1476. #endif
  1477. {
  1478. NODE PCCRAP *dawg;
  1479. INDEX nedges;
  1480.   if (!dawg_init((argc == 1 ? "" : argv[1]), &dawg, &nedges)) exit(EXIT_ERROR);
  1481.   dawg_print(dawg, (INDEX)ROOT_NODE);
  1482.   fprintf(stderr, "Finished printing dawg\n");
  1483.   exit(0);
  1484. }
  1485. SHAR_EOF
  1486. cat - << \SHAR_EOF > ppack.c
  1487. /* Manadatory headers */
  1488. #include <stdio.h>
  1489. #include "dawg.h"
  1490. #include "grope.h"
  1491. #include "utils.c"
  1492.  
  1493. /* Headers here as needed on per-program basis */
  1494. #include <ctype.h>  /* for isalpha() */
  1495.  
  1496. /* Spelling library utilities */
  1497. #include "init.c"
  1498. #include "print.c"
  1499. /*
  1500. #include "check.c"
  1501. #include "locate.c"
  1502. #include "similcmp.c"
  1503. #include "soundex.c"
  1504. #include "correct.c"
  1505. */
  1506. /*#include "dyntrie.c"*/
  1507.  
  1508.  
  1509.  
  1510. int
  1511. #ifdef PROTOTYPES
  1512. main(int argc, char **argv)
  1513. #else
  1514. main(argc, argv)
  1515. int argc;
  1516. char **argv;
  1517. #endif
  1518. {
  1519. NODE PCCRAP *ptrie;
  1520. INDEX nedges;
  1521.   if (!pack_init((argc == 1 ? "": argv[1]), &ptrie, &nedges)) exit(EXIT_ERROR);
  1522.   pack_print(ptrie, (INDEX)ROOT_NODE);
  1523.   exit(0);
  1524. }
  1525. SHAR_EOF
  1526. cat - << \SHAR_EOF > proot.c
  1527. /*
  1528.  
  1529.     File:          proot.c
  1530.     Author:        Graham Toal
  1531.     Purpose:       find all words starting with 'root'
  1532.     Creation date: 22/06/90
  1533.     Lastedit:      22:24:32
  1534.  
  1535.     Description:
  1536.       some spelling programs remove characters from the end of
  1537.     wrongly spelt words one by one until the resulting root is
  1538.     found to be a prefix of other words in the dictionary.  This
  1539.     works because the assumption is made that the word was in
  1540.     fact correct, but was an inflected form of a word in the
  1541.     dictionary which had not been stored.
  1542. */
  1543.  
  1544.  
  1545. /* Manadatory header files */
  1546. #include <stdio.h>
  1547. #include "dawg.h"
  1548. #include "grope.h"
  1549. #include "utils.c"
  1550.  
  1551. /* Headers here as needed on per-program basis */
  1552. #include <ctype.h>  /* eg, for isalpha() */
  1553.  
  1554. /* Spelling library utilities */
  1555. #include "init.c"        /* Loading dicts */
  1556. /*#include "dyntrie.c"*/ /* Creating dicts at run-time */
  1557. #include "print.c"       /* Printing dicts */
  1558. /*#include "check.c"*/   /* Checking words */
  1559. #include "locate.c"      /* Finding words by their stems */
  1560.  
  1561. /*#include "soundex.c"*/ /* Soundex algorithm for word-likeness comparison */
  1562. /*#include "similcmp.c"*//* Closeness-metric for correction */
  1563. /*#include "correct.c"*/ /* Code to attempt error correction (uses above) */
  1564.  
  1565. /* Let's be friendly to these guys... */
  1566. #ifdef SYS_MAC
  1567. /* To compile with THINK C 4.0, place all the relevant .h and .c
  1568.    files in a folder.  Then create a project which contains this main.c
  1569.    and the libraries unix and ANSI.
  1570. */
  1571. #include <unix.h>
  1572. #include <stdlib.h>
  1573. #include <console.h>
  1574. #endif
  1575.  
  1576. /* Your own header files go here, for instance:
  1577.                #include "readword.h"
  1578.  */
  1579.  
  1580.  
  1581.  
  1582. int
  1583. #ifdef PROTOTYPES
  1584. main(int argc, char **argv)
  1585. #else
  1586. main(argc, argv)
  1587. int argc;
  1588. char **argv;
  1589. #endif
  1590. {
  1591. NODE PCCRAP *dawg;
  1592. INDEX root;
  1593. INDEX edges;
  1594. int each;
  1595.  
  1596. #ifdef SYS_MAC
  1597.   argc = ccommand(&argv);  /* Mac users have my sympathy */
  1598. #endif
  1599.  
  1600.   /* Your program goes here... */
  1601.   if (argc == 1) {
  1602.     fprintf(stderr, "usage: %s part\n", argv[0]);
  1603.     exit(EXIT_ERROR);
  1604.   }
  1605.   if (!dawg_init("", &dawg, &edges)) exit(EXIT_ERROR);
  1606.   for (each = 1; each < argc; each++) {
  1607.     fprintf(stderr, "* %s:\n", argv[each]);
  1608.     root = dawg_locate_prefix(dawg, argv[each], ROOT_NODE);
  1609.     if (root != ROOT_NODE) {
  1610.       dawg_print_prefix(dawg, argv[each], root);
  1611.     } else {
  1612.       fprintf(stderr, "(none found)\n");
  1613.     }
  1614.     if (each+1 != argc) fprintf(stderr, "\n");
  1615.   }
  1616.  
  1617.   exit(EXIT_OK);
  1618. }
  1619. SHAR_EOF
  1620. cat - << \SHAR_EOF > sample.c
  1621. /*
  1622.    Dummy program for writing word utilities.
  1623.    If you stick to the style shown here, your programs will
  1624.    remain portable across a vast range of machines.
  1625.    Skeleton file by Graham Toal.  Remove this header when you've
  1626.    added your own...
  1627.  
  1628.    (If you want to see some worked examples, try
  1629.     tell.c  dwgcheck.c  pckcheck.c)
  1630.  
  1631. */
  1632.  
  1633. /*
  1634.  
  1635.     File:          
  1636.     Author:        
  1637.     Purpose:       
  1638.     Creation date: 
  1639.     Lastedit:      
  1640.  
  1641.     Description:
  1642.  
  1643. */
  1644.  
  1645.  
  1646. /* Manadatory header files */
  1647. #include <stdio.h>
  1648. #include "dawg.h"
  1649. #include "grope.h"
  1650. #include "utils.c"
  1651.  
  1652. /* Headers here as needed on per-program basis */
  1653. #include <ctype.h>  /* eg, for isalpha() */
  1654.  
  1655. /* Spelling library utilities */
  1656. #include "init.c"      /* Loading dicts */
  1657. #include "dyntrie.c"   /* Creating dicts at run-time */
  1658. #include "print.c"     /* Printing dicts */
  1659. #include "check.c"     /* Checking words */
  1660. #include "locate.c"    /* Finding words by their stems */
  1661.  
  1662. #include "soundex.c"   /* Soundex algorithm for word-likeness comparison */
  1663. #include "similcmp.c"  /* Closeness-metric for correction */
  1664. #include "correct.c"   /* Hack code to attempt error correction (uses above) */
  1665.  
  1666. /* Let's be friendly to these guys... */
  1667. #ifdef SYS_MAC
  1668. /* To compile with THINK C 4.0, place all the relevant .h and .c
  1669.    files in a folder.  Then create a project which contains this main.c
  1670.    and the libraries unix and ANSI.
  1671. */
  1672. #include <unix.h>
  1673. #include <stdlib.h>
  1674. #include <console.h>
  1675. #endif
  1676.  
  1677. /* Your own header files go here, for instance:
  1678.                #include "readword.h"
  1679.  */
  1680.  
  1681.  
  1682.  
  1683. int
  1684. #ifdef PROTOTYPES
  1685. main(int argc, char **argv)
  1686. #else
  1687. main(argc, argv)
  1688. int argc;
  1689. char **argv;
  1690. #endif
  1691. {
  1692. #ifdef SYS_MAC
  1693.   argc = ccommand(&argv);  /* Mac users have my sympathy */
  1694. #endif
  1695.  
  1696.   /* Your program goes here... */
  1697.  
  1698.   exit(EXIT_OK);
  1699. }
  1700. SHAR_EOF
  1701. cat - << \SHAR_EOF > tell.c
  1702. /*
  1703.  
  1704.     File:          tell.c
  1705.     Author:        Graham Toal
  1706.     Purpose:       offer correct spelling
  1707.     Creation date: 22/06/90
  1708.     Lastedit:      22:24:32
  1709.  
  1710.     Description:
  1711.  
  1712.        Like the unix 'spelltell' command.
  1713.  
  1714. */
  1715.  
  1716.  
  1717. /* Manadatory header files */
  1718. #include <stdio.h>
  1719. #include "dawg.h"
  1720. #include "grope.h"
  1721. #include "utils.c"
  1722.  
  1723. /* Headers here as needed on per-program basis */
  1724. #include <ctype.h>  /* eg, for isalpha() */
  1725.  
  1726. /* Spelling library utilities */
  1727. #include "init.c"      /* Loading dicts */
  1728. #include "dyntrie.c"   /* Creating dicts at run-time */
  1729. #include "print.c"     /* Printing dicts */
  1730. #include "check.c"     /* Checking words */
  1731. #include "locate.c"    /* Finding words by their stems */
  1732.  
  1733. #include "soundex.c"   /* Soundex algorithm for word-likeness comparison */
  1734. #include "similcmp.c"  /* Closeness-metric for correction */
  1735. #include "correct.c"   /* Hack code to attempt error correction (uses above) */
  1736.  
  1737. /* Let's be friendly to these guys... */
  1738. #ifdef SYS_MAC
  1739. /* To compile with THINK C 4.0, place all the relevant .h and .c
  1740.    files in a folder.  Then create a project which contains this main.c
  1741.    and the libraries unix and ANSI.
  1742. */
  1743. #include <unix.h>
  1744. #include <stdlib.h>
  1745. #include <console.h>
  1746. #endif
  1747.  
  1748. /* Your own header files go here, for instance:
  1749.                #include "readword.h"
  1750.  */
  1751.  
  1752.  
  1753.  
  1754. int
  1755. #ifdef PROTOTYPES
  1756. main(int argc, char **argv)
  1757. #else
  1758. main(argc, argv)
  1759. int argc;
  1760. char **argv;
  1761. #endif
  1762. {
  1763. NODE PCCRAP *dawg;
  1764. INDEX edges;
  1765. int each;
  1766.  
  1767. #ifdef SYS_MAC
  1768.   argc = ccommand(&argv);  /* Mac users have my sympathy */
  1769. #endif
  1770.  
  1771.   /* Your program goes here... */
  1772.   if (argc == 1) {
  1773.     fprintf(stderr, "usage: %s mispeled wurdz\n", argv[0]);
  1774.     exit(EXIT_ERROR);
  1775.   }
  1776.   if (!dawg_init("", &dawg, &edges)) exit(EXIT_ERROR);
  1777.   for (each = 1; each < argc; each++) {
  1778.     fprintf(stderr, "* %s:\n", argv[each]);
  1779.     if (!dawg_correct(dawg, argv[each])) {
  1780.       fprintf(stderr, "(none found)\n");
  1781.     }
  1782.     if (each+1 != argc) fprintf(stderr, "\n");
  1783.   }
  1784.  
  1785.   exit(EXIT_OK);
  1786. }
  1787. SHAR_EOF
  1788.