2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2012 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.
75 HOW TO WRITE A PAGE BREAKING ALGORITHM
76 All page breakers supported by this class work more-or-less in the same way.
77 First, they request a particular number of systems by saying
78 set_current_breakpoints (0, last_break_position (), system_count)
79 (never mind what the first two arguments do, I'll get to them later).
80 Alternatively, you can do
81 set_to_ideal_line_configuration (0, last_break_position ()),
82 and the number of systems will be automatically chosen according to what
83 the line breaker wants.
85 If there are multiple scores, there will be many different ways to achieve
86 a certain number of lines. You can see how many alternatives are available
87 with current_configuration_count (). For every i from 0 to
88 current_configuration_count ()-1, you can see the line division of the
89 corresponding configuration with current_configuration (i), or you can try
90 out various page configurations with one of the space_systems_xxx or
91 pack_systems_xxx functions. The first argument to each of these functions
92 is the configuration index.
94 When you're done trying out configurations and you've picked the one
96 break_into_pieces (0, last_break_position (), line_division_that_you_want);
97 return make_pages (systems_per_page, systems ());
98 where systems_per_page is a vector of numbers telling how many systems are
99 on each page. You can get your systems_per_page vector by looking inside
100 the Page_spacing_results that are returned by space_systems_xxx or
103 A note on performance: set_current_breakpoints is EXPONENTIALLY SLOW unless
104 you constrain it by giving it a lower or an upper bound on the configurations
105 it looks for. Optimal_page_breaking, for example, works by trying
106 out a bunch of configurations, increasing the system count by one, trying
107 again and so on. Each time we increase the system count, we assume that the
108 best new configurations are going to be elementwise larger than the
109 best configuration for the previous system count (in other words, we're going
110 to get a new configuration just by adding an extra line to sone score
111 and leaving the rest the same). Therefore, we pass the best previous line
112 division as an lower bound to set_current_breakpoints.
114 Now you should be in a position to understand Optimal_page_breaking::solve.
115 Go ahead and read that before finding out, in the next paragraph,
116 what the first two arguments to set_current_breakpoints do.
119 Sometimes, it's useful to run this whole page-breaking machinery on a subset
120 of the book. To do this, you can mark certain "breaks" in the book (a poor
121 choice of name, perhaps, since a "break" here is different from a page break)
122 and you can run page breaking between any two breaks. You mark your breaks
123 by providing a Break_predicate (and, if you want, a Prob_break_predicate)
124 to Page_breaking's constructor. You then choose a subset of your book
125 by passing the starting and ending breaks to set_current_breakpoints. You
126 can see an example of this in Page_turn_page_breaking, where there is a break
127 everywhere that a page turn is allowed.
130 #include "page-breaking.hh"
132 #include "international.hh"
134 #include "line-interface.hh"
135 #include "output-def.hh"
136 #include "page-layout-problem.hh"
137 #include "page-spacing.hh"
138 #include "paper-book.hh"
139 #include "paper-score.hh"
140 #include "paper-system.hh"
141 #include "text-interface.hh"
145 /* for each forbidden page break, merge the systems around it into one
147 static vector<Line_details>
148 compress_lines (const vector<Line_details> &orig)
150 vector<Line_details> ret;
152 for (vsize i = 0; i < orig.size (); i++)
154 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
156 Line_details const &old = ret.back ();
157 Line_details compressed = orig[i];
159 We must account for the padding between the lines that we are compressing.
160 The padding values come from "old," which is the upper system here. Note
161 the meaning of tight-spacing: if a system has tight-spacing, then the padding
162 _before_ it is ignored.
165 if (!orig[i].tight_spacing_)
166 padding = orig[i].title_ ? old.title_padding_ : old.padding_;
168 // FIXME: double check these. Doesn't foo.piggyback (bar) mean
169 // that foo goes on top?
170 // TODO: break out a Line_details::piggyback from here?
171 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
172 compressed.refpoint_extent_[UP] = old.refpoint_extent_[UP];
173 compressed.refpoint_extent_[DOWN] += compressed.shape_.rest_[UP] - old.shape_.rest_[UP];
174 compressed.space_ += old.space_;
175 compressed.inverse_hooke_ += old.inverse_hooke_;
177 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
178 compressed.compressed_nontitle_lines_count_
179 = old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
181 // compressed.title_ is true if and only if the first of its
182 // compressed lines was a title.
183 compressed.title_ = old.title_;
185 // adds footnotes of one line to the footnotes of another
186 compressed.footnote_heights_.insert (compressed.footnote_heights_.begin (),
187 old.footnote_heights_.begin (),
188 old.footnote_heights_.end ());
189 compressed.in_note_heights_.insert (compressed.in_note_heights_.begin (),
190 old.in_note_heights_.begin (),
191 old.in_note_heights_.end ());
193 ret.back () = compressed;
197 ret.push_back (orig[i]);
198 ret.back ().force_ = 0;
204 /* translate the number of systems-per-page into something meaningful for
205 the uncompressed lines.
208 uncompress_solution (vector<vsize> const &systems_per_page,
209 vector<Line_details> const &compressed)
214 for (vsize i = 0; i < systems_per_page.size (); i++)
216 int compressed_count = 0;
217 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
218 compressed_count += compressed[j].compressed_lines_count_ - 1;
220 ret.push_back (systems_per_page[i] + compressed_count);
221 start_sys += systems_per_page[i];
226 /* for Page_breaking, the start index (when we are dealing with the stuff
227 between a pair of breakpoints) refers to the break_ index of the end of
228 the previous page. So the system index of the start of the current page
229 could either be the same as the end of the previous page or one more than
232 /* Turn a break index into the sys index that starts the next page */
234 Page_breaking::next_system (Break_position const &break_pos) const
236 vsize sys = break_pos.system_spec_index_;
238 if (sys == VPOS) /* beginning of the book */
240 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
241 return sys; /* the score overflows the previous page */
242 return sys + 1; /* this page starts with a new System_spec */
245 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
249 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
250 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
251 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
252 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
253 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
254 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
255 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
257 Stencil footnote_separator = Page_layout_problem::get_footnote_separator_stencil (pb->paper_);
259 if (!footnote_separator.is_empty ())
261 Interval separator_extent = footnote_separator.extent (Y_AXIS);
262 Real separator_span = separator_extent.length ();
264 footnote_separator_stencil_height_ = separator_span;
267 footnote_separator_stencil_height_ = 0.0;
269 footnote_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
270 in_note_padding_ = robust_scm2double (pb->paper_->c_variable ("in-note-padding"), 0.0);
271 footnote_footer_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-footer-padding"), 0.0);
273 footnote_number_raise_ = robust_scm2double (pb->paper_->c_variable ("footnote-number-raise"), 0.0);
275 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
277 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
278 min_systems_per_page_ = max_systems_per_page_ = 0;
280 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
282 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
283 min_systems_per_page_ = max_systems_per_page_ = 0;
286 create_system_list ();
287 find_chunks_and_breaks (is_break, prob_break);
290 Page_breaking::~Page_breaking ()
295 Page_breaking::ragged () const
301 Page_breaking::ragged_last () const
307 Page_breaking::systems_per_page () const
309 return systems_per_page_;
313 Page_breaking::max_systems_per_page () const
315 if (systems_per_page_)
316 return systems_per_page_;
317 return max_systems_per_page_;
321 Page_breaking::min_systems_per_page () const
323 if (systems_per_page_)
324 return systems_per_page_;
325 return min_systems_per_page_;
329 Page_breaking::system_count () const
331 return system_count_;
335 Page_breaking::footnote_separator_stencil_height () const
337 return footnote_separator_stencil_height_;
341 Page_breaking::in_note_padding () const
343 return in_note_padding_;
347 Page_breaking::footnote_padding () const
349 return footnote_padding_;
353 Page_breaking::footnote_footer_padding () const
355 return footnote_footer_padding_;
359 Page_breaking::footnote_number_raise () const
361 return footnote_number_raise_;
365 Page_breaking::too_many_lines (int line_count) const
367 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
371 Page_breaking::too_few_lines (int line_count) const
373 return line_count < min_systems_per_page ();
377 Page_breaking::line_count_penalty (int line_count) const
379 if (too_many_lines (line_count))
380 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
381 if (too_few_lines (line_count))
382 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
388 Page_breaking::line_count_status (int line_count) const
390 if (too_many_lines (line_count))
391 return SYSTEM_COUNT_TOO_MANY;
392 if (too_few_lines (line_count))
393 return SYSTEM_COUNT_TOO_FEW;
395 return SYSTEM_COUNT_OK;
398 /* translate indices into breaks_ into start-end parameters for the line breaker */
400 Page_breaking::line_breaker_args (vsize sys,
401 Break_position const &start,
402 Break_position const &end,
403 vsize *line_breaker_start,
404 vsize *line_breaker_end)
406 assert (system_specs_[sys].pscore_);
407 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
409 if (start.system_spec_index_ == sys)
410 *line_breaker_start = start.score_break_;
412 *line_breaker_start = 0;
414 if (end.system_spec_index_ == sys)
415 *line_breaker_end = end.score_break_;
417 *line_breaker_end = VPOS;
421 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
422 Line_division const &div)
424 vector<Break_position> chunks = chunk_list (start_break, end_break);
425 bool ignore_div = false;
426 if (chunks.size () != div.size () + 1)
428 programming_error ("did not find a valid page breaking configuration");
432 for (vsize i = 0; i + 1 < chunks.size (); i++)
434 vsize sys = next_system (chunks[i]);
435 if (system_specs_[sys].pscore_)
439 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
441 vector<Column_x_positions> pos = ignore_div
442 ? line_breaking_[sys].best_solution (start, end)
443 : line_breaking_[sys].solve (start, end, div[i]);
444 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
450 Page_breaking::systems ()
453 for (vsize sys = 0; sys < system_specs_.size (); sys++)
455 if (system_specs_[sys].pscore_)
457 system_specs_[sys].pscore_->root_system ()
458 ->do_break_substitution_and_fixup_refpoints ();
459 SCM lines = system_specs_[sys].pscore_->root_system ()
460 ->get_broken_system_grobs ();
461 ret = scm_cons (lines, ret);
463 else if (Prob *pb = system_specs_[sys].prob_)
465 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
469 return scm_append (scm_reverse_x (ret, SCM_EOL));
473 Page_breaking::make_page (int page_num, bool last) const
475 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
476 SCM mod = scm_c_resolve_module ("scm page");
477 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
479 make_page_scm = scm_variable_ref (make_page_scm);
481 return scm_apply_0 (make_page_scm,
482 scm_list_n (book_->self_scm (),
483 ly_symbol2scm ("page-number"), scm_from_int (page_num),
484 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
485 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
489 // Returns the total height of the paper, including margins and
490 // space for the header/footer. This is an upper bound on
491 // page_height, and it doesn't depend on the current page.
493 Page_breaking::paper_height () const
495 return paper_height_;
499 Page_breaking::page_height (int page_num, bool last) const
501 // The caches allow us to store the page heights for any
502 // non-negative page numbers. We use a negative value in the
503 // cache to signal that that position has not yet been initialized.
504 // This means that we won't cache properly if page_num is negative or
505 // if calc_height returns a negative number. But that's likely to
506 // be rare, so it shouldn't affect performance.
507 vector<Real>& cache = last ? last_page_height_cache_ : page_height_cache_;
508 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
509 return cache[page_num];
512 SCM mod = scm_c_resolve_module ("scm page");
513 SCM page = make_page (page_num, last);
514 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
515 calc_height = scm_variable_ref (calc_height);
517 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
518 Real height = scm_to_double (height_scm);
522 if ((int) cache.size () <= page_num)
523 cache.resize (page_num + 1, -1);
524 cache[page_num] = height;
531 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
533 Break_position const &pos = breaks_[breakpoint];
535 if (pos.system_spec_index_ == VPOS)
537 if (system_specs_[pos.system_spec_index_].pscore_)
538 return pos.col_->get_property (str);
539 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
543 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
545 SCM dummy_page = make_page (page_num, last);
546 Page_layout_problem layout (book_, dummy_page, systems);
547 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
551 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
553 // Create a stencil for each system.
554 SCM paper_systems = SCM_EOL;
555 for (SCM s = systems; scm_is_pair (s); s = scm_cdr (s))
557 SCM paper_system = scm_car (s);
558 if (Grob *g = unsmob_grob (scm_car (s)))
560 System *sys = dynamic_cast<System *> (g);
561 paper_system = sys->get_paper_system ();
564 paper_systems = scm_cons (paper_system, paper_systems);
566 paper_systems = scm_reverse_x (paper_systems, SCM_EOL);
568 // Create the page and draw it.
569 SCM page = make_page (page_num, last);
570 SCM page_module = scm_c_resolve_module ("scm page");
571 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
572 page_stencil = scm_variable_ref (page_stencil);
574 Prob *p = unsmob_prob (page);
575 p->set_property ("lines", paper_systems);
576 p->set_property ("configuration", configuration);
578 Stencil *foot_p = unsmob_stencil (p->get_property ("foot-stencil"));
579 Stencil foot = foot_p ? *foot_p : Stencil ();
581 SCM footnotes = Page_layout_problem::get_footnotes_from_lines (systems);
583 foot = Page_layout_problem::add_footnotes_to_footer (footnotes, foot, book_);
585 p->set_property ("foot-stencil", foot.smobbed_copy ());
586 scm_apply_1 (page_stencil, page, SCM_EOL);
592 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
594 if (scm_is_null (systems))
597 int first_page_number
598 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
600 bool reset_footnotes_on_new_page = to_boolean (book_->top_paper ()->c_variable ("reset-footnotes-on-new-page"));
601 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
602 if (label_page_table == SCM_UNDEFINED)
603 label_page_table = SCM_EOL;
605 // Build a list of (systems configuration . footnote-count) triples.
606 // Note that we lay out
607 // the staves and find the configurations before drawing anything. Some
608 // grobs (like tuplet brackets) look at their neighbours while drawing
609 // themselves. If this happens before the neighbouring staves have
610 // been laid out, bad side-effects could happen (in particular,
611 // Align_interface::align_to_ideal_distances might be called).
612 SCM systems_configs_fncounts = SCM_EOL;
613 vsize footnote_count = 0;
614 Real last_page_force = 0;
616 for (vsize i = 0; i < lines_per_page.size (); i++)
618 int page_num = i + first_page_number;
619 bool bookpart_last_page = (i == lines_per_page.size () - 1);
620 bool rag = ragged () || (bookpart_last_page && ragged_last ());
621 SCM line_count = scm_from_int (lines_per_page[i]);
622 SCM lines = scm_list_head (systems, line_count);
623 int fn_lines = Page_layout_problem::get_footnote_count (lines);
624 Page_layout_problem::add_footnotes_to_lines (lines, reset_footnotes_on_new_page ? 0 : footnote_count, book_);
626 SCM config = SCM_EOL;
627 SCM dummy_page = make_page (page_num, bookpart_last_page);
628 Page_layout_problem layout (book_, dummy_page, lines);
629 if (!scm_is_pair (systems))
631 else if (rag && !ragged ())
632 // If we're ragged-last but not ragged, make the last page
633 // have the same force as the previous page.
634 config = layout.fixed_force_solution (last_page_force);
636 config = layout.solution (rag);
638 last_page_force = layout.force ();
640 systems_configs_fncounts = scm_cons (scm_cons (lines, config), systems_configs_fncounts);
641 footnote_count += fn_lines;
642 systems = scm_list_tail (systems, line_count);
645 // Now it's safe to make the pages.
646 int page_num = first_page_number + lines_per_page.size () - 1;
647 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
649 SCM lines = scm_caar (s);
650 SCM config = scm_cdar (s);
652 bool bookpart_last_page = (s == systems_configs_fncounts);
653 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
655 SCM page_num_scm = scm_from_int (page_num);
656 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
658 SCM labels = SCM_EOL;
659 if (Grob *line = unsmob_grob (scm_car (l)))
661 System *system = dynamic_cast<System *> (line);
662 labels = system->get_property ("labels");
664 else if (Prob *prob = unsmob_prob (scm_car (l)))
665 labels = prob->get_property ("labels");
667 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
668 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
672 ret = scm_cons (page, ret);
676 // By reversing the table, we ensure that duplicated labels (eg. those
677 // straddling a page turn) will appear in the table with their last
679 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
680 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
684 /* The page-turn-page-breaker needs to have a line-breaker between any two
685 columns with non-NULL page-turn-permission.
687 The optimal-breaker needs to have a line-breaker between any two columns
688 with page-break-permission = 'force.
690 By using a grob predicate, we can accommodate both of these uses.
693 Page_breaking::create_system_list ()
695 SCM specs = book_->get_system_specs ();
696 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
698 if (Paper_score *ps = dynamic_cast<Paper_score *> (unsmob_music_output (scm_car (s))))
700 system_specs_.push_back (System_spec (ps));
704 Prob *pb = unsmob_prob (scm_car (s));
708 system_specs_.push_back (System_spec (pb));
711 if (!system_specs_.size ())
712 system_specs_.push_back (System_spec ());
716 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
718 SCM force_sym = ly_symbol2scm ("force");
720 chunks_.push_back (Break_position ());
721 breaks_.push_back (Break_position ());
723 for (vsize i = 0; i < system_specs_.size (); i++)
725 if (system_specs_[i].pscore_)
727 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
728 vector<Grob *> forced_line_break_cols;
730 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
731 if (scm_is_number (system_count))
733 // With system-count given, the line configuration for
734 // this score is fixed. We need to ensure that chunk
735 // boundaries only occur at line breaks.
736 Constrained_breaking breaking (system_specs_[i].pscore_);
737 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
739 for (vsize j = 0; j < details.size (); j++)
740 forced_line_break_cols.push_back (details[j].last_column_);
743 int last_forced_line_break_idx = 0;
744 vsize forced_line_break_idx = 0;
745 vector<vsize> line_breaker_columns;
746 line_breaker_columns.push_back (0);
748 for (vsize j = 1; j < cols.size (); j++)
750 if (forced_line_break_cols.size ())
752 if (forced_line_break_idx >= forced_line_break_cols.size ()
753 || forced_line_break_cols[forced_line_break_idx] != cols[j])
756 forced_line_break_idx++;
759 bool last = (j == cols.size () - 1);
760 bool break_point = is_break && is_break (cols[j]);
761 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
762 Break_position cur_pos = Break_position (i,
763 line_breaker_columns.size (),
767 // NOTE: even in the breaks_ list, forced_line_count_
768 // refers to the number of lines between a
769 // Break_position and the start of that /chunk/. This
770 // is needed for system_count_bounds to work correctly,
771 // since it mixes Break_positions from breaks_ and
773 if (scm_is_number (system_count))
774 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
776 if (break_point || (i == system_specs_.size () - 1 && last))
777 breaks_.push_back (cur_pos);
778 if (chunk_end || last)
780 chunks_.push_back (cur_pos);
781 last_forced_line_break_idx = forced_line_break_idx;
784 if ((break_point || chunk_end) && !last)
785 line_breaker_columns.push_back (j);
787 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
789 else if (system_specs_[i].prob_)
791 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
792 if (break_point || i == system_specs_.size () - 1)
793 breaks_.push_back (Break_position (i));
795 chunks_.push_back (Break_position (i));
797 /* FIXME: shouldn't we push a Null_breaker or similar dummy
799 line_breaking_.push_back (Constrained_breaking (NULL));
804 vector<Break_position>
805 Page_breaking::chunk_list (vsize start_index, vsize end_index)
807 Break_position start = breaks_[start_index];
808 Break_position end = breaks_[end_index];
811 for (; i < chunks_.size () && chunks_[i] <= start; i++)
814 vector<Break_position> ret;
815 ret.push_back (start);
816 for (; i < chunks_.size () && chunks_[i] < end; i++)
817 ret.push_back (chunks_[i]);
822 // Returns the minimum number of _non-title_ lines.
824 Page_breaking::min_system_count (vsize start, vsize end)
826 vector<Break_position> chunks = chunk_list (start, end);
827 Line_division div = system_count_bounds (chunks, true);
830 for (vsize i = 0; i < div.size (); i++)
835 // Returns the maximum number of _non-title_ lines.
837 Page_breaking::max_system_count (vsize start, vsize end)
839 vector<Break_position> chunks = chunk_list (start, end);
840 Line_division div = system_count_bounds (chunks, false);
843 for (vsize i = 0; i < div.size (); i++)
848 // The numbers returned by this function represent either
849 // the maximum or minimum number of _non-title_ lines
851 Page_breaking::Line_division
852 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
855 assert (chunks.size () >= 2);
858 ret.resize (chunks.size () - 1, 0);
860 for (vsize i = 0; i + 1 < chunks.size (); i++)
862 vsize sys = next_system (chunks[i]);
864 if (chunks[i + 1].forced_line_count_)
865 ret[i] = chunks[i + 1].forced_line_count_;
866 else if (system_specs_[sys].pscore_)
870 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
872 ? line_breaking_[sys].min_system_count (start, end)
873 : line_breaking_[sys].max_system_count (start, end);
881 Page_breaking::set_current_breakpoints (vsize start,
884 Line_division lower_bound,
885 Line_division upper_bound)
887 system_count_ = system_count;
888 current_chunks_ = chunk_list (start, end);
889 current_start_breakpoint_ = start;
890 current_end_breakpoint_ = end;
891 clear_line_details_cache ();
893 if (!lower_bound.size ())
894 lower_bound = system_count_bounds (current_chunks_, true);
895 if (!upper_bound.size ())
896 upper_bound = system_count_bounds (current_chunks_, false);
898 assert (lower_bound.size () == current_chunks_.size () - 1);
899 assert (upper_bound.size () == current_chunks_.size () - 1);
901 Line_division work_in_progress;
902 current_configurations_.clear ();
903 line_divisions_rec (system_count,
908 /* we only consider a constant number of configurations. Otherwise,
909 this becomes slow when there are many small scores. The constant
910 5 is somewhat arbitrary. */
911 if (current_configurations_.size () > 5)
913 vector<pair<Real, vsize> > dems_and_indices;
915 for (vsize i = 0; i < current_configurations_.size (); i++)
917 cache_line_details (i);
919 for (vsize j = 0; j < cached_line_details_.size (); j++)
920 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
921 + cached_line_details_[j].break_penalty_;
923 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
925 vector_sort (dems_and_indices, less<pair<Real, vsize> > ());
927 vector<Line_division> best_5_configurations;
928 for (vsize i = 0; i < 5; i++)
929 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
931 clear_line_details_cache ();
932 current_configurations_ = best_5_configurations;
937 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
939 current_chunks_ = chunk_list (start, end);
940 current_start_breakpoint_ = start;
941 current_end_breakpoint_ = end;
942 clear_line_details_cache ();
946 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
948 vsize sys = next_system (current_chunks_[i]);
950 if (current_chunks_[i + 1].forced_line_count_)
951 div.push_back (current_chunks_[i + 1].forced_line_count_);
952 else if (system_specs_[sys].pscore_)
954 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
955 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
960 system_count_ += div.back ();
962 current_configurations_.clear ();
963 current_configurations_.push_back (div);
967 Page_breaking::current_configuration_count () const
969 return current_configurations_.size ();
973 Page_breaking::cache_line_details (vsize configuration_index)
975 if (cached_configuration_index_ != configuration_index)
977 cached_configuration_index_ = configuration_index;
979 Line_division &div = current_configurations_[configuration_index];
980 uncompressed_line_details_.clear ();
981 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
983 vsize sys = next_system (current_chunks_[i]);
984 if (system_specs_[sys].pscore_)
988 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
990 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
991 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
995 assert (div[i] == 0);
996 uncompressed_line_details_.push_back (system_specs_[sys].prob_
997 ? Line_details (system_specs_[sys].prob_, book_->paper_)
1001 cached_line_details_ = compress_lines (uncompressed_line_details_);
1002 compute_line_heights ();
1007 Page_breaking::clear_line_details_cache ()
1009 cached_configuration_index_ = VPOS;
1010 cached_line_details_.clear ();
1011 uncompressed_line_details_.clear ();
1015 Page_breaking::line_divisions_rec (vsize system_count,
1016 Line_division const &min_sys,
1017 Line_division const &max_sys,
1018 Line_division *cur_division)
1020 vsize my_index = cur_division->size ();
1024 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1026 others_min += min_sys[i];
1027 others_max += max_sys[i];
1029 others_max = min (others_max, (int) system_count);
1030 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
1031 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
1033 if (real_min > real_max || real_min < 0)
1035 /* this should never happen within a recursive call. If it happens
1036 at all, it means that we were called with an unsolvable problem
1037 and we should return an empty result */
1038 assert (my_index == 0);
1042 for (int i = real_min; i <= real_max; i++)
1044 cur_division->push_back (i);
1045 if (my_index == min_sys.size () - 1)
1046 current_configurations_.push_back (*cur_division);
1048 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1049 cur_division->pop_back ();
1054 Page_breaking::compute_line_heights ()
1056 Real prev_hanging = 0;
1057 Real prev_hanging_begin = 0;
1058 Real prev_hanging_rest = 0;
1060 // refpoint_hanging is the y coordinate of the origin of this system.
1061 // It may not be the same as refpoint_extent[UP], which is the
1062 // refpoint of the first spaceable staff in this system.
1063 Real prev_refpoint_hanging = 0;
1064 for (vsize i = 0; i < cached_line_details_.size (); i++)
1066 Line_details &cur = cached_line_details_[i];
1067 Line_shape shape = cur.shape_;
1068 Real a = shape.begin_[UP];
1069 Real b = shape.rest_[UP];
1070 bool title = cur.title_;
1071 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1076 Line_details const &prev = cached_line_details_[i - 1];
1077 if (!cur.tight_spacing_)
1079 ? prev.title_padding_
1081 Real min_dist = title
1082 ? prev.title_min_distance_
1083 : prev.min_distance_;
1084 refpoint_hanging = max (refpoint_hanging + padding,
1085 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1086 + cur.refpoint_extent_[UP] + min_dist);
1089 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1090 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1091 Real hanging = max (hanging_begin, hanging_rest);
1092 cur.tallness_ = hanging - prev_hanging;
1093 prev_hanging = hanging;
1094 prev_hanging_begin = hanging_begin;
1095 prev_hanging_rest = hanging_rest;
1096 prev_refpoint_hanging = refpoint_hanging;
1101 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1104 vsize page_starter = 0;
1105 Real cur_rod_height = 0;
1106 Real cur_spring_height = 0;
1107 Real cur_page_height = page_height (first_page_num, false);
1110 cache_line_details (configuration);
1112 if (cached_line_details_.size ())
1113 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1115 for (vsize i = 0; i < cached_line_details_.size (); i++)
1117 Line_details const &cur = cached_line_details_[i];
1118 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1120 if (cur_rod_height > 0)
1121 ext_len = cur.tallness_;
1123 ext_len = cur.full_height ();
1125 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1126 Real next_rod_height = cur_rod_height + ext_len;
1127 Real next_spring_height = cur_spring_height + spring_len;
1128 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1129 + min_whitespace_at_bottom_of_page (cur);
1130 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1132 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1133 || too_many_lines (next_line_count)
1134 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1136 line_count = cur.compressed_nontitle_lines_count_;
1137 cur_rod_height = cur.full_height ();
1138 cur_spring_height = 0;
1141 cur_page_height = page_height (first_page_num + ret, false);
1142 cur_page_height -= min_whitespace_at_top_of_page (cur);
1148 cur_rod_height = next_rod_height;
1149 cur_spring_height = next_spring_height;
1150 line_count = next_line_count;
1154 /* there are two potential problems with the last page (because we didn't know
1155 it was the last page until after we managed to fit all the systems to it):
1156 - we are ragged-last but the last page has a compressed spring
1157 - the value returned by page_height (num, true) is smaller than the
1158 value returned by page_height (num, false) and it causes the page not to
1161 In either case, we just need to add one more page. This is because the last
1162 line will always fit on the extra page and by adding one more page to the
1163 end, the previous page is no longer the last page, so our previous
1164 calculations that treated it as a non-last page were ok.
1169 cur_page_height = page_height (first_page_num + ret - 1, true);
1170 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1171 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1173 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1174 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1175 && cur_height > cur_page_height
1176 /* don't increase the page count if the last page had only one system */
1177 && cur_rod_height > cached_line_details_.back ().full_height ())
1179 assert (ret <= cached_line_details_.size ());
1185 // If systems_per_page_ is positive, we don't really try to space on N pages;
1186 // we just put the requested number of systems on each page and penalize
1187 // if the result doesn't have N pages.
1189 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1191 Page_spacing_result ret;
1193 if (systems_per_page_ > 0)
1195 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1196 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1200 cache_line_details (configuration);
1201 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1202 && n <= cached_line_details_.size ());
1205 programming_error ("number of pages is out of bounds");
1207 if (n == 1 && valid_n)
1208 ret = space_systems_on_1_page (cached_line_details_,
1209 page_height (first_page_num, is_last ()),
1210 ragged () || (is_last () && ragged_last ()));
1211 else if (n == 2 && valid_n)
1212 ret = space_systems_on_2_pages (configuration, first_page_num);
1215 Page_spacer ps (cached_line_details_, first_page_num, this);
1219 return finalize_spacing_result (configuration, ret);
1223 Page_breaking::blank_page_penalty () const
1228 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1229 else if (ends_score ())
1230 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1232 penalty_sym = ly_symbol2scm ("blank-page-force");
1234 Break_position const &pos = breaks_[current_end_breakpoint_];
1235 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1236 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1238 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1241 // If systems_per_page_ is positive, we don't really try to space on N
1242 // or N+1 pages; see the comment to space_systems_on_n_pages.
1244 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1245 Real penalty_for_fewer_pages)
1247 Page_spacing_result n_res;
1248 Page_spacing_result m_res;
1250 if (systems_per_page_ > 0)
1252 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1253 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1257 cache_line_details (configuration);
1258 vsize min_p_count = min_page_count (configuration, first_page_num);
1259 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1262 programming_error ("both page counts are out of bounds");
1264 if (n == 1 && valid_n)
1266 bool rag = ragged () || (is_last () && ragged_last ());
1267 Real height = page_height (first_page_num, is_last ());
1269 if (1 >= min_p_count)
1270 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1271 if (1 < cached_line_details_.size ())
1272 m_res = space_systems_on_2_pages (configuration, first_page_num);
1276 Page_spacer ps (cached_line_details_, first_page_num, this);
1278 if (n >= min_p_count || !valid_n)
1279 n_res = ps.solve (n);
1280 if (n < cached_line_details_.size () || !valid_n)
1281 m_res = ps.solve (n + 1);
1284 m_res = finalize_spacing_result (configuration, m_res);
1285 n_res = finalize_spacing_result (configuration, n_res);
1287 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1288 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1290 if (n_res.force_.size ())
1291 n_res.force_.back () += penalty_for_fewer_pages;
1293 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1297 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1299 if (systems_per_page_ > 0)
1300 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1302 cache_line_details (configuration);
1303 Page_spacer ps (cached_line_details_, first_page_num, this);
1305 return finalize_spacing_result (configuration, ps.solve ());
1309 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1310 vsize first_page_num)
1312 Page_spacing_result res;
1313 Page_spacing space (page_height (first_page_num, false), this);
1316 vsize page_first_line = 0;
1318 cache_line_details (configuration);
1319 while (line < cached_line_details_.size ())
1323 space.resize (page_height (first_page_num + page, false));
1325 int system_count_on_this_page = 0;
1326 while (system_count_on_this_page < systems_per_page_
1327 && line < cached_line_details_.size ())
1329 Line_details const &cur_line = cached_line_details_[line];
1330 space.append_system (cur_line);
1331 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1334 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1338 res.systems_per_page_.push_back (line - page_first_line);
1340 res.force_.push_back (space.force_);
1341 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1342 if (system_count_on_this_page != systems_per_page_)
1344 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1345 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1346 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1349 page_first_line = line;
1352 /* Recalculate forces for the last page because we know now that is
1353 really the last page. */
1354 space.resize (page_height (first_page_num + page, true));
1355 res.force_.back () = space.force_;
1356 return finalize_spacing_result (configuration, res);
1360 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1362 // TODO: add support for min/max-systems-per-page.
1363 Page_spacing_result res;
1365 vsize page_first_line = 0;
1366 Page_spacing space (page_height (first_page_num, false), this);
1368 cache_line_details (configuration);
1369 for (vsize line = 0; line < cached_line_details_.size (); line++)
1371 Real prev_force = space.force_;
1372 space.append_system (cached_line_details_[line]);
1373 if ((line > page_first_line)
1374 && (isinf (space.force_)
1376 && (cached_line_details_[line - 1].page_permission_ == ly_symbol2scm ("force")))))
1378 res.systems_per_page_.push_back (line - page_first_line);
1379 res.force_.push_back (prev_force);
1380 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1382 space.resize (page_height (first_page_num + page, false));
1384 space.append_system (cached_line_details_[line]);
1385 page_first_line = line;
1388 if (line == cached_line_details_.size () - 1)
1390 /* This is the last line */
1391 /* When the last page height was computed, we did not know yet that it
1392 * was the last one. If the systems put on it don't fit anymore, the last
1393 * system is moved to a new page */
1394 space.resize (page_height (first_page_num + page, true));
1395 if ((line > page_first_line) && (isinf (space.force_)))
1397 res.systems_per_page_.push_back (line - page_first_line);
1398 res.force_.push_back (prev_force);
1399 /* the last page containing the last line */
1400 space.resize (page_height (first_page_num + page + 1, true));
1402 space.append_system (cached_line_details_[line]);
1403 res.systems_per_page_.push_back (1);
1404 res.force_.push_back (space.force_);
1405 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1406 res.penalty_ += cached_line_details_[line].page_penalty_;
1410 res.systems_per_page_.push_back (line + 1 - page_first_line);
1411 res.force_.push_back (space.force_);
1412 res.penalty_ += cached_line_details_[line].page_penalty_;
1416 return finalize_spacing_result (configuration, res);
1419 /* Calculate demerits and fix res.systems_per_page_ so that
1420 it refers to the original line numbers, not the ones given by compress_lines (). */
1422 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1424 if (res.force_.empty ())
1427 cache_line_details (configuration);
1428 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1430 Real line_force = 0;
1431 Real line_penalty = 0;
1432 Real page_demerits = res.penalty_;
1433 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1435 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1437 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1438 line_penalty += uncompressed_line_details_[i].break_penalty_;
1441 for (vsize i = 0; i < res.force_.size (); i++)
1443 Real f = res.force_[i];
1445 page_demerits += min (f * f, BAD_SPACING_PENALTY);
1448 /* for a while we tried averaging page and line forces across pages instead
1449 of summing them, but it caused a problem: if there is a single page
1450 with a very bad page force (for example because of a forced page break),
1451 the page breaker will put in a _lot_ of pages so that the bad force
1452 becomes averaged out over many pages. */
1453 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1458 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1459 are by far the most common cases, we have special functions for them.
1461 space_systems_on_1_page has a different calling convention than most of the
1462 space_systems functions. This is because space_systems_on_1_page is (unlike
1463 the other space_systems functions) sometimes called on subsets of a full
1466 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1468 Page_spacing space (page_height, this);
1469 Page_spacing_result ret;
1472 for (vsize i = 0; i < lines.size (); i++)
1474 space.append_system (lines[i]);
1475 line_count += lines[i].compressed_nontitle_lines_count_;
1478 ret.systems_per_page_.push_back (lines.size ());
1479 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1480 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1481 ret.system_count_status_ |= line_count_status (line_count);
1483 /* don't do finalize_spacing_result () because we are only an internal function */
1488 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1490 Real page1_height = page_height (first_page_num, false);
1491 Real page2_height = page_height (first_page_num + 1, is_last ());
1492 bool ragged1 = ragged ();
1493 bool ragged2 = ragged () || (is_last () && ragged_last ());
1495 /* if there is a forced break, this reduces to 2 1-page problems */
1496 cache_line_details (configuration);
1497 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1498 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1500 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1501 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1502 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1503 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1505 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1506 p1.force_.push_back (p2.force_[0]);
1507 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1508 p1.system_count_status_ |= p2.system_count_status_;
1512 vector<Real> page1_force;
1513 vector<Real> page2_force;
1515 // page1_penalty and page2_penalty store the penalties based
1516 // on min-systems-per-page and max-systems-per-page.
1517 vector<Real> page1_penalty;
1518 vector<Real> page2_penalty;
1520 // page1_status and page2_status keep track of whether the min-systems-per-page
1521 // and max-systems-per-page constraints are satisfied.
1522 vector<int> page1_status;
1523 vector<int> page2_status;
1525 Page_spacing page1 (page1_height, this);
1526 Page_spacing page2 (page2_height, this);
1527 int page1_line_count = 0;
1528 int page2_line_count = 0;
1530 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1531 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1532 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1533 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1534 page1_status.resize (cached_line_details_.size () - 1, 0);
1535 page2_status.resize (cached_line_details_.size () - 1, 0);
1537 /* find the page 1 and page 2 forces for each page-breaking position */
1538 for (vsize i = 0; i < page1_force.size (); i++)
1540 page1.append_system (cached_line_details_[i]);
1541 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1542 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1543 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1545 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1546 page1_penalty[i] = line_count_penalty (page1_line_count);
1547 page1_status[i] = line_count_status (page1_line_count);
1550 page2_force[page2_force.size () - 1 - i]
1551 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1553 page2_force[page2_force.size () - 1 - i] = page2.force_;
1554 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1555 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1558 /* find the position that minimises the sum of the page forces */
1559 vsize best_sys_count = 1;
1560 Real best_demerits = infinity_f;
1561 for (vsize i = 0; i < page1_force.size (); i++)
1563 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1565 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1566 // constraints. That is, we penalize harshly when they don't happen
1567 // but we don't completely reject.
1569 + page1_penalty[i] + page2_penalty[i]
1570 + cached_line_details_[i + 1].page_penalty_
1571 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1572 if (dem < best_demerits)
1574 best_demerits = dem;
1575 best_sys_count = i + 1;
1579 Page_spacing_result ret;
1580 ret.systems_per_page_.push_back (best_sys_count);
1581 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1582 ret.force_.push_back (page1_force[best_sys_count - 1]);
1583 ret.force_.push_back (page2_force[best_sys_count - 1]);
1584 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1585 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1586 + cached_line_details_.back ().page_penalty_
1587 + cached_line_details_.back ().turn_penalty_
1588 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1590 /* don't do finalize_spacing_result () because we are only an internal function */
1595 Page_breaking::all_lines_stretched (vsize configuration)
1597 cache_line_details (configuration);
1598 for (vsize i = 0; i < cached_line_details_.size (); i++)
1599 if (cached_line_details_[i].force_ < 0)
1605 Page_breaking::Line_division
1606 Page_breaking::current_configuration (vsize configuration_index) const
1608 return current_configurations_[configuration_index];
1612 Page_breaking::is_last () const
1614 return current_end_breakpoint_ == last_break_position ();
1618 Page_breaking::ends_score () const
1620 return breaks_[current_end_breakpoint_].score_ender_;
1624 Page_breaking::last_break_position () const
1626 return breaks_.size () - 1;
1629 // This gives the minimum distance between the top of the
1630 // printable area (ie. the bottom of the top-margin) and
1631 // the extent box of the topmost system.
1633 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1635 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1637 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1639 Real min_distance = -infinity_f;
1642 Page_layout_problem::read_spacing_spec (first_system_spacing,
1644 ly_symbol2scm ("minimum-distance"));
1645 Page_layout_problem::read_spacing_spec (first_system_spacing,
1647 ly_symbol2scm ("padding"));
1649 // FIXME: take into account the height of the header
1650 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1651 return max (0.0, max (padding, min_distance - translate));
1655 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1657 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1658 Real min_distance = -infinity_f;
1661 Page_layout_problem::read_spacing_spec (last_system_spacing,
1663 ly_symbol2scm ("minimum-distance"));
1664 Page_layout_problem::read_spacing_spec (last_system_spacing,
1666 ly_symbol2scm ("padding"));
1668 // FIXME: take into account the height of the footer
1669 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1670 return max (0.0, max (padding, min_distance + translate));
1674 Page_breaking::orphan_penalty () const
1676 return orphan_penalty_;