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 (ret));
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 = scm_reverse (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);
567 // Create the page and draw it.
568 SCM page = make_page (page_num, last);
569 SCM page_module = scm_c_resolve_module ("scm page");
570 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
571 page_stencil = scm_variable_ref (page_stencil);
573 Prob *p = unsmob_prob (page);
574 p->set_property ("lines", paper_systems);
575 p->set_property ("configuration", configuration);
577 Stencil *foot_p = unsmob_stencil (p->get_property ("foot-stencil"));
578 Stencil foot = foot_p ? *foot_p : Stencil ();
580 SCM footnotes = Page_layout_problem::get_footnotes_from_lines (systems);
582 foot = Page_layout_problem::add_footnotes_to_footer (footnotes, foot, book_);
584 p->set_property ("foot-stencil", foot.smobbed_copy ());
585 scm_apply_1 (page_stencil, page, SCM_EOL);
591 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
593 if (scm_is_null (systems))
596 int first_page_number
597 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
599 bool reset_footnotes_on_new_page = to_boolean (book_->top_paper ()->c_variable ("reset-footnotes-on-new-page"));
600 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
601 if (label_page_table == SCM_UNDEFINED)
602 label_page_table = SCM_EOL;
604 // Build a list of (systems configuration . footnote-count) triples.
605 // Note that we lay out
606 // the staves and find the configurations before drawing anything. Some
607 // grobs (like tuplet brackets) look at their neighbours while drawing
608 // themselves. If this happens before the neighbouring staves have
609 // been laid out, bad side-effects could happen (in particular,
610 // Align_interface::align_to_ideal_distances might be called).
611 SCM systems_configs_fncounts = SCM_EOL;
612 vsize footnote_count = 0;
613 Real last_page_force = 0;
615 for (vsize i = 0; i < lines_per_page.size (); i++)
617 int page_num = i + first_page_number;
618 bool bookpart_last_page = (i == lines_per_page.size () - 1);
619 bool rag = ragged () || (bookpart_last_page && ragged_last ());
620 SCM line_count = scm_from_int (lines_per_page[i]);
621 SCM lines = scm_list_head (systems, line_count);
622 int fn_lines = Page_layout_problem::get_footnote_count (lines);
623 Page_layout_problem::add_footnotes_to_lines (lines, reset_footnotes_on_new_page ? 0 : footnote_count, book_);
625 SCM config = SCM_EOL;
626 SCM dummy_page = make_page (page_num, bookpart_last_page);
627 Page_layout_problem layout (book_, dummy_page, lines);
628 if (!scm_is_pair (systems))
630 else if (rag && !ragged ())
631 // If we're ragged-last but not ragged, make the last page
632 // have the same force as the previous page.
633 config = layout.fixed_force_solution (last_page_force);
635 config = layout.solution (rag);
637 last_page_force = layout.force ();
639 systems_configs_fncounts = scm_cons (scm_cons (lines, config), systems_configs_fncounts);
640 footnote_count += fn_lines;
641 systems = scm_list_tail (systems, line_count);
644 // Now it's safe to make the pages.
645 int page_num = first_page_number + lines_per_page.size () - 1;
646 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
648 SCM lines = scm_caar (s);
649 SCM config = scm_cdar (s);
651 bool bookpart_last_page = (s == systems_configs_fncounts);
652 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
654 SCM page_num_scm = scm_from_int (page_num);
655 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
657 SCM labels = SCM_EOL;
658 if (Grob *line = unsmob_grob (scm_car (l)))
660 System *system = dynamic_cast<System *> (line);
661 labels = system->get_property ("labels");
663 else if (Prob *prob = unsmob_prob (scm_car (l)))
664 labels = prob->get_property ("labels");
666 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
667 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
671 ret = scm_cons (page, ret);
675 // By reversing the table, we ensure that duplicated labels (eg. those
676 // straddling a page turn) will appear in the table with their last
678 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
679 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
683 /* The page-turn-page-breaker needs to have a line-breaker between any two
684 columns with non-NULL page-turn-permission.
686 The optimal-breaker needs to have a line-breaker between any two columns
687 with page-break-permission = 'force.
689 By using a grob predicate, we can accommodate both of these uses.
692 Page_breaking::create_system_list ()
694 SCM specs = book_->get_system_specs ();
695 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
697 if (Paper_score *ps = dynamic_cast<Paper_score *> (unsmob_music_output (scm_car (s))))
699 system_specs_.push_back (System_spec (ps));
703 Prob *pb = unsmob_prob (scm_car (s));
707 system_specs_.push_back (System_spec (pb));
710 if (!system_specs_.size ())
711 system_specs_.push_back (System_spec ());
715 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
717 SCM force_sym = ly_symbol2scm ("force");
719 chunks_.push_back (Break_position ());
720 breaks_.push_back (Break_position ());
722 for (vsize i = 0; i < system_specs_.size (); i++)
724 if (system_specs_[i].pscore_)
726 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
727 vector<Grob *> forced_line_break_cols;
729 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
730 if (scm_is_number (system_count))
732 // With system-count given, the line configuration for
733 // this score is fixed. We need to ensure that chunk
734 // boundaries only occur at line breaks.
735 Constrained_breaking breaking (system_specs_[i].pscore_);
736 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
738 for (vsize j = 0; j < details.size (); j++)
739 forced_line_break_cols.push_back (details[j].last_column_);
742 int last_forced_line_break_idx = 0;
743 vsize forced_line_break_idx = 0;
744 vector<vsize> line_breaker_columns;
745 line_breaker_columns.push_back (0);
747 for (vsize j = 1; j < cols.size (); j++)
749 if (forced_line_break_cols.size ())
751 if (forced_line_break_idx >= forced_line_break_cols.size ()
752 || forced_line_break_cols[forced_line_break_idx] != cols[j])
755 forced_line_break_idx++;
758 bool last = (j == cols.size () - 1);
759 bool break_point = is_break && is_break (cols[j]);
760 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
761 Break_position cur_pos = Break_position (i,
762 line_breaker_columns.size (),
766 // NOTE: even in the breaks_ list, forced_line_count_
767 // refers to the number of lines between a
768 // Break_position and the start of that /chunk/. This
769 // is needed for system_count_bounds to work correctly,
770 // since it mixes Break_positions from breaks_ and
772 if (scm_is_number (system_count))
773 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
775 if (break_point || (i == system_specs_.size () - 1 && last))
776 breaks_.push_back (cur_pos);
777 if (chunk_end || last)
779 chunks_.push_back (cur_pos);
780 last_forced_line_break_idx = forced_line_break_idx;
783 if ((break_point || chunk_end) && !last)
784 line_breaker_columns.push_back (j);
786 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
788 else if (system_specs_[i].prob_)
790 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
791 if (break_point || i == system_specs_.size () - 1)
792 breaks_.push_back (Break_position (i));
794 chunks_.push_back (Break_position (i));
796 /* FIXME: shouldn't we push a Null_breaker or similar dummy
798 line_breaking_.push_back (Constrained_breaking (NULL));
803 vector<Break_position>
804 Page_breaking::chunk_list (vsize start_index, vsize end_index)
806 Break_position start = breaks_[start_index];
807 Break_position end = breaks_[end_index];
810 for (; i < chunks_.size () && chunks_[i] <= start; i++)
813 vector<Break_position> ret;
814 ret.push_back (start);
815 for (; i < chunks_.size () && chunks_[i] < end; i++)
816 ret.push_back (chunks_[i]);
821 // Returns the minimum number of _non-title_ lines.
823 Page_breaking::min_system_count (vsize start, vsize end)
825 vector<Break_position> chunks = chunk_list (start, end);
826 Line_division div = system_count_bounds (chunks, true);
829 for (vsize i = 0; i < div.size (); i++)
834 // Returns the maximum number of _non-title_ lines.
836 Page_breaking::max_system_count (vsize start, vsize end)
838 vector<Break_position> chunks = chunk_list (start, end);
839 Line_division div = system_count_bounds (chunks, false);
842 for (vsize i = 0; i < div.size (); i++)
847 // The numbers returned by this function represent either
848 // the maximum or minimum number of _non-title_ lines
850 Page_breaking::Line_division
851 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
854 assert (chunks.size () >= 2);
857 ret.resize (chunks.size () - 1, 0);
859 for (vsize i = 0; i + 1 < chunks.size (); i++)
861 vsize sys = next_system (chunks[i]);
863 if (chunks[i + 1].forced_line_count_)
864 ret[i] = chunks[i + 1].forced_line_count_;
865 else if (system_specs_[sys].pscore_)
869 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
871 ? line_breaking_[sys].min_system_count (start, end)
872 : line_breaking_[sys].max_system_count (start, end);
880 Page_breaking::set_current_breakpoints (vsize start,
883 Line_division lower_bound,
884 Line_division upper_bound)
886 system_count_ = system_count;
887 current_chunks_ = chunk_list (start, end);
888 current_start_breakpoint_ = start;
889 current_end_breakpoint_ = end;
890 clear_line_details_cache ();
892 if (!lower_bound.size ())
893 lower_bound = system_count_bounds (current_chunks_, true);
894 if (!upper_bound.size ())
895 upper_bound = system_count_bounds (current_chunks_, false);
897 assert (lower_bound.size () == current_chunks_.size () - 1);
898 assert (upper_bound.size () == current_chunks_.size () - 1);
900 Line_division work_in_progress;
901 current_configurations_.clear ();
902 line_divisions_rec (system_count,
907 /* we only consider a constant number of configurations. Otherwise,
908 this becomes slow when there are many small scores. The constant
909 5 is somewhat arbitrary. */
910 if (current_configurations_.size () > 5)
912 vector<pair<Real, vsize> > dems_and_indices;
914 for (vsize i = 0; i < current_configurations_.size (); i++)
916 cache_line_details (i);
918 for (vsize j = 0; j < cached_line_details_.size (); j++)
919 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
920 + cached_line_details_[j].break_penalty_;
922 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
924 vector_sort (dems_and_indices, less<pair<Real, vsize> > ());
926 vector<Line_division> best_5_configurations;
927 for (vsize i = 0; i < 5; i++)
928 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
930 clear_line_details_cache ();
931 current_configurations_ = best_5_configurations;
936 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
938 current_chunks_ = chunk_list (start, end);
939 current_start_breakpoint_ = start;
940 current_end_breakpoint_ = end;
941 clear_line_details_cache ();
945 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
947 vsize sys = next_system (current_chunks_[i]);
949 if (current_chunks_[i + 1].forced_line_count_)
950 div.push_back (current_chunks_[i + 1].forced_line_count_);
951 else if (system_specs_[sys].pscore_)
953 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
954 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
959 system_count_ += div.back ();
961 current_configurations_.clear ();
962 current_configurations_.push_back (div);
966 Page_breaking::current_configuration_count () const
968 return current_configurations_.size ();
972 Page_breaking::cache_line_details (vsize configuration_index)
974 if (cached_configuration_index_ != configuration_index)
976 cached_configuration_index_ = configuration_index;
978 Line_division &div = current_configurations_[configuration_index];
979 uncompressed_line_details_.clear ();
980 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
982 vsize sys = next_system (current_chunks_[i]);
983 if (system_specs_[sys].pscore_)
987 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
989 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
990 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
994 assert (div[i] == 0);
995 uncompressed_line_details_.push_back (system_specs_[sys].prob_
996 ? Line_details (system_specs_[sys].prob_, book_->paper_)
1000 cached_line_details_ = compress_lines (uncompressed_line_details_);
1001 compute_line_heights ();
1006 Page_breaking::clear_line_details_cache ()
1008 cached_configuration_index_ = VPOS;
1009 cached_line_details_.clear ();
1010 uncompressed_line_details_.clear ();
1014 Page_breaking::line_divisions_rec (vsize system_count,
1015 Line_division const &min_sys,
1016 Line_division const &max_sys,
1017 Line_division *cur_division)
1019 vsize my_index = cur_division->size ();
1023 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1025 others_min += min_sys[i];
1026 others_max += max_sys[i];
1028 others_max = min (others_max, (int) system_count);
1029 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
1030 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
1032 if (real_min > real_max || real_min < 0)
1034 /* this should never happen within a recursive call. If it happens
1035 at all, it means that we were called with an unsolvable problem
1036 and we should return an empty result */
1037 assert (my_index == 0);
1041 for (int i = real_min; i <= real_max; i++)
1043 cur_division->push_back (i);
1044 if (my_index == min_sys.size () - 1)
1045 current_configurations_.push_back (*cur_division);
1047 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1048 cur_division->pop_back ();
1053 Page_breaking::compute_line_heights ()
1055 Real prev_hanging = 0;
1056 Real prev_hanging_begin = 0;
1057 Real prev_hanging_rest = 0;
1059 // refpoint_hanging is the y coordinate of the origin of this system.
1060 // It may not be the same as refpoint_extent[UP], which is the
1061 // refpoint of the first spaceable staff in this system.
1062 Real prev_refpoint_hanging = 0;
1063 for (vsize i = 0; i < cached_line_details_.size (); i++)
1065 Line_details &cur = cached_line_details_[i];
1066 Line_shape shape = cur.shape_;
1067 Real a = shape.begin_[UP];
1068 Real b = shape.rest_[UP];
1069 bool title = cur.title_;
1070 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1075 Line_details const &prev = cached_line_details_[i - 1];
1076 if (!cur.tight_spacing_)
1078 ? prev.title_padding_
1080 Real min_dist = title
1081 ? prev.title_min_distance_
1082 : prev.min_distance_;
1083 refpoint_hanging = max (refpoint_hanging + padding,
1084 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1085 + cur.refpoint_extent_[UP] + min_dist);
1088 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1089 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1090 Real hanging = max (hanging_begin, hanging_rest);
1091 cur.tallness_ = hanging - prev_hanging;
1092 prev_hanging = hanging;
1093 prev_hanging_begin = hanging_begin;
1094 prev_hanging_rest = hanging_rest;
1095 prev_refpoint_hanging = refpoint_hanging;
1100 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1103 vsize page_starter = 0;
1104 Real cur_rod_height = 0;
1105 Real cur_spring_height = 0;
1106 Real cur_page_height = page_height (first_page_num, false);
1109 cache_line_details (configuration);
1111 if (cached_line_details_.size ())
1112 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1114 for (vsize i = 0; i < cached_line_details_.size (); i++)
1116 Line_details const &cur = cached_line_details_[i];
1117 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1119 if (cur_rod_height > 0)
1120 ext_len = cur.tallness_;
1122 ext_len = cur.full_height ();
1124 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1125 Real next_rod_height = cur_rod_height + ext_len;
1126 Real next_spring_height = cur_spring_height + spring_len;
1127 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1128 + min_whitespace_at_bottom_of_page (cur);
1129 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1131 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1132 || too_many_lines (next_line_count)
1133 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1135 line_count = cur.compressed_nontitle_lines_count_;
1136 cur_rod_height = cur.full_height ();
1137 cur_spring_height = 0;
1140 cur_page_height = page_height (first_page_num + ret, false);
1141 cur_page_height -= min_whitespace_at_top_of_page (cur);
1147 cur_rod_height = next_rod_height;
1148 cur_spring_height = next_spring_height;
1149 line_count = next_line_count;
1153 /* there are two potential problems with the last page (because we didn't know
1154 it was the last page until after we managed to fit all the systems to it):
1155 - we are ragged-last but the last page has a compressed spring
1156 - the value returned by page_height (num, true) is smaller than the
1157 value returned by page_height (num, false) and it causes the page not to
1160 In either case, we just need to add one more page. This is because the last
1161 line will always fit on the extra page and by adding one more page to the
1162 end, the previous page is no longer the last page, so our previous
1163 calculations that treated it as a non-last page were ok.
1168 cur_page_height = page_height (first_page_num + ret - 1, true);
1169 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1170 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1172 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1173 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1174 && cur_height > cur_page_height
1175 /* don't increase the page count if the last page had only one system */
1176 && cur_rod_height > cached_line_details_.back ().full_height ())
1178 assert (ret <= cached_line_details_.size ());
1184 // If systems_per_page_ is positive, we don't really try to space on N pages;
1185 // we just put the requested number of systems on each page and penalize
1186 // if the result doesn't have N pages.
1188 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1190 Page_spacing_result ret;
1192 if (systems_per_page_ > 0)
1194 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1195 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1199 cache_line_details (configuration);
1200 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1201 && n <= cached_line_details_.size ());
1204 programming_error ("number of pages is out of bounds");
1206 if (n == 1 && valid_n)
1207 ret = space_systems_on_1_page (cached_line_details_,
1208 page_height (first_page_num, is_last ()),
1209 ragged () || (is_last () && ragged_last ()));
1210 else if (n == 2 && valid_n)
1211 ret = space_systems_on_2_pages (configuration, first_page_num);
1214 Page_spacer ps (cached_line_details_, first_page_num, this);
1218 return finalize_spacing_result (configuration, ret);
1222 Page_breaking::blank_page_penalty () const
1227 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1228 else if (ends_score ())
1229 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1231 penalty_sym = ly_symbol2scm ("blank-page-force");
1233 Break_position const &pos = breaks_[current_end_breakpoint_];
1234 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1235 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1237 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1240 // If systems_per_page_ is positive, we don't really try to space on N
1241 // or N+1 pages; see the comment to space_systems_on_n_pages.
1243 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1244 Real penalty_for_fewer_pages)
1246 Page_spacing_result n_res;
1247 Page_spacing_result m_res;
1249 if (systems_per_page_ > 0)
1251 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1252 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1256 cache_line_details (configuration);
1257 vsize min_p_count = min_page_count (configuration, first_page_num);
1258 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1261 programming_error ("both page counts are out of bounds");
1263 if (n == 1 && valid_n)
1265 bool rag = ragged () || (is_last () && ragged_last ());
1266 Real height = page_height (first_page_num, is_last ());
1268 if (1 >= min_p_count)
1269 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1270 if (1 < cached_line_details_.size ())
1271 m_res = space_systems_on_2_pages (configuration, first_page_num);
1275 Page_spacer ps (cached_line_details_, first_page_num, this);
1277 if (n >= min_p_count || !valid_n)
1278 n_res = ps.solve (n);
1279 if (n < cached_line_details_.size () || !valid_n)
1280 m_res = ps.solve (n + 1);
1283 m_res = finalize_spacing_result (configuration, m_res);
1284 n_res = finalize_spacing_result (configuration, n_res);
1286 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1287 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1289 if (n_res.force_.size ())
1290 n_res.force_.back () += penalty_for_fewer_pages;
1292 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1296 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1298 if (systems_per_page_ > 0)
1299 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1301 cache_line_details (configuration);
1302 Page_spacer ps (cached_line_details_, first_page_num, this);
1304 return finalize_spacing_result (configuration, ps.solve ());
1308 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1309 vsize first_page_num)
1311 Page_spacing_result res;
1312 Page_spacing space (page_height (first_page_num, false), this);
1315 vsize page_first_line = 0;
1317 cache_line_details (configuration);
1318 while (line < cached_line_details_.size ())
1322 space.resize (page_height (first_page_num + page, false));
1324 int system_count_on_this_page = 0;
1325 while (system_count_on_this_page < systems_per_page_
1326 && line < cached_line_details_.size ())
1328 Line_details const &cur_line = cached_line_details_[line];
1329 space.append_system (cur_line);
1330 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1333 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1337 res.systems_per_page_.push_back (line - page_first_line);
1339 res.force_.push_back (space.force_);
1340 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1341 if (system_count_on_this_page != systems_per_page_)
1343 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1344 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1345 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1348 page_first_line = line;
1351 /* Recalculate forces for the last page because we know now that is
1352 really the last page. */
1353 space.resize (page_height (first_page_num + page, true));
1354 res.force_.back () = space.force_;
1355 return finalize_spacing_result (configuration, res);
1359 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1361 // TODO: add support for min/max-systems-per-page.
1362 Page_spacing_result res;
1364 vsize page_first_line = 0;
1365 Page_spacing space (page_height (first_page_num, false), this);
1367 cache_line_details (configuration);
1368 for (vsize line = 0; line < cached_line_details_.size (); line++)
1370 Real prev_force = space.force_;
1371 space.append_system (cached_line_details_[line]);
1372 if ((line > page_first_line)
1373 && (isinf (space.force_)
1375 && (cached_line_details_[line - 1].page_permission_ == ly_symbol2scm ("force")))))
1377 res.systems_per_page_.push_back (line - page_first_line);
1378 res.force_.push_back (prev_force);
1379 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1381 space.resize (page_height (first_page_num + page, false));
1383 space.append_system (cached_line_details_[line]);
1384 page_first_line = line;
1387 if (line == cached_line_details_.size () - 1)
1389 /* This is the last line */
1390 /* When the last page height was computed, we did not know yet that it
1391 * was the last one. If the systems put on it don't fit anymore, the last
1392 * system is moved to a new page */
1393 space.resize (page_height (first_page_num + page, true));
1394 if ((line > page_first_line) && (isinf (space.force_)))
1396 res.systems_per_page_.push_back (line - page_first_line);
1397 res.force_.push_back (prev_force);
1398 /* the last page containing the last line */
1399 space.resize (page_height (first_page_num + page + 1, true));
1401 space.append_system (cached_line_details_[line]);
1402 res.systems_per_page_.push_back (1);
1403 res.force_.push_back (space.force_);
1404 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1405 res.penalty_ += cached_line_details_[line].page_penalty_;
1409 res.systems_per_page_.push_back (line + 1 - page_first_line);
1410 res.force_.push_back (space.force_);
1411 res.penalty_ += cached_line_details_[line].page_penalty_;
1415 return finalize_spacing_result (configuration, res);
1418 /* Calculate demerits and fix res.systems_per_page_ so that
1419 it refers to the original line numbers, not the ones given by compress_lines (). */
1421 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1423 if (res.force_.empty ())
1426 cache_line_details (configuration);
1427 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1429 Real line_force = 0;
1430 Real line_penalty = 0;
1431 Real page_demerits = res.penalty_;
1432 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1434 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1436 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1437 line_penalty += uncompressed_line_details_[i].break_penalty_;
1440 for (vsize i = 0; i < res.force_.size (); i++)
1442 Real f = res.force_[i];
1444 page_demerits += min (f * f, BAD_SPACING_PENALTY);
1447 /* for a while we tried averaging page and line forces across pages instead
1448 of summing them, but it caused a problem: if there is a single page
1449 with a very bad page force (for example because of a forced page break),
1450 the page breaker will put in a _lot_ of pages so that the bad force
1451 becomes averaged out over many pages. */
1452 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1457 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1458 are by far the most common cases, we have special functions for them.
1460 space_systems_on_1_page has a different calling convention than most of the
1461 space_systems functions. This is because space_systems_on_1_page is (unlike
1462 the other space_systems functions) sometimes called on subsets of a full
1465 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1467 Page_spacing space (page_height, this);
1468 Page_spacing_result ret;
1471 for (vsize i = 0; i < lines.size (); i++)
1473 space.append_system (lines[i]);
1474 line_count += lines[i].compressed_nontitle_lines_count_;
1477 ret.systems_per_page_.push_back (lines.size ());
1478 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1479 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1480 ret.system_count_status_ |= line_count_status (line_count);
1482 /* don't do finalize_spacing_result () because we are only an internal function */
1487 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1489 Real page1_height = page_height (first_page_num, false);
1490 Real page2_height = page_height (first_page_num + 1, is_last ());
1491 bool ragged1 = ragged ();
1492 bool ragged2 = ragged () || (is_last () && ragged_last ());
1494 /* if there is a forced break, this reduces to 2 1-page problems */
1495 cache_line_details (configuration);
1496 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1497 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1499 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1500 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1501 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1502 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1504 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1505 p1.force_.push_back (p2.force_[0]);
1506 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1507 p1.system_count_status_ |= p2.system_count_status_;
1511 vector<Real> page1_force;
1512 vector<Real> page2_force;
1514 // page1_penalty and page2_penalty store the penalties based
1515 // on min-systems-per-page and max-systems-per-page.
1516 vector<Real> page1_penalty;
1517 vector<Real> page2_penalty;
1519 // page1_status and page2_status keep track of whether the min-systems-per-page
1520 // and max-systems-per-page constraints are satisfied.
1521 vector<int> page1_status;
1522 vector<int> page2_status;
1524 Page_spacing page1 (page1_height, this);
1525 Page_spacing page2 (page2_height, this);
1526 int page1_line_count = 0;
1527 int page2_line_count = 0;
1529 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1530 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1531 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1532 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1533 page1_status.resize (cached_line_details_.size () - 1, 0);
1534 page2_status.resize (cached_line_details_.size () - 1, 0);
1536 /* find the page 1 and page 2 forces for each page-breaking position */
1537 for (vsize i = 0; i < page1_force.size (); i++)
1539 page1.append_system (cached_line_details_[i]);
1540 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1541 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1542 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1544 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1545 page1_penalty[i] = line_count_penalty (page1_line_count);
1546 page1_status[i] = line_count_status (page1_line_count);
1549 page2_force[page2_force.size () - 1 - i]
1550 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1552 page2_force[page2_force.size () - 1 - i] = page2.force_;
1553 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1554 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1557 /* find the position that minimises the sum of the page forces */
1558 vsize best_sys_count = 1;
1559 Real best_demerits = infinity_f;
1560 for (vsize i = 0; i < page1_force.size (); i++)
1562 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1564 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1565 // constraints. That is, we penalize harshly when they don't happen
1566 // but we don't completely reject.
1568 + page1_penalty[i] + page2_penalty[i]
1569 + cached_line_details_[i + 1].page_penalty_
1570 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1571 if (dem < best_demerits)
1573 best_demerits = dem;
1574 best_sys_count = i + 1;
1578 Page_spacing_result ret;
1579 ret.systems_per_page_.push_back (best_sys_count);
1580 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1581 ret.force_.push_back (page1_force[best_sys_count - 1]);
1582 ret.force_.push_back (page2_force[best_sys_count - 1]);
1583 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1584 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1585 + cached_line_details_.back ().page_penalty_
1586 + cached_line_details_.back ().turn_penalty_
1587 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1589 /* don't do finalize_spacing_result () because we are only an internal function */
1594 Page_breaking::all_lines_stretched (vsize configuration)
1596 cache_line_details (configuration);
1597 for (vsize i = 0; i < cached_line_details_.size (); i++)
1598 if (cached_line_details_[i].force_ < 0)
1604 Page_breaking::Line_division
1605 Page_breaking::current_configuration (vsize configuration_index) const
1607 return current_configurations_[configuration_index];
1611 Page_breaking::is_last () const
1613 return current_end_breakpoint_ == last_break_position ();
1617 Page_breaking::ends_score () const
1619 return breaks_[current_end_breakpoint_].score_ender_;
1623 Page_breaking::last_break_position () const
1625 return breaks_.size () - 1;
1628 // This gives the minimum distance between the top of the
1629 // printable area (ie. the bottom of the top-margin) and
1630 // the extent box of the topmost system.
1632 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1634 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1636 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1638 Real min_distance = -infinity_f;
1641 Page_layout_problem::read_spacing_spec (first_system_spacing,
1643 ly_symbol2scm ("minimum-distance"));
1644 Page_layout_problem::read_spacing_spec (first_system_spacing,
1646 ly_symbol2scm ("padding"));
1648 // FIXME: take into account the height of the header
1649 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1650 return max (0.0, max (padding, min_distance - translate));
1654 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1656 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1657 Real min_distance = -infinity_f;
1660 Page_layout_problem::read_spacing_spec (last_system_spacing,
1662 ly_symbol2scm ("minimum-distance"));
1663 Page_layout_problem::read_spacing_spec (last_system_spacing,
1665 ly_symbol2scm ("padding"));
1667 // FIXME: take into account the height of the footer
1668 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1669 return max (0.0, max (padding, min_distance + translate));
1673 Page_breaking::orphan_penalty () const
1675 return orphan_penalty_;