home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / par150o2.zip / reformat.c < prev    next >
C/C++ Source or Header  |  1996-01-21  |  15KB  |  540 lines
  1. /*********************/
  2. /* reformat.c        */
  3. /* for Par 1.50      */
  4. /* Copyright 1996 by */
  5. /* Adam M. Costello  */
  6. /*********************/
  7.  
  8. /* This is ANSI C code. */
  9.  
  10.  
  11. #include "reformat.h"  /* Makes sure we're consistent with the  */
  12.                        /* prototype.  Also includes "errmsg.h". */
  13. #include "buffer.h"    /* Also includes <stddef.h>.             */
  14.  
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include <ctype.h>
  18. #include <string.h>
  19.  
  20. #undef NULL
  21. #define NULL ((void *) 0)
  22.  
  23. #ifdef DONTFREE
  24. #define free(ptr)
  25. #endif
  26.  
  27.  
  28. typedef unsigned char wflag_t;
  29.  
  30. typedef struct word {
  31.   const char *chrs;       /* Pointer to the characters in the word */
  32.                           /* (NOT terminated by '\0').             */
  33.   struct word *prev,      /* Pointer to previous word.             */
  34.               *next,      /* Pointer to next word.                 */
  35.                           /* Supposing this word were the first... */
  36.               *nextline;  /*   Pointer to first word in next line. */
  37.   int score,              /*   Value of the objective function.    */
  38.       length;             /* Length of this word.                  */
  39.   wflag_t flags;          /* Notable properties of this word.      */
  40. } word;
  41.  
  42. /* The following may be bitwise-OR'd together */
  43. /* to set the flags field of a word:          */
  44.  
  45. static const wflag_t
  46.   W_SHIFTED = 1,  /* This word should have an extra space before */
  47.                   /* it unless it's the first word in the line.  */
  48.   W_CURIOUS = 2,  /* This is a curious word (see par.doc).       */
  49.   W_CAPITAL = 4;  /* This is a capitalized word (see par.doc).   */
  50.  
  51. #define isshifted(w) ( (w)->flags & 1)
  52. #define iscurious(w) (((w)->flags & 2) != 0)
  53. #define iscapital(w) (((w)->flags & 4) != 0)
  54.  
  55.  
  56. static int checkcapital(word *w)
  57. /* Returns 1 if *w is capitalized according to the definition */
  58. /* in par.doc (assuming <cap> is 0), or 0 if not.             */
  59. {
  60.   const char *p, *end;
  61.  
  62.   for (p = w->chrs, end = p + w->length;  p < end && !isalnum(*p);  ++p);
  63.   return p < end && !islower(*p);
  64. }
  65.  
  66.  
  67. static int checkcurious(word *w)
  68. /* Returns 1 if *w is curious according to */
  69. /* the definition in par.doc, or 0 if not. */
  70. {
  71.   const char *start, *p;
  72.   char ch;
  73.  
  74.   for (start = w->chrs, p = start + w->length;  p > start;  --p) {
  75.     ch = p[-1];
  76.     if (isalnum(ch)) return 0;
  77.     if (ch == '.' || ch == '?' || ch == '!' || ch == ':') break;
  78.   }
  79.  
  80.   if (p <= start + 1) return 0;
  81.  
  82.   --p;
  83.   do if (isalnum(*--p)) return 1;
  84.   while (p > start);
  85.  
  86.   return 0;
  87. }
  88.  
  89.  
  90. static int simplebreaks(word *head, word *tail, int L, int last)
  91.  
  92. /* Chooses line breaks in a list of words which maximize the length of the   */
  93. /* shortest line.  L is the maximum line length.  The last line counts as a  */
  94. /* line only if last is non-zero. _head must point to a dummy word, and tail */
  95. /* must point to the last word, whose next field must be NULL.  Returns the  */
  96. /* length of the shortest line on success, -1 if there is a word of length   */
  97. /* greater than L, or L if there are no lines.                               */
  98. {
  99.   word *w1, *w2;
  100.   int linelen, score;
  101.  
  102.   if (!head->next) return L;
  103.  
  104.   for (w1 = tail, linelen = w1->length;
  105.        w1 != head && linelen <= L;
  106.        linelen += isshifted(w1), w1 = w1->prev, linelen += 1 + w1->length) {
  107.     w1->score = last ? linelen : L;
  108.     w1->nextline = NULL;
  109.   }
  110.  
  111.   for ( ;  w1 != head;  w1 = w1->prev) {
  112.     w1->score = -1;
  113.     for (linelen = w1->length,  w2 = w1->next;
  114.          linelen <= L;
  115.          linelen += 1 + isshifted(w2) + w2->length,  w2 = w2->next) {
  116.       score = w2->score;
  117.       if (linelen < score) score = linelen;
  118.       if (score >= w1->score) {
  119.         w1->nextline = w2;
  120.         w1->score = score;
  121.       }
  122.     }
  123.   }
  124.  
  125.   return head->next->score;
  126. }
  127.  
  128.  
  129. static void normalbreaks(
  130.   word *head, word *tail, int L, int fit, int last, errmsg_t errmsg
  131. )
  132. /* Chooses line breaks in a list of words according to the policy   */
  133. /* in "par.doc" for <just> = 0 (L is <L>, fit is <fit>, and last is */
  134. /* <last>).  head must point to a dummy word, and tail must point   */
  135. /* to the last word, whose next field must be NULL.                 */
  136. {
  137.   word *w1, *w2;
  138.   int tryL, shortest, score, target, linelen, extra, minlen;
  139.  
  140.   *errmsg = '\0';
  141.   if (!head->next) return;
  142.  
  143.   target = L;
  144.  
  145. /* Determine minimum possible difference between  */
  146. /* the lengths of the shortest and longest lines: */
  147.  
  148.   if (fit) {
  149.     score = L + 1;
  150.     for (tryL = L;  ;  --tryL) {
  151.       shortest = simplebreaks(head,tail,tryL,last);
  152.       if (shortest < 0) break;
  153.       if (tryL - shortest < score) {
  154.         target = tryL;
  155.         score = target - shortest;
  156.       }
  157.     }
  158.   }
  159.  
  160. /* Determine maximum possible length of the shortest line: */
  161.  
  162.   shortest = simplebreaks(head,tail,target,last);
  163.   if (shortest < 0) {
  164.     sprintf(errmsg,impossibility,1);
  165.     return;
  166.   }
  167.  
  168. /* Minimize the sum of the squares of the differences */
  169. /* between target and the lengths of the lines:       */
  170.  
  171.   w1 = tail;
  172.   do {
  173.     w1->score = -1;
  174.     for (linelen = w1->length,  w2 = w1->next;
  175.          linelen <= target;
  176.          linelen += 1 + isshifted(w2) + w2->length,  w2 = w2->next) {
  177.       extra = target - linelen;
  178.       minlen = shortest;
  179.       if (w2)
  180.         score = w2->score;
  181.       else {
  182.         score = 0;
  183.         if (!last) extra = minlen = 0;
  184.       }
  185.       if (linelen >= minlen  &&  score >= 0) {
  186.         score += extra * extra;
  187.         if (w1->score < 0  ||  score <= w1->score) {
  188.           w1->nextline = w2;
  189.           w1->score = score;
  190.         }
  191.       }
  192.       if (!w2) break;
  193.     }
  194.     w1 = w1->prev;
  195.   } while (w1 != head);
  196.  
  197.   if (head->next->score < 0)
  198.     sprintf(errmsg,impossibility,2);
  199. }
  200.  
  201.  
  202. static void justbreaks(
  203.   word *head, word *tail, int L, int last, errmsg_t errmsg
  204. )
  205. /* Chooses line breaks in a list of words according to the  */
  206. /* policy in "par.doc" for <just> = 1 (L is <L> and last is */
  207. /* <last>).  head must point to a dummy word, and tail must */
  208. /* point to the last word, whose next field must be NULL.   */
  209. {
  210.   word *w1, *w2;
  211.   int numgaps, extra, score, gap, maxgap, numbiggaps;
  212.  
  213.   *errmsg = '\0';
  214.   if (!head->next) return;
  215.  
  216. /* Determine the minimum possible largest inter-word gap: */
  217.  
  218.   w1 = tail;
  219.   do {
  220.     w1->score = L;
  221.     for (numgaps = 0, extra = L - w1->length, w2 = w1->next;
  222.          extra >= 0;
  223.          ++numgaps, extra -= 1 + isshifted(w2) + w2->length, w2 = w2->next) {
  224.       gap = numgaps ? (extra + numgaps - 1) / numgaps : L;
  225.       if (w2)
  226.         score = w2->score;
  227.       else {
  228.         score = 0;
  229.         if (!last) gap = 0;
  230.       }
  231.       if (gap > score) score = gap;
  232.       if (score < w1->score) {
  233.         w1->nextline = w2;
  234.         w1->score = score;
  235.       }
  236.       if (!w2) break;
  237.     }
  238.     w1 = w1->prev;
  239.   } while (w1 != head);
  240.  
  241.   maxgap = head->next->score;
  242.   if (maxgap >= L) {
  243.     strcpy(errmsg, "Cannot justify.\n");
  244.     return;
  245.   }
  246.  
  247. /* Minimize the sum of the squares of the numbers   */
  248. /* of extra spaces required in each inter-word gap: */
  249.  
  250.   w1 = tail;
  251.   do {
  252.     w1->score = -1;
  253.     for (numgaps = 0, extra = L - w1->length, w2 = w1->next;
  254.          extra >= 0;
  255.          ++numgaps, extra -= 1 + isshifted(w2) + w2->length, w2 = w2->next) {
  256.       gap = numgaps ? (extra + numgaps - 1) / numgaps : L;
  257.       if (w2)
  258.         score = w2->score;
  259.       else {
  260.         if (!last) {
  261.           w1->nextline = NULL;
  262.           w1->score = 0;
  263.           break;
  264.         }
  265.         score = 0;
  266.       }
  267.       if (gap <= maxgap && score >= 0) {
  268.         numbiggaps = extra % numgaps;
  269.         score += (extra / numgaps) * (extra + numbiggaps) + numbiggaps;
  270.         /* The above may not look like the sum of the squares of the numbers */
  271.         /* of extra spaces required in each inter-word gap, but trust me, it */
  272.         /* is.  It's easier to prove graphically than algebraicly.           */
  273.         if (w1->score < 0  ||  score <= w1->score) {
  274.           w1->nextline = w2;
  275.           w1->score = score;
  276.         }
  277.       }
  278.       if (!w2) break;
  279.     }
  280.     w1 = w1->prev;
  281.   } while (w1 != head);
  282.  
  283.   if (head->next->score < 0)
  284.     sprintf(errmsg,impossibility,3);
  285. }
  286.  
  287.  
  288. char **reformat(
  289.   const char * const *inlines, const char * const *endline, int afp, int fs,
  290.   int hang, int prefix, int suffix, int width, int cap, int fit, int guess,
  291.   int just, int last, int Report, int touch, errmsg_t errmsg
  292. )
  293. {
  294.   int numin, affix, L, onfirstword = 1, linelen, numout, numgaps, extra, phase;
  295.   const char * const *line, **suffixes = NULL, **suf, *end, *p1, *p2;
  296.   char *q1, *q2, **outlines = NULL;
  297.   word dummy, *head, *tail, *w1, *w2;
  298.   buffer *pbuf = NULL;
  299.  
  300. /* Initialization: */
  301.  
  302.   *errmsg = '\0';
  303.   dummy.next = dummy.prev = NULL;
  304.   dummy.flags = 0;
  305.   head = tail = &dummy;
  306.   numin = endline - inlines;
  307.   if (numin <= 0) {
  308.     sprintf(errmsg,impossibility,4);
  309.     goto rfcleanup;
  310.   }
  311.  
  312. /* Allocate space for pointers to the suffixes: */
  313.  
  314.   suffixes = malloc(numin * sizeof (const char *));
  315.   if (!suffixes) {
  316.     strcpy(errmsg,outofmem);
  317.     goto rfcleanup;
  318.   }
  319.  
  320. /* Set the pointers to the suffixes, and create the words: */
  321.  
  322.   affix = prefix + suffix;
  323.   L = width - prefix - suffix;
  324.  
  325.   line = inlines, suf = suffixes;
  326.   do {
  327.     for (end = *line;  *end;  ++end);
  328.     if (end - *line < affix) {
  329.       sprintf(errmsg,
  330.               "Line %d shorter than <prefix> + <suffix> = %d + %d = %d\n",
  331.               line - inlines + 1, prefix, suffix, affix);
  332.       goto rfcleanup;
  333.     }
  334.     end -= suffix;
  335.     *suf = end;
  336.     p1 = *line + prefix;
  337.     for (;;) {
  338.       while (p1 < end && *p1 == ' ') ++p1;
  339.       if (p1 == end) break;
  340.       p2 = p1;
  341.       if (onfirstword) {
  342.         p1 = *line + prefix;
  343.         onfirstword = 0;
  344.       }
  345.       while (p2 < end && *p2 != ' ') ++p2;
  346.       w1 = malloc(sizeof (word));
  347.       if (!w1) {
  348.         strcpy(errmsg,outofmem);
  349.         goto rfcleanup;
  350.       }
  351.       w1->next = NULL;
  352.       w1->prev = tail;
  353.       tail = tail->next = w1;
  354.       w1->chrs = p1;
  355.       w1->length = p2 - p1;
  356.       w1->flags = 0;
  357.       p1 = p2;
  358.     }
  359.     ++line, ++suf;
  360.   } while (line < endline);
  361.  
  362. /* If guess is 1, set flag values and merge words: */
  363.  
  364.   if (guess) {
  365.     for (w1 = head, w2 = head->next;  w2;  w1 = w2, w2 = w2->next) {
  366.       if (checkcurious(w2)) w2->flags |= W_CURIOUS;
  367.       if (cap || checkcapital(w2)) {
  368.         w2->flags |= W_CAPITAL;
  369.         if (iscurious(w1))
  370.           if (w1->chrs[w1->length] && w1->chrs + w1->length + 1 == w2->chrs) {
  371.             w2->length += w1->length + 1;
  372.             w2->chrs = w1->chrs;
  373.             w2->prev = w1->prev;
  374.             w2->prev->next = w2;
  375.             if (iscapital(w1)) w2->flags |= W_CAPITAL;
  376.             else w2->flags &= ~W_CAPITAL;
  377.             if (isshifted(w1)) w2->flags |= W_SHIFTED;
  378.             else w2->flags &= ~W_SHIFTED;
  379.             free(w1);
  380.           }
  381.           else
  382.             w2->flags |= W_SHIFTED;
  383.       }
  384.     }
  385.     tail = w1;
  386.   }
  387.  
  388. /* Check for too-long words: */
  389.  
  390.   if (Report)
  391.     for (w2 = head->next;  w2;  w2 = w2->next) {
  392.       if (w2->length > L) {
  393.         linelen = w2->length;
  394.         if (linelen > errmsg_size - 17)
  395.           linelen = errmsg_size - 17;
  396.         sprintf(errmsg, "Word too long: %.*s\n", linelen, w2->chrs);
  397.         goto rfcleanup;
  398.       }
  399.     }
  400.   else
  401.     for (w2 = head->next;  w2;  w2 = w2->next)
  402.       while (w2->length > L) {
  403.         w1 = malloc(sizeof (word));
  404.         if (!w1) {
  405.           strcpy(errmsg,outofmem);
  406.           goto rfcleanup;
  407.         }
  408.         w1->next = w2;
  409.         w1->prev = w2->prev;
  410.         w1->prev->next = w1;
  411.         w2->prev = w1;
  412.         w1->chrs = w2->chrs;
  413.         w2->chrs += L;
  414.         w1->length = L;
  415.         w2->length -= L;
  416.         w1->flags = 0;
  417.         if (iscapital(w2)) {
  418.           w1->flags |= W_CAPITAL;
  419.           w2->flags &= ~W_CAPITAL;
  420.         }
  421.         if (isshifted(w2)) {
  422.           w1->flags |= W_SHIFTED;
  423.           w2->flags &= ~W_SHIFTED;
  424.         }
  425.       }
  426.  
  427. /* Choose line breaks according to policy in "par.doc": */
  428.  
  429.   if (just) justbreaks(head,tail,L,last,errmsg);
  430.   else normalbreaks(head,tail,L,fit,last,errmsg);
  431.   if (*errmsg) goto rfcleanup;
  432.  
  433. /* Change L to the length of the longest line if required: */
  434.  
  435.   if (!just && touch) {
  436.     L = 0;
  437.     w1 = head->next;
  438.     while (w1) {
  439.       for (linelen = w1->length, w2 = w1->next;
  440.            w2 != w1->nextline;
  441.            linelen += 1 + isshifted(w2) + w2->length, w2 = w2->next);
  442.       if (linelen > L) L = linelen;
  443.       w1 = w2;
  444.     }
  445.   }
  446.  
  447. /* Construct the lines: */
  448.  
  449.   pbuf = newbuffer(sizeof (char *), errmsg);
  450.   if (*errmsg) goto rfcleanup;
  451.  
  452.   numout = 0;
  453.   w1 = head->next;
  454.   while (numout < hang || w1) {
  455.     if (w1)
  456.       for (w2 = w1->next, numgaps = 0, extra = L - w1->length;
  457.            w2 != w1->nextline;
  458.            ++numgaps, extra -= 1 + isshifted(w2) + w2->length, w2 = w2->next);
  459.     linelen = suffix  ||  just && (w2 || last) ?
  460.                 L + affix :
  461.                 w1 ? prefix + L - extra : prefix;
  462.     q1 = malloc((linelen + 1) * sizeof (char));
  463.     if (!q1) {
  464.       strcpy(errmsg,outofmem);
  465.       goto rfcleanup;
  466.     }
  467.     additem(pbuf, &q1, errmsg);
  468.     if (*errmsg) goto rfcleanup;
  469.     ++numout;
  470.     q2 = q1 + prefix;
  471.     if      (numout <= numin) memcpy(q1, inlines[numout - 1], prefix);
  472.     else if (numin  >  hang ) memcpy(q1, endline[-1],         prefix);
  473.     else {
  474.       if (afp > prefix) afp = prefix;
  475.       memcpy(q1, endline[-1], afp);
  476.       q1 += afp;
  477.       while (q1 < q2) *q1++ = ' ';
  478.     }
  479.     q1 = q2;
  480.     if (w1) {
  481.       phase = numgaps / 2;
  482.       for (w2 = w1;  ;  ) {
  483.         memcpy(q1, w2->chrs, w2->length);
  484.         q1 += w2->length;
  485.         w2 = w2->next;
  486.         if (w2 == w1->nextline) break;
  487.         *q1++ = ' ';
  488.         if (just && (w1->nextline || last)) {
  489.           phase += extra;
  490.           while (phase >= numgaps) {
  491.             *q1++ = ' ';
  492.             phase -= numgaps;
  493.           }
  494.         }
  495.         if (isshifted(w2)) *q1++ = ' ';
  496.       }
  497.     }
  498.     q2 += linelen - affix;
  499.     while (q1 < q2) *q1++ = ' ';
  500.     q2 = q1 + suffix;
  501.     if      (numout <= numin) memcpy(q1, suffixes[numout - 1], suffix);
  502.     else if (numin  >  hang ) memcpy(q1, suffixes[numin  - 1], suffix);
  503.     else {
  504.       if (fs > suffix) fs = suffix;
  505.       memcpy(q1, suffixes[numin - 1], fs);
  506.       q1 += fs;
  507.       while(q1 < q2) *q1++ = ' ';
  508.     }
  509.     *q2 = '\0';
  510.     if (w1) w1 = w1->nextline;
  511.   }
  512.  
  513.   q1 = NULL;
  514.   additem(pbuf, &q1, errmsg);
  515.   if (*errmsg) goto rfcleanup;
  516.  
  517.   outlines = copyitems(pbuf,errmsg);
  518.  
  519. rfcleanup:
  520.  
  521.   if (suffixes) free(suffixes);
  522.  
  523.   while (tail != head) {
  524.     tail = tail->prev;
  525.     free(tail->next);
  526.   }
  527.  
  528.   if (pbuf) {
  529.     if (!outlines)
  530.       for (;;) {
  531.         outlines = nextitem(pbuf);
  532.         if (!outlines) break;
  533.         free(*outlines);
  534.       }
  535.     freebuffer(pbuf);
  536.   }
  537.  
  538.   return outlines;
  539. }
  540.