2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2010 Joe Neeman <joeneeman@gmail.com>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
21 This is a utility class for page-breaking algorithms. There are some complex
22 parts of this class, some of which are useful to understand if you intend
23 to write a page breaking algorithm (ie. a subclass of Page_breaking). Most
24 of these complexities were introduced in order to break the problem of
25 page-breaking into simpler subproblems and to hide some of the bookkeeping
26 complexities of page breaking from the page breaking algorithms.
29 There are several functions that actually distribute systems across pages
30 (for example, the space_systems_XXX and pack_systems_XXX functions). If
31 each of these functions had to handle \noPageBreak, it would be a mess.
32 Therefore, we handle \noPageBreak by "compressing" the list of systems
33 before doing any layout: we concatenate any two systems separated by a
34 \noPageBreak into a single system. The page-breaking functions can do their
35 magic without encountering a \noPageBreak; we then "uncompress" the systems
36 at the end. We almost always work with cached_line_details_, which are
40 The basic operation of a page breaking algorithm is to repeatedly request
41 some systems from the line-breaker and place those systems on some pages.
42 With each repetition, the page breaking algorithm asks the line-breaker for
43 some systems that it thinks will help it achieve a better layout. The
44 Page_breaking class provides functionality to facilitate this in the case
45 that the page breaking algorithm only cares about the number of systems.
47 Even if a page breaking algorithm only cares number of systems, there may
48 be many ways to satisfy its request. For example, in a piece with 2 scores
49 and a request for 10 systems, we could return 5 systems from each score or
50 4 from the first and 6 from the second. Even within a score, we might
51 want to try several different line breaking configurations with a fixed
52 system count; if there is a forced \pageBreak, for example, we might wish
53 to tweak the number of systems on both sides of the \pageBreak independently.
55 The Page_breaking class takes care of finding these configurations. It
56 divides the piece into "chunks" and sets up the line-breaker in such a way
57 that the number of systems in each chunk can be modified independently.
58 Chunks never cross score boundaries; each title and markup is its own chunk.
59 When a page breaking algorithm requests a number of systems, the Page_breaker
60 stores an array of potential configurations, which the page breaking
61 algorithm can iterate over using current_configuration(vsize).
64 A Line_division is simply a way of storing the exact way in which the
65 total number of systems is distributed among chunks. Note that a
66 Line_division may not (in fact, usually will not) describe all of the chunks
67 in the entire book. Rather, it will describe the subset of chunks that lie
68 between some fixed starting and ending point. This subset of chunks changes
69 whenever a page breaking algorithm asks to consider a different pair of
70 starting and ending breakpoints. In particular, a Line_division should be
71 discarded after a call to set_current_breakpoints, since that Line_division
72 refers to a subset of chunks which might be different from the current
73 subset of chunks under consideration.
76 #include "page-breaking.hh"
78 #include "international.hh"
80 #include "output-def.hh"
81 #include "page-layout-problem.hh"
82 #include "page-spacing.hh"
83 #include "paper-book.hh"
84 #include "paper-score.hh"
85 #include "paper-system.hh"
89 /* for each forbidden page break, merge the systems around it into one
91 static vector<Line_details>
92 compress_lines (const vector<Line_details> &orig)
94 vector<Line_details> ret;
96 for (vsize i = 0; i < orig.size (); i++)
98 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
100 Line_details const &old = ret.back ();
101 Line_details compressed = orig[i];
103 We must account for the padding between the lines that we are compressing.
104 The padding values come from "old," which is the upper system here. Note
105 the meaning of tight-spacing: if a system has tight-spacing, then the padding
106 _before_ it is ignored.
109 if (!orig[i].tight_spacing_)
110 padding = orig[i].title_ ? old.title_padding_ : old.padding_;
112 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
113 compressed.first_refpoint_offset_ += compressed.shape_.rest_[UP] - old.shape_.rest_[UP];
114 compressed.space_ += old.space_;
115 compressed.inverse_hooke_ += old.inverse_hooke_;
117 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
118 compressed.compressed_nontitle_lines_count_ =
119 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
121 // compressed.title_ is true if and only if the first of its
122 // compressed lines was a title.
123 compressed.title_ = old.title_;
124 ret.back () = compressed;
128 ret.push_back (orig[i]);
129 ret.back ().force_ = 0;
135 /* translate the number of systems-per-page into something meaningful for
136 the uncompressed lines.
139 uncompress_solution (vector<vsize> const &systems_per_page,
140 vector<Line_details> const &compressed)
145 for (vsize i = 0; i < systems_per_page.size (); i++)
147 int compressed_count = 0;
148 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
149 compressed_count += compressed[j].compressed_lines_count_ - 1;
151 ret.push_back (systems_per_page[i] + compressed_count);
152 start_sys += systems_per_page[i];
157 /* for Page_breaking, the start index (when we are dealing with the stuff
158 between a pair of breakpoints) refers to the break_ index of the end of
159 the previous page. So the system index of the start of the current page
160 could either be the same as the end of the previous page or one more than
163 /* Turn a break index into the sys index that starts the next page */
165 Page_breaking::next_system (Break_position const &break_pos) const
167 vsize sys = break_pos.system_spec_index_;
169 if (sys == VPOS) /* beginning of the book */
171 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
172 return sys; /* the score overflows the previous page */
173 return sys + 1; /* this page starts with a new System_spec */
176 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
180 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
181 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
182 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
183 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
184 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
185 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
186 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
188 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
190 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
191 min_systems_per_page_ = max_systems_per_page_ = 0;
193 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
195 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
196 min_systems_per_page_ = max_systems_per_page_ = 0;
199 create_system_list ();
200 find_chunks_and_breaks (is_break, prob_break);
203 Page_breaking::~Page_breaking ()
208 Page_breaking::ragged () const
214 Page_breaking::ragged_last () const
220 Page_breaking::systems_per_page () const
222 return systems_per_page_;
226 Page_breaking::max_systems_per_page () const
228 return max_systems_per_page_;
232 Page_breaking::min_systems_per_page () const
234 return min_systems_per_page_;
238 Page_breaking::system_count () const
240 return system_count_;
244 Page_breaking::too_many_lines (int line_count) const
246 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
250 Page_breaking::too_few_lines (int line_count) const
252 return line_count < min_systems_per_page ();
256 Page_breaking::line_count_penalty (int line_count) const
258 if (too_many_lines (line_count))
259 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
260 if (too_few_lines (line_count))
261 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
267 Page_breaking::line_count_status (int line_count) const
269 if (too_many_lines (line_count))
270 return SYSTEM_COUNT_TOO_MANY;
271 if (too_few_lines (line_count))
272 return SYSTEM_COUNT_TOO_FEW;
274 return SYSTEM_COUNT_OK;
277 /* translate indices into breaks_ into start-end parameters for the line breaker */
279 Page_breaking::line_breaker_args (vsize sys,
280 Break_position const &start,
281 Break_position const &end,
282 vsize *line_breaker_start,
283 vsize *line_breaker_end)
285 assert (system_specs_[sys].pscore_);
286 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
288 if (start.system_spec_index_ == sys)
289 *line_breaker_start = start.score_break_;
291 *line_breaker_start = 0;
293 if (end.system_spec_index_ == sys)
294 *line_breaker_end = end.score_break_;
296 *line_breaker_end = VPOS;
300 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
301 Line_division const &div)
303 vector<Break_position> chunks = chunk_list (start_break, end_break);
304 bool ignore_div = false;
305 if (chunks.size () != div.size () + 1)
307 programming_error ("did not find a valid page breaking configuration");
311 for (vsize i = 0; i + 1 < chunks.size (); i++)
313 vsize sys = next_system (chunks[i]);
314 if (system_specs_[sys].pscore_)
318 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
320 vector<Column_x_positions> pos = ignore_div
321 ? line_breaking_[sys].best_solution (start, end)
322 : line_breaking_[sys].solve (start, end, div[i]);
323 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
329 Page_breaking::systems ()
332 for (vsize sys = 0; sys < system_specs_.size (); sys++)
334 if (system_specs_[sys].pscore_)
336 system_specs_[sys].pscore_->root_system ()
337 ->do_break_substitution_and_fixup_refpoints ();
338 SCM lines = system_specs_[sys].pscore_->root_system ()
339 ->get_broken_system_grobs ();
340 ret = scm_cons (lines, ret);
344 Prob *pb = system_specs_[sys].prob_;
345 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
349 return scm_append (scm_reverse (ret));
353 Page_breaking::make_page (int page_num, bool last) const
355 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
356 SCM mod = scm_c_resolve_module ("scm page");
357 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
359 make_page_scm = scm_variable_ref (make_page_scm);
361 return scm_apply_0 (make_page_scm,
362 scm_list_n (book_->self_scm (),
363 ly_symbol2scm ("page-number"), scm_from_int (page_num),
364 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
365 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
369 // Returns the total height of the paper, including margins and
370 // space for the header/footer. This is an upper bound on
371 // page_height, and it doesn't depend on the current page.
373 Page_breaking::paper_height () const
375 return paper_height_;
379 Page_breaking::page_height (int page_num, bool last) const
381 // The caches allow us to store the page heights for any
382 // non-negative page numbers. We use a negative value in the
383 // cache to signal that that position has not yet been initialized.
384 // This means that we won't cache properly if page_num is negative or
385 // if calc_height returns a negative number. But that's likely to
386 // be rare, so it shouldn't affect performance.
387 vector<Real>& cache = last ? last_page_height_cache_ : page_height_cache_;
388 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
389 return cache[page_num];
392 SCM mod = scm_c_resolve_module ("scm page");
393 SCM page = make_page (page_num, last);
394 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
395 calc_height = scm_variable_ref (calc_height);
397 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
398 Real height = scm_to_double (height_scm);
402 if ((int) cache.size () <= page_num)
403 cache.resize (page_num + 1, -1);
404 cache[page_num] = height;
411 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
413 Break_position const &pos = breaks_[breakpoint];
415 if (pos.system_spec_index_ == VPOS)
417 if (system_specs_[pos.system_spec_index_].pscore_)
418 return pos.col_->get_property (str);
419 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
423 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
425 SCM dummy_page = make_page (page_num, last);
426 Page_layout_problem layout (book_, dummy_page, systems);
427 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
431 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
433 // Create a stencil for each system.
434 SCM paper_systems = SCM_EOL;
435 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
437 SCM paper_system = scm_car (s);
438 if (Grob *g = unsmob_grob (scm_car (s)))
440 System *sys = dynamic_cast<System*> (g);
441 paper_system = sys->get_paper_system ();
444 paper_systems = scm_cons (paper_system, paper_systems);
447 // Create the page and draw it.
448 SCM page = make_page (page_num, last);
449 SCM page_module = scm_c_resolve_module ("scm page");
450 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
451 page_stencil = scm_variable_ref (page_stencil);
453 Prob *p = unsmob_prob (page);
454 p->set_property ("lines", paper_systems);
455 p->set_property ("configuration", configuration);
456 scm_apply_1 (page_stencil, page, SCM_EOL);
462 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
464 int first_page_number
465 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
467 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
468 if (label_page_table == SCM_UNDEFINED)
469 label_page_table = SCM_EOL;
471 // Build a list of (systems . configuration) pairs. Note that we lay out
472 // the staves and find the configurations before drawing anything. Some
473 // grobs (like tuplet brackets) look at their neighbours while drawing
474 // themselves. If this happens before the neighbouring staves have
475 // been laid out, bad side-effects could happen (in particular,
476 // Align_interface::align_to_ideal_distances might be called).
477 SCM systems_and_configs = SCM_EOL;
479 for (vsize i = 0; i < lines_per_page.size (); i++)
481 int page_num = i + first_page_number;
482 bool bookpart_last_page = (i == lines_per_page.size () - 1);
483 bool rag = ragged () || (bookpart_last_page && ragged_last ());
484 SCM line_count = scm_from_int (lines_per_page[i]);
485 SCM lines = scm_list_head (systems, line_count);
486 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
488 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
489 systems = scm_list_tail (systems, line_count);
492 // Now it's safe to make the pages.
493 int page_num = first_page_number + lines_per_page.size () - 1;
494 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
496 SCM lines = scm_caar (s);
497 SCM config = scm_cdar (s);
498 bool bookpart_last_page = (s == systems_and_configs);
499 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
502 SCM page_num_scm = scm_from_int (page_num);
503 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
505 SCM labels = SCM_EOL;
506 if (Grob * line = unsmob_grob (scm_car (l)))
508 System *system = dynamic_cast<System*> (line);
509 labels = system->get_property ("labels");
511 else if (Prob *prob = unsmob_prob (scm_car (l)))
512 labels = prob->get_property ("labels");
514 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
515 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
519 ret = scm_cons (page, ret);
522 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
526 /* The page-turn-page-breaker needs to have a line-breaker between any two
527 columns with non-NULL page-turn-permission.
529 The optimal-breaker needs to have a line-breaker between any two columns
530 with page-break-permission = 'force.
532 By using a grob predicate, we can accommodate both of these uses.
535 Page_breaking::create_system_list ()
537 SCM specs = book_->get_system_specs ();
538 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
540 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
542 system_specs_.push_back (System_spec (ps));
546 Prob *pb = unsmob_prob (scm_car (s));
550 system_specs_.push_back (System_spec (pb));
556 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
558 SCM force_sym = ly_symbol2scm ("force");
560 chunks_.push_back (Break_position ());
561 breaks_.push_back (Break_position ());
563 for (vsize i = 0; i < system_specs_.size (); i++)
565 if (system_specs_[i].pscore_)
567 vector<Grob*> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
568 vector<Grob*> forced_line_break_cols;
570 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
571 if (scm_is_number (system_count))
573 // With system-count given, the line configuration for
574 // this score is fixed. We need to ensure that chunk
575 // boundaries only occur at line breaks.
576 Constrained_breaking breaking (system_specs_[i].pscore_);
577 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
579 for (vsize j = 0; j < details.size (); j++)
580 forced_line_break_cols.push_back (details[j].last_column_);
583 int last_forced_line_break_idx = 0;
584 vsize forced_line_break_idx = 0;
585 vector<vsize> line_breaker_columns;
586 line_breaker_columns.push_back (0);
588 for (vsize j = 1; j < cols.size (); j++)
590 if (forced_line_break_cols.size ())
592 if (forced_line_break_idx >= forced_line_break_cols.size ()
593 || forced_line_break_cols[forced_line_break_idx] != cols[j])
596 forced_line_break_idx++;
599 bool last = (j == cols.size () - 1);
600 bool break_point = is_break && is_break (cols[j]);
601 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
602 Break_position cur_pos = Break_position (i,
603 line_breaker_columns.size (),
607 // NOTE: even in the breaks_ list, forced_line_count_
608 // refers to the number of lines between a
609 // Break_position and the start of that /chunk/. This
610 // is needed for system_count_bounds to work correctly,
611 // since it mixes Break_positions from breaks_ and
613 if (scm_is_number (system_count))
614 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
616 if (break_point || (i == system_specs_.size () - 1 && last))
617 breaks_.push_back (cur_pos);
618 if (chunk_end || last)
620 chunks_.push_back (cur_pos);
621 last_forced_line_break_idx = forced_line_break_idx;
624 if ((break_point || chunk_end) && !last)
625 line_breaker_columns.push_back (j);
627 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
631 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
632 if (break_point || i == system_specs_.size () - 1)
633 breaks_.push_back (Break_position (i));
635 chunks_.push_back (Break_position (i));
637 /* FIXME: shouldn't we push a Null_breaker or similar dummy
639 line_breaking_.push_back (Constrained_breaking (NULL));
644 vector<Break_position>
645 Page_breaking::chunk_list (vsize start_index, vsize end_index)
647 Break_position start = breaks_[start_index];
648 Break_position end = breaks_[end_index];
651 for (; i < chunks_.size () && chunks_[i] <= start; i++)
654 vector<Break_position> ret;
655 ret.push_back (start);
656 for (; i < chunks_.size () && chunks_[i] < end; i++)
657 ret.push_back (chunks_[i]);
663 Page_breaking::min_system_count (vsize start, vsize end)
665 vector<Break_position> chunks = chunk_list (start, end);
666 Line_division div = system_count_bounds (chunks, true);
669 for (vsize i = 0; i < div.size (); i++)
675 Page_breaking::max_system_count (vsize start, vsize end)
677 vector<Break_position> chunks = chunk_list (start, end);
678 Line_division div = system_count_bounds (chunks, false);
681 for (vsize i = 0; i < div.size (); i++)
686 Page_breaking::Line_division
687 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
690 assert (chunks.size () >= 2);
693 ret.resize (chunks.size () - 1, 1);
695 for (vsize i = 0; i + 1 < chunks.size (); i++)
697 vsize sys = next_system (chunks[i]);
699 if (chunks[i+1].forced_line_count_)
700 ret[i] = chunks[i+1].forced_line_count_;
701 else if (system_specs_[sys].pscore_)
705 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
707 ? line_breaking_[sys].min_system_count (start, end)
708 : line_breaking_[sys].max_system_count (start, end);
716 Page_breaking::set_current_breakpoints (vsize start,
719 Line_division lower_bound,
720 Line_division upper_bound)
722 system_count_ = system_count;
723 current_chunks_ = chunk_list (start, end);
724 current_start_breakpoint_ = start;
725 current_end_breakpoint_ = end;
726 clear_line_details_cache ();
728 if (!lower_bound.size ())
729 lower_bound = system_count_bounds (current_chunks_, true);
730 if (!upper_bound.size ())
731 upper_bound = system_count_bounds (current_chunks_, false);
733 assert (lower_bound.size () == current_chunks_.size () - 1);
734 assert (upper_bound.size () == current_chunks_.size () - 1);
736 Line_division work_in_progress;
737 current_configurations_.clear ();
738 line_divisions_rec (system_count,
743 /* we only consider a constant number of configurations. Otherwise,
744 this becomes slow when there are many small scores. The constant
745 5 is somewhat arbitrary. */
746 if (current_configurations_.size () > 5)
748 vector<pair<Real,vsize> > dems_and_indices;
750 for (vsize i = 0; i < current_configurations_.size (); i++)
752 cache_line_details (i);
754 for (vsize j = 0; j < cached_line_details_.size (); j++)
755 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
756 + cached_line_details_[j].break_penalty_;
758 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
760 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
762 vector<Line_division> best_5_configurations;
763 for (vsize i = 0; i < 5; i++)
764 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
766 clear_line_details_cache ();
767 current_configurations_ = best_5_configurations;
772 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
774 current_chunks_ = chunk_list (start, end);
775 current_start_breakpoint_ = start;
776 current_end_breakpoint_ = end;
777 clear_line_details_cache ();
781 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
783 vsize sys = next_system (current_chunks_[i]);
785 if (current_chunks_[i+1].forced_line_count_)
786 div.push_back (current_chunks_[i+1].forced_line_count_);
787 else if (system_specs_[sys].pscore_)
789 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
790 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
795 system_count_ += div.back ();
797 current_configurations_.clear ();
798 current_configurations_.push_back (div);
802 Page_breaking::current_configuration_count () const
804 return current_configurations_.size ();
808 Page_breaking::cache_line_details (vsize configuration_index)
810 if (cached_configuration_index_ != configuration_index)
812 cached_configuration_index_ = configuration_index;
814 Line_division &div = current_configurations_[configuration_index];
815 uncompressed_line_details_.clear ();
816 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
818 vsize sys = next_system (current_chunks_[i]);
819 if (system_specs_[sys].pscore_)
823 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
825 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
826 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
830 assert (div[i] == 1);
831 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_, book_->paper_));
834 cached_line_details_ = compress_lines (uncompressed_line_details_);
835 compute_line_heights ();
840 Page_breaking::clear_line_details_cache ()
842 cached_configuration_index_ = VPOS;
843 cached_line_details_.clear ();
844 uncompressed_line_details_.clear ();
848 Page_breaking::line_divisions_rec (vsize system_count,
849 Line_division const &min_sys,
850 Line_division const &max_sys,
851 Line_division *cur_division)
853 vsize my_index = cur_division->size ();
857 for (vsize i = my_index + 1; i < min_sys.size (); i++)
859 others_min += min_sys[i];
860 others_max += max_sys[i];
862 others_max = min (others_max, (int) system_count);
863 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
864 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
866 if (real_min > real_max || real_min <= 0)
868 /* this should never happen within a recursive call. If it happens
869 at all, it means that we were called with an unsolvable problem
870 and we should return an empty result */
871 assert (my_index == 0);
875 for (int i = real_min; i <= real_max; i++)
877 cur_division->push_back (i);
878 if (my_index == min_sys.size () - 1)
879 current_configurations_.push_back (*cur_division);
881 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
882 cur_division->pop_back ();
887 Page_breaking::compute_line_heights ()
889 Real prev_hanging = 0;
890 Real prev_hanging_begin = 0;
891 Real prev_hanging_rest = 0;
892 Real prev_refpoint_hanging = 0;
893 for (vsize i = 0; i < cached_line_details_.size (); i++)
895 Line_shape shape = cached_line_details_[i].shape_;
896 Real a = shape.begin_[UP];
897 Real b = shape.rest_[UP];
898 bool title = cached_line_details_[i].title_;
899 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
904 if (!cached_line_details_[i].tight_spacing_)
906 ? cached_line_details_[i-1].title_padding_
907 : cached_line_details_[i-1].padding_;
908 Real min_dist = title
909 ? cached_line_details_[i-1].title_min_distance_
910 : cached_line_details_[i-1].min_distance_;
911 refpoint_hanging = max (refpoint_hanging + padding,
912 prev_refpoint_hanging + min_dist
913 + cached_line_details_[i].first_refpoint_offset_);
916 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
917 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
918 Real hanging = max (hanging_begin, hanging_rest);
919 cached_line_details_[i].tallness_ = hanging - prev_hanging;
920 prev_hanging = hanging;
921 prev_hanging_begin = hanging_begin;
922 prev_hanging_rest = hanging_rest;
923 prev_refpoint_hanging = refpoint_hanging;
928 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
931 vsize page_starter = 0;
932 Real cur_rod_height = 0;
933 Real cur_spring_height = 0;
934 Real cur_page_height = page_height (first_page_num, false);
937 cache_line_details (configuration);
939 if (cached_line_details_.size ())
940 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
942 for (vsize i = 0; i < cached_line_details_.size (); i++)
945 if (cur_rod_height > 0)
946 ext_len = cached_line_details_[i].tallness_;
948 ext_len = cached_line_details_[i].full_height();
950 Real next_rod_height = cur_rod_height + ext_len;
951 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
952 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
953 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
954 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
956 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
957 || too_many_lines (next_line_count)
959 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
961 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
962 cur_rod_height = cached_line_details_[i].full_height();
963 cur_spring_height = cached_line_details_[i].space_;
966 cur_page_height = page_height (first_page_num + ret, false);
967 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
973 cur_rod_height = next_rod_height;
974 cur_spring_height = next_spring_height;
975 line_count = next_line_count;
979 /* there are two potential problems with the last page (because we didn't know
980 it was the last page until after we managed to fit all the systems to it):
981 - we are ragged-last but the last page has a compressed spring
982 - the value returned by page_height (num, true) is smaller than the
983 value returned by page_height (num, false) and it causes the page not to
986 In either case, we just need to add one more page. This is because the last
987 line will always fit on the extra page and by adding one more page to the
988 end, the previous page is no longer the last page, so our previous
989 calculations that treated it as a non-last page were ok.
992 cur_page_height = page_height (first_page_num + ret - 1, true);
993 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
994 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
996 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
997 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
998 && cur_height > cur_page_height
999 /* don't increase the page count if the last page had only one system */
1000 && cur_rod_height > cached_line_details_.back ().full_height ())
1003 assert (ret <= cached_line_details_.size ());
1007 // If systems_per_page_ is positive, we don't really try to space on N pages;
1008 // we just put the requested number of systems on each page and penalize
1009 // if the result doesn't have N pages.
1011 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1013 Page_spacing_result ret;
1015 if (systems_per_page_ > 0)
1017 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1018 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1022 cache_line_details (configuration);
1023 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1024 && n <= cached_line_details_.size ());
1027 programming_error ("number of pages is out of bounds");
1029 if (n == 1 && valid_n)
1030 ret = space_systems_on_1_page (cached_line_details_,
1031 page_height (first_page_num, is_last ()),
1032 ragged () || (is_last () && ragged_last ()));
1033 else if (n == 2 && valid_n)
1034 ret = space_systems_on_2_pages (configuration, first_page_num);
1037 Page_spacer ps (cached_line_details_, first_page_num, this);
1041 return finalize_spacing_result (configuration, ret);
1045 Page_breaking::blank_page_penalty () const
1050 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1051 else if (ends_score ())
1052 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1054 penalty_sym = ly_symbol2scm ("blank-page-force");
1056 Break_position const &pos = breaks_[current_end_breakpoint_];
1057 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1058 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1060 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1063 // If systems_per_page_ is positive, we don't really try to space on N
1064 // or N+1 pages; see the comment to space_systems_on_n_pages.
1066 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1067 Real penalty_for_fewer_pages)
1069 Page_spacing_result n_res;
1070 Page_spacing_result m_res;
1072 if (systems_per_page_ > 0)
1074 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1075 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
1079 cache_line_details (configuration);
1080 vsize min_p_count = min_page_count (configuration, first_page_num);
1081 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1084 programming_error ("both page counts are out of bounds");
1086 if (n == 1 && valid_n)
1088 bool rag = ragged () || (is_last () && ragged_last ());
1089 Real height = page_height (first_page_num, is_last ());
1091 if (1 >= min_p_count)
1092 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1093 if (1 < cached_line_details_.size ())
1094 m_res = space_systems_on_2_pages (configuration, first_page_num);
1098 Page_spacer ps (cached_line_details_, first_page_num, this);
1100 if (n >= min_p_count || !valid_n)
1101 n_res = ps.solve (n);
1102 if (n < cached_line_details_.size () || !valid_n)
1103 m_res = ps.solve (n+1);
1106 m_res = finalize_spacing_result (configuration, m_res);
1107 n_res = finalize_spacing_result (configuration, n_res);
1109 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1110 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1112 if (n_res.force_.size ())
1113 n_res.force_.back () += penalty_for_fewer_pages;
1115 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1119 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1121 cache_line_details (configuration);
1122 Page_spacer ps (cached_line_details_, first_page_num, this);
1124 return finalize_spacing_result (configuration, ps.solve ());
1128 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1129 vsize first_page_num)
1131 Page_spacing_result res;
1132 Page_spacing space (page_height (first_page_num, false), this);
1135 vsize page_first_line = 0;
1137 cache_line_details (configuration);
1138 while (line < cached_line_details_.size ())
1142 space.resize (page_height (first_page_num + page, false));
1144 int system_count_on_this_page = 0;
1145 while (system_count_on_this_page < systems_per_page_
1146 && line < cached_line_details_.size ())
1148 Line_details const &cur_line = cached_line_details_[line];
1149 space.append_system (cur_line);
1150 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1153 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1157 res.systems_per_page_.push_back (line - page_first_line);
1159 res.force_.push_back (space.force_);
1160 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1161 if (system_count_on_this_page != systems_per_page_)
1163 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1164 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1165 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1168 page_first_line = line;
1171 /* Recalculate forces for the last page because we know now that is
1172 really the last page. */
1173 space.resize (page_height (first_page_num + page, true));
1174 res.force_.back () = space.force_;
1175 return finalize_spacing_result (configuration, res);
1179 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1181 // TODO: add support for min/max-systems-per-page.
1182 Page_spacing_result res;
1184 vsize page_first_line = 0;
1185 Page_spacing space (page_height (first_page_num, false), this);
1187 cache_line_details (configuration);
1188 for (vsize line = 0; line < cached_line_details_.size (); line++)
1190 Real prev_force = space.force_;
1191 space.append_system (cached_line_details_[line]);
1192 if ((line > page_first_line)
1193 && (isinf (space.force_)
1195 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1197 res.systems_per_page_.push_back (line - page_first_line);
1198 res.force_.push_back (prev_force);
1199 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1201 space.resize (page_height (first_page_num + page, false));
1203 space.append_system (cached_line_details_[line]);
1204 page_first_line = line;
1207 if (line == cached_line_details_.size () - 1)
1209 /* This is the last line */
1210 /* When the last page height was computed, we did not know yet that it
1211 * was the last one. If the systems put on it don't fit anymore, the last
1212 * system is moved to a new page */
1213 space.resize (page_height (first_page_num + page, true));
1214 if ((line > page_first_line) && (isinf (space.force_)))
1216 res.systems_per_page_.push_back (line - page_first_line);
1217 res.force_.push_back (prev_force);
1218 /* the last page containing the last line */
1219 space.resize (page_height (first_page_num + page + 1, true));
1221 space.append_system (cached_line_details_[line]);
1222 res.systems_per_page_.push_back (1);
1223 res.force_.push_back (space.force_);
1224 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1225 res.penalty_ += cached_line_details_[line].page_penalty_;
1229 res.systems_per_page_.push_back (line + 1 - page_first_line);
1230 res.force_.push_back (space.force_);
1231 res.penalty_ += cached_line_details_[line].page_penalty_;
1235 return finalize_spacing_result (configuration, res);
1238 /* Calculate demerits and fix res.systems_per_page_ so that
1239 it refers to the original line numbers, not the ones given by compress_lines (). */
1241 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1243 if (res.force_.empty ())
1246 cache_line_details (configuration);
1247 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1249 Real line_force = 0;
1250 Real line_penalty = 0;
1251 Real page_demerits = res.penalty_;
1252 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1254 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1256 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1257 line_penalty += uncompressed_line_details_[i].break_penalty_;
1260 for (vsize i = 0; i < res.force_.size (); i++)
1262 Real f = res.force_[i];
1264 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1267 /* for a while we tried averaging page and line forces across pages instead
1268 of summing them, but it caused a problem: if there is a single page
1269 with a very bad page force (for example because of a forced page break),
1270 the page breaker will put in a _lot_ of pages so that the bad force
1271 becomes averaged out over many pages. */
1272 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1277 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1278 are by far the most common cases, we have special functions for them.
1280 space_systems_on_1_page has a different calling convention than most of the
1281 space_systems functions. This is because space_systems_on_1_page is (unlike
1282 the other space_systems functions) sometimes called on subsets of a full
1285 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1287 Page_spacing space (page_height, this);
1288 Page_spacing_result ret;
1291 for (vsize i = 0; i < lines.size (); i++)
1293 space.append_system (lines[i]);
1294 line_count += lines[i].compressed_nontitle_lines_count_;
1297 ret.systems_per_page_.push_back (lines.size ());
1298 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1299 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1300 ret.system_count_status_ |= line_count_status (line_count);
1302 /* don't do finalize_spacing_result () because we are only an internal function */
1307 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1309 Real page1_height = page_height (first_page_num, false);
1310 Real page2_height = page_height (first_page_num + 1, is_last ());
1311 bool ragged1 = ragged ();
1312 bool ragged2 = ragged () || (is_last () && ragged_last ());
1314 /* if there is a forced break, this reduces to 2 1-page problems */
1315 cache_line_details (configuration);
1316 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1317 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1319 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1320 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1321 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1322 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1324 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1325 p1.force_.push_back (p2.force_[0]);
1326 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1327 p1.system_count_status_ |= p2.system_count_status_;
1331 vector<Real> page1_force;
1332 vector<Real> page2_force;
1334 // page1_penalty and page2_penalty store the penalties based
1335 // on min-systems-per-page and max-systems-per-page.
1336 vector<Real> page1_penalty;
1337 vector<Real> page2_penalty;
1339 // page1_status and page2_status keep track of whether the min-systems-per-page
1340 // and max-systems-per-page constraints are satisfied.
1341 vector<int> page1_status;
1342 vector<int> page2_status;
1344 Page_spacing page1 (page1_height, this);
1345 Page_spacing page2 (page2_height, this);
1346 int page1_line_count = 0;
1347 int page2_line_count = 0;
1349 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1350 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1351 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1352 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1353 page1_status.resize (cached_line_details_.size () - 1, 0);
1354 page2_status.resize (cached_line_details_.size () - 1, 0);
1356 /* find the page 1 and page 2 forces for each page-breaking position */
1357 for (vsize i = 0; i < page1_force.size (); i++)
1359 page1.append_system (cached_line_details_[i]);
1360 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1361 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1362 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1364 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1365 page1_penalty[i] = line_count_penalty (page1_line_count);
1366 page1_status[i] = line_count_status (page1_line_count);
1369 page2_force[page2_force.size () - 1 - i] =
1370 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1372 page2_force[page2_force.size () - 1 - i] = page2.force_;
1373 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1374 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1377 /* find the position that minimises the sum of the page forces */
1378 vsize best_sys_count = 1;
1379 Real best_demerits = infinity_f;
1380 for (vsize i = 0; i < page1_force.size (); i++)
1382 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1384 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1385 // constraints. That is, we penalize harshly when they don't happen
1386 // but we don't completely reject.
1388 + page1_penalty[i] + page2_penalty[i]
1389 + cached_line_details_[i+1].page_penalty_
1390 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1391 if (dem < best_demerits)
1393 best_demerits = dem;
1394 best_sys_count = i+1;
1398 Page_spacing_result ret;
1399 ret.systems_per_page_.push_back (best_sys_count);
1400 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1401 ret.force_.push_back (page1_force[best_sys_count-1]);
1402 ret.force_.push_back (page2_force[best_sys_count-1]);
1403 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1404 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1405 + cached_line_details_.back ().page_penalty_
1406 + cached_line_details_.back ().turn_penalty_
1407 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1409 /* don't do finalize_spacing_result () because we are only an internal function */
1414 Page_breaking::all_lines_stretched (vsize configuration)
1416 cache_line_details (configuration);
1417 for (vsize i = 0; i < cached_line_details_.size (); i++)
1418 if (cached_line_details_[i].force_ < 0)
1424 Page_breaking::Line_division
1425 Page_breaking::current_configuration (vsize configuration_index) const
1427 return current_configurations_[configuration_index];
1431 Page_breaking::is_last () const
1433 return current_end_breakpoint_ == last_break_position ();
1437 Page_breaking::ends_score () const
1439 return breaks_[current_end_breakpoint_].score_ender_;
1443 Page_breaking::last_break_position () const
1445 return breaks_.size () - 1;
1448 // This gives the minimum distance between the top of the
1449 // printable area (ie. the bottom of the top-margin) and
1450 // the extent box of the topmost system.
1452 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1454 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1456 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1458 Real min_distance = -infinity_f;
1461 Page_layout_problem::read_spacing_spec (first_system_spacing,
1463 ly_symbol2scm ("minimum-distance"));
1464 Page_layout_problem::read_spacing_spec (first_system_spacing,
1466 ly_symbol2scm ("padding"));
1468 // FIXME: take into account the height of the header
1469 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1470 return max (0.0, max (padding, min_distance - translate));
1474 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1476 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1477 Real min_distance = -infinity_f;
1480 Page_layout_problem::read_spacing_spec (last_system_spacing,
1482 ly_symbol2scm ("minimum-distance"));
1483 Page_layout_problem::read_spacing_spec (last_system_spacing,
1485 ly_symbol2scm ("padding"));
1487 // FIXME: take into account the height of the footer
1488 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1489 return max (0.0, max (padding, min_distance + translate));
1493 Page_breaking::orphan_penalty () const
1495 return orphan_penalty_;