2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2015 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"
148 /* for each forbidden page break, merge the systems around it into one
150 static vector<Line_details>
151 compress_lines (const vector<Line_details> &orig)
153 vector<Line_details> ret;
155 for (vsize i = 0; i < orig.size (); i++)
157 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
159 Line_details const &old = ret.back ();
160 Line_details compressed = orig[i];
162 We must account for the padding between the lines that we are compressing.
163 The padding values come from "old," which is the upper system here. Note
164 the meaning of tight-spacing: if a system has tight-spacing, then the padding
165 _before_ it is ignored.
168 if (!orig[i].tight_spacing_)
169 padding = orig[i].title_ ? old.title_padding_ : old.padding_;
171 // FIXME: double check these. Doesn't foo.piggyback (bar) mean
172 // that foo goes on top?
173 // TODO: break out a Line_details::piggyback from here?
174 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
175 compressed.refpoint_extent_[UP] = old.refpoint_extent_[UP];
176 compressed.refpoint_extent_[DOWN] += compressed.shape_.rest_[UP] - old.shape_.rest_[UP];
177 compressed.space_ += old.space_;
178 compressed.inverse_hooke_ += old.inverse_hooke_;
180 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
181 compressed.compressed_nontitle_lines_count_
182 = old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
184 // compressed.title_ is true if and only if the first of its
185 // compressed lines was a title.
186 compressed.title_ = old.title_;
188 // adds footnotes of one line to the footnotes of another
189 compressed.footnote_heights_.insert (compressed.footnote_heights_.begin (),
190 old.footnote_heights_.begin (),
191 old.footnote_heights_.end ());
192 compressed.in_note_heights_.insert (compressed.in_note_heights_.begin (),
193 old.in_note_heights_.begin (),
194 old.in_note_heights_.end ());
196 ret.back () = compressed;
200 ret.push_back (orig[i]);
206 /* translate the number of systems-per-page into something meaningful for
207 the uncompressed lines.
210 uncompress_solution (vector<vsize> const &systems_per_page,
211 vector<Line_details> const &compressed)
216 for (vsize i = 0; i < systems_per_page.size (); i++)
218 int compressed_count = 0;
219 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
220 compressed_count += compressed[j].compressed_lines_count_ - 1;
222 ret.push_back (systems_per_page[i] + compressed_count);
223 start_sys += systems_per_page[i];
228 /* for Page_breaking, the start index (when we are dealing with the stuff
229 between a pair of breakpoints) refers to the break_ index of the end of
230 the previous page. So the system index of the start of the current page
231 could either be the same as the end of the previous page or one more than
234 /* Turn a break index into the sys index that starts the next page */
236 Page_breaking::next_system (Break_position const &break_pos) const
238 vsize sys = break_pos.system_spec_index_;
240 if (sys == VPOS) /* beginning of the book */
242 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
243 return sys; /* the score overflows the previous page */
244 return sys + 1; /* this page starts with a new System_spec */
247 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
251 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
252 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
253 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
254 systems_per_page_ = std::max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
255 max_systems_per_page_ = std::max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
256 min_systems_per_page_ = std::max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
257 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
259 Stencil footnote_separator = Page_layout_problem::get_footnote_separator_stencil (pb->paper_);
261 if (!footnote_separator.is_empty ())
263 Interval separator_extent = footnote_separator.extent (Y_AXIS);
264 Real separator_span = separator_extent.length ();
266 footnote_separator_stencil_height_ = separator_span;
269 footnote_separator_stencil_height_ = 0.0;
271 footnote_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
272 in_note_padding_ = robust_scm2double (pb->paper_->c_variable ("in-note-padding"), 0.0);
273 footnote_footer_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-footer-padding"), 0.0);
275 footnote_number_raise_ = robust_scm2double (pb->paper_->c_variable ("footnote-number-raise"), 0.0);
277 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
279 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
280 min_systems_per_page_ = max_systems_per_page_ = 0;
282 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
284 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
285 min_systems_per_page_ = max_systems_per_page_ = 0;
288 create_system_list ();
289 find_chunks_and_breaks (is_break, prob_break);
292 Page_breaking::~Page_breaking ()
297 Page_breaking::ragged () const
303 Page_breaking::ragged_last () const
309 Page_breaking::systems_per_page () const
311 return systems_per_page_;
315 Page_breaking::max_systems_per_page () const
317 if (systems_per_page_)
318 return systems_per_page_;
319 return max_systems_per_page_;
323 Page_breaking::min_systems_per_page () const
325 if (systems_per_page_)
326 return systems_per_page_;
327 return min_systems_per_page_;
331 Page_breaking::system_count () const
333 return system_count_;
337 Page_breaking::footnote_separator_stencil_height () const
339 return footnote_separator_stencil_height_;
343 Page_breaking::in_note_padding () const
345 return in_note_padding_;
349 Page_breaking::footnote_padding () const
351 return footnote_padding_;
355 Page_breaking::footnote_footer_padding () const
357 return footnote_footer_padding_;
361 Page_breaking::footnote_number_raise () const
363 return footnote_number_raise_;
367 Page_breaking::too_many_lines (int line_count) const
369 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
373 Page_breaking::too_few_lines (int line_count) const
375 return line_count < min_systems_per_page ();
379 Page_breaking::line_count_penalty (int line_count) const
381 if (too_many_lines (line_count))
382 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
383 if (too_few_lines (line_count))
384 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
390 Page_breaking::line_count_status (int line_count) const
392 if (too_many_lines (line_count))
393 return SYSTEM_COUNT_TOO_MANY;
394 if (too_few_lines (line_count))
395 return SYSTEM_COUNT_TOO_FEW;
397 return SYSTEM_COUNT_OK;
400 /* translate indices into breaks_ into start-end parameters for the line breaker */
402 Page_breaking::line_breaker_args (vsize sys,
403 Break_position const &start,
404 Break_position const &end,
405 vsize *line_breaker_start,
406 vsize *line_breaker_end)
408 assert (system_specs_[sys].pscore_);
409 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
411 if (start.system_spec_index_ == sys)
412 *line_breaker_start = start.score_break_;
414 *line_breaker_start = 0;
416 if (end.system_spec_index_ == sys)
417 *line_breaker_end = end.score_break_;
419 *line_breaker_end = VPOS;
423 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
424 Line_division const &div)
426 vector<Break_position> chunks = chunk_list (start_break, end_break);
427 bool ignore_div = false;
428 if (chunks.size () != div.size () + 1)
430 programming_error ("did not find a valid page breaking configuration");
434 for (vsize i = 0; i + 1 < chunks.size (); i++)
436 vsize sys = next_system (chunks[i]);
437 if (system_specs_[sys].pscore_)
441 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
443 vector<Column_x_positions> pos = ignore_div
444 ? line_breaking_[sys].best_solution (start, end)
445 : line_breaking_[sys].solve (start, end, div[i]);
446 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
452 Page_breaking::systems ()
455 for (vsize sys = 0; sys < system_specs_.size (); sys++)
457 if (system_specs_[sys].pscore_)
459 system_specs_[sys].pscore_->root_system ()
460 ->do_break_substitution_and_fixup_refpoints ();
461 SCM lines = system_specs_[sys].pscore_->root_system ()
462 ->get_broken_system_grobs ();
463 ret = scm_cons (lines, ret);
465 else if (Prob *pb = system_specs_[sys].prob_)
467 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
471 return scm_append (scm_reverse_x (ret, SCM_EOL));
475 Page_breaking::make_page (int page_num, bool last) const
477 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
478 SCM mod = scm_c_resolve_module ("scm page");
479 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
481 make_page_scm = scm_variable_ref (make_page_scm);
483 return scm_apply_0 (make_page_scm,
484 scm_list_n (book_->self_scm (),
485 ly_symbol2scm ("page-number"), scm_from_int (page_num),
486 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
487 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
491 // Returns the total height of the paper, including margins and
492 // space for the header/footer. This is an upper bound on
493 // page_height, and it doesn't depend on the current page.
495 Page_breaking::paper_height () const
497 return paper_height_;
501 Page_breaking::page_height (int page_num, bool last) const
503 // The caches allow us to store the page heights for any
504 // non-negative page numbers. We use a negative value in the
505 // cache to signal that that position has not yet been initialized.
506 // This means that we won't cache properly if page_num is negative or
507 // if calc_height returns a negative number. But that's likely to
508 // be rare, so it shouldn't affect performance.
509 vector<Real> &cache = last ? last_page_height_cache_ : page_height_cache_;
510 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
511 return cache[page_num];
514 SCM mod = scm_c_resolve_module ("scm page");
515 SCM page = make_page (page_num, last);
516 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
517 calc_height = scm_variable_ref (calc_height);
519 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
520 Real height = scm_to_double (height_scm);
524 if ((int) cache.size () <= page_num)
525 cache.resize (page_num + 1, -1);
526 cache[page_num] = height;
533 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
535 Break_position const &pos = breaks_[breakpoint];
537 if (pos.system_spec_index_ == VPOS)
539 if (system_specs_[pos.system_spec_index_].pscore_)
540 return pos.col_->get_property (str);
541 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
545 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
547 SCM dummy_page = make_page (page_num, last);
548 Page_layout_problem layout (book_, dummy_page, systems);
549 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
553 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
555 // Create a stencil for each system.
556 SCM paper_systems = SCM_EOL;
557 for (SCM s = systems; scm_is_pair (s); s = scm_cdr (s))
559 SCM paper_system = scm_car (s);
560 if (Grob *g = unsmob<Grob> (scm_car (s)))
562 System *sys = dynamic_cast<System *> (g);
563 paper_system = sys->get_paper_system ();
566 paper_systems = scm_cons (paper_system, paper_systems);
568 paper_systems = scm_reverse_x (paper_systems, SCM_EOL);
570 // Create the page and draw it.
571 SCM page = make_page (page_num, last);
573 Prob *p = unsmob<Prob> (page);
574 p->set_property ("lines", paper_systems);
575 p->set_property ("configuration", configuration);
577 Stencil *foot_p = unsmob<Stencil> (p->get_property ("foot-stencil"));
578 Stencil foot = foot_p ? *foot_p : Stencil ();
580 SCM footnotes = Page_layout_problem::get_footnotes_from_lines (systems);
582 foot = Page_layout_problem::add_footnotes_to_footer (footnotes, foot, book_);
584 p->set_property ("foot-stencil", foot.smobbed_copy ());
590 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
592 if (scm_is_null (systems))
595 int first_page_number
596 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
598 bool reset_footnotes_on_new_page = to_boolean (book_->top_paper ()->c_variable ("reset-footnotes-on-new-page"));
599 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
600 if (SCM_UNBNDP (label_page_table))
601 label_page_table = SCM_EOL;
603 // Build a list of (systems configuration . footnote-count) triples.
604 // Note that we lay out the staves and find the configurations,
605 // but we do not draw anything in this function. It is important
606 // that all staves are laid out vertically before any are drawn; some
607 // grobs (like tuplet brackets) look at their neighbours while drawing
608 // themselves. If this happens before the neighbouring staves have
609 // been laid out, bad side-effects could happen (in particular,
610 // Align_interface::align_to_ideal_distances might be called).
611 SCM systems_configs_fncounts = SCM_EOL;
612 vsize footnote_count = 0;
613 Real last_page_force = 0;
615 for (vsize i = 0; i < lines_per_page.size (); i++)
617 int page_num = i + first_page_number;
618 bool bookpart_last_page = (i == lines_per_page.size () - 1);
619 bool rag = ragged () || (bookpart_last_page && ragged_last ());
620 SCM line_count = scm_from_int (lines_per_page[i]);
621 SCM lines = scm_list_head (systems, line_count);
622 int fn_lines = Page_layout_problem::get_footnote_count (lines);
623 Page_layout_problem::add_footnotes_to_lines (lines, reset_footnotes_on_new_page ? 0 : footnote_count, book_);
625 SCM config = SCM_EOL;
626 SCM dummy_page = make_page (page_num, bookpart_last_page);
627 Page_layout_problem layout (book_, dummy_page, lines);
628 if (!scm_is_pair (systems))
630 else if (rag && !ragged ())
631 // If we're ragged-last but not ragged, make the last page
632 // have the same force as the previous page.
633 config = layout.fixed_force_solution (last_page_force);
635 config = layout.solution (rag);
637 if ((ragged () && layout.force () < 0.0)
638 || isinf (layout.force ()))
639 warning (_f ("page %d has been compressed", page_num));
641 last_page_force = layout.force ();
643 systems_configs_fncounts = scm_cons (scm_cons (lines, config), systems_configs_fncounts);
644 footnote_count += fn_lines;
645 systems = scm_list_tail (systems, line_count);
648 // TODO: previously, the following loop caused the systems to be
649 // drawn. Now that we no longer draw anything in Page_breaking,
650 // it is safe to merge these two loops.
651 int page_num = first_page_number + lines_per_page.size () - 1;
652 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
654 SCM lines = scm_caar (s);
655 SCM config = scm_cdar (s);
657 bool bookpart_last_page = (s == systems_configs_fncounts);
658 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
660 SCM page_num_scm = scm_from_int (page_num);
661 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
663 SCM labels = SCM_EOL;
664 if (Grob *line = unsmob<Grob> (scm_car (l)))
666 System *system = dynamic_cast<System *> (line);
667 labels = system->get_property ("labels");
669 else if (Prob *prob = unsmob<Prob> (scm_car (l)))
670 labels = prob->get_property ("labels");
672 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
673 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
677 ret = scm_cons (page, ret);
681 // By reversing the table, we ensure that duplicated labels (eg. those
682 // straddling a page turn) will appear in the table with their last
684 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
685 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
690 Page_breaking::create_system_list ()
692 SCM specs = book_->get_system_specs ();
693 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
695 if (Paper_score *ps = unsmob<Paper_score> (scm_car (s)))
697 system_specs_.push_back (System_spec (ps));
701 Prob *pb = unsmob<Prob> (scm_car (s));
705 system_specs_.push_back (System_spec (pb));
708 if (!system_specs_.size ())
709 system_specs_.push_back (System_spec ());
712 /* The page-turn-page-breaker needs to have a line-breaker between any two
713 columns with non-NULL page-turn-permission.
715 The optimal-breaker needs to have a line-breaker between any two columns
716 with page-break-permission = 'force.
718 By using a grob predicate, we can accommodate both of these uses.
721 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
723 SCM force_sym = ly_symbol2scm ("force");
725 chunks_.push_back (Break_position ());
726 breaks_.push_back (Break_position ());
728 for (vsize i = 0; i < system_specs_.size (); i++)
730 if (system_specs_[i].pscore_)
732 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
733 vector<Grob *> forced_line_break_cols;
735 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
736 if (scm_is_number (system_count))
738 // With system-count given, the line configuration for
739 // this score is fixed. We need to ensure that chunk
740 // boundaries only occur at line breaks.
741 Constrained_breaking breaking (system_specs_[i].pscore_);
742 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
744 for (vsize j = 0; j < details.size (); j++)
745 forced_line_break_cols.push_back (details[j].last_column_);
748 int last_forced_line_break_idx = 0;
749 vsize forced_line_break_idx = 0;
750 vector<vsize> line_breaker_columns;
751 line_breaker_columns.push_back (0);
753 for (vsize j = 0; j < cols.size (); j++)
755 if (forced_line_break_cols.size ())
757 if (forced_line_break_idx >= forced_line_break_cols.size ()
758 || forced_line_break_cols[forced_line_break_idx] != cols[j])
761 forced_line_break_idx++;
764 bool last = (j == cols.size () - 1);
765 bool break_point = is_break && is_break (cols[j]);
766 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
767 Break_position cur_pos = Break_position (i,
768 line_breaker_columns.size (),
772 // NOTE: even in the breaks_ list, forced_line_count_
773 // refers to the number of lines between a
774 // Break_position and the start of that /chunk/. This
775 // is needed for system_count_bounds to work correctly,
776 // since it mixes Break_positions from breaks_ and
778 if (scm_is_number (system_count))
779 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
781 if (break_point || (i == system_specs_.size () - 1 && last))
782 breaks_.push_back (cur_pos);
783 if (chunk_end || last)
785 chunks_.push_back (cur_pos);
786 last_forced_line_break_idx = forced_line_break_idx;
789 if ((break_point || chunk_end) && !last)
790 line_breaker_columns.push_back (j);
792 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
794 else if (system_specs_[i].prob_)
796 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
797 if (break_point || i == system_specs_.size () - 1)
798 breaks_.push_back (Break_position (i));
800 chunks_.push_back (Break_position (i));
802 /* FIXME: shouldn't we push a Null_breaker or similar dummy
804 line_breaking_.push_back (Constrained_breaking (NULL));
809 vector<Break_position>
810 Page_breaking::chunk_list (vsize start_index, vsize end_index)
812 Break_position start = breaks_[start_index];
813 Break_position end = breaks_[end_index];
816 for (; i < chunks_.size () && chunks_[i] <= start; i++)
819 vector<Break_position> ret;
820 ret.push_back (start);
821 for (; i < chunks_.size () && chunks_[i] < end; i++)
822 ret.push_back (chunks_[i]);
827 // Returns the minimum number of _non-title_ lines.
829 Page_breaking::min_system_count (vsize start, vsize end)
831 vector<Break_position> chunks = chunk_list (start, end);
832 Line_division div = system_count_bounds (chunks, true);
835 for (vsize i = 0; i < div.size (); i++)
840 // Returns the maximum number of _non-title_ lines.
842 Page_breaking::max_system_count (vsize start, vsize end)
844 vector<Break_position> chunks = chunk_list (start, end);
845 Line_division div = system_count_bounds (chunks, false);
848 for (vsize i = 0; i < div.size (); i++)
853 // The numbers returned by this function represent either
854 // the maximum or minimum number of _non-title_ lines
856 Page_breaking::Line_division
857 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
860 assert (chunks.size () >= 2);
863 ret.resize (chunks.size () - 1, 0);
865 for (vsize i = 0; i + 1 < chunks.size (); i++)
867 vsize sys = next_system (chunks[i]);
869 if (chunks[i + 1].forced_line_count_)
870 ret[i] = chunks[i + 1].forced_line_count_;
871 else if (system_specs_[sys].pscore_)
875 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
877 ? line_breaking_[sys].min_system_count (start, end)
878 : line_breaking_[sys].max_system_count (start, end);
886 Page_breaking::set_current_breakpoints (vsize start,
889 Line_division lower_bound,
890 Line_division upper_bound)
892 system_count_ = system_count;
893 current_chunks_ = chunk_list (start, end);
894 current_start_breakpoint_ = start;
895 current_end_breakpoint_ = end;
896 clear_line_details_cache ();
898 if (!lower_bound.size ())
899 lower_bound = system_count_bounds (current_chunks_, true);
900 if (!upper_bound.size ())
901 upper_bound = system_count_bounds (current_chunks_, false);
903 assert (lower_bound.size () == current_chunks_.size () - 1);
904 assert (upper_bound.size () == current_chunks_.size () - 1);
906 Line_division work_in_progress;
907 current_configurations_.clear ();
908 line_divisions_rec (system_count,
913 /* we only consider a constant number of configurations. Otherwise,
914 this becomes slow when there are many small scores. The constant
915 5 is somewhat arbitrary. */
916 if (current_configurations_.size () > 5)
918 vector<pair<Real, vsize> > dems_and_indices;
920 for (vsize i = 0; i < current_configurations_.size (); i++)
922 cache_line_details (i);
924 for (vsize j = 0; j < cached_line_details_.size (); j++)
925 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
926 + cached_line_details_[j].break_penalty_;
928 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
930 vector_sort (dems_and_indices, std::less<pair<Real, vsize> > ());
932 vector<Line_division> best_5_configurations;
933 for (vsize i = 0; i < 5; i++)
934 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
936 clear_line_details_cache ();
937 current_configurations_ = best_5_configurations;
942 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
944 current_chunks_ = chunk_list (start, end);
945 current_start_breakpoint_ = start;
946 current_end_breakpoint_ = end;
947 clear_line_details_cache ();
951 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
953 vsize sys = next_system (current_chunks_[i]);
955 if (current_chunks_[i + 1].forced_line_count_)
956 div.push_back (current_chunks_[i + 1].forced_line_count_);
957 else if (system_specs_[sys].pscore_)
959 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
960 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
965 system_count_ += div.back ();
967 current_configurations_.clear ();
968 current_configurations_.push_back (div);
972 Page_breaking::current_configuration_count () const
974 return current_configurations_.size ();
978 Page_breaking::cache_line_details (vsize configuration_index)
980 if (cached_configuration_index_ != configuration_index)
982 cached_configuration_index_ = configuration_index;
984 Line_division &div = current_configurations_[configuration_index];
985 uncompressed_line_details_.clear ();
986 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
988 vsize sys = next_system (current_chunks_[i]);
989 if (system_specs_[sys].pscore_)
993 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
995 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
996 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
1000 assert (div[i] == 0);
1001 uncompressed_line_details_.push_back (system_specs_[sys].prob_
1002 ? Line_details (system_specs_[sys].prob_, book_->paper_)
1006 cached_line_details_ = compress_lines (uncompressed_line_details_);
1007 compute_line_heights ();
1012 Page_breaking::clear_line_details_cache ()
1014 cached_configuration_index_ = VPOS;
1015 cached_line_details_.clear ();
1016 uncompressed_line_details_.clear ();
1020 Page_breaking::line_divisions_rec (vsize system_count,
1021 Line_division const &min_sys,
1022 Line_division const &max_sys,
1023 Line_division *cur_division)
1025 vsize my_index = cur_division->size ();
1029 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1031 others_min += min_sys[i];
1032 others_max += max_sys[i];
1034 others_max = std::min (others_max, (int) system_count);
1035 int real_min = std::max ((int) min_sys[my_index], (int) system_count - others_max);
1036 int real_max = std::min ((int) max_sys[my_index], (int) system_count - others_min);
1038 if (real_min > real_max || real_min < 0)
1040 /* this should never happen within a recursive call. If it happens
1041 at all, it means that we were called with an unsolvable problem
1042 and we should return an empty result */
1043 assert (my_index == 0);
1047 for (int i = real_min; i <= real_max; i++)
1049 cur_division->push_back (i);
1050 if (my_index == min_sys.size () - 1)
1051 current_configurations_.push_back (*cur_division);
1053 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1054 cur_division->pop_back ();
1059 Page_breaking::compute_line_heights ()
1061 Real prev_hanging = 0;
1062 Real prev_hanging_begin = 0;
1063 Real prev_hanging_rest = 0;
1065 // refpoint_hanging is the y coordinate of the origin of this system.
1066 // It may not be the same as refpoint_extent[UP], which is the
1067 // refpoint of the first spaceable staff in this system.
1068 Real prev_refpoint_hanging = 0;
1069 for (vsize i = 0; i < cached_line_details_.size (); i++)
1071 Line_details &cur = cached_line_details_[i];
1072 Line_shape shape = cur.shape_;
1073 Real a = shape.begin_[UP];
1074 Real b = shape.rest_[UP];
1075 bool title = cur.title_;
1076 Real refpoint_hanging = std::max (prev_hanging_begin + a, prev_hanging_rest + b);
1081 Line_details const &prev = cached_line_details_[i - 1];
1082 if (!cur.tight_spacing_)
1084 ? prev.title_padding_
1086 Real min_dist = title
1087 ? prev.title_min_distance_
1088 : prev.min_distance_;
1089 refpoint_hanging = std::max (refpoint_hanging + padding,
1090 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1091 + cur.refpoint_extent_[UP] + min_dist);
1094 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1095 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1096 Real hanging = std::max (hanging_begin, hanging_rest);
1097 cur.tallness_ = hanging - prev_hanging;
1098 prev_hanging = hanging;
1099 prev_hanging_begin = hanging_begin;
1100 prev_hanging_rest = hanging_rest;
1101 prev_refpoint_hanging = refpoint_hanging;
1106 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1109 vsize page_starter = 0;
1110 Real cur_rod_height = 0;
1111 Real cur_spring_height = 0;
1112 Real cur_page_height = page_height (first_page_num, false);
1115 cache_line_details (configuration);
1117 if (cached_line_details_.size ())
1118 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1120 for (vsize i = 0; i < cached_line_details_.size (); i++)
1122 Line_details const &cur = cached_line_details_[i];
1123 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1125 if (cur_rod_height > 0)
1126 ext_len = cur.tallness_;
1128 ext_len = cur.full_height ();
1130 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1131 Real next_rod_height = cur_rod_height + ext_len;
1132 Real next_spring_height = cur_spring_height + spring_len;
1133 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1134 + min_whitespace_at_bottom_of_page (cur);
1135 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1137 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1138 || too_many_lines (next_line_count)
1139 || (prev && scm_is_eq (prev->page_permission_, ly_symbol2scm ("force"))))
1141 line_count = cur.compressed_nontitle_lines_count_;
1142 cur_rod_height = cur.full_height ();
1143 cur_spring_height = 0;
1146 cur_page_height = page_height (first_page_num + ret, false);
1147 cur_page_height -= min_whitespace_at_top_of_page (cur);
1153 cur_rod_height = next_rod_height;
1154 cur_spring_height = next_spring_height;
1155 line_count = next_line_count;
1159 /* there are two potential problems with the last page (because we didn't know
1160 it was the last page until after we managed to fit all the systems to it):
1161 - we are ragged-last but the last page has a compressed spring
1162 - the value returned by page_height (num, true) is smaller than the
1163 value returned by page_height (num, false) and it causes the page not to
1166 In either case, we just need to add one more page. This is because the last
1167 line will always fit on the extra page and by adding one more page to the
1168 end, the previous page is no longer the last page, so our previous
1169 calculations that treated it as a non-last page were ok.
1174 cur_page_height = page_height (first_page_num + ret - 1, true);
1175 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1176 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1178 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1179 && cur_rod_height > cur_page_height
1180 /* don't increase the page count if the last page had only one system */
1181 && cur_rod_height > cached_line_details_.back ().full_height ())
1183 assert (ret <= cached_line_details_.size ());
1189 // If systems_per_page_ is positive, we don't really try to space on N pages;
1190 // we just put the requested number of systems on each page and penalize
1191 // if the result doesn't have N pages.
1193 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1195 Page_spacing_result ret;
1197 if (systems_per_page_ > 0)
1199 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1200 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1204 cache_line_details (configuration);
1205 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1206 && n <= cached_line_details_.size ());
1209 programming_error ("number of pages is out of bounds");
1211 if (n == 1 && valid_n)
1212 ret = space_systems_on_1_page (cached_line_details_,
1213 page_height (first_page_num, is_last ()),
1214 ragged () || (is_last () && ragged_last ()));
1215 else if (n == 2 && valid_n)
1216 ret = space_systems_on_2_pages (configuration, first_page_num);
1219 Page_spacer ps (cached_line_details_, first_page_num, this);
1223 return finalize_spacing_result (configuration, ret);
1227 Page_breaking::blank_page_penalty () const
1232 penalty_sym = ly_symbol2scm ("blank-last-page-penalty");
1233 else if (ends_score ())
1234 penalty_sym = ly_symbol2scm ("blank-after-score-page-penalty");
1236 penalty_sym = ly_symbol2scm ("blank-page-penalty");
1238 Break_position const &pos = breaks_[current_end_breakpoint_];
1239 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1240 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1242 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1245 // If systems_per_page_ is positive, we don't really try to space on N
1246 // or N+1 pages; see the comment to space_systems_on_n_pages.
1248 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1249 Real penalty_for_fewer_pages)
1251 Page_spacing_result n_res;
1252 Page_spacing_result m_res;
1254 if (systems_per_page_ > 0)
1256 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1257 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1261 cache_line_details (configuration);
1262 vsize min_p_count = min_page_count (configuration, first_page_num);
1263 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1266 programming_error ("both page counts are out of bounds");
1268 if (n == 1 && valid_n)
1270 bool rag = ragged () || (is_last () && ragged_last ());
1271 Real height = page_height (first_page_num, is_last ());
1273 if (1 >= min_p_count)
1274 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1275 if (1 < cached_line_details_.size ())
1276 m_res = space_systems_on_2_pages (configuration, first_page_num);
1280 Page_spacer ps (cached_line_details_, first_page_num, this);
1282 if (n >= min_p_count || !valid_n)
1283 n_res = ps.solve (n);
1284 if (n < cached_line_details_.size () || !valid_n)
1285 m_res = ps.solve (n + 1);
1288 m_res = finalize_spacing_result (configuration, m_res);
1289 n_res = finalize_spacing_result (configuration, n_res);
1291 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1292 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1294 if (n_res.force_.size ())
1295 n_res.force_.back () += penalty_for_fewer_pages;
1297 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1301 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1303 if (systems_per_page_ > 0)
1304 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1306 cache_line_details (configuration);
1307 Page_spacer ps (cached_line_details_, first_page_num, this);
1309 return finalize_spacing_result (configuration, ps.solve ());
1313 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1314 vsize first_page_num)
1316 Page_spacing_result res;
1317 Page_spacing space (page_height (first_page_num, false), this);
1320 vsize page_first_line = 0;
1322 cache_line_details (configuration);
1323 while (line < cached_line_details_.size ())
1327 space.resize (page_height (first_page_num + page, false));
1329 int system_count_on_this_page = 0;
1330 while (system_count_on_this_page < systems_per_page_
1331 && line < cached_line_details_.size ())
1333 Line_details const &cur_line = cached_line_details_[line];
1334 space.append_system (cur_line);
1335 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1338 if (scm_is_eq (cur_line.page_permission_, ly_symbol2scm ("force")))
1342 res.systems_per_page_.push_back (line - page_first_line);
1344 res.force_.push_back (space.force_);
1345 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1346 if (system_count_on_this_page != systems_per_page_)
1348 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1349 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1350 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1353 page_first_line = line;
1356 /* Recalculate forces for the last page because we know now that is
1357 really the last page. */
1358 space.resize (page_height (first_page_num + page, true));
1359 res.force_.back () = space.force_;
1360 return finalize_spacing_result (configuration, res);
1364 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1366 // TODO: add support for min/max-systems-per-page.
1367 Page_spacing_result res;
1369 vsize page_first_line = 0;
1370 Page_spacing space (page_height (first_page_num, false), this);
1372 cache_line_details (configuration);
1373 for (vsize line = 0; line < cached_line_details_.size (); line++)
1375 Real prev_force = space.force_;
1376 space.append_system (cached_line_details_[line]);
1377 if ((line > page_first_line)
1378 && (isinf (space.force_)
1380 && scm_is_eq (cached_line_details_[line - 1].page_permission_,
1381 ly_symbol2scm ("force")))))
1383 res.systems_per_page_.push_back (line - page_first_line);
1384 res.force_.push_back (prev_force);
1385 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1387 space.resize (page_height (first_page_num + page, false));
1389 space.append_system (cached_line_details_[line]);
1390 page_first_line = line;
1393 if (line == cached_line_details_.size () - 1)
1395 /* This is the last line */
1396 /* When the last page height was computed, we did not know yet that it
1397 * was the last one. If the systems put on it don't fit anymore, the last
1398 * system is moved to a new page */
1399 space.resize (page_height (first_page_num + page, true));
1400 if ((line > page_first_line) && (isinf (space.force_)))
1402 res.systems_per_page_.push_back (line - page_first_line);
1403 res.force_.push_back (prev_force);
1404 /* the last page containing the last line */
1405 space.resize (page_height (first_page_num + page + 1, true));
1407 space.append_system (cached_line_details_[line]);
1408 res.systems_per_page_.push_back (1);
1409 res.force_.push_back (space.force_);
1410 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1411 res.penalty_ += cached_line_details_[line].page_penalty_;
1415 res.systems_per_page_.push_back (line + 1 - page_first_line);
1416 res.force_.push_back (space.force_);
1417 res.penalty_ += cached_line_details_[line].page_penalty_;
1421 return finalize_spacing_result (configuration, res);
1424 /* Calculate demerits and fix res.systems_per_page_ so that
1425 it refers to the original line numbers, not the ones given by compress_lines (). */
1427 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1429 if (res.force_.empty ())
1432 cache_line_details (configuration);
1433 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1435 Real line_force = 0;
1436 Real line_penalty = 0;
1437 Real page_demerits = res.penalty_;
1438 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1440 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1442 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1443 line_penalty += uncompressed_line_details_[i].break_penalty_;
1446 for (vsize i = ragged () ? res.force_.size () - 1 : 0;
1447 i < res.force_.size () - (is_last () && ragged_last ());
1450 Real f = res.force_[i];
1452 page_demerits += std::min (f * f, BAD_SPACING_PENALTY);
1455 /* for a while we tried averaging page and line forces across pages instead
1456 of summing them, but it caused a problem: if there is a single page
1457 with a very bad page force (for example because of a forced page break),
1458 the page breaker will put in a _lot_ of pages so that the bad force
1459 becomes averaged out over many pages. */
1460 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1465 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1466 are by far the most common cases, we have special functions for them.
1468 space_systems_on_1_page has a different calling convention than most of the
1469 space_systems functions. This is because space_systems_on_1_page is (unlike
1470 the other space_systems functions) sometimes called on subsets of a full
1473 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1475 Page_spacing space (page_height, this);
1476 Page_spacing_result ret;
1479 for (vsize i = 0; i < lines.size (); i++)
1481 space.append_system (lines[i]);
1482 line_count += lines[i].compressed_nontitle_lines_count_;
1485 ret.systems_per_page_.push_back (lines.size ());
1486 ret.force_.push_back (ragged ? std::min (space.force_, 0.0) : space.force_);
1487 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1488 ret.system_count_status_ |= line_count_status (line_count);
1490 /* don't do finalize_spacing_result () because we are only an internal function */
1495 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1497 Real page1_height = page_height (first_page_num, false);
1498 Real page2_height = page_height (first_page_num + 1, is_last ());
1499 bool ragged1 = ragged ();
1500 bool ragged2 = ragged () || (is_last () && ragged_last ());
1502 /* if there is a forced break, this reduces to 2 1-page problems */
1503 cache_line_details (configuration);
1504 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1505 if (scm_is_eq (cached_line_details_[i].page_permission_,
1506 ly_symbol2scm ("force")))
1508 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1509 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1510 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1511 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1513 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1514 p1.force_.push_back (p2.force_[0]);
1515 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1516 p1.system_count_status_ |= p2.system_count_status_;
1520 vector<Real> page1_force;
1521 vector<Real> page2_force;
1523 // page1_penalty and page2_penalty store the penalties based
1524 // on min-systems-per-page and max-systems-per-page.
1525 vector<Real> page1_penalty;
1526 vector<Real> page2_penalty;
1528 // page1_status and page2_status keep track of whether the min-systems-per-page
1529 // and max-systems-per-page constraints are satisfied.
1530 vector<int> page1_status;
1531 vector<int> page2_status;
1533 Page_spacing page1 (page1_height, this);
1534 Page_spacing page2 (page2_height, this);
1535 int page1_line_count = 0;
1536 int page2_line_count = 0;
1538 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1539 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1540 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1541 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1542 page1_status.resize (cached_line_details_.size () - 1, 0);
1543 page2_status.resize (cached_line_details_.size () - 1, 0);
1545 /* find the page 1 and page 2 forces for each page-breaking position */
1546 for (vsize i = 0; i < page1_force.size (); i++)
1548 page1.append_system (cached_line_details_[i]);
1549 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1550 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1551 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1553 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1554 page1_penalty[i] = line_count_penalty (page1_line_count);
1555 page1_status[i] = line_count_status (page1_line_count);
1558 page2_force[page2_force.size () - 1 - i]
1559 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1560 else if (ragged2 && page2.force_ > 0)
1561 page2_force[page2_force.size () - 1 - i] = 0.0;
1563 page2_force[page2_force.size () - 1 - i] = page2.force_;
1564 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1565 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1568 /* find the position that minimises the sum of the page forces */
1569 vsize best_sys_count = 1;
1570 Real best_demerits = infinity_f;
1571 for (vsize i = 0; i < page1_force.size (); i++)
1573 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1575 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1576 // constraints. That is, we penalize harshly when they don't happen
1577 // but we don't completely reject.
1579 + page1_penalty[i] + page2_penalty[i]
1580 + cached_line_details_[i + 1].page_penalty_
1581 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1582 if (dem < best_demerits)
1584 best_demerits = dem;
1585 best_sys_count = i + 1;
1589 Page_spacing_result ret;
1590 ret.systems_per_page_.push_back (best_sys_count);
1591 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1592 ret.force_.push_back (page1_force[best_sys_count - 1]);
1593 ret.force_.push_back (page2_force[best_sys_count - 1]);
1594 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1595 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1596 + cached_line_details_.back ().page_penalty_
1597 + cached_line_details_.back ().turn_penalty_
1598 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1600 /* don't do finalize_spacing_result () because we are only an internal function */
1605 Page_breaking::all_lines_stretched (vsize configuration)
1607 cache_line_details (configuration);
1608 for (vsize i = 0; i < cached_line_details_.size (); i++)
1609 if (cached_line_details_[i].force_ < 0)
1615 Page_breaking::Line_division
1616 Page_breaking::current_configuration (vsize configuration_index) const
1618 return current_configurations_[configuration_index];
1622 Page_breaking::is_last () const
1624 return current_end_breakpoint_ == last_break_position ();
1628 Page_breaking::ends_score () const
1630 return breaks_[current_end_breakpoint_].score_ender_;
1634 Page_breaking::last_break_position () const
1636 return breaks_.size () - 1;
1639 // This gives the minimum distance between the top of the
1640 // printable area (ie. the bottom of the top-margin) and
1641 // the extent box of the topmost system.
1643 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1645 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1647 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1649 Real min_distance = -infinity_f;
1652 Page_layout_problem::read_spacing_spec (first_system_spacing,
1654 ly_symbol2scm ("minimum-distance"));
1655 Page_layout_problem::read_spacing_spec (first_system_spacing,
1657 ly_symbol2scm ("padding"));
1659 // FIXME: take into account the height of the header
1660 Real translate = std::max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1661 return std::max (0.0, std::max (padding, min_distance - translate));
1665 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1667 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1668 Real min_distance = -infinity_f;
1671 Page_layout_problem::read_spacing_spec (last_system_spacing,
1673 ly_symbol2scm ("minimum-distance"));
1674 Page_layout_problem::read_spacing_spec (last_system_spacing,
1676 ly_symbol2scm ("padding"));
1678 // FIXME: take into account the height of the footer
1679 Real translate = std::min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1680 return std::max (0.0, std::max (padding, min_distance + translate));
1684 Page_breaking::orphan_penalty () const
1686 return orphan_penalty_;