home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / FM25.ZIP / fm.tar / hyphenate.c < prev    next >
C/C++ Source or Header  |  1992-05-12  |  5KB  |  139 lines
  1. /*
  2.  * Function hyphenate() takes as arguments a word to be split up
  3.  * by hyphenation, the room available to fit the first part into, and
  4.  * the hyphenation level.  If successful in finding a hyphenation
  5.  * point that will permit a small enough first part, the function
  6.  * returns the length of the first part, including one space for the
  7.  * hyphen that will presumably be added.  Otherwise, the original
  8.  * length of the word is returned.
  9.  * Hyphenation level >= 6 blocks hyphenation after hyphen, and
  10.  * level >= 7 blocks hyphenation when there are non-alphabetic
  11.  * characters surrounded by alphabetic ones (such as in email
  12.  * addresses).
  13.  *
  14.  * The tables were taken from a dump of TeX (initex) after
  15.  * it finished digesting the file hyphen.tex, and consequently this
  16.  * data is derivative from the work of Donald E. Knuth and Frank
  17.  * M. Liang.  Almost all the code for the hyphenation function was
  18.  * taken from TeX, from sections 923-924 of TeX: The Program, by
  19.  * Donald E. Knuth, 1986, Addison Wesley.  See section 919-920 of
  20.  * that book for other references.  The original algorithm is
  21.  * intended to apply only to spans of alphabetic characters, but
  22.  * here it is applied more generally.  If it malfunctions, then,
  23.  * that is likely my fault.
  24.  *
  25.  * This program code is in the public domain.
  26.  * Greg Lee, 4/10/92.
  27.  */
  28.  
  29. #include <ctype.h>
  30. #include "trie_link.h"
  31. #include "trie_char.h"
  32. #include "trie_op.h"
  33.  
  34. unsigned char hyf_distance[] = { 0,
  35.  0, 3, 1, 1, 2, 1, 2, 2, 0, 1, 3, 0, 0, 3, 1, 0, 1, 1, 4, 4,
  36.  4, 2, 2, 3, 3, 3, 4, 3, 4, 2, 5, 5, 4, 5, 3, 2, 5, 2, 6, 2,
  37.  2, 3, 4, 1, 3, 2, 2, 3, 3, 3, 2, 3, 1, 5, 5, 1, 4, 3, 1, 2,
  38.  2, 3, 4, 3, 4, 4, 3, 2, 3, 1, 2, 7, 5, 1, 2, 2, 3, 5, 2, 2,
  39.  3, 1, 3, 1, 3, 4, 4, 3, 3, 3, 2, 2, 2, 2, 3, 3, 1, 1, 4, 3,
  40.  3, 2, 3, 6, 2, 3, 4, 4, 3, 4, 1, 4, 4, 3, 2, 2, 2, 3, 4, 4,
  41.  3, 4, 4, 2, 3, 2, 2, 4, 4, 2, 2, 4, 3, 4, 3, 3, 4, 4, 3, 3,
  42.  3, 4, 3, 3, 4, 8, 1, 3, 1, 1, 3, 2, 3, 6, 2, 4, 4, 3, 2, 2,
  43.  2, 3, 4, 1, 2, 5, 2, 5, 5, 1, 4, 1, 2, 4, 3, 3, 3, 3, 2, 3,
  44.  2 };
  45.  
  46. unsigned char hyf_num[] = { 0,
  47.  4, 4, 1, 3, 5, 5, 3, 4, 5, 4, 5, 2, 3, 5, 3, 1, 2, 5, 5, 5,
  48.  5, 1, 2, 4, 3, 2, 4, 4, 3, 4, 4, 5, 4, 3, 4, 3, 5, 2, 5, 5,
  49.  5, 5, 5, 4, 1, 2, 4, 4, 4, 4, 4, 2, 5, 3, 3, 2, 4, 5, 5, 2,
  50.  4, 2, 2, 5, 4, 4, 3, 2, 2, 4, 1, 5, 4, 3, 4, 5, 3, 4, 1, 3,
  51.  2, 1, 3, 1, 1, 5, 1, 4, 1, 4, 4, 2, 1, 1, 4, 2, 4, 2, 4, 5,
  52.  3, 1, 3, 4, 4, 3, 4, 2, 1, 4, 2, 4, 2, 1, 2, 2, 4, 1, 3, 5,
  53.  3, 4, 5, 5, 2, 5, 4, 3, 4, 2, 4, 2, 5, 5, 2, 4, 4, 4, 2, 1,
  54.  4, 1, 4, 2, 3, 5, 4, 5, 1, 2, 2, 3, 4, 5, 3, 3, 1, 3, 2, 1,
  55.  3, 1, 5, 4, 1, 5, 3, 5, 5, 3, 2, 2, 2, 5, 2, 5, 4, 2, 4, 3,
  56.  5 };
  57.  
  58. unsigned char hyf_next[] = { 0,
  59.  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 1, 0, 0, 9, 0, 5,
  60.  11, 0, 0, 23, 0, 0, 0, 10, 0, 10, 0, 19, 11, 0, 22, 4, 0, 17, 0, 1,
  61.  6, 10, 42, 12, 0, 3, 3, 17, 6, 1, 4, 7, 1, 25, 5, 12, 45, 1, 12, 59,
  62.  6, 5, 10, 8, 7, 22, 12, 6, 22, 1, 70, 0, 29, 12, 74, 10, 8, 19, 17, 10,
  63.  80, 1, 10, 12, 51, 7, 0, 4, 3, 5, 82, 84, 3, 10, 7, 23, 16, 1, 25, 9,
  64.  13, 12, 7, 0, 1, 4, 106, 0, 1, 23, 9, 8, 25, 4, 9, 4, 84, 10, 2, 2,
  65.  30, 103, 6, 4, 124, 9, 12, 10, 10, 1, 53, 8, 23, 133, 3, 3, 6, 26, 41, 23,
  66.  30, 2, 8, 1, 25, 0, 9, 5, 13, 16, 79, 17, 152, 148, 13, 7, 45, 3, 74, 56,
  67.  9, 8, 10, 13, 1, 11, 1, 25, 10, 13, 11, 13, 12, 4, 17, 4, 79, 94, 17, 1,
  68.  17 };
  69.  
  70. #define DEL 127
  71.  
  72. int hyphenate(word, room, hlevel)
  73. char *word;
  74. int room, hlevel;
  75. {
  76.     unsigned char *hc, *hyf;
  77.     char embflag = 0;
  78.     int i, j, z, l, v, ret;
  79.     int hn = strlen(word);
  80.  
  81.     if (room >= hn) return(hn);
  82.     if (hn < 5) return(hn);
  83.     if ((hc = (unsigned char *)calloc(hn + 3, 1)) == 0) return(hn);
  84.     if ((hyf = (unsigned char *)calloc(hn + 3, 1)) == 0) {
  85.         free(hc);
  86.         return(hn);
  87.     }
  88.  
  89.     hc[0] = hc[hn+1] = DEL; hc[hn+2] = 256;
  90.     for (j = 0; word[j]; j++)
  91.         hc[j+1] = (isalpha(word[j]))? tolower(word[j]) - 1 : DEL;
  92.  
  93.     for (j = 0; j <= hn - 2; j++) {
  94.         z = hc[j]; l = j;
  95.         while (hc[l] == trie_char[z]) {
  96.             if (v = trie_op[z]) {
  97.                 do {
  98.                     i = l - hyf_distance[v];
  99.                     if (hyf_num[v] > hyf[i]) hyf[i] = hyf_num[v];
  100.                     v = hyf_next[v];
  101.                 } while (v);
  102.             }
  103.             l++;  z = trie_link[z] + hc[l];
  104.         }
  105.     }
  106.  
  107.     hyf[1] = 0; hyf[hn-1] = 0; hyf[hn] = 0; hyf[hn-2] = 0;
  108.     for (j = 0; word[j]; j++) {
  109.         if (!isalpha(word[j])) {
  110.             hyf[j+1] = 0;
  111.             hyf[j+2] = 0;
  112.             hyf[j] = 0;
  113.             if (j > 0) hyf[j-1] = 0;
  114.             if (j > 1) hyf[j-2] = 0;
  115.             if (embflag == 1) embflag++;
  116.         }
  117.         /* hlevel 7 or greater prevents split when non-alpha
  118.          * is in the midst of alpha characters */
  119.         else if (hlevel >= 7) {
  120.             if (!embflag) embflag++;
  121.             else if (embflag == 2) return(hn);
  122.         }
  123.         /* hlevel 6 or greater prevents split after '-' */
  124.         if (hlevel <= 5 && word[j] == '-') hyf[j+1] = 1;
  125.     }
  126.  
  127.     ret = hn;
  128.     for (j = hn-3 ; j > 1; j--) {
  129.         z = (hc[j]+1 == '-')? j : j+1;
  130.         if ((hyf[j] % 2) && (z <= room)) {
  131.             ret = z;
  132.             break;
  133.         }
  134.     }
  135.     free(hc);
  136.     free(hyf);
  137.     return(ret);
  138. }
  139.