From: simon <simon@cda61777-01e9-0310-a592-d414129be87e>
Date: Tue, 13 Apr 2004 19:41:36 +0000 (+0000)
Subject: Fine-tuned the page breaking algorithm by adding penalties and
X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/halibut/commitdiff_plain/39a0cfb92d9abe44deab3ceb816aa9571054981c

Fine-tuned the page breaking algorithm by adding penalties and
bonuses for breaking in particular places. (For example, it's
especially bad to break just after a heading, and especially good to
break just before one.)


git-svn-id: svn://svn.tartarus.org/sgt/halibut@4064 cda61777-01e9-0310-a592-d414129be87e
---

diff --git a/bk_paper.c b/bk_paper.c
index 2ee6a2c..417edf8 100644
--- a/bk_paper.c
+++ b/bk_paper.c
@@ -12,16 +12,6 @@
 /*
  * To be done:
  * 
- *  - tune the page breaking algorithm to impose penalties on
- *    various things
- *     * breaking in the middle of a code paragraph
- *     * breaking one line from the start or end of a paragraph
- *     * breaking immediately after a heading of any kind (or
- * 	 indeed within one)
- *     * we may also need to impose a limit on the amount by which
- * 	 we can _stretch_ a page; after a certain point we may
- * 	 prefer just to unapologetically leave space at the bottom.
- * 
  *  - implement some simple graphics
  *     * I had an underline below chapter headings in the original
  * 	 Perl version, and I thought it looked rather nice
@@ -164,6 +154,10 @@ void *paper_pre_backend(paragraph *sourceform, keywordlist *keywords,
 	    pdata = mknew(para_data);
 	    code_paragraph(pdata, cr, co, cb, 12, indent, p->words);
 	    p->private_data = pdata;
+	    if (pdata->first != pdata->last) {
+		pdata->first->penalty_after += 100000;
+		pdata->last->penalty_before += 100000;
+	    }
 	    break;
 
 	    /*
@@ -362,6 +356,51 @@ void *paper_pre_backend(paragraph *sourceform, keywordlist *keywords,
 	    pdata->first->aux_text_2 = aux2;
 	    pdata->first->aux_left_indent = aux_indent;
 
+	    /*
+	     * Line breaking penalties.
+	     */
+	    switch (p->type) {
+	      case para_Chapter:
+	      case para_Appendix:
+	      case para_Heading:
+	      case para_Subsect:
+	      case para_UnnumberedChapter:
+		/*
+		 * Fixed and large penalty for breaking straight
+		 * after a heading; corresponding bonus for
+		 * breaking straight before.
+		 */
+		pdata->first->penalty_before = -500000;
+		pdata->last->penalty_after = 500000;
+		for (ldata = pdata->first; ldata; ldata = ldata->next)
+		    ldata->penalty_after = 500000;
+		break;
+
+	      case para_DescribedThing:
+		/*
+		 * This is treated a bit like a small heading:
+		 * there's a penalty for breaking after it (i.e.
+		 * between it and its description), and a bonus for
+		 * breaking before it (actually _between_ list
+		 * items).
+		 */
+		pdata->first->penalty_before = -200000;
+		pdata->last->penalty_after = 200000;
+		break;
+
+	      default:
+		/*
+		 * Most paragraph types: widow/orphan control by
+		 * discouraging breaking one line from the end of
+		 * any paragraph.
+		 */
+		if (pdata->first != pdata->last) {
+		    pdata->first->penalty_after = 100000;
+		    pdata->last->penalty_before = 100000;
+		}
+		break;
+	    }
+
 	    break;
 	}
 
@@ -729,6 +768,7 @@ static void wrap_paragraph(para_data *pdata, word *words,
 	ldata->aux_text = NULL;
 	ldata->aux_text_2 = NULL;
 	ldata->aux_left_indent = 0;
+	ldata->penalty_before = ldata->penalty_after = 0;
     }
 
 }
@@ -793,16 +833,13 @@ static page_data *page_breaks(line_data *first, line_data *last,
 	    } else
 		cost = 0;
 
-	    /*
-	     * FIXME: here I should introduce penalties for
-	     * breaking in mid-paragraph, particularly very close
-	     * to one end of a paragraph and particularly in code
-	     * paragraphs.
-	     */
+	    if (m->next && !m->next->page_break) {
+		cost += m->penalty_after;
+		cost += m->next->penalty_before;
+	    }
 
 	    if (m->next && !m->next->page_break)
 		cost += m->next->bestcost;
-
 	    if (l->bestcost == -1 || l->bestcost > cost) {
 		/*
 		 * This is the best option yet for this starting
@@ -1248,6 +1285,7 @@ static void code_paragraph(para_data *pdata,
 	ldata->aux_text = NULL;
 	ldata->aux_text_2 = NULL;
 	ldata->aux_left_indent = 0;
-
+	/* General opprobrium for breaking in a code paragraph. */
+	ldata->penalty_before = ldata->penalty_after = 50000;
     }
 }
diff --git a/paper.h b/paper.h
index c537dd2..8478e25 100644
--- a/paper.h
+++ b/paper.h
@@ -182,6 +182,10 @@ struct line_data_Tag {
     int space_after;
     int line_height;
     /*
+     * Penalties for page breaking before or after this line.
+     */
+    int penalty_before, penalty_after;
+    /*
      * These fields are used in the page breaking algorithm.
      */
     int bestcost;