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]);
203 /* translate the number of systems-per-page into something meaningful for
204 the uncompressed lines.
207 uncompress_solution (vector<vsize> const &systems_per_page,
208 vector<Line_details> const &compressed)
213 for (vsize i = 0; i < systems_per_page.size (); i++)
215 int compressed_count = 0;
216 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
217 compressed_count += compressed[j].compressed_lines_count_ - 1;
219 ret.push_back (systems_per_page[i] + compressed_count);
220 start_sys += systems_per_page[i];
225 /* for Page_breaking, the start index (when we are dealing with the stuff
226 between a pair of breakpoints) refers to the break_ index of the end of
227 the previous page. So the system index of the start of the current page
228 could either be the same as the end of the previous page or one more than
231 /* Turn a break index into the sys index that starts the next page */
233 Page_breaking::next_system (Break_position const &break_pos) const
235 vsize sys = break_pos.system_spec_index_;
237 if (sys == VPOS) /* beginning of the book */
239 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
240 return sys; /* the score overflows the previous page */
241 return sys + 1; /* this page starts with a new System_spec */
244 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
248 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
249 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
250 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
251 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
252 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
253 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
254 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
256 Stencil footnote_separator = Page_layout_problem::get_footnote_separator_stencil (pb->paper_);
258 if (!footnote_separator.is_empty ())
260 Interval separator_extent = footnote_separator.extent (Y_AXIS);
261 Real separator_span = separator_extent.length ();
263 footnote_separator_stencil_height_ = separator_span;
266 footnote_separator_stencil_height_ = 0.0;
268 footnote_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
269 in_note_padding_ = robust_scm2double (pb->paper_->c_variable ("in-note-padding"), 0.0);
270 footnote_footer_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-footer-padding"), 0.0);
272 footnote_number_raise_ = robust_scm2double (pb->paper_->c_variable ("footnote-number-raise"), 0.0);
274 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
276 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
277 min_systems_per_page_ = max_systems_per_page_ = 0;
279 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
281 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
282 min_systems_per_page_ = max_systems_per_page_ = 0;
285 create_system_list ();
286 find_chunks_and_breaks (is_break, prob_break);
289 Page_breaking::~Page_breaking ()
294 Page_breaking::ragged () const
300 Page_breaking::ragged_last () const
306 Page_breaking::systems_per_page () const
308 return systems_per_page_;
312 Page_breaking::max_systems_per_page () const
314 if (systems_per_page_)
315 return systems_per_page_;
316 return max_systems_per_page_;
320 Page_breaking::min_systems_per_page () const
322 if (systems_per_page_)
323 return systems_per_page_;
324 return min_systems_per_page_;
328 Page_breaking::system_count () const
330 return system_count_;
334 Page_breaking::footnote_separator_stencil_height () const
336 return footnote_separator_stencil_height_;
340 Page_breaking::in_note_padding () const
342 return in_note_padding_;
346 Page_breaking::footnote_padding () const
348 return footnote_padding_;
352 Page_breaking::footnote_footer_padding () const
354 return footnote_footer_padding_;
358 Page_breaking::footnote_number_raise () const
360 return footnote_number_raise_;
364 Page_breaking::too_many_lines (int line_count) const
366 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
370 Page_breaking::too_few_lines (int line_count) const
372 return line_count < min_systems_per_page ();
376 Page_breaking::line_count_penalty (int line_count) const
378 if (too_many_lines (line_count))
379 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
380 if (too_few_lines (line_count))
381 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
387 Page_breaking::line_count_status (int line_count) const
389 if (too_many_lines (line_count))
390 return SYSTEM_COUNT_TOO_MANY;
391 if (too_few_lines (line_count))
392 return SYSTEM_COUNT_TOO_FEW;
394 return SYSTEM_COUNT_OK;
397 /* translate indices into breaks_ into start-end parameters for the line breaker */
399 Page_breaking::line_breaker_args (vsize sys,
400 Break_position const &start,
401 Break_position const &end,
402 vsize *line_breaker_start,
403 vsize *line_breaker_end)
405 assert (system_specs_[sys].pscore_);
406 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
408 if (start.system_spec_index_ == sys)
409 *line_breaker_start = start.score_break_;
411 *line_breaker_start = 0;
413 if (end.system_spec_index_ == sys)
414 *line_breaker_end = end.score_break_;
416 *line_breaker_end = VPOS;
420 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
421 Line_division const &div)
423 vector<Break_position> chunks = chunk_list (start_break, end_break);
424 bool ignore_div = false;
425 if (chunks.size () != div.size () + 1)
427 programming_error ("did not find a valid page breaking configuration");
431 for (vsize i = 0; i + 1 < chunks.size (); i++)
433 vsize sys = next_system (chunks[i]);
434 if (system_specs_[sys].pscore_)
438 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
440 vector<Column_x_positions> pos = ignore_div
441 ? line_breaking_[sys].best_solution (start, end)
442 : line_breaking_[sys].solve (start, end, div[i]);
443 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
449 Page_breaking::systems ()
452 for (vsize sys = 0; sys < system_specs_.size (); sys++)
454 if (system_specs_[sys].pscore_)
456 system_specs_[sys].pscore_->root_system ()
457 ->do_break_substitution_and_fixup_refpoints ();
458 SCM lines = system_specs_[sys].pscore_->root_system ()
459 ->get_broken_system_grobs ();
460 ret = scm_cons (lines, ret);
462 else if (Prob *pb = system_specs_[sys].prob_)
464 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
468 return scm_append (scm_reverse_x (ret, SCM_EOL));
472 Page_breaking::make_page (int page_num, bool last) const
474 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
475 SCM mod = scm_c_resolve_module ("scm page");
476 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
478 make_page_scm = scm_variable_ref (make_page_scm);
480 return scm_apply_0 (make_page_scm,
481 scm_list_n (book_->self_scm (),
482 ly_symbol2scm ("page-number"), scm_from_int (page_num),
483 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
484 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
488 // Returns the total height of the paper, including margins and
489 // space for the header/footer. This is an upper bound on
490 // page_height, and it doesn't depend on the current page.
492 Page_breaking::paper_height () const
494 return paper_height_;
498 Page_breaking::page_height (int page_num, bool last) const
500 // The caches allow us to store the page heights for any
501 // non-negative page numbers. We use a negative value in the
502 // cache to signal that that position has not yet been initialized.
503 // This means that we won't cache properly if page_num is negative or
504 // if calc_height returns a negative number. But that's likely to
505 // be rare, so it shouldn't affect performance.
506 vector<Real> &cache = last ? last_page_height_cache_ : page_height_cache_;
507 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
508 return cache[page_num];
511 SCM mod = scm_c_resolve_module ("scm page");
512 SCM page = make_page (page_num, last);
513 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
514 calc_height = scm_variable_ref (calc_height);
516 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
517 Real height = scm_to_double (height_scm);
521 if ((int) cache.size () <= page_num)
522 cache.resize (page_num + 1, -1);
523 cache[page_num] = height;
530 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
532 Break_position const &pos = breaks_[breakpoint];
534 if (pos.system_spec_index_ == VPOS)
536 if (system_specs_[pos.system_spec_index_].pscore_)
537 return pos.col_->get_property (str);
538 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
542 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
544 SCM dummy_page = make_page (page_num, last);
545 Page_layout_problem layout (book_, dummy_page, systems);
546 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
550 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
552 // Create a stencil for each system.
553 SCM paper_systems = SCM_EOL;
554 for (SCM s = systems; scm_is_pair (s); s = scm_cdr (s))
556 SCM paper_system = scm_car (s);
557 if (Grob *g = unsmob_grob (scm_car (s)))
559 System *sys = dynamic_cast<System *> (g);
560 paper_system = sys->get_paper_system ();
563 paper_systems = scm_cons (paper_system, paper_systems);
565 paper_systems = scm_reverse_x (paper_systems, SCM_EOL);
567 // Create the page and draw it.
568 SCM page = make_page (page_num, last);
570 Prob *p = unsmob_prob (page);
571 p->set_property ("lines", paper_systems);
572 p->set_property ("configuration", configuration);
574 Stencil *foot_p = unsmob_stencil (p->get_property ("foot-stencil"));
575 Stencil foot = foot_p ? *foot_p : Stencil ();
577 SCM footnotes = Page_layout_problem::get_footnotes_from_lines (systems);
579 foot = Page_layout_problem::add_footnotes_to_footer (footnotes, foot, book_);
581 p->set_property ("foot-stencil", foot.smobbed_copy ());
587 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
589 if (scm_is_null (systems))
592 int first_page_number
593 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
595 bool reset_footnotes_on_new_page = to_boolean (book_->top_paper ()->c_variable ("reset-footnotes-on-new-page"));
596 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
597 if (label_page_table == SCM_UNDEFINED)
598 label_page_table = SCM_EOL;
600 // Build a list of (systems configuration . footnote-count) triples.
601 // Note that we lay out the staves and find the configurations,
602 // but we do not draw anything in this function. It is important
603 // that all staves are laid out vertically before any are drawn; some
604 // grobs (like tuplet brackets) look at their neighbours while drawing
605 // themselves. If this happens before the neighbouring staves have
606 // been laid out, bad side-effects could happen (in particular,
607 // Align_interface::align_to_ideal_distances might be called).
608 SCM systems_configs_fncounts = SCM_EOL;
609 vsize footnote_count = 0;
610 Real last_page_force = 0;
612 for (vsize i = 0; i < lines_per_page.size (); i++)
614 int page_num = i + first_page_number;
615 bool bookpart_last_page = (i == lines_per_page.size () - 1);
616 bool rag = ragged () || (bookpart_last_page && ragged_last ());
617 SCM line_count = scm_from_int (lines_per_page[i]);
618 SCM lines = scm_list_head (systems, line_count);
619 int fn_lines = Page_layout_problem::get_footnote_count (lines);
620 Page_layout_problem::add_footnotes_to_lines (lines, reset_footnotes_on_new_page ? 0 : footnote_count, book_);
622 SCM config = SCM_EOL;
623 SCM dummy_page = make_page (page_num, bookpart_last_page);
624 Page_layout_problem layout (book_, dummy_page, lines);
625 if (!scm_is_pair (systems))
627 else if (rag && !ragged ())
628 // If we're ragged-last but not ragged, make the last page
629 // have the same force as the previous page.
630 config = layout.fixed_force_solution (last_page_force);
632 config = layout.solution (rag);
634 last_page_force = layout.force ();
636 systems_configs_fncounts = scm_cons (scm_cons (lines, config), systems_configs_fncounts);
637 footnote_count += fn_lines;
638 systems = scm_list_tail (systems, line_count);
641 // TODO: previously, the following loop caused the systems to be
642 // drawn. Now that we no longer draw anything in Page_breaking,
643 // it is safe to merge these two loops.
644 int page_num = first_page_number + lines_per_page.size () - 1;
645 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
647 SCM lines = scm_caar (s);
648 SCM config = scm_cdar (s);
650 bool bookpart_last_page = (s == systems_configs_fncounts);
651 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
653 SCM page_num_scm = scm_from_int (page_num);
654 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
656 SCM labels = SCM_EOL;
657 if (Grob *line = unsmob_grob (scm_car (l)))
659 System *system = dynamic_cast<System *> (line);
660 labels = system->get_property ("labels");
662 else if (Prob *prob = unsmob_prob (scm_car (l)))
663 labels = prob->get_property ("labels");
665 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
666 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
670 ret = scm_cons (page, ret);
674 // By reversing the table, we ensure that duplicated labels (eg. those
675 // straddling a page turn) will appear in the table with their last
677 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
678 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
683 Page_breaking::create_system_list ()
685 SCM specs = book_->get_system_specs ();
686 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
688 if (Paper_score *ps = dynamic_cast<Paper_score *> (unsmob_music_output (scm_car (s))))
690 system_specs_.push_back (System_spec (ps));
694 Prob *pb = unsmob_prob (scm_car (s));
698 system_specs_.push_back (System_spec (pb));
701 if (!system_specs_.size ())
702 system_specs_.push_back (System_spec ());
705 /* The page-turn-page-breaker needs to have a line-breaker between any two
706 columns with non-NULL page-turn-permission.
708 The optimal-breaker needs to have a line-breaker between any two columns
709 with page-break-permission = 'force.
711 By using a grob predicate, we can accommodate both of these uses.
714 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
716 SCM force_sym = ly_symbol2scm ("force");
718 chunks_.push_back (Break_position ());
719 breaks_.push_back (Break_position ());
721 for (vsize i = 0; i < system_specs_.size (); i++)
723 if (system_specs_[i].pscore_)
725 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
726 vector<Grob *> forced_line_break_cols;
728 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
729 if (scm_is_number (system_count))
731 // With system-count given, the line configuration for
732 // this score is fixed. We need to ensure that chunk
733 // boundaries only occur at line breaks.
734 Constrained_breaking breaking (system_specs_[i].pscore_);
735 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
737 for (vsize j = 0; j < details.size (); j++)
738 forced_line_break_cols.push_back (details[j].last_column_);
741 int last_forced_line_break_idx = 0;
742 vsize forced_line_break_idx = 0;
743 vector<vsize> line_breaker_columns;
744 line_breaker_columns.push_back (0);
746 for (vsize j = 1; j < cols.size (); j++)
748 if (forced_line_break_cols.size ())
750 if (forced_line_break_idx >= forced_line_break_cols.size ()
751 || forced_line_break_cols[forced_line_break_idx] != cols[j])
754 forced_line_break_idx++;
757 bool last = (j == cols.size () - 1);
758 bool break_point = is_break && is_break (cols[j]);
759 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
760 Break_position cur_pos = Break_position (i,
761 line_breaker_columns.size (),
765 // NOTE: even in the breaks_ list, forced_line_count_
766 // refers to the number of lines between a
767 // Break_position and the start of that /chunk/. This
768 // is needed for system_count_bounds to work correctly,
769 // since it mixes Break_positions from breaks_ and
771 if (scm_is_number (system_count))
772 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
774 if (break_point || (i == system_specs_.size () - 1 && last))
775 breaks_.push_back (cur_pos);
776 if (chunk_end || last)
778 chunks_.push_back (cur_pos);
779 last_forced_line_break_idx = forced_line_break_idx;
782 if ((break_point || chunk_end) && !last)
783 line_breaker_columns.push_back (j);
785 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
787 else if (system_specs_[i].prob_)
789 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
790 if (break_point || i == system_specs_.size () - 1)
791 breaks_.push_back (Break_position (i));
793 chunks_.push_back (Break_position (i));
795 /* FIXME: shouldn't we push a Null_breaker or similar dummy
797 line_breaking_.push_back (Constrained_breaking (NULL));
802 vector<Break_position>
803 Page_breaking::chunk_list (vsize start_index, vsize end_index)
805 Break_position start = breaks_[start_index];
806 Break_position end = breaks_[end_index];
809 for (; i < chunks_.size () && chunks_[i] <= start; i++)
812 vector<Break_position> ret;
813 ret.push_back (start);
814 for (; i < chunks_.size () && chunks_[i] < end; i++)
815 ret.push_back (chunks_[i]);
820 // Returns the minimum number of _non-title_ lines.
822 Page_breaking::min_system_count (vsize start, vsize end)
824 vector<Break_position> chunks = chunk_list (start, end);
825 Line_division div = system_count_bounds (chunks, true);
828 for (vsize i = 0; i < div.size (); i++)
833 // Returns the maximum number of _non-title_ lines.
835 Page_breaking::max_system_count (vsize start, vsize end)
837 vector<Break_position> chunks = chunk_list (start, end);
838 Line_division div = system_count_bounds (chunks, false);
841 for (vsize i = 0; i < div.size (); i++)
846 // The numbers returned by this function represent either
847 // the maximum or minimum number of _non-title_ lines
849 Page_breaking::Line_division
850 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
853 assert (chunks.size () >= 2);
856 ret.resize (chunks.size () - 1, 0);
858 for (vsize i = 0; i + 1 < chunks.size (); i++)
860 vsize sys = next_system (chunks[i]);
862 if (chunks[i + 1].forced_line_count_)
863 ret[i] = chunks[i + 1].forced_line_count_;
864 else if (system_specs_[sys].pscore_)
868 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
870 ? line_breaking_[sys].min_system_count (start, end)
871 : line_breaking_[sys].max_system_count (start, end);
879 Page_breaking::set_current_breakpoints (vsize start,
882 Line_division lower_bound,
883 Line_division upper_bound)
885 system_count_ = system_count;
886 current_chunks_ = chunk_list (start, end);
887 current_start_breakpoint_ = start;
888 current_end_breakpoint_ = end;
889 clear_line_details_cache ();
891 if (!lower_bound.size ())
892 lower_bound = system_count_bounds (current_chunks_, true);
893 if (!upper_bound.size ())
894 upper_bound = system_count_bounds (current_chunks_, false);
896 assert (lower_bound.size () == current_chunks_.size () - 1);
897 assert (upper_bound.size () == current_chunks_.size () - 1);
899 Line_division work_in_progress;
900 current_configurations_.clear ();
901 line_divisions_rec (system_count,
906 /* we only consider a constant number of configurations. Otherwise,
907 this becomes slow when there are many small scores. The constant
908 5 is somewhat arbitrary. */
909 if (current_configurations_.size () > 5)
911 vector<pair<Real, vsize> > dems_and_indices;
913 for (vsize i = 0; i < current_configurations_.size (); i++)
915 cache_line_details (i);
917 for (vsize j = 0; j < cached_line_details_.size (); j++)
918 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
919 + cached_line_details_[j].break_penalty_;
921 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
923 vector_sort (dems_and_indices, less<pair<Real, vsize> > ());
925 vector<Line_division> best_5_configurations;
926 for (vsize i = 0; i < 5; i++)
927 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
929 clear_line_details_cache ();
930 current_configurations_ = best_5_configurations;
935 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
937 current_chunks_ = chunk_list (start, end);
938 current_start_breakpoint_ = start;
939 current_end_breakpoint_ = end;
940 clear_line_details_cache ();
944 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
946 vsize sys = next_system (current_chunks_[i]);
948 if (current_chunks_[i + 1].forced_line_count_)
949 div.push_back (current_chunks_[i + 1].forced_line_count_);
950 else if (system_specs_[sys].pscore_)
952 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
953 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
958 system_count_ += div.back ();
960 current_configurations_.clear ();
961 current_configurations_.push_back (div);
965 Page_breaking::current_configuration_count () const
967 return current_configurations_.size ();
971 Page_breaking::cache_line_details (vsize configuration_index)
973 if (cached_configuration_index_ != configuration_index)
975 cached_configuration_index_ = configuration_index;
977 Line_division &div = current_configurations_[configuration_index];
978 uncompressed_line_details_.clear ();
979 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
981 vsize sys = next_system (current_chunks_[i]);
982 if (system_specs_[sys].pscore_)
986 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
988 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
989 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
993 assert (div[i] == 0);
994 uncompressed_line_details_.push_back (system_specs_[sys].prob_
995 ? Line_details (system_specs_[sys].prob_, book_->paper_)
999 cached_line_details_ = compress_lines (uncompressed_line_details_);
1000 compute_line_heights ();
1005 Page_breaking::clear_line_details_cache ()
1007 cached_configuration_index_ = VPOS;
1008 cached_line_details_.clear ();
1009 uncompressed_line_details_.clear ();
1013 Page_breaking::line_divisions_rec (vsize system_count,
1014 Line_division const &min_sys,
1015 Line_division const &max_sys,
1016 Line_division *cur_division)
1018 vsize my_index = cur_division->size ();
1022 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1024 others_min += min_sys[i];
1025 others_max += max_sys[i];
1027 others_max = min (others_max, (int) system_count);
1028 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
1029 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
1031 if (real_min > real_max || real_min < 0)
1033 /* this should never happen within a recursive call. If it happens
1034 at all, it means that we were called with an unsolvable problem
1035 and we should return an empty result */
1036 assert (my_index == 0);
1040 for (int i = real_min; i <= real_max; i++)
1042 cur_division->push_back (i);
1043 if (my_index == min_sys.size () - 1)
1044 current_configurations_.push_back (*cur_division);
1046 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1047 cur_division->pop_back ();
1052 Page_breaking::compute_line_heights ()
1054 Real prev_hanging = 0;
1055 Real prev_hanging_begin = 0;
1056 Real prev_hanging_rest = 0;
1058 // refpoint_hanging is the y coordinate of the origin of this system.
1059 // It may not be the same as refpoint_extent[UP], which is the
1060 // refpoint of the first spaceable staff in this system.
1061 Real prev_refpoint_hanging = 0;
1062 for (vsize i = 0; i < cached_line_details_.size (); i++)
1064 Line_details &cur = cached_line_details_[i];
1065 Line_shape shape = cur.shape_;
1066 Real a = shape.begin_[UP];
1067 Real b = shape.rest_[UP];
1068 bool title = cur.title_;
1069 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1074 Line_details const &prev = cached_line_details_[i - 1];
1075 if (!cur.tight_spacing_)
1077 ? prev.title_padding_
1079 Real min_dist = title
1080 ? prev.title_min_distance_
1081 : prev.min_distance_;
1082 refpoint_hanging = max (refpoint_hanging + padding,
1083 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1084 + cur.refpoint_extent_[UP] + min_dist);
1087 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1088 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1089 Real hanging = max (hanging_begin, hanging_rest);
1090 cur.tallness_ = hanging - prev_hanging;
1091 prev_hanging = hanging;
1092 prev_hanging_begin = hanging_begin;
1093 prev_hanging_rest = hanging_rest;
1094 prev_refpoint_hanging = refpoint_hanging;
1099 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1102 vsize page_starter = 0;
1103 Real cur_rod_height = 0;
1104 Real cur_spring_height = 0;
1105 Real cur_page_height = page_height (first_page_num, false);
1108 cache_line_details (configuration);
1110 if (cached_line_details_.size ())
1111 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1113 for (vsize i = 0; i < cached_line_details_.size (); i++)
1115 Line_details const &cur = cached_line_details_[i];
1116 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1118 if (cur_rod_height > 0)
1119 ext_len = cur.tallness_;
1121 ext_len = cur.full_height ();
1123 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1124 Real next_rod_height = cur_rod_height + ext_len;
1125 Real next_spring_height = cur_spring_height + spring_len;
1126 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1127 + min_whitespace_at_bottom_of_page (cur);
1128 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1130 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1131 || too_many_lines (next_line_count)
1132 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1134 line_count = cur.compressed_nontitle_lines_count_;
1135 cur_rod_height = cur.full_height ();
1136 cur_spring_height = 0;
1139 cur_page_height = page_height (first_page_num + ret, false);
1140 cur_page_height -= min_whitespace_at_top_of_page (cur);
1146 cur_rod_height = next_rod_height;
1147 cur_spring_height = next_spring_height;
1148 line_count = next_line_count;
1152 /* there are two potential problems with the last page (because we didn't know
1153 it was the last page until after we managed to fit all the systems to it):
1154 - we are ragged-last but the last page has a compressed spring
1155 - the value returned by page_height (num, true) is smaller than the
1156 value returned by page_height (num, false) and it causes the page not to
1159 In either case, we just need to add one more page. This is because the last
1160 line will always fit on the extra page and by adding one more page to the
1161 end, the previous page is no longer the last page, so our previous
1162 calculations that treated it as a non-last page were ok.
1167 cur_page_height = page_height (first_page_num + ret - 1, true);
1168 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1169 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1171 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1172 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1173 && cur_height > cur_page_height
1174 /* don't increase the page count if the last page had only one system */
1175 && cur_rod_height > cached_line_details_.back ().full_height ())
1177 assert (ret <= cached_line_details_.size ());
1183 // If systems_per_page_ is positive, we don't really try to space on N pages;
1184 // we just put the requested number of systems on each page and penalize
1185 // if the result doesn't have N pages.
1187 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1189 Page_spacing_result ret;
1191 if (systems_per_page_ > 0)
1193 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1194 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1198 cache_line_details (configuration);
1199 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1200 && n <= cached_line_details_.size ());
1203 programming_error ("number of pages is out of bounds");
1205 if (n == 1 && valid_n)
1206 ret = space_systems_on_1_page (cached_line_details_,
1207 page_height (first_page_num, is_last ()),
1208 ragged () || (is_last () && ragged_last ()));
1209 else if (n == 2 && valid_n)
1210 ret = space_systems_on_2_pages (configuration, first_page_num);
1213 Page_spacer ps (cached_line_details_, first_page_num, this);
1217 return finalize_spacing_result (configuration, ret);
1221 Page_breaking::blank_page_penalty () const
1226 penalty_sym = ly_symbol2scm ("blank-last-page-penalty");
1227 else if (ends_score ())
1228 penalty_sym = ly_symbol2scm ("blank-after-score-page-penalty");
1230 penalty_sym = ly_symbol2scm ("blank-page-penalty");
1232 Break_position const &pos = breaks_[current_end_breakpoint_];
1233 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1234 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1236 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1239 // If systems_per_page_ is positive, we don't really try to space on N
1240 // or N+1 pages; see the comment to space_systems_on_n_pages.
1242 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1243 Real penalty_for_fewer_pages)
1245 Page_spacing_result n_res;
1246 Page_spacing_result m_res;
1248 if (systems_per_page_ > 0)
1250 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1251 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1255 cache_line_details (configuration);
1256 vsize min_p_count = min_page_count (configuration, first_page_num);
1257 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1260 programming_error ("both page counts are out of bounds");
1262 if (n == 1 && valid_n)
1264 bool rag = ragged () || (is_last () && ragged_last ());
1265 Real height = page_height (first_page_num, is_last ());
1267 if (1 >= min_p_count)
1268 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1269 if (1 < cached_line_details_.size ())
1270 m_res = space_systems_on_2_pages (configuration, first_page_num);
1274 Page_spacer ps (cached_line_details_, first_page_num, this);
1276 if (n >= min_p_count || !valid_n)
1277 n_res = ps.solve (n);
1278 if (n < cached_line_details_.size () || !valid_n)
1279 m_res = ps.solve (n + 1);
1282 m_res = finalize_spacing_result (configuration, m_res);
1283 n_res = finalize_spacing_result (configuration, n_res);
1285 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1286 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1288 if (n_res.force_.size ())
1289 n_res.force_.back () += penalty_for_fewer_pages;
1291 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1295 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1297 if (systems_per_page_ > 0)
1298 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1300 cache_line_details (configuration);
1301 Page_spacer ps (cached_line_details_, first_page_num, this);
1303 return finalize_spacing_result (configuration, ps.solve ());
1307 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1308 vsize first_page_num)
1310 Page_spacing_result res;
1311 Page_spacing space (page_height (first_page_num, false), this);
1314 vsize page_first_line = 0;
1316 cache_line_details (configuration);
1317 while (line < cached_line_details_.size ())
1321 space.resize (page_height (first_page_num + page, false));
1323 int system_count_on_this_page = 0;
1324 while (system_count_on_this_page < systems_per_page_
1325 && line < cached_line_details_.size ())
1327 Line_details const &cur_line = cached_line_details_[line];
1328 space.append_system (cur_line);
1329 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1332 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1336 res.systems_per_page_.push_back (line - page_first_line);
1338 res.force_.push_back (space.force_);
1339 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1340 if (system_count_on_this_page != systems_per_page_)
1342 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1343 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1344 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1347 page_first_line = line;
1350 /* Recalculate forces for the last page because we know now that is
1351 really the last page. */
1352 space.resize (page_height (first_page_num + page, true));
1353 res.force_.back () = space.force_;
1354 return finalize_spacing_result (configuration, res);
1358 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1360 // TODO: add support for min/max-systems-per-page.
1361 Page_spacing_result res;
1363 vsize page_first_line = 0;
1364 Page_spacing space (page_height (first_page_num, false), this);
1366 cache_line_details (configuration);
1367 for (vsize line = 0; line < cached_line_details_.size (); line++)
1369 Real prev_force = space.force_;
1370 space.append_system (cached_line_details_[line]);
1371 if ((line > page_first_line)
1372 && (isinf (space.force_)
1374 && (cached_line_details_[line - 1].page_permission_ == ly_symbol2scm ("force")))))
1376 res.systems_per_page_.push_back (line - page_first_line);
1377 res.force_.push_back (prev_force);
1378 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1380 space.resize (page_height (first_page_num + page, false));
1382 space.append_system (cached_line_details_[line]);
1383 page_first_line = line;
1386 if (line == cached_line_details_.size () - 1)
1388 /* This is the last line */
1389 /* When the last page height was computed, we did not know yet that it
1390 * was the last one. If the systems put on it don't fit anymore, the last
1391 * system is moved to a new page */
1392 space.resize (page_height (first_page_num + page, true));
1393 if ((line > page_first_line) && (isinf (space.force_)))
1395 res.systems_per_page_.push_back (line - page_first_line);
1396 res.force_.push_back (prev_force);
1397 /* the last page containing the last line */
1398 space.resize (page_height (first_page_num + page + 1, true));
1400 space.append_system (cached_line_details_[line]);
1401 res.systems_per_page_.push_back (1);
1402 res.force_.push_back (space.force_);
1403 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1404 res.penalty_ += cached_line_details_[line].page_penalty_;
1408 res.systems_per_page_.push_back (line + 1 - page_first_line);
1409 res.force_.push_back (space.force_);
1410 res.penalty_ += cached_line_details_[line].page_penalty_;
1414 return finalize_spacing_result (configuration, res);
1417 /* Calculate demerits and fix res.systems_per_page_ so that
1418 it refers to the original line numbers, not the ones given by compress_lines (). */
1420 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1422 if (res.force_.empty ())
1425 cache_line_details (configuration);
1426 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1428 Real line_force = 0;
1429 Real line_penalty = 0;
1430 Real page_demerits = res.penalty_;
1431 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1433 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1435 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1436 line_penalty += uncompressed_line_details_[i].break_penalty_;
1439 for (vsize i = ragged () ? res.force_.size () - 1 : 0;
1440 i < res.force_.size () - ragged_last ();
1443 Real f = res.force_[i];
1445 page_demerits += min (f * f, BAD_SPACING_PENALTY);
1448 /* for a while we tried averaging page and line forces across pages instead
1449 of summing them, but it caused a problem: if there is a single page
1450 with a very bad page force (for example because of a forced page break),
1451 the page breaker will put in a _lot_ of pages so that the bad force
1452 becomes averaged out over many pages. */
1453 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1458 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1459 are by far the most common cases, we have special functions for them.
1461 space_systems_on_1_page has a different calling convention than most of the
1462 space_systems functions. This is because space_systems_on_1_page is (unlike
1463 the other space_systems functions) sometimes called on subsets of a full
1466 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1468 Page_spacing space (page_height, this);
1469 Page_spacing_result ret;
1472 for (vsize i = 0; i < lines.size (); i++)
1474 space.append_system (lines[i]);
1475 line_count += lines[i].compressed_nontitle_lines_count_;
1478 ret.systems_per_page_.push_back (lines.size ());
1479 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1480 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1481 ret.system_count_status_ |= line_count_status (line_count);
1483 /* don't do finalize_spacing_result () because we are only an internal function */
1488 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1490 Real page1_height = page_height (first_page_num, false);
1491 Real page2_height = page_height (first_page_num + 1, is_last ());
1492 bool ragged1 = ragged ();
1493 bool ragged2 = ragged () || (is_last () && ragged_last ());
1495 /* if there is a forced break, this reduces to 2 1-page problems */
1496 cache_line_details (configuration);
1497 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1498 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1500 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1501 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1502 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1503 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1505 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1506 p1.force_.push_back (p2.force_[0]);
1507 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1508 p1.system_count_status_ |= p2.system_count_status_;
1512 vector<Real> page1_force;
1513 vector<Real> page2_force;
1515 // page1_penalty and page2_penalty store the penalties based
1516 // on min-systems-per-page and max-systems-per-page.
1517 vector<Real> page1_penalty;
1518 vector<Real> page2_penalty;
1520 // page1_status and page2_status keep track of whether the min-systems-per-page
1521 // and max-systems-per-page constraints are satisfied.
1522 vector<int> page1_status;
1523 vector<int> page2_status;
1525 Page_spacing page1 (page1_height, this);
1526 Page_spacing page2 (page2_height, this);
1527 int page1_line_count = 0;
1528 int page2_line_count = 0;
1530 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1531 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1532 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1533 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1534 page1_status.resize (cached_line_details_.size () - 1, 0);
1535 page2_status.resize (cached_line_details_.size () - 1, 0);
1537 /* find the page 1 and page 2 forces for each page-breaking position */
1538 for (vsize i = 0; i < page1_force.size (); i++)
1540 page1.append_system (cached_line_details_[i]);
1541 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1542 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1543 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1545 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1546 page1_penalty[i] = line_count_penalty (page1_line_count);
1547 page1_status[i] = line_count_status (page1_line_count);
1550 page2_force[page2_force.size () - 1 - i]
1551 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1553 page2_force[page2_force.size () - 1 - i] = page2.force_;
1554 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1555 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1558 /* find the position that minimises the sum of the page forces */
1559 vsize best_sys_count = 1;
1560 Real best_demerits = infinity_f;
1561 for (vsize i = 0; i < page1_force.size (); i++)
1563 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1565 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1566 // constraints. That is, we penalize harshly when they don't happen
1567 // but we don't completely reject.
1569 + page1_penalty[i] + page2_penalty[i]
1570 + cached_line_details_[i + 1].page_penalty_
1571 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1572 if (dem < best_demerits)
1574 best_demerits = dem;
1575 best_sys_count = i + 1;
1579 Page_spacing_result ret;
1580 ret.systems_per_page_.push_back (best_sys_count);
1581 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1582 ret.force_.push_back (page1_force[best_sys_count - 1]);
1583 ret.force_.push_back (page2_force[best_sys_count - 1]);
1584 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1585 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1586 + cached_line_details_.back ().page_penalty_
1587 + cached_line_details_.back ().turn_penalty_
1588 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1590 /* don't do finalize_spacing_result () because we are only an internal function */
1595 Page_breaking::all_lines_stretched (vsize configuration)
1597 cache_line_details (configuration);
1598 for (vsize i = 0; i < cached_line_details_.size (); i++)
1599 if (cached_line_details_[i].force_ < 0)
1605 Page_breaking::Line_division
1606 Page_breaking::current_configuration (vsize configuration_index) const
1608 return current_configurations_[configuration_index];
1612 Page_breaking::is_last () const
1614 return current_end_breakpoint_ == last_break_position ();
1618 Page_breaking::ends_score () const
1620 return breaks_[current_end_breakpoint_].score_ender_;
1624 Page_breaking::last_break_position () const
1626 return breaks_.size () - 1;
1629 // This gives the minimum distance between the top of the
1630 // printable area (ie. the bottom of the top-margin) and
1631 // the extent box of the topmost system.
1633 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1635 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1637 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1639 Real min_distance = -infinity_f;
1642 Page_layout_problem::read_spacing_spec (first_system_spacing,
1644 ly_symbol2scm ("minimum-distance"));
1645 Page_layout_problem::read_spacing_spec (first_system_spacing,
1647 ly_symbol2scm ("padding"));
1649 // FIXME: take into account the height of the header
1650 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1651 return max (0.0, max (padding, min_distance - translate));
1655 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1657 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1658 Real min_distance = -infinity_f;
1661 Page_layout_problem::read_spacing_spec (last_system_spacing,
1663 ly_symbol2scm ("minimum-distance"));
1664 Page_layout_problem::read_spacing_spec (last_system_spacing,
1666 ly_symbol2scm ("padding"));
1668 // FIXME: take into account the height of the footer
1669 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1670 return max (0.0, max (padding, min_distance + translate));
1674 Page_breaking::orphan_penalty () const
1676 return orphan_penalty_;