2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2011 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.footnotes_.insert (compressed.footnotes_.begin (),
187 old.footnotes_.begin (), old.footnotes_.end ());
189 ret.back () = compressed;
193 ret.push_back (orig[i]);
194 ret.back ().force_ = 0;
200 /* translate the number of systems-per-page into something meaningful for
201 the uncompressed lines.
204 uncompress_solution (vector<vsize> const &systems_per_page,
205 vector<Line_details> const &compressed)
210 for (vsize i = 0; i < systems_per_page.size (); i++)
212 int compressed_count = 0;
213 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
214 compressed_count += compressed[j].compressed_lines_count_ - 1;
216 ret.push_back (systems_per_page[i] + compressed_count);
217 start_sys += systems_per_page[i];
222 /* for Page_breaking, the start index (when we are dealing with the stuff
223 between a pair of breakpoints) refers to the break_ index of the end of
224 the previous page. So the system index of the start of the current page
225 could either be the same as the end of the previous page or one more than
228 /* Turn a break index into the sys index that starts the next page */
230 Page_breaking::next_system (Break_position const &break_pos) const
232 vsize sys = break_pos.system_spec_index_;
234 if (sys == VPOS) /* beginning of the book */
236 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
237 return sys; /* the score overflows the previous page */
238 return sys + 1; /* this page starts with a new System_spec */
241 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
245 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
246 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
247 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
248 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
249 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
250 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
251 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
253 Stencil *footnote_separator = Page_layout_problem::get_footnote_separator_stencil (pb->paper_);
255 if (footnote_separator)
257 Interval separator_extent = footnote_separator->extent (Y_AXIS);
258 Real separator_span = separator_extent.length ();
260 footnote_separator_stencil_height_ = separator_span;
263 footnote_separator_stencil_height_ = 0.0;
265 footnote_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
266 footnote_footer_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-footer-padding"), 0.0);
268 footnote_number_raise_ = robust_scm2double (pb->paper_->c_variable ("footnote-number-raise"), 0.0);
270 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
272 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
273 min_systems_per_page_ = max_systems_per_page_ = 0;
275 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
277 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
278 min_systems_per_page_ = max_systems_per_page_ = 0;
281 create_system_list ();
282 find_chunks_and_breaks (is_break, prob_break);
285 Page_breaking::~Page_breaking ()
290 Page_breaking::ragged () const
296 Page_breaking::ragged_last () const
302 Page_breaking::systems_per_page () const
304 return systems_per_page_;
308 Page_breaking::max_systems_per_page () const
310 if (systems_per_page_)
311 return systems_per_page_;
312 return max_systems_per_page_;
316 Page_breaking::min_systems_per_page () const
318 if (systems_per_page_)
319 return systems_per_page_;
320 return min_systems_per_page_;
324 Page_breaking::system_count () const
326 return system_count_;
330 Page_breaking::footnote_separator_stencil_height () const
332 return footnote_separator_stencil_height_;
336 Page_breaking::footnote_padding () const
338 return footnote_padding_;
342 Page_breaking::footnote_footer_padding () const
344 return footnote_footer_padding_;
348 Page_breaking::footnote_number_raise () const
350 return footnote_number_raise_;
354 Page_breaking::too_many_lines (int line_count) const
356 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
360 Page_breaking::too_few_lines (int line_count) const
362 return line_count < min_systems_per_page ();
366 Page_breaking::line_count_penalty (int line_count) const
368 if (too_many_lines (line_count))
369 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
370 if (too_few_lines (line_count))
371 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
377 Page_breaking::line_count_status (int line_count) const
379 if (too_many_lines (line_count))
380 return SYSTEM_COUNT_TOO_MANY;
381 if (too_few_lines (line_count))
382 return SYSTEM_COUNT_TOO_FEW;
384 return SYSTEM_COUNT_OK;
387 /* translate indices into breaks_ into start-end parameters for the line breaker */
389 Page_breaking::line_breaker_args (vsize sys,
390 Break_position const &start,
391 Break_position const &end,
392 vsize *line_breaker_start,
393 vsize *line_breaker_end)
395 assert (system_specs_[sys].pscore_);
396 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
398 if (start.system_spec_index_ == sys)
399 *line_breaker_start = start.score_break_;
401 *line_breaker_start = 0;
403 if (end.system_spec_index_ == sys)
404 *line_breaker_end = end.score_break_;
406 *line_breaker_end = VPOS;
410 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
411 Line_division const &div)
413 vector<Break_position> chunks = chunk_list (start_break, end_break);
414 bool ignore_div = false;
415 if (chunks.size () != div.size () + 1)
417 programming_error ("did not find a valid page breaking configuration");
421 for (vsize i = 0; i + 1 < chunks.size (); i++)
423 vsize sys = next_system (chunks[i]);
424 if (system_specs_[sys].pscore_)
428 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
430 vector<Column_x_positions> pos = ignore_div
431 ? line_breaking_[sys].best_solution (start, end)
432 : line_breaking_[sys].solve (start, end, div[i]);
433 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
439 Page_breaking::systems ()
442 for (vsize sys = 0; sys < system_specs_.size (); sys++)
444 if (system_specs_[sys].pscore_)
446 system_specs_[sys].pscore_->root_system ()
447 ->do_break_substitution_and_fixup_refpoints ();
448 SCM lines = system_specs_[sys].pscore_->root_system ()
449 ->get_broken_system_grobs ();
450 ret = scm_cons (lines, ret);
452 else if (Prob *pb = system_specs_[sys].prob_)
454 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
458 return scm_append (scm_reverse (ret));
462 Page_breaking::make_page (int page_num, bool last) const
464 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
465 SCM mod = scm_c_resolve_module ("scm page");
466 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
468 make_page_scm = scm_variable_ref (make_page_scm);
470 return scm_apply_0 (make_page_scm,
471 scm_list_n (book_->self_scm (),
472 ly_symbol2scm ("page-number"), scm_from_int (page_num),
473 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
474 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
478 // Returns the total height of the paper, including margins and
479 // space for the header/footer. This is an upper bound on
480 // page_height, and it doesn't depend on the current page.
482 Page_breaking::paper_height () const
484 return paper_height_;
488 Page_breaking::page_height (int page_num, bool last) const
490 // The caches allow us to store the page heights for any
491 // non-negative page numbers. We use a negative value in the
492 // cache to signal that that position has not yet been initialized.
493 // This means that we won't cache properly if page_num is negative or
494 // if calc_height returns a negative number. But that's likely to
495 // be rare, so it shouldn't affect performance.
496 vector<Real>& cache = last ? last_page_height_cache_ : page_height_cache_;
497 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
498 return cache[page_num];
501 SCM mod = scm_c_resolve_module ("scm page");
502 SCM page = make_page (page_num, last);
503 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
504 calc_height = scm_variable_ref (calc_height);
506 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
507 Real height = scm_to_double (height_scm);
511 if ((int) cache.size () <= page_num)
512 cache.resize (page_num + 1, -1);
513 cache[page_num] = height;
520 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
522 Break_position const &pos = breaks_[breakpoint];
524 if (pos.system_spec_index_ == VPOS)
526 if (system_specs_[pos.system_spec_index_].pscore_)
527 return pos.col_->get_property (str);
528 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
532 Page_breaking::get_page_configuration (SCM systems, int page_num, int footnote_count, bool ragged, bool last)
534 SCM dummy_page = make_page (page_num, last);
535 Page_layout_problem layout (book_, dummy_page, systems, footnote_count);
536 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
540 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, int footnote_num, bool last)
542 // Create a stencil for each system.
543 SCM paper_systems = SCM_EOL;
544 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
546 SCM paper_system = scm_car (s);
547 if (Grob *g = unsmob_grob (scm_car (s)))
549 System *sys = dynamic_cast<System *> (g);
550 paper_system = sys->get_paper_system ();
553 paper_systems = scm_cons (paper_system, paper_systems);
556 // Create the page and draw it.
557 SCM page = make_page (page_num, last);
558 SCM page_module = scm_c_resolve_module ("scm page");
559 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
560 page_stencil = scm_variable_ref (page_stencil);
562 Prob *p = unsmob_prob (page);
563 p->set_property ("lines", paper_systems);
564 p->set_property ("configuration", configuration);
566 Stencil *foot = unsmob_stencil (p->get_property ("foot-stencil"));
568 footnote_num = (to_boolean (book_->paper_->c_variable ("reset-footnotes-on-new-page"))
572 SCM footnotes = Page_layout_problem::get_footnotes_from_lines (systems,
576 Page_layout_problem::add_footnotes_to_footer (footnotes, foot, book_);
579 p->set_property ("foot-stencil", foot->smobbed_copy ());
580 scm_apply_1 (page_stencil, page, SCM_EOL);
586 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
588 if (scm_is_null (systems))
591 int first_page_number
592 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
594 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
595 if (label_page_table == SCM_UNDEFINED)
596 label_page_table = SCM_EOL;
598 // Build a list of (systems . configuration) pairs. Note that we lay out
599 // the staves and find the configurations before drawing anything. Some
600 // grobs (like tuplet brackets) look at their neighbours while drawing
601 // themselves. If this happens before the neighbouring staves have
602 // been laid out, bad side-effects could happen (in particular,
603 // Align_interface::align_to_ideal_distances might be called).
604 SCM systems_configs_fncounts = SCM_EOL;
605 vsize footnote_count = 0;
607 for (vsize i = 0; i < lines_per_page.size (); i++)
609 int page_num = i + first_page_number;
610 bool bookpart_last_page = (i == lines_per_page.size () - 1);
611 bool rag = ragged () || (bookpart_last_page && ragged_last ());
612 SCM line_count = scm_from_int (lines_per_page[i]);
613 SCM lines = scm_list_head (systems, line_count);
614 int fn_lines = Page_layout_problem::get_footnote_count (lines);
615 SCM config = get_page_configuration (lines, page_num, footnote_count, rag, bookpart_last_page);
617 systems_configs_fncounts = scm_cons (scm_list_3 (lines, config, scm_from_int ((int)footnote_count)), systems_configs_fncounts);
618 footnote_count += fn_lines;
619 systems = scm_list_tail (systems, line_count);
622 // Now it's safe to make the pages.
623 int page_num = first_page_number + lines_per_page.size () - 1;
624 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
626 SCM lines = scm_caar (s);
627 SCM config = scm_cadar (s);
628 int footnote_num = scm_to_int (scm_caddar (s));
630 bool bookpart_last_page = (s == systems_configs_fncounts);
631 SCM page = draw_page (lines, config, page_num, footnote_num, bookpart_last_page);
633 SCM page_num_scm = scm_from_int (page_num);
634 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
636 SCM labels = SCM_EOL;
637 if (Grob *line = unsmob_grob (scm_car (l)))
639 System *system = dynamic_cast<System *> (line);
640 labels = system->get_property ("labels");
642 else if (Prob *prob = unsmob_prob (scm_car (l)))
643 labels = prob->get_property ("labels");
645 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
646 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
650 ret = scm_cons (page, ret);
654 // By reversing the table, we ensure that duplicated labels (eg. those
655 // straddling a page turn) will appear in the table with their last
657 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
658 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
662 /* The page-turn-page-breaker needs to have a line-breaker between any two
663 columns with non-NULL page-turn-permission.
665 The optimal-breaker needs to have a line-breaker between any two columns
666 with page-break-permission = 'force.
668 By using a grob predicate, we can accommodate both of these uses.
671 Page_breaking::create_system_list ()
673 SCM specs = book_->get_system_specs ();
674 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
676 if (Paper_score *ps = dynamic_cast<Paper_score *> (unsmob_music_output (scm_car (s))))
678 system_specs_.push_back (System_spec (ps));
682 Prob *pb = unsmob_prob (scm_car (s));
686 system_specs_.push_back (System_spec (pb));
689 if (!system_specs_.size ())
690 system_specs_.push_back (System_spec ());
694 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
696 SCM force_sym = ly_symbol2scm ("force");
698 chunks_.push_back (Break_position ());
699 breaks_.push_back (Break_position ());
701 for (vsize i = 0; i < system_specs_.size (); i++)
703 if (system_specs_[i].pscore_)
705 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
706 vector<Grob *> forced_line_break_cols;
708 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
709 if (scm_is_number (system_count))
711 // With system-count given, the line configuration for
712 // this score is fixed. We need to ensure that chunk
713 // boundaries only occur at line breaks.
714 Constrained_breaking breaking (system_specs_[i].pscore_);
715 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
717 for (vsize j = 0; j < details.size (); j++)
718 forced_line_break_cols.push_back (details[j].last_column_);
721 int last_forced_line_break_idx = 0;
722 vsize forced_line_break_idx = 0;
723 vector<vsize> line_breaker_columns;
724 line_breaker_columns.push_back (0);
726 for (vsize j = 1; j < cols.size (); j++)
728 if (forced_line_break_cols.size ())
730 if (forced_line_break_idx >= forced_line_break_cols.size ()
731 || forced_line_break_cols[forced_line_break_idx] != cols[j])
734 forced_line_break_idx++;
737 bool last = (j == cols.size () - 1);
738 bool break_point = is_break && is_break (cols[j]);
739 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
740 Break_position cur_pos = Break_position (i,
741 line_breaker_columns.size (),
745 // NOTE: even in the breaks_ list, forced_line_count_
746 // refers to the number of lines between a
747 // Break_position and the start of that /chunk/. This
748 // is needed for system_count_bounds to work correctly,
749 // since it mixes Break_positions from breaks_ and
751 if (scm_is_number (system_count))
752 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
754 if (break_point || (i == system_specs_.size () - 1 && last))
755 breaks_.push_back (cur_pos);
756 if (chunk_end || last)
758 chunks_.push_back (cur_pos);
759 last_forced_line_break_idx = forced_line_break_idx;
762 if ((break_point || chunk_end) && !last)
763 line_breaker_columns.push_back (j);
765 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
767 else if (system_specs_[i].prob_)
769 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
770 if (break_point || i == system_specs_.size () - 1)
771 breaks_.push_back (Break_position (i));
773 chunks_.push_back (Break_position (i));
775 /* FIXME: shouldn't we push a Null_breaker or similar dummy
777 line_breaking_.push_back (Constrained_breaking (NULL));
782 vector<Break_position>
783 Page_breaking::chunk_list (vsize start_index, vsize end_index)
785 Break_position start = breaks_[start_index];
786 Break_position end = breaks_[end_index];
789 for (; i < chunks_.size () && chunks_[i] <= start; i++)
792 vector<Break_position> ret;
793 ret.push_back (start);
794 for (; i < chunks_.size () && chunks_[i] < end; i++)
795 ret.push_back (chunks_[i]);
800 // Returns the minimum number of _non-title_ lines.
802 Page_breaking::min_system_count (vsize start, vsize end)
804 vector<Break_position> chunks = chunk_list (start, end);
805 Line_division div = system_count_bounds (chunks, true);
808 for (vsize i = 0; i < div.size (); i++)
813 // Returns the maximum number of _non-title_ lines.
815 Page_breaking::max_system_count (vsize start, vsize end)
817 vector<Break_position> chunks = chunk_list (start, end);
818 Line_division div = system_count_bounds (chunks, false);
821 for (vsize i = 0; i < div.size (); i++)
826 // The numbers returned by this function represent either
827 // the maximum or minimum number of _non-title_ lines
829 Page_breaking::Line_division
830 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
833 assert (chunks.size () >= 2);
836 ret.resize (chunks.size () - 1, 0);
838 for (vsize i = 0; i + 1 < chunks.size (); i++)
840 vsize sys = next_system (chunks[i]);
842 if (chunks[i + 1].forced_line_count_)
843 ret[i] = chunks[i + 1].forced_line_count_;
844 else if (system_specs_[sys].pscore_)
848 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
850 ? line_breaking_[sys].min_system_count (start, end)
851 : line_breaking_[sys].max_system_count (start, end);
859 Page_breaking::set_current_breakpoints (vsize start,
862 Line_division lower_bound,
863 Line_division upper_bound)
865 system_count_ = system_count;
866 current_chunks_ = chunk_list (start, end);
867 current_start_breakpoint_ = start;
868 current_end_breakpoint_ = end;
869 clear_line_details_cache ();
871 if (!lower_bound.size ())
872 lower_bound = system_count_bounds (current_chunks_, true);
873 if (!upper_bound.size ())
874 upper_bound = system_count_bounds (current_chunks_, false);
876 assert (lower_bound.size () == current_chunks_.size () - 1);
877 assert (upper_bound.size () == current_chunks_.size () - 1);
879 Line_division work_in_progress;
880 current_configurations_.clear ();
881 line_divisions_rec (system_count,
886 /* we only consider a constant number of configurations. Otherwise,
887 this becomes slow when there are many small scores. The constant
888 5 is somewhat arbitrary. */
889 if (current_configurations_.size () > 5)
891 vector<pair<Real, vsize> > dems_and_indices;
893 for (vsize i = 0; i < current_configurations_.size (); i++)
895 cache_line_details (i);
897 for (vsize j = 0; j < cached_line_details_.size (); j++)
898 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
899 + cached_line_details_[j].break_penalty_;
901 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
903 vector_sort (dems_and_indices, less<pair<Real, vsize> > ());
905 vector<Line_division> best_5_configurations;
906 for (vsize i = 0; i < 5; i++)
907 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
909 clear_line_details_cache ();
910 current_configurations_ = best_5_configurations;
915 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
917 current_chunks_ = chunk_list (start, end);
918 current_start_breakpoint_ = start;
919 current_end_breakpoint_ = end;
920 clear_line_details_cache ();
924 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
926 vsize sys = next_system (current_chunks_[i]);
928 if (current_chunks_[i + 1].forced_line_count_)
929 div.push_back (current_chunks_[i + 1].forced_line_count_);
930 else if (system_specs_[sys].pscore_)
932 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
933 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
938 system_count_ += div.back ();
940 current_configurations_.clear ();
941 current_configurations_.push_back (div);
945 Page_breaking::current_configuration_count () const
947 return current_configurations_.size ();
951 Page_breaking::cache_line_details (vsize configuration_index)
953 if (cached_configuration_index_ != configuration_index)
955 cached_configuration_index_ = configuration_index;
957 Line_division &div = current_configurations_[configuration_index];
958 uncompressed_line_details_.clear ();
959 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
961 vsize sys = next_system (current_chunks_[i]);
962 if (system_specs_[sys].pscore_)
966 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
968 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
969 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
973 assert (div[i] == 0);
974 uncompressed_line_details_.push_back (system_specs_[sys].prob_
975 ? Line_details (system_specs_[sys].prob_, book_->paper_)
979 cached_line_details_ = compress_lines (uncompressed_line_details_);
980 compute_line_heights ();
985 Page_breaking::clear_line_details_cache ()
987 cached_configuration_index_ = VPOS;
988 cached_line_details_.clear ();
989 uncompressed_line_details_.clear ();
993 Page_breaking::line_divisions_rec (vsize system_count,
994 Line_division const &min_sys,
995 Line_division const &max_sys,
996 Line_division *cur_division)
998 vsize my_index = cur_division->size ();
1002 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1004 others_min += min_sys[i];
1005 others_max += max_sys[i];
1007 others_max = min (others_max, (int) system_count);
1008 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
1009 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
1011 if (real_min > real_max || real_min < 0)
1013 /* this should never happen within a recursive call. If it happens
1014 at all, it means that we were called with an unsolvable problem
1015 and we should return an empty result */
1016 assert (my_index == 0);
1020 for (int i = real_min; i <= real_max; i++)
1022 cur_division->push_back (i);
1023 if (my_index == min_sys.size () - 1)
1024 current_configurations_.push_back (*cur_division);
1026 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1027 cur_division->pop_back ();
1032 Page_breaking::compute_line_heights ()
1034 Real prev_hanging = 0;
1035 Real prev_hanging_begin = 0;
1036 Real prev_hanging_rest = 0;
1038 // refpoint_hanging is the y coordinate of the origin of this system.
1039 // It may not be the same as refpoint_extent[UP], which is the
1040 // refpoint of the first spaceable staff in this system.
1041 Real prev_refpoint_hanging = 0;
1042 for (vsize i = 0; i < cached_line_details_.size (); i++)
1044 Line_details &cur = cached_line_details_[i];
1045 Line_shape shape = cur.shape_;
1046 Real a = shape.begin_[UP];
1047 Real b = shape.rest_[UP];
1048 bool title = cur.title_;
1049 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1054 Line_details const &prev = cached_line_details_[i - 1];
1055 if (!cur.tight_spacing_)
1057 ? prev.title_padding_
1059 Real min_dist = title
1060 ? prev.title_min_distance_
1061 : prev.min_distance_;
1062 refpoint_hanging = max (refpoint_hanging + padding,
1063 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1064 + cur.refpoint_extent_[UP] + min_dist);
1067 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1068 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1069 Real hanging = max (hanging_begin, hanging_rest);
1070 cur.tallness_ = hanging - prev_hanging;
1071 prev_hanging = hanging;
1072 prev_hanging_begin = hanging_begin;
1073 prev_hanging_rest = hanging_rest;
1074 prev_refpoint_hanging = refpoint_hanging;
1079 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1082 vsize page_starter = 0;
1083 Real cur_rod_height = 0;
1084 Real cur_spring_height = 0;
1085 Real cur_page_height = page_height (first_page_num, false);
1088 cache_line_details (configuration);
1090 if (cached_line_details_.size ())
1091 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1093 for (vsize i = 0; i < cached_line_details_.size (); i++)
1095 Line_details const &cur = cached_line_details_[i];
1096 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1098 if (cur_rod_height > 0)
1099 ext_len = cur.tallness_;
1101 ext_len = cur.full_height ();
1103 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1104 Real next_rod_height = cur_rod_height + ext_len;
1105 Real next_spring_height = cur_spring_height + spring_len;
1106 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1107 + min_whitespace_at_bottom_of_page (cur);
1108 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1110 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1111 || too_many_lines (next_line_count)
1112 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1114 line_count = cur.compressed_nontitle_lines_count_;
1115 cur_rod_height = cur.full_height ();
1116 cur_spring_height = 0;
1119 cur_page_height = page_height (first_page_num + ret, false);
1120 cur_page_height -= min_whitespace_at_top_of_page (cur);
1126 cur_rod_height = next_rod_height;
1127 cur_spring_height = next_spring_height;
1128 line_count = next_line_count;
1132 /* there are two potential problems with the last page (because we didn't know
1133 it was the last page until after we managed to fit all the systems to it):
1134 - we are ragged-last but the last page has a compressed spring
1135 - the value returned by page_height (num, true) is smaller than the
1136 value returned by page_height (num, false) and it causes the page not to
1139 In either case, we just need to add one more page. This is because the last
1140 line will always fit on the extra page and by adding one more page to the
1141 end, the previous page is no longer the last page, so our previous
1142 calculations that treated it as a non-last page were ok.
1147 cur_page_height = page_height (first_page_num + ret - 1, true);
1148 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1149 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1151 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1152 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1153 && cur_height > cur_page_height
1154 /* don't increase the page count if the last page had only one system */
1155 && cur_rod_height > cached_line_details_.back ().full_height ())
1157 assert (ret <= cached_line_details_.size ());
1163 // If systems_per_page_ is positive, we don't really try to space on N pages;
1164 // we just put the requested number of systems on each page and penalize
1165 // if the result doesn't have N pages.
1167 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1169 Page_spacing_result ret;
1171 if (systems_per_page_ > 0)
1173 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1174 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1178 cache_line_details (configuration);
1179 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1180 && n <= cached_line_details_.size ());
1183 programming_error ("number of pages is out of bounds");
1185 if (n == 1 && valid_n)
1186 ret = space_systems_on_1_page (cached_line_details_,
1187 page_height (first_page_num, is_last ()),
1188 ragged () || (is_last () && ragged_last ()));
1189 else if (n == 2 && valid_n)
1190 ret = space_systems_on_2_pages (configuration, first_page_num);
1193 Page_spacer ps (cached_line_details_, first_page_num, this);
1197 return finalize_spacing_result (configuration, ret);
1201 Page_breaking::blank_page_penalty () const
1206 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1207 else if (ends_score ())
1208 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1210 penalty_sym = ly_symbol2scm ("blank-page-force");
1212 Break_position const &pos = breaks_[current_end_breakpoint_];
1213 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1214 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1216 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1219 // If systems_per_page_ is positive, we don't really try to space on N
1220 // or N+1 pages; see the comment to space_systems_on_n_pages.
1222 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1223 Real penalty_for_fewer_pages)
1225 Page_spacing_result n_res;
1226 Page_spacing_result m_res;
1228 if (systems_per_page_ > 0)
1230 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1231 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1235 cache_line_details (configuration);
1236 vsize min_p_count = min_page_count (configuration, first_page_num);
1237 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1240 programming_error ("both page counts are out of bounds");
1242 if (n == 1 && valid_n)
1244 bool rag = ragged () || (is_last () && ragged_last ());
1245 Real height = page_height (first_page_num, is_last ());
1247 if (1 >= min_p_count)
1248 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1249 if (1 < cached_line_details_.size ())
1250 m_res = space_systems_on_2_pages (configuration, first_page_num);
1254 Page_spacer ps (cached_line_details_, first_page_num, this);
1256 if (n >= min_p_count || !valid_n)
1257 n_res = ps.solve (n);
1258 if (n < cached_line_details_.size () || !valid_n)
1259 m_res = ps.solve (n + 1);
1262 m_res = finalize_spacing_result (configuration, m_res);
1263 n_res = finalize_spacing_result (configuration, n_res);
1265 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1266 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1268 if (n_res.force_.size ())
1269 n_res.force_.back () += penalty_for_fewer_pages;
1271 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1275 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1277 if (systems_per_page_ > 0)
1278 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1280 cache_line_details (configuration);
1281 Page_spacer ps (cached_line_details_, first_page_num, this);
1283 return finalize_spacing_result (configuration, ps.solve ());
1287 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1288 vsize first_page_num)
1290 Page_spacing_result res;
1291 Page_spacing space (page_height (first_page_num, false), this);
1294 vsize page_first_line = 0;
1296 cache_line_details (configuration);
1297 while (line < cached_line_details_.size ())
1301 space.resize (page_height (first_page_num + page, false));
1303 int system_count_on_this_page = 0;
1304 while (system_count_on_this_page < systems_per_page_
1305 && line < cached_line_details_.size ())
1307 Line_details const &cur_line = cached_line_details_[line];
1308 space.append_system (cur_line);
1309 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1312 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1316 res.systems_per_page_.push_back (line - page_first_line);
1318 res.force_.push_back (space.force_);
1319 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1320 if (system_count_on_this_page != systems_per_page_)
1322 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1323 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1324 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1327 page_first_line = line;
1330 /* Recalculate forces for the last page because we know now that is
1331 really the last page. */
1332 space.resize (page_height (first_page_num + page, true));
1333 res.force_.back () = space.force_;
1334 return finalize_spacing_result (configuration, res);
1338 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1340 // TODO: add support for min/max-systems-per-page.
1341 Page_spacing_result res;
1343 vsize page_first_line = 0;
1344 Page_spacing space (page_height (first_page_num, false), this);
1346 cache_line_details (configuration);
1347 for (vsize line = 0; line < cached_line_details_.size (); line++)
1349 Real prev_force = space.force_;
1350 space.append_system (cached_line_details_[line]);
1351 if ((line > page_first_line)
1352 && (isinf (space.force_)
1354 && (cached_line_details_[line - 1].page_permission_ == ly_symbol2scm ("force")))))
1356 res.systems_per_page_.push_back (line - page_first_line);
1357 res.force_.push_back (prev_force);
1358 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1360 space.resize (page_height (first_page_num + page, false));
1362 space.append_system (cached_line_details_[line]);
1363 page_first_line = line;
1366 if (line == cached_line_details_.size () - 1)
1368 /* This is the last line */
1369 /* When the last page height was computed, we did not know yet that it
1370 * was the last one. If the systems put on it don't fit anymore, the last
1371 * system is moved to a new page */
1372 space.resize (page_height (first_page_num + page, true));
1373 if ((line > page_first_line) && (isinf (space.force_)))
1375 res.systems_per_page_.push_back (line - page_first_line);
1376 res.force_.push_back (prev_force);
1377 /* the last page containing the last line */
1378 space.resize (page_height (first_page_num + page + 1, true));
1380 space.append_system (cached_line_details_[line]);
1381 res.systems_per_page_.push_back (1);
1382 res.force_.push_back (space.force_);
1383 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1384 res.penalty_ += cached_line_details_[line].page_penalty_;
1388 res.systems_per_page_.push_back (line + 1 - page_first_line);
1389 res.force_.push_back (space.force_);
1390 res.penalty_ += cached_line_details_[line].page_penalty_;
1394 return finalize_spacing_result (configuration, res);
1397 /* Calculate demerits and fix res.systems_per_page_ so that
1398 it refers to the original line numbers, not the ones given by compress_lines (). */
1400 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1402 if (res.force_.empty ())
1405 cache_line_details (configuration);
1406 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1408 Real line_force = 0;
1409 Real line_penalty = 0;
1410 Real page_demerits = res.penalty_;
1411 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1413 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1415 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1416 line_penalty += uncompressed_line_details_[i].break_penalty_;
1419 for (vsize i = 0; i < res.force_.size (); i++)
1421 Real f = res.force_[i];
1423 page_demerits += min (f * f, BAD_SPACING_PENALTY);
1426 /* for a while we tried averaging page and line forces across pages instead
1427 of summing them, but it caused a problem: if there is a single page
1428 with a very bad page force (for example because of a forced page break),
1429 the page breaker will put in a _lot_ of pages so that the bad force
1430 becomes averaged out over many pages. */
1431 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1436 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1437 are by far the most common cases, we have special functions for them.
1439 space_systems_on_1_page has a different calling convention than most of the
1440 space_systems functions. This is because space_systems_on_1_page is (unlike
1441 the other space_systems functions) sometimes called on subsets of a full
1444 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1446 Page_spacing space (page_height, this);
1447 Page_spacing_result ret;
1450 for (vsize i = 0; i < lines.size (); i++)
1452 space.append_system (lines[i]);
1453 line_count += lines[i].compressed_nontitle_lines_count_;
1456 ret.systems_per_page_.push_back (lines.size ());
1457 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1458 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1459 ret.system_count_status_ |= line_count_status (line_count);
1461 /* don't do finalize_spacing_result () because we are only an internal function */
1466 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1468 Real page1_height = page_height (first_page_num, false);
1469 Real page2_height = page_height (first_page_num + 1, is_last ());
1470 bool ragged1 = ragged ();
1471 bool ragged2 = ragged () || (is_last () && ragged_last ());
1473 /* if there is a forced break, this reduces to 2 1-page problems */
1474 cache_line_details (configuration);
1475 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1476 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1478 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1479 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1480 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1481 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1483 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1484 p1.force_.push_back (p2.force_[0]);
1485 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1486 p1.system_count_status_ |= p2.system_count_status_;
1490 vector<Real> page1_force;
1491 vector<Real> page2_force;
1493 // page1_penalty and page2_penalty store the penalties based
1494 // on min-systems-per-page and max-systems-per-page.
1495 vector<Real> page1_penalty;
1496 vector<Real> page2_penalty;
1498 // page1_status and page2_status keep track of whether the min-systems-per-page
1499 // and max-systems-per-page constraints are satisfied.
1500 vector<int> page1_status;
1501 vector<int> page2_status;
1503 Page_spacing page1 (page1_height, this);
1504 Page_spacing page2 (page2_height, this);
1505 int page1_line_count = 0;
1506 int page2_line_count = 0;
1508 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1509 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1510 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1511 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1512 page1_status.resize (cached_line_details_.size () - 1, 0);
1513 page2_status.resize (cached_line_details_.size () - 1, 0);
1515 /* find the page 1 and page 2 forces for each page-breaking position */
1516 for (vsize i = 0; i < page1_force.size (); i++)
1518 page1.append_system (cached_line_details_[i]);
1519 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1520 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1521 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1523 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1524 page1_penalty[i] = line_count_penalty (page1_line_count);
1525 page1_status[i] = line_count_status (page1_line_count);
1528 page2_force[page2_force.size () - 1 - i]
1529 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1531 page2_force[page2_force.size () - 1 - i] = page2.force_;
1532 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1533 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1536 /* find the position that minimises the sum of the page forces */
1537 vsize best_sys_count = 1;
1538 Real best_demerits = infinity_f;
1539 for (vsize i = 0; i < page1_force.size (); i++)
1541 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1543 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1544 // constraints. That is, we penalize harshly when they don't happen
1545 // but we don't completely reject.
1547 + page1_penalty[i] + page2_penalty[i]
1548 + cached_line_details_[i + 1].page_penalty_
1549 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1550 if (dem < best_demerits)
1552 best_demerits = dem;
1553 best_sys_count = i + 1;
1557 Page_spacing_result ret;
1558 ret.systems_per_page_.push_back (best_sys_count);
1559 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1560 ret.force_.push_back (page1_force[best_sys_count - 1]);
1561 ret.force_.push_back (page2_force[best_sys_count - 1]);
1562 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1563 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1564 + cached_line_details_.back ().page_penalty_
1565 + cached_line_details_.back ().turn_penalty_
1566 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1568 /* don't do finalize_spacing_result () because we are only an internal function */
1573 Page_breaking::all_lines_stretched (vsize configuration)
1575 cache_line_details (configuration);
1576 for (vsize i = 0; i < cached_line_details_.size (); i++)
1577 if (cached_line_details_[i].force_ < 0)
1583 Page_breaking::Line_division
1584 Page_breaking::current_configuration (vsize configuration_index) const
1586 return current_configurations_[configuration_index];
1590 Page_breaking::is_last () const
1592 return current_end_breakpoint_ == last_break_position ();
1596 Page_breaking::ends_score () const
1598 return breaks_[current_end_breakpoint_].score_ender_;
1602 Page_breaking::last_break_position () const
1604 return breaks_.size () - 1;
1607 // This gives the minimum distance between the top of the
1608 // printable area (ie. the bottom of the top-margin) and
1609 // the extent box of the topmost system.
1611 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1613 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1615 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1617 Real min_distance = -infinity_f;
1620 Page_layout_problem::read_spacing_spec (first_system_spacing,
1622 ly_symbol2scm ("minimum-distance"));
1623 Page_layout_problem::read_spacing_spec (first_system_spacing,
1625 ly_symbol2scm ("padding"));
1627 // FIXME: take into account the height of the header
1628 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1629 return max (0.0, max (padding, min_distance - translate));
1633 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1635 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1636 Real min_distance = -infinity_f;
1639 Page_layout_problem::read_spacing_spec (last_system_spacing,
1641 ly_symbol2scm ("minimum-distance"));
1642 Page_layout_problem::read_spacing_spec (last_system_spacing,
1644 ly_symbol2scm ("padding"));
1646 // FIXME: take into account the height of the footer
1647 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1648 return max (0.0, max (padding, min_distance + translate));
1652 Page_breaking::orphan_penalty () const
1654 return orphan_penalty_;