]> git.donarmstrong.com Git - lilypond.git/blob - lily/page-breaking.cc
Rewrite the vertical layout of staves/systems.
[lilypond.git] / lily / page-breaking.cc
1 /*
2   page-breaking.cc -- implement a superclass and utility
3   functions shared by various page-breaking algorithms
4
5   source file of the GNU LilyPond music typesetter
6
7   (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
8 */
9
10 /*
11   This is a utility class for page-breaking algorithms. There are some complex
12   parts of this class, some of which are useful to understand if you intend
13   to write a page breaking algorithm (ie. a subclass of Page_breaking). Most
14   of these complexities were introduced in order to break the problem of
15   page-breaking into simpler subproblems and to hide some of the bookkeeping
16   complexities of page breaking from the page breaking algorithms.
17
18   COMPRESSED LINES
19   There are several functions that actually distribute systems across pages
20   (for example, the space_systems_XXX and pack_systems_XXX functions). If
21   each of these functions had to handle \noPageBreak, it would be a mess.
22   Therefore, we handle \noPageBreak by "compressing" the list of systems
23   before doing any layout: we concatenate any two systems separated by a
24   \noPageBreak into a single system. The page-breaking functions can do their
25   magic without encountering a \noPageBreak; we then "uncompress" the systems
26   at the end. We almost always work with cached_line_details_, which are
27   "compressed."
28
29   CHUNKS
30   The basic operation of a page breaking algorithm is to repeatedly request
31   some systems from the line-breaker and place those systems on some pages.
32   With each repetition, the page breaking algorithm asks the line-breaker for
33   some systems that it thinks will help it achieve a better layout. The
34   Page_breaking class provides functionality to facilitate this in the case
35   that the page breaking algorithm only cares about the number of systems.
36
37   Even if a page breaking algorithm only cares number of systems, there may
38   be many ways to satisfy its request. For example, in a piece with 2 scores
39   and a request for 10 systems, we could return 5 systems from each score or
40   4 from the first and 6 from the second. Even within a score, we might
41   want to try several different line breaking configurations with a fixed
42   system count; if there is a forced \pageBreak, for example, we might wish
43   to tweak the number of systems on both sides of the \pageBreak independently.
44
45   The Page_breaking class takes care of finding these configurations. It
46   divides the piece into "chunks" and sets up the line-breaker in such a way
47   that the number of systems in each chunk can be modified independently.
48   Chunks never cross score boundaries; each title and markup is its own chunk.
49   When a page breaking algorithm requests a number of systems, the Page_breaker
50   stores an array of potential configurations, which the page breaking
51   algorithm can iterate over using current_configuration(vsize).
52
53   LINE_DIVISION
54   A Line_division is simply a way of storing the exact way in which the
55   total number of systems is distributed among chunks. Note that a
56   Line_division may not (in fact, usually will not) describe all of the chunks
57   in the entire book. Rather, it will describe the subset of chunks that lie
58   between some fixed starting and ending point. This subset of chunks changes
59   whenever a page breaking algorithm asks to consider a different pair of
60   starting and ending breakpoints. In particular, a Line_division should be
61   discarded after a call to set_current_breakpoints, since that Line_division
62   refers to a subset of chunks which might be different from the current
63   subset of chunks under consideration.
64 */
65
66 #include "page-breaking.hh"
67
68 #include "international.hh"
69 #include "item.hh"
70 #include "output-def.hh"
71 #include "page-layout-problem.hh"
72 #include "page-spacing.hh"
73 #include "paper-book.hh"
74 #include "paper-score.hh"
75 #include "paper-system.hh"
76 #include "system.hh"
77 #include "warn.hh"
78
79 /* for each forbidden page break, merge the systems around it into one
80    system. */
81 static vector<Line_details>
82 compress_lines (const vector<Line_details> &orig)
83 {
84   vector<Line_details> ret;
85
86   for (vsize i = 0; i < orig.size (); i++)
87     {
88       if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
89         {
90           Line_details const &old = ret.back ();
91           Line_details compressed = orig[i];
92           compressed.extent_[DOWN] = old.extent_[DOWN];
93           compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
94           compressed.space_ += old.space_;
95           compressed.inverse_hooke_ += old.inverse_hooke_;
96
97           compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
98           compressed.compressed_nontitle_lines_count_ =
99             old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
100
101           // compressed.title_ is true if and only if the first of its
102           // compressed lines was a title.
103           compressed.title_ = old.title_;
104           ret.back () = compressed;
105         }
106       else
107         {
108           ret.push_back (orig[i]);
109           ret.back ().force_ = 0;
110         }
111     }
112   return ret;
113 }
114
115 /* translate the number of systems-per-page into something meaningful for
116    the uncompressed lines.
117 */
118 static vector<vsize>
119 uncompress_solution (vector<vsize> const &systems_per_page,
120                      vector<Line_details> const &compressed)
121 {
122   vector<vsize> ret;
123   vsize start_sys = 0;
124
125   for (vsize i = 0; i < systems_per_page.size (); i++)
126     {
127       int compressed_count = 0;
128       for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
129         compressed_count += compressed[j].compressed_lines_count_ - 1;
130
131       ret.push_back (systems_per_page[i] + compressed_count);
132       start_sys += systems_per_page[i];
133     }
134   return ret;
135 }
136
137 /* for Page_breaking, the start index (when we are dealing with the stuff
138    between a pair of breakpoints) refers to the break_ index of the end of
139    the previous page. So the system index of the start of the current page
140    could either be the same as the end of the previous page or one more than
141    it. */
142
143 /* Turn a break index into the sys index that starts the next page */
144 vsize
145 Page_breaking::next_system (Break_position const &break_pos) const
146 {
147   vsize sys = break_pos.system_spec_index_;
148
149   if (sys == VPOS) /* beginning of the book */
150     return 0;
151   if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
152     return sys; /* the score overflows the previous page */
153   return sys + 1; /* this page starts with a new System_spec */
154 }
155
156 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
157 {
158   book_ = pb;
159   system_count_ = 0;
160   ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
161   ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
162   systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
163   max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
164   min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
165
166   if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
167     {
168       warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
169       min_systems_per_page_ = max_systems_per_page_ = 0;
170     }
171   if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
172     {
173       warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
174       min_systems_per_page_ = max_systems_per_page_ = 0;
175     }
176
177   create_system_list ();
178   find_chunks_and_breaks (is_break);
179 }
180
181 Page_breaking::~Page_breaking ()
182 {
183 }
184
185 bool
186 Page_breaking::ragged () const
187 {
188   return ragged_;
189 }
190
191 bool
192 Page_breaking::ragged_last () const
193 {
194   return ragged_last_;
195 }
196
197 int
198 Page_breaking::systems_per_page () const
199 {
200   return systems_per_page_;
201 }
202
203 int
204 Page_breaking::max_systems_per_page () const
205 {
206   return max_systems_per_page_;
207 }
208
209 int
210 Page_breaking::min_systems_per_page () const
211 {
212   return min_systems_per_page_;
213 }
214
215 vsize
216 Page_breaking::system_count () const
217 {
218   return system_count_;
219 }
220
221 bool
222 Page_breaking::too_many_lines (int line_count) const
223 {
224   return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
225 }
226
227 bool
228 Page_breaking::too_few_lines (int line_count) const
229 {
230   return line_count < min_systems_per_page ();
231 }
232
233 Real
234 Page_breaking::line_count_penalty (int line_count) const
235 {
236   if (too_many_lines (line_count))
237     return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
238   if (too_few_lines (line_count))
239     return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
240
241   return 0;
242 }
243
244 int
245 Page_breaking::line_count_status (int line_count) const
246 {
247   if (too_many_lines (line_count))
248     return SYSTEM_COUNT_TOO_MANY;
249   if (too_few_lines (line_count))
250     return SYSTEM_COUNT_TOO_FEW;
251
252   return SYSTEM_COUNT_OK;
253 }
254
255 /* translate indices into breaks_ into start-end parameters for the line breaker */
256 void
257 Page_breaking::line_breaker_args (vsize sys,
258                                   Break_position const &start,
259                                   Break_position const &end,
260                                   vsize *line_breaker_start,
261                                   vsize *line_breaker_end)
262 {
263   assert (system_specs_[sys].pscore_);
264   assert (next_system (start) <= sys && sys <= end.system_spec_index_);
265
266   if (start.system_spec_index_ == sys)
267     *line_breaker_start = start.score_break_;
268   else
269     *line_breaker_start = 0;
270
271   if (end.system_spec_index_ == sys)
272     *line_breaker_end = end.score_break_;
273   else
274     *line_breaker_end = VPOS;
275 }
276
277 void
278 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
279                                   Line_division const &div)
280 {
281   vector<Break_position> chunks = chunk_list (start_break, end_break);
282   bool ignore_div = false;
283   if (chunks.size () != div.size () + 1)
284     {
285       programming_error ("did not find a valid page breaking configuration");
286       ignore_div = true;
287     }
288
289   for (vsize i = 0; i + 1 < chunks.size (); i++)
290     {
291       vsize sys = next_system (chunks[i]);
292       if (system_specs_[sys].pscore_)
293         {
294           vsize start;
295           vsize end;
296           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
297
298           vector<Column_x_positions> pos = ignore_div
299             ? line_breaking_[sys].best_solution (start, end)
300             : line_breaking_[sys].solve (start, end, div[i]);
301           system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
302         }
303     }
304 }
305
306 SCM
307 Page_breaking::systems ()
308 {
309   SCM ret = SCM_EOL;
310   for (vsize sys = 0; sys < system_specs_.size (); sys++)
311     {
312       if (system_specs_[sys].pscore_)
313         {
314           system_specs_[sys].pscore_->root_system ()
315             ->do_break_substitution_and_fixup_refpoints ();
316           SCM lines = system_specs_[sys].pscore_->root_system ()
317             ->get_broken_system_grobs ();
318           ret = scm_cons (lines, ret);
319         }
320       else
321         {
322           Prob *pb = system_specs_[sys].prob_;
323           ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
324           pb->unprotect ();
325         }
326     }
327   return scm_append (scm_reverse (ret));
328 }
329
330 SCM
331 Page_breaking::make_page (int page_num, bool last) const
332 {
333   bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
334   SCM mod = scm_c_resolve_module ("scm page");
335   SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
336
337   make_page_scm = scm_variable_ref (make_page_scm);
338
339   return scm_apply_0 (make_page_scm,
340                       scm_list_n (book_->self_scm (),
341                                   ly_symbol2scm ("page-number"), scm_from_int (page_num),
342                                   ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
343                                   ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
344                                   SCM_UNDEFINED));
345 }
346
347 Real
348 Page_breaking::page_height (int page_num, bool last) const
349 {
350   SCM mod = scm_c_resolve_module ("scm page");
351   SCM page = make_page (page_num, last);
352   SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
353   calc_height = scm_variable_ref (calc_height);
354
355   SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
356   return scm_to_double (height);
357 }
358
359 SCM
360 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
361 {
362   Break_position const &pos = breaks_[breakpoint];
363
364   if (pos.system_spec_index_ == VPOS)
365     return SCM_EOL;
366   if (system_specs_[pos.system_spec_index_].pscore_)
367     return pos.col_->get_property (str);
368   return system_specs_[pos.system_spec_index_].prob_->get_property (str);
369 }
370
371 SCM
372 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
373 {
374   SCM dummy_page = make_page (page_num, last);
375   Page_layout_problem layout (book_, dummy_page, systems);
376   return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
377 }
378
379 SCM
380 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
381 {
382   // Create a stencil for each system.
383   SCM paper_systems = SCM_EOL;
384   for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
385     {
386       SCM paper_system = scm_car (s);
387       if (Grob *g = unsmob_grob (scm_car (s)))
388         {
389           System *sys = dynamic_cast<System*> (g);
390           paper_system = sys->get_paper_system ();
391         }
392
393       paper_systems = scm_cons (paper_system, paper_systems);
394     }
395
396   // Create the page and draw it.
397   SCM page = make_page (page_num, last);
398   SCM page_module = scm_c_resolve_module ("scm page");
399   SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
400   page_stencil = scm_variable_ref (page_stencil);
401
402   Prob *p = unsmob_prob (page);
403   p->set_property ("lines", paper_systems);
404   p->set_property ("configuration", configuration);
405   scm_apply_1 (page_stencil, page, SCM_EOL);
406
407   return page;
408 }
409
410 SCM
411 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
412 {
413   int first_page_number
414     = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
415   SCM ret = SCM_EOL;
416   SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
417   if (label_page_table == SCM_UNDEFINED)
418     label_page_table = SCM_EOL;
419
420   // Build a list of (systems . configuration) pairs. Note that we lay out
421   // the staves and find the configurations before drawing anything. Some
422   // grobs (like tuplet brackets) look at their neighbours while drawing
423   // themselves. If this happens before the neighbouring staves have
424   // been laid out, bad side-effects could happen (in particular,
425   // Align_interface::align_to_ideal_distances might be called).
426   SCM systems_and_configs = SCM_EOL;
427
428   for (vsize i = 0; i < lines_per_page.size (); i++)
429     {
430       int page_num = i + first_page_number;
431       bool bookpart_last_page = (i == lines_per_page.size () - 1);
432       bool rag = ragged () || (bookpart_last_page && ragged_last ());
433       SCM line_count = scm_from_int (lines_per_page[i]);
434       SCM lines = scm_list_head (systems, line_count);
435       SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
436
437       systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
438       systems = scm_list_tail (systems, line_count);
439     }
440
441   // Now it's safe to make the pages.
442   int page_num = first_page_number + lines_per_page.size () - 1;
443   for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
444     {
445       SCM lines = scm_caar (s);
446       SCM config = scm_cdar (s);
447       bool bookpart_last_page = (s == systems_and_configs);
448       SCM page = draw_page (lines, config, page_num, bookpart_last_page);
449
450       /* collect labels */
451       SCM page_num_scm = scm_from_int (page_num);
452       for (SCM l = lines ; scm_is_pair (l)  ; l = scm_cdr (l))
453         {
454           SCM labels = SCM_EOL;
455           if (Grob * line = unsmob_grob (scm_car (l)))
456             {
457               System *system = dynamic_cast<System*> (line);
458               labels = system->get_property ("labels");
459             }
460           else if (Prob *prob = unsmob_prob (scm_car (l)))
461             labels = prob->get_property ("labels");
462
463           for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
464             label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
465                                          label_page_table);
466         }
467
468       ret = scm_cons (page, ret);
469       --page_num;
470     }
471   book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
472   return ret;
473 }
474
475 /* The page-turn-page-breaker needs to have a line-breaker between any two
476    columns with non-NULL page-turn-permission.
477
478    The optimal-breaker needs to have a line-breaker between any two columns
479    with page-break-permission = 'force.
480
481    By using a grob predicate, we can accommodate both of these uses.
482 */
483 void
484 Page_breaking::create_system_list ()
485 {
486   SCM specs = book_->get_system_specs ();
487   for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
488     {
489       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
490         {
491           SCM system_count = ps->layout ()->c_variable ("system-count");
492
493           if (scm_is_number (system_count))
494             s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
495                                         scm_vector_to_list (ps->get_paper_systems ()),
496                                         scm_cdr (s)));
497           else
498             system_specs_.push_back (System_spec (ps));
499         }
500       else
501         {
502           Prob *pb = unsmob_prob (scm_car (s));
503           assert (pb);
504
505           pb->protect ();
506           system_specs_.push_back (System_spec (pb));
507         }
508     }
509 }
510
511 void
512 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
513 {
514   SCM force_sym = ly_symbol2scm ("force");
515
516   chunks_.push_back (Break_position ());
517   breaks_.push_back (Break_position ());
518
519   for (vsize i = 0; i < system_specs_.size (); i++)
520     {
521       if (system_specs_[i].pscore_)
522         {
523           vector<Grob*> cols
524             = system_specs_[i].pscore_->root_system ()->used_columns ();
525           vector<vsize> line_breaker_columns;
526           line_breaker_columns.push_back (0);
527
528           for (vsize j = 1; j < cols.size (); j++)
529             {
530               bool last = (j == cols.size () - 1);
531               bool break_point = is_break (cols[j]);
532               bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
533               Break_position cur_pos = Break_position (i,
534                                                        line_breaker_columns.size (),
535                                                        cols[j],
536                                                        last);
537
538               if (break_point || (i == system_specs_.size () - 1 && last))
539                 breaks_.push_back (cur_pos);
540               if (chunk_end || last)
541                 chunks_.push_back (cur_pos);
542
543               if ((break_point || chunk_end) && !last)
544                 line_breaker_columns.push_back (j);
545             }
546           line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
547         }
548       else
549         {
550           /* TODO: we want some way of applying Break_p to a prob? */
551           if (i == system_specs_.size () - 1)
552             breaks_.push_back (Break_position (i));
553
554           chunks_.push_back (Break_position (i));
555
556           /* FIXME: shouldn't we push a Null_breaker or similar dummy
557              class? --hwn */
558           line_breaking_.push_back (Constrained_breaking (NULL));
559         }
560     }
561 }
562
563 vector<Break_position>
564 Page_breaking::chunk_list (vsize start_index, vsize end_index)
565 {
566   Break_position start = breaks_[start_index];
567   Break_position end = breaks_[end_index];
568
569   vsize i = 0;
570   for (; i < chunks_.size () && chunks_[i] <= start; i++)
571     ;
572
573   vector<Break_position> ret;
574   ret.push_back (start);
575   for (; i < chunks_.size () && chunks_[i] < end; i++)
576     ret.push_back (chunks_[i]);
577   ret.push_back (end);
578   return ret;
579 }
580
581 vsize
582 Page_breaking::min_system_count (vsize start, vsize end)
583 {
584   vector<Break_position> chunks = chunk_list (start, end);
585   Line_division div = system_count_bounds (chunks, true);
586   vsize ret = 0;
587
588   for (vsize i = 0; i < div.size (); i++)
589     ret += div[i];
590   return ret;
591 }
592
593 vsize
594 Page_breaking::max_system_count (vsize start, vsize end)
595 {
596   vector<Break_position> chunks = chunk_list (start, end);
597   Line_division div = system_count_bounds (chunks, false);
598   vsize ret = 0;
599
600   for (vsize i = 0; i < div.size (); i++)
601     ret += div[i];
602   return ret;
603 }
604
605 Page_breaking::Line_division
606 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
607                                     bool min)
608 {
609   assert (chunks.size () >= 2);
610
611   Line_division ret;
612   ret.resize (chunks.size () - 1, 1);
613
614   for (vsize i = 0; i + 1 < chunks.size (); i++)
615     {
616       vsize sys = next_system (chunks[i]);
617       if (system_specs_[sys].pscore_)
618         {
619           vsize start;
620           vsize end;
621           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
622           ret[i] = min
623             ? line_breaking_[sys].min_system_count (start, end)
624             : line_breaking_[sys].max_system_count (start, end);
625         }
626     }
627
628   return ret;
629 }
630
631 void
632 Page_breaking::set_current_breakpoints (vsize start,
633                                         vsize end,
634                                         vsize system_count,
635                                         Line_division lower_bound,
636                                         Line_division upper_bound)
637 {
638   system_count_ = system_count;
639   current_chunks_ = chunk_list (start, end);
640   current_start_breakpoint_ = start;
641   current_end_breakpoint_ = end;
642   clear_line_details_cache ();
643
644   if (!lower_bound.size ())
645     lower_bound = system_count_bounds (current_chunks_, true);
646   if (!upper_bound.size ())
647     upper_bound = system_count_bounds (current_chunks_, false);
648
649   assert (lower_bound.size () == current_chunks_.size () - 1);
650   assert (upper_bound.size () == current_chunks_.size () - 1);
651
652   Line_division work_in_progress;
653   current_configurations_.clear ();
654   line_divisions_rec (system_count,
655                       lower_bound,
656                       upper_bound,
657                       &work_in_progress);
658
659   /* we only consider a constant number of configurations. Otherwise,
660      this becomes slow when there are many small scores. The constant
661      5 is somewhat arbitrary. */
662   if (current_configurations_.size () > 5)
663     {
664       vector<pair<Real,vsize> > dems_and_indices;
665
666       for (vsize i = 0; i < current_configurations_.size (); i++)
667         {
668           cache_line_details (i);
669           Real dem = 0;
670           for (vsize j = 0; j < cached_line_details_.size (); j++)
671             dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
672               + cached_line_details_[j].break_penalty_;
673
674           dems_and_indices.push_back (pair<Real,vsize> (dem, i));
675         }
676       vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
677
678       vector<Line_division> best_5_configurations;
679       for (vsize i = 0; i < 5; i++)
680         best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
681
682       clear_line_details_cache ();
683       current_configurations_ = best_5_configurations;
684     }
685 }
686
687 void
688 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
689 {
690   current_chunks_ = chunk_list (start, end);
691   current_start_breakpoint_ = start;
692   current_end_breakpoint_ = end;
693   clear_line_details_cache ();
694   system_count_ = 0;
695
696   Line_division div;
697   for (vsize i = 0; i+1 < current_chunks_.size (); i++)
698     {
699       vsize sys = next_system (current_chunks_[i]);
700       if (system_specs_[sys].pscore_)
701         {
702           line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
703           div.push_back (line_breaking_[sys].best_solution (start, end).size ());
704         }
705       else
706         div.push_back (1);
707
708       system_count_ += div.back ();
709     }
710   current_configurations_.clear ();
711   current_configurations_.push_back (div);
712 }
713
714 vsize
715 Page_breaking::current_configuration_count () const
716 {
717   return current_configurations_.size ();
718 }
719
720 void
721 Page_breaking::cache_line_details (vsize configuration_index)
722 {
723   if (cached_configuration_index_ != configuration_index)
724     {
725       cached_configuration_index_ = configuration_index;
726       Real padding = 0;
727       SCM spacing_spec = book_->paper_->c_variable ("between-system-spacing");
728       SCM page_breaking_spacing_spec = book_->paper_->c_variable ("page-breaking-between-system-spacing");
729       Page_layout_problem::read_spacing_spec (spacing_spec, &padding, ly_symbol2scm ("padding"));
730       Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec, &padding, ly_symbol2scm ("padding"));
731
732       Line_division &div = current_configurations_[configuration_index];
733       uncompressed_line_details_.clear ();
734       for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
735         {
736           vsize sys = next_system (current_chunks_[i]);
737           if (system_specs_[sys].pscore_)
738             {
739               vsize start;
740               vsize end;
741               line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
742
743               vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
744               uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
745             }
746           else
747             {
748               assert (div[i] == 1);
749               uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
750               uncompressed_line_details_.back ().padding_ =
751                 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
752                                    padding);
753             }
754         }
755       cached_line_details_ = compress_lines (uncompressed_line_details_);
756     }
757 }
758
759 void
760 Page_breaking::clear_line_details_cache ()
761 {
762   cached_configuration_index_ = VPOS;
763   cached_line_details_.clear ();
764   uncompressed_line_details_.clear ();
765 }
766
767 void
768 Page_breaking::line_divisions_rec (vsize system_count,
769                                    Line_division const &min_sys,
770                                    Line_division const &max_sys,
771                                    Line_division *cur_division)
772 {
773   vsize my_index = cur_division->size ();
774   vsize others_min = 0;
775   vsize others_max = 0;
776
777   for (vsize i = my_index + 1; i < min_sys.size (); i++)
778     {
779       others_min += min_sys[i];
780       others_max += max_sys[i];
781     }
782   others_max = min (others_max, system_count);
783   vsize real_min = max (min_sys[my_index], system_count - others_max);
784   vsize real_max = min (max_sys[my_index], system_count - others_min);
785
786   if (real_min > real_max || real_min <= 0)
787     {
788       /* this should never happen within a recursive call. If it happens
789          at all, it means that we were called with an unsolvable problem
790          and we should return an empty result */
791       assert (my_index == 0);
792       return;
793     }
794
795   for (vsize i = real_min; i <= real_max; i++)
796     {
797       cur_division->push_back (i);
798       if (my_index == min_sys.size () - 1)
799         current_configurations_.push_back (*cur_division);
800       else
801         line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
802       cur_division->pop_back ();
803     }
804 }
805
806 vsize
807 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
808 {
809   vsize ret = 1;
810   vsize page_starter = 0;
811   Real cur_rod_height = 0;
812   Real cur_spring_height = 0;
813   Real cur_page_height = page_height (first_page_num, false);
814   int line_count = 0;
815
816   cache_line_details (configuration);
817
818   if (cached_line_details_.size ())
819     cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
820
821   for (vsize i = 0; i < cached_line_details_.size (); i++)
822     {
823       Real ext_len = cached_line_details_[i].extent_.length ();
824       Real next_rod_height = cur_rod_height + ext_len
825         + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
826       Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
827       Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
828         + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
829       int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
830
831       if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
832           || too_many_lines (next_line_count)
833           || (i > 0
834               && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
835         {
836           line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
837           cur_rod_height = ext_len;
838           cur_spring_height = cached_line_details_[i].space_;
839           page_starter = i;
840
841           cur_page_height = page_height (first_page_num + ret, false);
842           cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
843
844           ret++;
845         }
846       else
847         {
848           cur_rod_height = next_rod_height;
849           cur_spring_height = next_spring_height;
850           line_count = next_line_count;
851         }
852     }
853
854   /* there are two potential problems with the last page (because we didn't know
855      it was the last page until after we managed to fit all the systems to it):
856      - we are ragged-last but the last page has a compressed spring
857      - the value returned by page_height (num, true) is smaller than the
858        value returned by page_height (num, false) and it causes the page not to
859        fit.
860
861      In either case, we just need to add one more page. This is because the last
862      line will always fit on the extra page and by adding one more page to the
863      end, the previous page is no longer the last page, so our previous
864      calculations that treated it as a non-last page were ok.
865   */
866
867   cur_page_height = page_height (first_page_num + ret - 1, true);
868   cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
869   cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
870
871   Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
872   if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
873       && cur_height > cur_page_height
874       /* don't increase the page count if the last page had only one system */
875       && cur_rod_height > cached_line_details_.back ().extent_.length ())
876     ret++;
877
878   assert (ret <= cached_line_details_.size ());
879   return ret;
880 }
881
882 // If systems_per_page_ is positive, we don't really try to space on N pages;
883 // we just put the requested number of systems on each page and penalize
884 // if the result doesn't have N pages.
885 Page_spacing_result
886 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
887 {
888   Page_spacing_result ret;
889
890   if (systems_per_page_ > 0)
891     {
892       Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
893       ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
894       return ret;
895     }
896
897   cache_line_details (configuration);
898   bool valid_n = (n >= min_page_count (configuration, first_page_num)
899                   && n <= cached_line_details_.size ());
900
901   if (!valid_n)
902     programming_error ("number of pages is out of bounds");
903
904   if (n == 1 && valid_n)
905     ret = space_systems_on_1_page (cached_line_details_,
906                                    page_height (first_page_num, is_last ()),
907                                    ragged () || (is_last () && ragged_last ()));
908   else if (n == 2 && valid_n)
909     ret = space_systems_on_2_pages (configuration, first_page_num);
910   else
911     {
912       Page_spacer ps (cached_line_details_, first_page_num, this);
913       ret = ps.solve (n);
914     }
915
916   return finalize_spacing_result (configuration, ret);
917 }
918
919 Real
920 Page_breaking::blank_page_penalty () const
921 {
922   SCM penalty_sym;
923
924   if (is_last ())
925     penalty_sym = ly_symbol2scm ("blank-last-page-force");
926   else if (ends_score ())
927     penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
928   else
929     penalty_sym = ly_symbol2scm ("blank-page-force");
930
931   Break_position const &pos = breaks_[current_end_breakpoint_];
932   if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
933     return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
934
935   return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
936 }
937
938 // If systems_per_page_ is positive, we don't really try to space on N
939 // or N+1 pages; see the comment to space_systems_on_n_pages.
940 Page_spacing_result
941 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
942 {
943   Page_spacing_result n_res;
944   Page_spacing_result m_res;
945
946   if (systems_per_page_ > 0)
947     {
948       Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
949       ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
950       return ret;
951     }
952
953   cache_line_details (configuration);
954   vsize min_p_count = min_page_count (configuration, first_page_num);
955   bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
956
957   if (!valid_n)
958     programming_error ("both page counts are out of bounds");
959
960   if (n == 1 && valid_n)
961     {
962       bool rag = ragged () || (is_last () && ragged_last ());
963       Real height = page_height (first_page_num, is_last ());
964
965       if (1 >= min_p_count)
966         n_res = space_systems_on_1_page (cached_line_details_, height, rag);
967       if (1 < cached_line_details_.size ())
968         m_res = space_systems_on_2_pages (configuration, first_page_num);
969     }
970   else
971     {
972       Page_spacer ps (cached_line_details_, first_page_num, this);
973       
974       if (n >= min_p_count || !valid_n)
975         n_res = ps.solve (n);
976       if (n < cached_line_details_.size () || !valid_n)
977         m_res = ps.solve (n+1);
978     }
979
980   m_res = finalize_spacing_result (configuration, m_res);
981   n_res = finalize_spacing_result (configuration, n_res);
982
983   Real penalty = blank_page_penalty ();
984   n_res.demerits_ += penalty;
985
986   if (n_res.force_.size ())
987     n_res.force_.back () += penalty;
988
989   return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
990 }
991
992 Page_spacing_result
993 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
994 {
995   vsize min_p_count = min_page_count (configuration, first_page_num);
996   Real odd_pages_penalty = blank_page_penalty ();
997
998   cache_line_details (configuration);
999   Page_spacer ps (cached_line_details_, first_page_num, this);
1000   Page_spacing_result best = ps.solve (min_p_count);
1001   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
1002   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
1003
1004   for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1005     {
1006       Page_spacing_result cur = ps.solve (i);
1007       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
1008       if (cur.demerits_ < best.demerits_)
1009         best = cur;
1010     }
1011
1012   return finalize_spacing_result (configuration, best);
1013 }
1014
1015 Page_spacing_result
1016 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1017                                                          vsize first_page_num)
1018 {
1019   Page_spacing_result res;
1020   Page_spacing space (page_height (first_page_num, false), this);
1021   vsize line = 0;
1022   vsize page = 0;
1023   vsize page_first_line = 0;
1024
1025   cache_line_details (configuration);
1026   while (line < cached_line_details_.size ())
1027     {
1028       page++;
1029       space.clear ();
1030       space.resize (page_height (first_page_num + page, false));
1031
1032       int system_count_on_this_page = 0;
1033       while (system_count_on_this_page < systems_per_page_
1034              && line < cached_line_details_.size ())
1035         {
1036           Line_details const &cur_line = cached_line_details_[line];
1037           space.append_system (cur_line);
1038           system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1039           line++;
1040
1041           if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1042             break;
1043         }
1044
1045       res.systems_per_page_.push_back (line - page_first_line);
1046
1047       res.force_.push_back (space.force_);
1048       res.penalty_ += cached_line_details_[line-1].page_penalty_;
1049       if (system_count_on_this_page != systems_per_page_)
1050         {
1051           res.penalty_ += TERRIBLE_SPACING_PENALTY;
1052           res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1053             ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1054         }
1055
1056       page_first_line = line;
1057     }
1058
1059   /* Recalculate forces for the last page because we know now that is
1060      really the last page. */
1061   space.resize (page_height (first_page_num + page, true));
1062   res.force_.back () = space.force_;
1063   return finalize_spacing_result (configuration, res);
1064 }
1065
1066 Page_spacing_result
1067 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1068 {
1069   // TODO: add support for min/max-systems-per-page.
1070   Page_spacing_result res;
1071   vsize page = 0;
1072   vsize page_first_line = 0;
1073   Page_spacing space (page_height (first_page_num, false), this);
1074
1075   cache_line_details (configuration);
1076   for (vsize line = 0; line < cached_line_details_.size (); line++)
1077     {
1078       Real prev_force = space.force_;
1079       space.append_system (cached_line_details_[line]);
1080       if ((line > page_first_line)
1081           && (isinf (space.force_)
1082               || ((line > 0)
1083                   && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1084         {
1085           res.systems_per_page_.push_back (line - page_first_line);
1086           res.force_.push_back (prev_force);
1087           res.penalty_ += cached_line_details_[line-1].page_penalty_;
1088           page++;
1089           space.resize (page_height (first_page_num + page, false));
1090           space.clear ();
1091           space.append_system (cached_line_details_[line]);
1092           page_first_line = line;
1093         }
1094
1095       if (line == cached_line_details_.size () - 1)
1096         {
1097           /* This is the last line */
1098           /* When the last page height was computed, we did not know yet that it
1099            * was the last one. If the systems put on it don't fit anymore, the last
1100            * system is moved to a new page */
1101           space.resize (page_height (first_page_num + page, true));
1102           if ((line > page_first_line) && (isinf (space.force_)))
1103             {
1104               res.systems_per_page_.push_back (line - page_first_line);
1105               res.force_.push_back (prev_force);
1106               /* the last page containing the last line */
1107               space.resize (page_height (first_page_num + page + 1, true));
1108               space.clear ();
1109               space.append_system (cached_line_details_[line]);
1110               res.systems_per_page_.push_back (1);
1111               res.force_.push_back (space.force_);
1112               res.penalty_ += cached_line_details_[line-1].page_penalty_;
1113               res.penalty_ += cached_line_details_[line].page_penalty_;
1114             }
1115           else
1116             {
1117               res.systems_per_page_.push_back (line + 1 - page_first_line);
1118               res.force_.push_back (space.force_);
1119               res.penalty_ += cached_line_details_[line].page_penalty_;
1120             }
1121         }
1122     }
1123   return finalize_spacing_result (configuration, res);
1124 }
1125
1126 /* Calculate demerits and fix res.systems_per_page_ so that
1127    it refers to the original line numbers, not the ones given by compress_lines (). */
1128 Page_spacing_result
1129 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1130 {
1131   if (res.force_.empty ())
1132     return res;
1133
1134   cache_line_details (configuration);
1135   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1136
1137   Real line_force = 0;
1138   Real line_penalty = 0;
1139   Real page_demerits = res.penalty_;
1140   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1141
1142   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1143     {
1144       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1145       line_penalty += uncompressed_line_details_[i].break_penalty_;
1146     }
1147
1148   for (vsize i = 0; i < res.force_.size (); i++)
1149     {
1150       Real f = res.force_[i];
1151
1152       page_demerits += min(f*f, BAD_SPACING_PENALTY);
1153     }
1154
1155   /* for a while we tried averaging page and line forces across pages instead
1156      of summing them, but it caused a problem: if there is a single page
1157      with a very bad page force (for example because of a forced page break),
1158      the page breaker will put in a _lot_ of pages so that the bad force
1159      becomes averaged out over many pages. */
1160   res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1161   return res;
1162
1163 }
1164
1165 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1166    are by far the most common cases, we have special functions for them.
1167
1168    space_systems_on_1_page has a different calling convention than most of the
1169    space_systems functions. This is because space_systems_on_1_page is (unlike
1170    the other space_systems functions) sometimes called on subsets of a full
1171    configuration. */
1172 Page_spacing_result
1173 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1174 {
1175   Page_spacing space (page_height, this);
1176   Page_spacing_result ret;
1177   int line_count = 0;
1178
1179   for (vsize i = 0; i < lines.size (); i++)
1180     {
1181       space.append_system (lines[i]);
1182       line_count += lines[i].compressed_nontitle_lines_count_;
1183     }
1184
1185   ret.systems_per_page_.push_back (lines.size ());
1186   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1187   ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1188   ret.system_count_status_ |= line_count_status (line_count);
1189
1190   /* don't do finalize_spacing_result () because we are only an internal function */
1191   return ret;
1192 }
1193
1194 Page_spacing_result
1195 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1196 {
1197   Real page1_height = page_height (first_page_num, false);
1198   Real page2_height = page_height (first_page_num + 1, is_last ());
1199   bool ragged1 = ragged ();
1200   bool ragged2 = ragged () || (is_last () && ragged_last ());
1201
1202   /* if there is a forced break, this reduces to 2 1-page problems */
1203   cache_line_details (configuration);
1204   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1205     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1206       {
1207         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1208         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1209         Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1210         Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1211
1212         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1213         p1.force_.push_back (p2.force_[0]);
1214         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1215         return p1;
1216       }
1217
1218   vector<Real> page1_force;
1219   vector<Real> page2_force;
1220
1221   // page1_penalty and page2_penalty store the penalties based
1222   // on min-systems-per-page and max-systems-per-page.
1223   vector<Real> page1_penalty;
1224   vector<Real> page2_penalty;
1225
1226   // page1_status and page2_status keep track of whether the min-systems-per-page
1227   // and max-systems-per-page constraints are satisfied.
1228   vector<int> page1_status;
1229   vector<int> page2_status;
1230
1231   Page_spacing page1 (page1_height, this);
1232   Page_spacing page2 (page2_height, this);
1233   int page1_line_count = 0;
1234   int page2_line_count = 0;
1235
1236   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1237   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1238   page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1239   page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1240   page1_status.resize (cached_line_details_.size () - 1, 0);
1241   page2_status.resize (cached_line_details_.size () - 1, 0);
1242
1243   /* find the page 1 and page 2 forces for each page-breaking position */
1244   for (vsize i = 0; i < page1_force.size (); i++)
1245     {
1246       page1.append_system (cached_line_details_[i]);
1247       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1248       page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1249       page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1250
1251       page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1252       page1_penalty[i] = line_count_penalty (page1_line_count);
1253       page1_status[i] = line_count_status (page1_line_count);
1254
1255       if (ragged2)
1256         page2_force[page2_force.size () - 1 - i] =
1257           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1258       else
1259         page2_force[page2_force.size () - 1 - i] = page2.force_;
1260       page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1261       page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1262     }
1263
1264   /* find the position that minimises the sum of the page forces */
1265   vsize best_sys_count = 1;
1266   Real best_demerits = infinity_f;
1267   for (vsize i = 0; i < page1_force.size (); i++)
1268     {
1269       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1270
1271       // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1272       // constraints. That is, we penalize harshly when they don't happen
1273       // but we don't completely reject.
1274       Real dem = f
1275         + page1_penalty[i] + page2_penalty[i]
1276         + cached_line_details_[i+1].page_penalty_
1277         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1278       if (dem < best_demerits)
1279         {
1280           best_demerits = dem;
1281           best_sys_count = i+1;
1282         }
1283     }
1284
1285   Page_spacing_result ret;
1286   ret.systems_per_page_.push_back (best_sys_count);
1287   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1288   ret.force_.push_back (page1_force[best_sys_count-1]);
1289   ret.force_.push_back (page2_force[best_sys_count-1]);
1290   ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1291   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1292     + cached_line_details_.back ().page_penalty_
1293     + cached_line_details_.back ().turn_penalty_
1294     + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1295
1296   /* don't do finalize_spacing_result () because we are only an internal function */
1297   return ret;
1298 }
1299
1300 bool
1301 Page_breaking::all_lines_stretched (vsize configuration)
1302 {
1303   cache_line_details (configuration);
1304   for (vsize i = 0; i < cached_line_details_.size (); i++)
1305     if (cached_line_details_[i].force_ < 0)
1306       return false;
1307
1308   return true;
1309 }
1310
1311 Page_breaking::Line_division
1312 Page_breaking::current_configuration (vsize configuration_index) const
1313 {
1314   return current_configurations_[configuration_index];
1315 }
1316
1317 bool
1318 Page_breaking::is_last () const
1319 {
1320   return current_end_breakpoint_ == last_break_position ();
1321 }
1322
1323 bool
1324 Page_breaking::ends_score () const
1325 {
1326   return breaks_[current_end_breakpoint_].score_ender_;
1327 }
1328
1329 vsize
1330 Page_breaking::last_break_position () const
1331 {
1332   return breaks_.size () - 1;  
1333 }
1334
1335 // This gives the minimum distance between the top of the
1336 // printable area (ie. the bottom of the top-margin) and
1337 // the extent box of the topmost system.
1338 Real
1339 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1340 {
1341   SCM first_system_spacing = book_->paper_->c_variable ("first-system-spacing");
1342   if (line.title_)
1343     first_system_spacing = book_->paper_->c_variable ("first-system-title-spacing");
1344
1345   Real min_distance = -infinity_f;
1346   Real padding = 0;
1347
1348   Page_layout_problem::read_spacing_spec (first_system_spacing,
1349                                           &min_distance,
1350                                           ly_symbol2scm ("minimum-distance"));
1351   Page_layout_problem::read_spacing_spec (first_system_spacing,
1352                                           &padding,
1353                                           ly_symbol2scm ("padding"));
1354
1355   // FIXME: take into account the height of the header
1356   return max (0.0, max (padding, min_distance - line.extent_[UP]));
1357 }
1358
1359 Real
1360 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1361 {
1362   SCM last_system_spacing = book_->paper_->c_variable ("last-system-spacing");
1363   Real min_distance = -infinity_f;
1364   Real padding = 0;
1365
1366   Page_layout_problem::read_spacing_spec (last_system_spacing,
1367                                           &min_distance,
1368                                           ly_symbol2scm ("minimum-distance"));
1369   Page_layout_problem::read_spacing_spec (last_system_spacing,
1370                                           &padding,
1371                                           ly_symbol2scm ("padding"));
1372
1373   // FIXME: take into account the height of the footer
1374   return max (0.0, max (padding, min_distance + line.extent_[DOWN]));
1375 }