home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / APPS / lout2.lzh / LOUT2 / z36.c < prev    next >
Text File  |  1994-01-23  |  31KB  |  725 lines
  1. /*@z36.c:Hyphenation: Declarations@*******************************************/
  2. /*                                                                           */
  3. /*  LOUT: A HIGH-LEVEL LANGUAGE FOR DOCUMENT FORMATTING (VERSION 2.05)       */
  4. /*  COPYRIGHT (C) 1993 Jeffrey H. Kingston                                   */
  5. /*                                                                           */
  6. /*  Jeffrey H. Kingston (jeff@cs.su.oz.au)                                   */
  7. /*  Basser Department of Computer Science                                    */
  8. /*  The University of Sydney 2006                                            */
  9. /*  AUSTRALIA                                                                */
  10. /*                                                                           */
  11. /*  This program is free software; you can redistribute it and/or modify     */
  12. /*  it under the terms of the GNU General Public License as published by     */
  13. /*  the Free Software Foundation; either version 1, or (at your option)      */
  14. /*  any later version.                                                       */
  15. /*                                                                           */
  16. /*  This program is distributed in the hope that it will be useful,          */
  17. /*  but WITHOUT ANY WARRANTY; without even the implied warranty of           */
  18. /*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            */
  19. /*  GNU General Public License for more details.                             */
  20. /*                                                                           */
  21. /*  You should have received a copy of the GNU General Public License        */
  22. /*  along with this program; if not, write to the Free Software              */
  23. /*  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                */
  24. /*                                                                           */
  25. /*  FILE:         z36.c                                                      */
  26. /*  MODULE:       Hyphenation                                                */
  27. /*  EXTERNS:      Hyphenate()                                                */
  28. /*                                                                           */
  29. /*****************************************************************************/
  30. #include "externs"
  31. #define MAX_CHAR    256        /* max chars represented in one char */
  32. #define TRIE_MAGIC    5361534
  33. #define KILL_CLASS    0        /* characters preventing hyphenation */
  34. #define PUNCT_CLASS    1        /* characters delimiting hyphenation */
  35.  
  36. typedef struct trie_rec
  37. { int        magic;            /* a magic number to make sure ok    */
  38.   int        class_count;        /* the number of character classes   */
  39.   unsigned char    class[MAX_CHAR];    /* the character classes             */
  40.   short        *node_mem;        /* the node memory                   */
  41.   int        node_lim;        /* top of node memory                */
  42.   int        node_free;        /* first free space in node memory   */
  43.   FULL_CHAR    *string_mem;        /* the string memory                 */
  44.   int        string_lim;        /* top of string memory              */
  45.   int        string_first;        /* the first (last inserted) string  */
  46. } *TRIE;
  47.  
  48.  
  49. /*****************************************************************************/
  50. /*                                                                           */
  51. /*  static TRIE T                                                            */
  52. /*                                                                           */
  53. /*  The packed hyphenation table, or NULL if not yet read in.                */
  54. /*                                                                           */
  55. /*****************************************************************************/
  56.  
  57. static TRIE    T = (TRIE) NULL;    /* the compressed hyphenation table  */
  58.  
  59.  
  60. /*****************************************************************************/
  61. /*                                                                           */
  62. /*  ClassConvert(in, out, T)                                                 */
  63. /*                                                                           */
  64. /*  Set out[i] to the character class of in[i] in T, for all i.              */
  65. /*                                                                           */
  66. /*****************************************************************************/
  67.  
  68. #define ClassConvert(in, out, T)                    \
  69. { int i;                                \
  70.   for( i = 0;  in[i] != '\0';  i++ )                    \
  71.     if( T->class[in[i]] != 0 )  out[i] = T->class[in[i]];        \
  72.     else Error(INTERN, no_fpos, "hyph: \"%s\" has illegal class", in);    \
  73.   out[i] = '\0';                            \
  74. } /* end ClassConvert */
  75.  
  76.  
  77. /*@::findrep(), TrieRetrieve(), ShowRate()@***********************************/
  78. /*                                                                           */
  79. /*  findrep(i, T)     Returns one character whose class in T is i.           */
  80. /*                                                                           */
  81. /*****************************************************************************/
  82. #if DEBUG_ON
  83.  
  84. static FULL_CHAR findrep(i, T)
  85. int i;  TRIE T;
  86. { int ch;
  87.   for( ch = 0;  ch < MAX_CHAR;  ch++ )
  88.     if( T->class[ch] == i ) return (FULL_CHAR) ch;
  89.   Error(INTERN, no_fpos, "hyph DoTriePrint: findrep failed");
  90. } /* end findrep */
  91.  
  92.  
  93. /*****************************************************************************/
  94. /*                                                                           */
  95. /*  static FULL_CHAR *TrieRetrieve(key, T)                                   */
  96. /*                                                                           */
  97. /*  Retrieve the value associated with key in T, or NULL if not present.     */
  98. /*                                                                           */
  99. /*****************************************************************************/
  100.  
  101. static FULL_CHAR *TrieRetrieve(key, T)
  102. FULL_CHAR *key;  TRIE T;
  103. { FULL_CHAR str[MAX_LINE];  int i, curr_node, next_node, pos;
  104.   debug1(DHY, DD, "TrieRetrieve(%s, T)", key);
  105.   ClassConvert(key, str, T);
  106.  
  107.   /* invariant: curr_node is an existing node of T with prefix str[0..i-1] */
  108.   curr_node = i = 0;
  109.   for(;;)
  110.   {
  111.     /* if next_node is 0, the string was never inserted */
  112.     next_node = T->node_mem[curr_node + str[i]];
  113.     if( next_node == 0 )  return (FULL_CHAR *) NULL;
  114.  
  115.     /* if next_node < 0 it represents an offset into the string memory */
  116.     if( next_node < 0 )
  117.     { pos = - next_node;
  118.       if( str[i] != '\0' )
  119.       {    do
  120.     { if( str[++i] != T->string_mem[pos++] )  return (FULL_CHAR *) NULL;
  121.     } while( str[i] != '\0' );
  122.       }
  123.       return &(T->string_mem[pos]);
  124.     }
  125.  
  126.     /* otherwise next_node is the trie node to be searched next */
  127.     curr_node = 2*next_node;  i++;
  128.   }
  129. } /* end TrieRetrieve */
  130.  
  131.  
  132. /*****************************************************************************/
  133. /*                                                                           */
  134. /*  static ShowRate(key, start, stop, rate, fp)                              */
  135. /*                                                                           */
  136. /*  Debug print of key[] and rate[] on file fp.                              */
  137. /*                                                                           */
  138. /*****************************************************************************/
  139.  
  140. static ShowRate(key, start, stop, rate, fp)
  141. FULL_CHAR *key;  int start, stop;  FULL_CHAR *rate;  FILE *fp;
  142. { int i;
  143.   fprintf(fp, "key:    ");
  144.   for( i = start;  i < stop;  i++ )  fprintf(fp, " %c", key[i]);
  145.   fprintf(fp, "\nrate:");
  146.   for( i = 0;  rate[i] != '\0';  i++ )  fprintf(fp, " %c", rate[i]);
  147.   fprintf(fp, "\n");
  148. } /* end ShowRate */
  149.  
  150.  
  151. /*@::DoTriePrint(), TriePrint()@**********************************************/
  152. /*                                                                           */
  153. /*  static DoTriePrint(T, node, len, fp)                                     */
  154. /*                                                                           */
  155. /*  Print on file fp the subset of the entries of trie T stored in node and  */
  156. /*  its descendants.  The node has prefix prefix[0..len-1].                  */
  157. /*                                                                           */
  158. /*****************************************************************************/
  159.  
  160. static FULL_CHAR prefix[MAX_LINE];
  161.  
  162. static DoTriePrint(T, node, len, fp)
  163. TRIE T; int node, len; FILE *fp;
  164. { int i, next_node, pos;
  165.   for( i = 0;  i < T->class_count;  i++ )
  166.   {
  167.     /* if next_node < 0, have string to print */
  168.     next_node = T->node_mem[node + i];
  169.     if( next_node < 0 )
  170.     {
  171.       prefix[len] = '\0';
  172.       fprintf(fp, "%s", prefix);
  173.       pos = - next_node;
  174.       if( i != 0 )
  175.       {
  176.     fprintf(fp, "%c", findrep(i, T));
  177.     while( T->string_mem[pos] != '\0' )
  178.     { fprintf(fp, "%c", findrep(T->string_mem[pos], T));
  179.       pos++;
  180.     }
  181.     pos++;
  182.       }
  183.       fprintf(fp, " %s\n", &(T->string_mem[pos]));
  184.     }
  185.  
  186.     /* else if next_node > 0 have a child node to explore */
  187.     else if( next_node > 0 )
  188.     { assert( i > 0, "DoTriePrint: i == 0!" );
  189.       prefix[len] = findrep(i, T);
  190.       prefix[len+1] = '\0';
  191.       DoTriePrint(T, 2*next_node, len+1, fp);
  192.     }
  193.   }
  194. } /* end DoTriePrint */
  195.  
  196.  
  197. /*****************************************************************************/
  198. /*                                                                           */
  199. /*  static TriePrint(T, fp)                                                  */
  200. /*                                                                           */
  201. /*  Print trie T on file fp.                                                 */
  202. /*                                                                           */
  203. /*****************************************************************************/
  204.  
  205. static TriePrint(T, fp)
  206. TRIE T;  FILE *fp;
  207. { int i, j, ch;
  208.   assert( T-> magic == TRIE_MAGIC, "TriePrint: magic!" );
  209.   fprintf(fp, "Classes:");
  210.   for( i = 1;  i < T->class_count;  i++ )
  211.   { fprintf(fp, " ");
  212.     for( ch = 0;  ch < MAX_CHAR;  ch++ )
  213.       if( T->class[ch] == i )  fprintf(fp, "%c", ch);
  214.   }
  215.   fprintf(fp, "\n");
  216.   fprintf(fp, "Node space: %d capacity, %d used\n", T->node_lim, T->node_free);
  217.   fprintf(fp, "String space: %d capacity, %d used\n", T->string_lim,
  218.     T->string_lim - T->string_first);
  219.   prefix[0] = '\0';
  220.   DoTriePrint(T, 0, 0, fp);
  221. } /* end TriePrint */
  222. #endif
  223.  
  224.  
  225. /*@::NewTrie(), ClassConvert(), NewTrieString(), NewTrieNode()@***************/
  226. /*                                                                           */
  227. /*  static TRIE NewTrie(node_lim, string_lim)                                */
  228. /*                                                                           */
  229. /*  Initialize a new trie with the this much space for nodes and strings.    */
  230. /*                                                                           */
  231. /*****************************************************************************/
  232.  
  233. static TRIE NewTrie(node_lim, string_lim)
  234. unsigned node_lim, string_lim;
  235. { TRIE T;  int i;  char *malloc();
  236.   debug2(DHY, D, "NewTrie(%d, %d)", node_lim, string_lim);
  237.   T = (TRIE) malloc( sizeof(struct trie_rec)
  238.              + node_lim*sizeof(short) + string_lim*sizeof(char));
  239.   if( T == (TRIE) NULL )  Error(FATAL, no_fpos,
  240.     "run out of memory while constructing hyphenation table");
  241.   T->magic = TRIE_MAGIC;  T->class_count = 1;
  242.   for( i = 0;  i < MAX_CHAR;  i++ )  T->class[i] = 0;
  243.   T->node_mem = (short *) ( (char *) T + sizeof(struct trie_rec));
  244.   T->node_lim = node_lim;  T->node_free = 0;
  245.   T->string_mem = (FULL_CHAR *) &(T->node_mem[node_lim]);
  246.   T->string_lim = T->string_first = string_lim;
  247.   debug0(DHY, D, "NewTrie returning.");
  248.   return T;
  249. } /* end NewTrie */
  250.  
  251.  
  252. /*****************************************************************************/
  253. /*                                                                           */
  254. /*  static short NewTrieString(str, T)                                       */
  255. /*                                                                           */
  256. /*  Copy a new string into T, and return its offset in string_mem;           */
  257. /*                                                                           */
  258. /*****************************************************************************/
  259.  
  260. static short NewTrieString(str, T)
  261. FULL_CHAR *str;  TRIE T;
  262. { short res = T->string_first - StringLength(str) - 1;
  263.   if( res < 0 )  Error(INTERN, no_fpos, "hyph: trie string limit exceeded");
  264.   T->string_first = res;  StringCopy(&(T->string_mem[res]), str);
  265.   return res;
  266. } /* end NewTrieString */
  267.  
  268.  
  269. /*****************************************************************************/
  270. /*                                                                           */
  271. /*  ststic int NewTrieNode(T)                                                */
  272. /*                                                                           */
  273. /*  Allocate a new empty trie node in T, and return its offset in node_mem.  */
  274. /*                                                                           */
  275. /*****************************************************************************/
  276.  
  277. static int NewTrieNode(T)
  278. TRIE T;
  279. { int i;  int res;
  280.   if( T->node_free + T->class_count > T->node_lim )
  281.     Error(INTERN, no_fpos, "hyph: trie node limit exceeded");
  282.   res = T->node_free;  T->node_free += T->class_count;
  283.   for( i = res;  i < T->node_free;  i++ )  T->node_mem[i] = 0;
  284.   return res;
  285. } /* end NewTrieNode */
  286.  
  287.  
  288. /*@::AddClassToTrie(), TrieInsert()@******************************************/
  289. /*                                                                           */
  290. /*  static AddClassToTrie(str, T)                                            */
  291. /*                                                                           */
  292. /*  Add a new character class, whose members are the characters of str, to   */
  293. /*  trie T.  This cannot occur after the first insertion.                    */
  294. /*                                                                           */
  295. /*****************************************************************************/
  296.  
  297. static AddClassToTrie(str, T)
  298. FULL_CHAR *str; TRIE T;
  299. { int i;
  300.   if( T->string_first != T-> string_lim )
  301.     Error(INTERN, no_fpos, "hyph AddClassToTrie after first insertion!");
  302.   for( i = 0;  str[i] != '\0';  i++ )
  303.     if( T->class[str[i]] == 0 ) T->class[str[i]] = T->class_count;
  304.     else Error(INTERN,no_fpos, "hyph: class of %c may not be changed!", str[i]);
  305.   T->class_count++;
  306. } /* end AddClassToTrie */
  307.  
  308.  
  309. /*****************************************************************************/
  310. /*                                                                           */
  311. /*  static TrieInsert(key, value, T)                                         */
  312. /*                                                                           */
  313. /*  Insert a new key and value into trie T.                                  */
  314. /*                                                                           */
  315. /*****************************************************************************/
  316.  
  317. static TrieInsert(key, value, T)
  318. FULL_CHAR *key, *value;  TRIE T;
  319. { FULL_CHAR str[MAX_LINE];  int i, curr_node, next_node, pos, ch;
  320.   debug2(DHY, D, "TrieInsert(%s, %s, T)", key, value);
  321.  
  322.   /* if first insertion, add one node after making sure class_count is even */
  323.   if( T->node_free == 0 )
  324.   { T->class_count = 2 * ceiling(T->class_count, 2);
  325.     ch = NewTrieNode(T);
  326.   }
  327.  
  328.   /* invariant: curr_node is an existing node of T with prefix str[0..i-1] */
  329.   ClassConvert(key, str, T);
  330.   curr_node = i = 0;
  331.   for(;;)
  332.   {
  333.     /* if str is ended, add value only to string memory */
  334.     if( str[i] == '\0' )
  335.     { if( T->node_mem[curr_node] != 0 )
  336.     Error(INTERN, no_fpos, "hyph string %s already inserted", key);
  337.       else T->node_mem[curr_node] = - NewTrieString(value, T);
  338.       debug0(DHY, D, "TrieInsert returning (empty suffix).");
  339.       return;
  340.     }
  341.  
  342.     /* if next position is unoccupied, store remainder of str and value */
  343.     next_node = T->node_mem[curr_node + str[i]];
  344.     if( next_node == 0 )
  345.     { ch = NewTrieString(value, T);
  346.       T->node_mem[curr_node + str[i]] = - NewTrieString(&str[i+1], T);
  347.       debug0(DHY, D, "TrieInsert returning (non-empty suffix).");
  348.       return;
  349.     }
  350.  
  351.     /* if next position is occupied by a non-empty string, move that */
  352.     /* string down one level and replace it by a trie node           */
  353.     if( next_node < 0 )
  354.     { pos = - next_node;
  355.       ch = T->string_mem[pos];
  356.       if( T->string_first == pos )  T->string_first++;
  357.       T->node_mem[curr_node + str[i]] = next_node = NewTrieNode(T)/2;
  358.       T->node_mem[2*next_node + ch] = -(pos+1);
  359.     }
  360.  
  361.     /* now next is the offset of the next node to be searched */
  362.     curr_node = 2*next_node;  i++;
  363.   }
  364. } /* end TrieInsert */
  365.  
  366.  
  367. /*@::BeGetChar(), BePutChar(), BeGetShort(), BePutShort(), etc.@**************/
  368. /*                                                                           */
  369. /*  BeGetChar(fp, pv)                                                        */
  370. /*  BePutChar(fp, v)                                                         */
  371. /*  BeGetShort(fp, pv)                                                       */
  372. /*  BePutShort(fp, v)                                                        */
  373. /*  BeGetInt(fp, pv)                                                         */
  374. /*  BePutInt(fp, v)                                                          */
  375. /*                                                                           */
  376. /*  Get char, short, or int pv from file fp, and put char, short, or int     */
  377. /*  onto file fp.  These routines are designed so that the file can be       */
  378. /*  written or read safely by big-endian and little-endian architectures;    */
  379. /*  this is accomplished by reading and writing one byte at a time to and    */
  380. /*  from a big-endian format file.  All return 0 on success, -1 on failure.  */
  381. /*  Thanks to David W. Sanderson for this code.                              */
  382. /*                                                                           */
  383. /*****************************************************************************/
  384.  
  385. #define BeGetChar(fp, pv)  ( (c = getc(fp)) == EOF ? -1 : (*pv = c & 0xFF, 0) )
  386. #define BePutChar(fp, v)   ( putc( (char) (v & 0xFF), fp), 0 )
  387.  
  388. #define BeGetShort(fp, pv)                        \
  389. (  (c = getc(fp)) == EOF ? -1 :                        \
  390.    (  *pv = (c & 0xFF) << 8,                        \
  391.       (c = getc(fp)) == EOF ? -1 : (*pv |= c & 0xFF, 0)            \
  392.    )                                    \
  393. )
  394.  
  395. #define BePutShort(fp, v)                        \
  396. ( putc((v >> 8) & 0xFF, fp), putc(v & 0xFF, fp), 0 )
  397.  
  398. int BeGetInt(fp, pv)
  399. FILE *fp; int *pv;
  400. { int c;
  401.   if ((c = getc(fp)) == EOF) return -1;
  402.   *pv = (c & 0xFF) << 24;
  403.   if ((c = getc(fp)) == EOF) return -1;
  404.   *pv |= (c & 0xFF) << 16;
  405.   if ((c = getc(fp)) == EOF) return -1;
  406.   *pv |= (c & 0xFF) << 8;
  407.   if ((c = getc(fp)) == EOF) return -1;
  408.   *pv |= c & 0xFF;
  409.   return 0;
  410. }
  411.  
  412. int BePutInt(fp, v)
  413. FILE *fp; int v;
  414. {
  415.   putc((v >> 24) & 0xFF, fp);
  416.   putc((v >> 16) & 0xFF, fp);
  417.   putc((v >> 8) & 0xFF, fp);
  418.   putc(v & 0xFF, fp);
  419.   return 0;
  420. }
  421.  
  422.  
  423. /*@::CompressTrie(), TrieRead(), AccumulateRating()@**************************/
  424. /*                                                                           */
  425. /*  static CompressTrie(T)                                                   */
  426. /*                                                                           */
  427. /*  Compress trie T and return its length in characters.                     */
  428. /*                                                                           */
  429. /*****************************************************************************/
  430.  
  431. static CompressTrie(T)
  432. TRIE T;
  433. { FULL_CHAR *p, *q;  int len, i;
  434.   debug0(DHY, D, "CompressTrie(T), T =");
  435.   ifdebug(DHY, DD, TriePrint(T, stderr));
  436.   T->node_lim = T->node_free;
  437.   for( i = 0;  i < T->node_lim;  i++ )
  438.     if( T->node_mem[i] < 0 )
  439.       T->node_mem[i] = - ( -T->node_mem[i] - T->string_first);
  440.   p = (FULL_CHAR *) &(T->node_mem[T->node_free]);
  441.   q = &(T->string_mem[T->string_first]);
  442.   len = T->string_lim - T->string_first;
  443.   for( i = 0;  i < len;  i++ )  *p++ = *q++;
  444.   T->string_mem = (FULL_CHAR *) &(T->node_mem[T->node_lim]);
  445.   T->string_first = 0;
  446.   T->string_lim = len;
  447.   len = sizeof(struct trie_rec) + T->node_lim * sizeof(short)
  448.                 + T->string_lim * sizeof(FULL_CHAR);
  449.   debug1(DHY, D, "CompressTrie returning; len = %d, T =", len);
  450.   ifdebug(DHY, DD, TriePrint(T, stderr));
  451. } /* end CompressTrie */
  452.  
  453.  
  454. /*****************************************************************************/
  455. /*                                                                           */
  456. /*  static TRIE TrieRead()                                                   */
  457. /*                                                                           */
  458. /*  Read in a packed trie if possible, otherwise pack an unpacked one.       */
  459. /*                                                                           */
  460. /*****************************************************************************/
  461.  
  462. static TRIE TrieRead()
  463. { TRIE T;  FILE_NUM unpacked_fnum, packed_fnum;
  464.   FILE *unpacked_fp, *packed_fp;  unsigned len; int prev, i, j, c;
  465.   char *malloc();
  466.   debug0(DHY, D, "TrieRead()");
  467.  
  468.   /* open file, using name stored in file handler */
  469.   packed_fnum = FirstFile(HYPH_PACKED_FILE);
  470.   assert( packed_fnum != NO_FILE, "TrieRead: packed_fnum!" );
  471.   packed_fp = OpenFile(packed_fnum, FALSE, FALSE);
  472.   if( packed_fp == NULL )
  473.   {
  474.     /* no packed file, so open unpacked one instead */
  475.     FULL_CHAR str[MAX_LINE], key[MAX_LINE], value[MAX_LINE],
  476.           buff[MAX_LINE+10];
  477.     unpacked_fnum = FirstFile(HYPH_FILE);
  478.     assert( unpacked_fnum != NO_FILE, "TrieRead: unpacked unpacked_fnum!" );
  479.     unpacked_fp = OpenFile(unpacked_fnum, FALSE, FALSE);
  480.     if( unpacked_fp == NULL )
  481.     { Error(WARN, no_fpos, "cannot open hyphenation file %s",
  482.     FileName(unpacked_fnum));
  483.       return (TRIE) NULL;
  484.     }
  485.  
  486.     /* read in unpacked hyphenation trie from unpacked_fp and compress it */
  487.     T = NewTrie( (unsigned) 60000,  (unsigned) 32767);
  488.     while( StringFGets(str, MAX_LINE, unpacked_fp) != NULL &&
  489.         str[0] != CH_NEWLINE )
  490.     { str[StringLength(str)-1] = '\0';
  491.       debug1(DHY, D, "adding class %s", str);
  492.       AddClassToTrie(str, T);
  493.     }
  494.     while( StringFGets(str, MAX_LINE, unpacked_fp) != NULL &&
  495.         str[0] != CH_NEWLINE )
  496.     { prev = CH_ZERO; j = 0;
  497.       for( i = 0;  str[i] != CH_NEWLINE && str[i] != '\0';  i++ )
  498.       { if( decimaldigit(str[i]) )  prev = str[i];
  499.         else key[j] = str[i], value[j++] = prev, prev = CH_ZERO;
  500.       }
  501.       key[j] = '\0';  value[j] = prev;  value[j+1] = '\0';
  502.       TrieInsert(key, value, T);
  503.     }
  504.     fclose(unpacked_fp);
  505.     CompressTrie(T);
  506.  
  507.     /* write the compressed trie out to the packed file */
  508.     StringCopy(buff, FileName(unpacked_fnum));
  509.     StringCat(buff, HYPH_SUFFIX);
  510.     packed_fp = StringFOpen(buff, "w");
  511.     if( packed_fp == NULL )  Error(FATAL, no_fpos,
  512.       "cannot write to hyphenation file %s", buff);
  513.     BePutInt(packed_fp, T->magic);
  514.     BePutInt(packed_fp, T->class_count);
  515.     for( i = 0; i < MAX_CHAR; i++ )  BePutChar(packed_fp, T->class[i]);
  516.     BePutInt(packed_fp, 0);  /* placeholder for node_mem */
  517.     BePutInt(packed_fp, T->node_lim);
  518.     BePutInt(packed_fp, T->node_free);
  519.     BePutInt(packed_fp, 0);  /* placeholder for string_mem */
  520.     BePutInt(packed_fp, T->string_lim);
  521.     BePutInt(packed_fp, T->string_first);
  522.     for( i = 0; i < T->node_free; i++ )  BePutShort(packed_fp, T->node_mem[i]);
  523.     for( i = 0; i < T->string_lim; i++)  BePutChar(packed_fp, T->string_mem[i]);
  524.     fclose(packed_fp);
  525.  
  526.     /* now try again to open packed_fnum, the file just written */
  527.     packed_fp = OpenFile(packed_fnum, FALSE, FALSE);
  528.     if( packed_fp == NULL )  Error(FATAL, no_fpos,
  529.       "cannot open hyphenation file %s", FileName(packed_fnum));
  530.   }
  531.  
  532.   /* now packed hyphenation file is open, read it in */
  533.   fseek(packed_fp,0L,2);  len = (unsigned) ftell(packed_fp);  rewind(packed_fp);
  534.   T = (TRIE) malloc(len);
  535.   if( T == (TRIE) NULL )  Error(FATAL, no_fpos,
  536.     "run out of memory while reading hyphenation table");
  537.   if( BeGetInt(packed_fp, &T->magic) != 0 )  Error(FATAL, no_fpos,
  538.       "error on read from packed hyphenation file %s", FileName(packed_fnum));
  539.   if( T->magic != TRIE_MAGIC )  Error(FATAL, no_fpos,
  540.       "bad magic number in hyphenation file %s", FileName(packed_fnum));
  541.   BeGetInt(packed_fp, &T->class_count);
  542.   for( i = 0; i < MAX_CHAR; i++ )  BeGetChar(packed_fp, &T->class[i]);
  543.   BeGetInt(packed_fp, &i);  /* placeholder for node_mem */
  544.   BeGetInt(packed_fp, &T->node_lim);
  545.   BeGetInt(packed_fp, &T->node_free);
  546.   BeGetInt(packed_fp, &i);  /* placeholder for string_mem */
  547.   BeGetInt(packed_fp, &T->string_lim);
  548.   BeGetInt(packed_fp, &T->string_first);
  549.   T->node_mem = (short *) ( (char *) T + sizeof(struct trie_rec) );
  550.   T->string_mem = (FULL_CHAR *) &(T->node_mem[T->node_lim]);
  551.   for( i = 0; i < T->node_free; i++ )  BeGetShort(packed_fp, &T->node_mem[i]);
  552.   for( i = 0; i < T->string_lim; i++ ) BeGetChar(packed_fp, &T->string_mem[i]);
  553.  
  554.   /* debug and exit */
  555.   debug0(DHY, D, "TrieRead returning, T =");
  556.   ifdebug(DHY, DD, TriePrint(T, stderr));
  557.   return T;
  558. } /* end TrieRead */
  559.  
  560.  
  561. /*****************************************************************************/
  562. /*                                                                           */
  563. /*  AccumulateRating(x, y)                                                   */
  564. /*                                                                           */
  565. /*  Accumulate the hyphenation rating string x into y.                       */
  566. /*                                                                           */
  567. /*****************************************************************************/
  568.  
  569. #define AccumulateRating(x, y)                        \
  570. { FULL_CHAR *p = x, *q = y;                        \
  571.   while( *p )                                \
  572.   { if( *p > *q )  *q = *p;                        \
  573.     p++, q++;                                \
  574.   }                                    \
  575. } /* end AccumulateRating */
  576.  
  577.  
  578. /*@::Hyphenate@***************************************************************/
  579. /*                                                                           */
  580. /*  OBJECT Hyphenate(x)                                                      */
  581. /*                                                                           */
  582. /*  Hyphenate ACAT object x, returning the hyphenated result.                */
  583. /*                                                                           */
  584. /*****************************************************************************/
  585.  
  586. OBJECT Hyphenate(x)
  587. OBJECT x;
  588. { OBJECT link, y, z, next_link;
  589.   FULL_CHAR str[MAX_LINE+2], rate[MAX_LINE+3], *class, *key, *ss, *s, *p, *rem;
  590.   int start, stop, i, curr_node, next_node, pos;
  591.   BOOLEAN hyphenated;  static ShowRate();
  592.   static BOOLEAN tried_file = FALSE;
  593.   assert( type(x) == ACAT, "Hyphenate: type(x) != ACAT!" );
  594.   debug1(DHY, DD, "Hyphenate(%s)", EchoObject(x));
  595.  
  596.   /* if no trie is present, try to get it from a file */
  597.   if( T == (TRIE) NULL )
  598.   { if( !tried_file )  T = TrieRead();
  599.     tried_file = TRUE;
  600.     if( T == (TRIE) NULL )
  601.     { debug0(DHY, DD, "Hyphenate returning (no trie).");
  602.       return x;
  603.     }
  604.   }
  605.  
  606.   /* for each word y of x, try to hyphenate it */
  607.   for( link = Down(x);  link != x;  link = NextDown(link) )
  608.   { Child(y, link);
  609.     if( !is_word(type(y)) )  continue;
  610.     debug1(DHY, DD, "Hyphenate() examining %s", EchoObject(y));
  611.  
  612.     /* start := index of first letter of y, stop := index following last */
  613.     key = string(y);  class = T->class;
  614.     for( start = 0;  class[key[start]] == PUNCT_CLASS;  start++ );
  615.     for( stop = start;  class[key[stop]] > PUNCT_CLASS;  stop++ );
  616.  
  617.     /* if a - ended the run, hyphenate there only */
  618.     if( key[stop] == CH_HYPHEN )
  619.     { next_link = NextDown(link);
  620.       z = MakeWord(WORD, &key[stop+1], &fpos(y));
  621.       word_font(z) = word_font(y);
  622.       FontWordSize(z);
  623.       Link(NextDown(link), z);
  624.       z = New(GAP_OBJ);
  625.       SetGap(gap(z), FALSE, TRUE, FIXED_UNIT, HYPH_MODE, 0);
  626.       Link(NextDown(link), z);
  627.       Link(z, MakeWord(WORD, STR_GAP_ZERO_HYPH, &fpos(y)));
  628.       key[stop + 1] = '\0';
  629.       FontWordSize(y);
  630.       link = PrevDown(next_link);
  631.       continue;
  632.     }
  633.  
  634.     /* do not hyphenate if less than 5 letters, or a kill char is nearby */
  635.     if( stop - start < 5 )  continue;
  636.     if( key[stop] != '\0' && class[key[stop]] == KILL_CLASS )  continue;
  637.  
  638.     /* let str[] be the converted substring, let rate[] be all CH_ZERO */
  639.     str[0] = PUNCT_CLASS;  rate[0] = CH_ZERO;
  640.     for( i = 0;  i < stop - start;  i++ )
  641.     { str[i+1] = class[key[start + i]];
  642.       rate[i+1] = CH_ZERO;
  643.     }
  644.     str[i+1] = PUNCT_CLASS;  rate[i+1] = CH_ZERO;
  645.     str[i+2] = '\0';  rate[i+2] = CH_ZERO;
  646.     rate[i+3] = '\0';
  647.     ifdebug(DHY, DD, ShowRate(key, start, stop, rate, stderr));
  648.  
  649.     /* for each suffix of str[], accumulate patterns matching its prefixes */
  650.     ss = str;
  651.     do
  652.     {
  653.       ifdebug(DHY, DD,
  654.     fprintf(stderr, "trying suffix \"");
  655.     for( p = ss; *p != 0;  p++ )  fprintf(stderr, "%c", findrep(*p, T));
  656.     fprintf(stderr, "\"\n");
  657.       );
  658.     
  659.       /* accumulate all prefixes of ss */
  660.       curr_node = 0;  s = ss;
  661.       for(;;)
  662.       {
  663.     /* if curr_node has empty string, that is one prefix */
  664.     pos = T->node_mem[curr_node];
  665.     if( pos < 0 )
  666.     { AccumulateRating(&T->string_mem[- pos], rate+(ss-str));
  667.       debug1(DHY, DD, " found %s", &(T->string_mem[- pos]));
  668.     }
  669.  
  670.     /* if ss is finished, no other prefixes are possible */
  671.     if( *s == '\0' )  break;
  672.  
  673.     /* determine next_node and break if empty */
  674.     next_node = T->node_mem[curr_node + *s];
  675.     if( next_node == 0 )  break;
  676.  
  677.     /* if next_node is a string, check whether it is a prefix of ss */
  678.     if( next_node < 0 )
  679.     { rem = &(T->string_mem[-next_node]);
  680.       do
  681.       { if( *rem == '\0' )
  682.         { AccumulateRating(rem+1, rate+(ss-str));
  683.           debug1(DHY, DD, " found %s", rem+1);
  684.           break;
  685.         }
  686.       } while( *++s == *rem++ );
  687.       break;
  688.     }
  689.  
  690.     /* otherwise go on to the next trie node */
  691.     curr_node = 2*next_node;  s++;
  692.       }
  693.     } while( *(++ss + 1) != PUNCT_CLASS );
  694.     ifdebug(DHY, DD, ShowRate(key, start, stop, rate, stderr));
  695.  
  696.     /* now rate[] has accumulated ratings; use it to perform hyphenations */
  697.     hyphenated = FALSE;
  698.     next_link = NextDown(link);
  699.     for( i = stop - start - 1;  i >= 3;  i-- )
  700.     {
  701.       /* hyphenate at i if rate[i] is odd */
  702.       if( is_odd(rate[i]) )
  703.       {    z = MakeWord(WORD, &key[start+i-1], &fpos(y));
  704.     word_font(z) = word_font(y);
  705.     FontWordSize(z);
  706.     Link(NextDown(link), z);
  707.     z = New(GAP_OBJ);
  708.     SetGap(gap(z), FALSE, TRUE, FIXED_UNIT, HYPH_MODE, 0);
  709.     Link(NextDown(link), z);
  710.     Link(z, MakeWord(WORD, STR_GAP_ZERO_HYPH, &fpos(y)));
  711.     key[start + i - 1] = '\0';
  712.     hyphenated = TRUE;
  713.       }
  714.     }
  715.     if( hyphenated )
  716.     { FontWordSize(y);
  717.       link = PrevDown(next_link);
  718.     }
  719.  
  720.   } /* end for each word */
  721.  
  722.   debug1(DHY, DD, "Hyphenate returning %s", EchoObject(x));
  723.   return x;
  724. } /* end Hyphenate */
  725.