home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume39 / par131 / part03 / Par131 / reformat.c < prev    next >
C/C++ Source or Header  |  1993-09-11  |  15KB  |  526 lines
  1. /*********************/
  2. /* reformat.c        */
  3. /* for Par 1.31      */
  4. /* Copyright 1993 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 struct word {
  29.   const char *chrs;       /* Pointer to the characters in the word */
  30.                           /* (NOT terminated by '\0').             */
  31.   struct word *prev,      /* Pointer to previous word.             */
  32.               *next,      /* Pointer to next word.                 */
  33.                           /* Supposing this word were the first... */
  34.               *nextline;  /*   Pointer to first word in next line. */
  35.   int score,              /*   Value of the objective function.    */
  36.       length;             /* Length of this word.                  */
  37.   short flags;            /* Notable properties of this word.      */
  38. } word;
  39.  
  40. /* The following may be bitwise-OR'd together */
  41. /* to set the flags field of a word:          */
  42.  
  43. const short W_SHIFTED = 1,  /* This word should have an extra space before */
  44.                             /* it unless it's the first word in the line.  */
  45.             W_CURIOUS = 2,  /* This is a curious word (see par.doc).       */
  46.             W_CAPITAL = 4;  /* This is a capitalized word (see par.doc).   */
  47.  
  48. #define isshifted(w) ((w)->flags & 1)
  49. #define iscurious(w) (((w)->flags & 2) >> 1)
  50. #define iscapital(w) (((w)->flags & 4) >> 2)
  51.  
  52. const char * const impossibility =
  53.   "Impossibility #%d has occurred. Please report it.\n";
  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(word *head, word *tail, int L,
  130.                          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(word *head, word *tail,
  203.                        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,
  290.   int hang, int prefix, int suffix, int width, int cap, int fit,
  291.   int guess, 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.  
  308. /* Allocate space for pointers to the suffixes: */
  309.  
  310.   if (numin) {
  311.     suffixes = malloc(numin * sizeof (const char *));
  312.     if (!suffixes) {
  313.       strcpy(errmsg,outofmem);
  314.       goto rfcleanup;
  315.     }
  316.   }
  317.  
  318. /* Set the pointers to the suffixes, and create the words: */
  319.  
  320.   affix = prefix + suffix;
  321.   L = width - prefix - suffix;
  322.  
  323.   for (line = inlines, suf = suffixes;  line < endline;  ++line, ++suf) {
  324.     for (end = *line;  *end;  ++end);
  325.     if (end - *line < affix) {
  326.       sprintf(errmsg,
  327.               "Line %d shorter than <prefix> + <suffix> = %d + %d = %d\n",
  328.               line - inlines + 1, prefix, suffix, affix);
  329.       goto rfcleanup;
  330.     }
  331.     end -= suffix;
  332.     *suf = end;
  333.     p1 = *line + prefix;
  334.     for (;;) {
  335.       while (p1 < end && *p1 == ' ') ++p1;
  336.       if (p1 == end) break;
  337.       p2 = p1;
  338.       if (onfirstword) {
  339.         p1 = *line + prefix;
  340.         onfirstword = 0;
  341.       }
  342.       while (p2 < end && *p2 != ' ') ++p2;
  343.       w1 = malloc(sizeof (word));
  344.       if (!w1) {
  345.         strcpy(errmsg,outofmem);
  346.         goto rfcleanup;
  347.       }
  348.       w1->next = NULL;
  349.       w1->prev = tail;
  350.       tail = tail->next = w1;
  351.       w1->chrs = p1;
  352.       w1->length = p2 - p1;
  353.       w1->flags = 0;
  354.       p1 = p2;
  355.     }
  356.   }
  357.  
  358. /* If guess is 1, set flag values and merge words: */
  359.  
  360.   if (guess) {
  361.     for (w1 = head, w2 = head->next;  w2;  w1 = w2, w2 = w2->next) {
  362.       if (checkcurious(w2)) w2->flags |= W_CURIOUS;
  363.       if (cap || checkcapital(w2)) {
  364.         w2->flags |= W_CAPITAL;
  365.         if (iscurious(w1))
  366.           if (w1->chrs[w1->length] && w1->chrs + w1->length + 1 == w2->chrs) {
  367.             w2->length += w1->length + 1;
  368.             w2->chrs = w1->chrs;
  369.             w2->prev = w1->prev;
  370.             w2->prev->next = w2;
  371.             if (iscapital(w1)) w2->flags |= W_CAPITAL;
  372.             else w2->flags &= ~W_CAPITAL;
  373.             if (isshifted(w1)) w2->flags |= W_SHIFTED;
  374.             else w2->flags &= ~W_SHIFTED;
  375.             free(w1);
  376.           }
  377.           else
  378.             w2->flags |= W_SHIFTED;
  379.       }
  380.     }
  381.     tail = w1;
  382.   }
  383.  
  384. /* Check for too-long words: */
  385.  
  386.   if (Report)
  387.     for (w2 = head->next;  w2;  w2 = w2->next) {
  388.       if (w2->length > L) {
  389.         linelen = w2->length;
  390.         if (linelen > errmsg_size - 17)
  391.           linelen = errmsg_size - 17;
  392.         sprintf(errmsg, "Word too long: %.*s\n", linelen, w2->chrs);
  393.         goto rfcleanup;
  394.       }
  395.     }
  396.   else
  397.     for (w2 = head->next;  w2;  w2 = w2->next)
  398.       while (w2->length > L) {
  399.         w1 = malloc(sizeof (word));
  400.         if (!w1) {
  401.           strcpy(errmsg,outofmem);
  402.           goto rfcleanup;
  403.         }
  404.         w1->next = w2;
  405.         w1->prev = w2->prev;
  406.         w1->prev->next = w1;
  407.         w2->prev = w1;
  408.         w1->chrs = w2->chrs;
  409.         w2->chrs += L;
  410.         w1->length = L;
  411.         w2->length -= L;
  412.         w1->flags = 0;
  413.         if (iscapital(w2)) {
  414.           w1->flags |= W_CAPITAL;
  415.           w2->flags &= ~W_CAPITAL;
  416.         }
  417.         if (isshifted(w2)) {
  418.           w1->flags |= W_SHIFTED;
  419.           w2->flags &= ~W_SHIFTED;
  420.         }
  421.       }
  422.  
  423. /* Choose line breaks according to policy in "par.doc": */
  424.  
  425.   if (just) justbreaks(head,tail,L,last,errmsg);
  426.   else normalbreaks(head,tail,L,fit,last,errmsg);
  427.   if (*errmsg) goto rfcleanup;
  428.  
  429. /* Change L to the length of the longest line if required: */
  430.  
  431.   if (!just && touch) {
  432.     L = 0;
  433.     w1 = head->next;
  434.     while (w1) {
  435.       for (linelen = w1->length, w2 = w1->next;
  436.            w2 != w1->nextline;
  437.            linelen += 1 + isshifted(w2) + w2->length, w2 = w2->next);
  438.       if (linelen > L) L = linelen;
  439.       w1 = w2;
  440.     }
  441.   }
  442.  
  443. /* Construct the lines: */
  444.  
  445.   pbuf = newbuffer(sizeof (char *), errmsg);
  446.   if (*errmsg) goto rfcleanup;
  447.  
  448.   numout = 0;
  449.   w1 = head->next;
  450.   while (numout < hang || w1) {
  451.     if (w1)
  452.       for (w2 = w1->next, numgaps = 0, extra = L - w1->length;
  453.            w2 != w1->nextline;
  454.            ++numgaps, extra -= 1 + isshifted(w2) + w2->length, w2 = w2->next);
  455.     linelen = suffix  ||  just && (w2 || last) ?
  456.                 L + affix :
  457.                 w1 ? prefix + L - extra : prefix;
  458.     q1 = malloc((linelen + 1) * sizeof (char));
  459.     if (!q1) {
  460.       strcpy(errmsg,outofmem);
  461.       goto rfcleanup;
  462.     }
  463.     additem(pbuf, &q1, errmsg);
  464.     if (*errmsg) goto rfcleanup;
  465.     ++numout;
  466.     q2 = q1 + prefix;
  467.     if      (numout <= numin) memcpy(q1, inlines[numout - 1], prefix);
  468.     else if (numin > hang)    memcpy(q1, inlines[numin - 1], prefix);
  469.     else                      while (q1 < q2) *q1++ = ' ';
  470.     q1 = q2;
  471.     if (w1) {
  472.       phase = numgaps / 2;
  473.       for (w2 = w1;  ;  ) {
  474.         memcpy(q1, w2->chrs, w2->length);
  475.         q1 += w2->length;
  476.         w2 = w2->next;
  477.         if (w2 == w1->nextline) break;
  478.         *q1++ = ' ';
  479.         if (just && (w1->nextline || last)) {
  480.           phase += extra;
  481.           while (phase >= numgaps) {
  482.             *q1++ = ' ';
  483.             phase -= numgaps;
  484.           }
  485.         }
  486.         if (isshifted(w2)) *q1++ = ' ';
  487.       }
  488.     }
  489.     q2 += linelen - affix;
  490.     while (q1 < q2) *q1++ = ' ';
  491.     q2 = q1 + suffix;
  492.     if      (numout <= numin) memcpy(q1, suffixes[numout - 1], suffix);
  493.     else if (numin)           memcpy(q1, suffixes[numin - 1], suffix);
  494.     else                      while(q1 < q2) *q1++ = ' ';
  495.     *q2 = '\0';
  496.     if (w1) w1 = w1->nextline;
  497.   }
  498.  
  499.   q1 = NULL;
  500.   additem(pbuf, &q1, errmsg);
  501.   if (*errmsg) goto rfcleanup;
  502.  
  503.   outlines = copyitems(pbuf,errmsg);
  504.  
  505. rfcleanup:
  506.  
  507.   if (suffixes) free(suffixes);
  508.  
  509.   while (tail != head) {
  510.     tail = tail->prev;
  511.     free(tail->next);
  512.   }
  513.  
  514.   if (pbuf) {
  515.     if (!outlines)
  516.       for (;;) {
  517.         outlines = nextitem(pbuf);
  518.         if (!outlines) break;
  519.         free(*outlines);
  520.       }
  521.     freebuffer(pbuf);
  522.   }
  523.  
  524.   return outlines;
  525. }
  526.