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