2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2014 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 if ((ragged () && layout.force () < 0.0)
635 || isinf (layout.force ()))
636 warning (_f ("page %d has been compressed", page_num));
638 last_page_force = layout.force ();
640 systems_configs_fncounts = scm_cons (scm_cons (lines, config), systems_configs_fncounts);
641 footnote_count += fn_lines;
642 systems = scm_list_tail (systems, line_count);
645 // TODO: previously, the following loop caused the systems to be
646 // drawn. Now that we no longer draw anything in Page_breaking,
647 // it is safe to merge these two loops.
648 int page_num = first_page_number + lines_per_page.size () - 1;
649 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
651 SCM lines = scm_caar (s);
652 SCM config = scm_cdar (s);
654 bool bookpart_last_page = (s == systems_configs_fncounts);
655 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
657 SCM page_num_scm = scm_from_int (page_num);
658 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
660 SCM labels = SCM_EOL;
661 if (Grob *line = unsmob_grob (scm_car (l)))
663 System *system = dynamic_cast<System *> (line);
664 labels = system->get_property ("labels");
666 else if (Prob *prob = unsmob_prob (scm_car (l)))
667 labels = prob->get_property ("labels");
669 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
670 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
674 ret = scm_cons (page, ret);
678 // By reversing the table, we ensure that duplicated labels (eg. those
679 // straddling a page turn) will appear in the table with their last
681 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
682 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
687 Page_breaking::create_system_list ()
689 SCM specs = book_->get_system_specs ();
690 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
692 if (Paper_score *ps = dynamic_cast<Paper_score *> (unsmob_music_output (scm_car (s))))
694 system_specs_.push_back (System_spec (ps));
698 Prob *pb = unsmob_prob (scm_car (s));
702 system_specs_.push_back (System_spec (pb));
705 if (!system_specs_.size ())
706 system_specs_.push_back (System_spec ());
709 /* The page-turn-page-breaker needs to have a line-breaker between any two
710 columns with non-NULL page-turn-permission.
712 The optimal-breaker needs to have a line-breaker between any two columns
713 with page-break-permission = 'force.
715 By using a grob predicate, we can accommodate both of these uses.
718 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
720 SCM force_sym = ly_symbol2scm ("force");
722 chunks_.push_back (Break_position ());
723 breaks_.push_back (Break_position ());
725 for (vsize i = 0; i < system_specs_.size (); i++)
727 if (system_specs_[i].pscore_)
729 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
730 vector<Grob *> forced_line_break_cols;
732 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
733 if (scm_is_number (system_count))
735 // With system-count given, the line configuration for
736 // this score is fixed. We need to ensure that chunk
737 // boundaries only occur at line breaks.
738 Constrained_breaking breaking (system_specs_[i].pscore_);
739 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
741 for (vsize j = 0; j < details.size (); j++)
742 forced_line_break_cols.push_back (details[j].last_column_);
745 int last_forced_line_break_idx = 0;
746 vsize forced_line_break_idx = 0;
747 vector<vsize> line_breaker_columns;
748 line_breaker_columns.push_back (0);
750 for (vsize j = 1; j < cols.size (); j++)
752 if (forced_line_break_cols.size ())
754 if (forced_line_break_idx >= forced_line_break_cols.size ()
755 || forced_line_break_cols[forced_line_break_idx] != cols[j])
758 forced_line_break_idx++;
761 bool last = (j == cols.size () - 1);
762 bool break_point = is_break && is_break (cols[j]);
763 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
764 Break_position cur_pos = Break_position (i,
765 line_breaker_columns.size (),
769 // NOTE: even in the breaks_ list, forced_line_count_
770 // refers to the number of lines between a
771 // Break_position and the start of that /chunk/. This
772 // is needed for system_count_bounds to work correctly,
773 // since it mixes Break_positions from breaks_ and
775 if (scm_is_number (system_count))
776 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
778 if (break_point || (i == system_specs_.size () - 1 && last))
779 breaks_.push_back (cur_pos);
780 if (chunk_end || last)
782 chunks_.push_back (cur_pos);
783 last_forced_line_break_idx = forced_line_break_idx;
786 if ((break_point || chunk_end) && !last)
787 line_breaker_columns.push_back (j);
789 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
791 else if (system_specs_[i].prob_)
793 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
794 if (break_point || i == system_specs_.size () - 1)
795 breaks_.push_back (Break_position (i));
797 chunks_.push_back (Break_position (i));
799 /* FIXME: shouldn't we push a Null_breaker or similar dummy
801 line_breaking_.push_back (Constrained_breaking (NULL));
806 vector<Break_position>
807 Page_breaking::chunk_list (vsize start_index, vsize end_index)
809 Break_position start = breaks_[start_index];
810 Break_position end = breaks_[end_index];
813 for (; i < chunks_.size () && chunks_[i] <= start; i++)
816 vector<Break_position> ret;
817 ret.push_back (start);
818 for (; i < chunks_.size () && chunks_[i] < end; i++)
819 ret.push_back (chunks_[i]);
824 // Returns the minimum number of _non-title_ lines.
826 Page_breaking::min_system_count (vsize start, vsize end)
828 vector<Break_position> chunks = chunk_list (start, end);
829 Line_division div = system_count_bounds (chunks, true);
832 for (vsize i = 0; i < div.size (); i++)
837 // Returns the maximum number of _non-title_ lines.
839 Page_breaking::max_system_count (vsize start, vsize end)
841 vector<Break_position> chunks = chunk_list (start, end);
842 Line_division div = system_count_bounds (chunks, false);
845 for (vsize i = 0; i < div.size (); i++)
850 // The numbers returned by this function represent either
851 // the maximum or minimum number of _non-title_ lines
853 Page_breaking::Line_division
854 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
857 assert (chunks.size () >= 2);
860 ret.resize (chunks.size () - 1, 0);
862 for (vsize i = 0; i + 1 < chunks.size (); i++)
864 vsize sys = next_system (chunks[i]);
866 if (chunks[i + 1].forced_line_count_)
867 ret[i] = chunks[i + 1].forced_line_count_;
868 else if (system_specs_[sys].pscore_)
872 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
874 ? line_breaking_[sys].min_system_count (start, end)
875 : line_breaking_[sys].max_system_count (start, end);
883 Page_breaking::set_current_breakpoints (vsize start,
886 Line_division lower_bound,
887 Line_division upper_bound)
889 system_count_ = system_count;
890 current_chunks_ = chunk_list (start, end);
891 current_start_breakpoint_ = start;
892 current_end_breakpoint_ = end;
893 clear_line_details_cache ();
895 if (!lower_bound.size ())
896 lower_bound = system_count_bounds (current_chunks_, true);
897 if (!upper_bound.size ())
898 upper_bound = system_count_bounds (current_chunks_, false);
900 assert (lower_bound.size () == current_chunks_.size () - 1);
901 assert (upper_bound.size () == current_chunks_.size () - 1);
903 Line_division work_in_progress;
904 current_configurations_.clear ();
905 line_divisions_rec (system_count,
910 /* we only consider a constant number of configurations. Otherwise,
911 this becomes slow when there are many small scores. The constant
912 5 is somewhat arbitrary. */
913 if (current_configurations_.size () > 5)
915 vector<pair<Real, vsize> > dems_and_indices;
917 for (vsize i = 0; i < current_configurations_.size (); i++)
919 cache_line_details (i);
921 for (vsize j = 0; j < cached_line_details_.size (); j++)
922 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
923 + cached_line_details_[j].break_penalty_;
925 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
927 vector_sort (dems_and_indices, less<pair<Real, vsize> > ());
929 vector<Line_division> best_5_configurations;
930 for (vsize i = 0; i < 5; i++)
931 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
933 clear_line_details_cache ();
934 current_configurations_ = best_5_configurations;
939 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
941 current_chunks_ = chunk_list (start, end);
942 current_start_breakpoint_ = start;
943 current_end_breakpoint_ = end;
944 clear_line_details_cache ();
948 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
950 vsize sys = next_system (current_chunks_[i]);
952 if (current_chunks_[i + 1].forced_line_count_)
953 div.push_back (current_chunks_[i + 1].forced_line_count_);
954 else if (system_specs_[sys].pscore_)
956 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
957 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
962 system_count_ += div.back ();
964 current_configurations_.clear ();
965 current_configurations_.push_back (div);
969 Page_breaking::current_configuration_count () const
971 return current_configurations_.size ();
975 Page_breaking::cache_line_details (vsize configuration_index)
977 if (cached_configuration_index_ != configuration_index)
979 cached_configuration_index_ = configuration_index;
981 Line_division &div = current_configurations_[configuration_index];
982 uncompressed_line_details_.clear ();
983 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
985 vsize sys = next_system (current_chunks_[i]);
986 if (system_specs_[sys].pscore_)
990 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
992 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
993 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
997 assert (div[i] == 0);
998 uncompressed_line_details_.push_back (system_specs_[sys].prob_
999 ? Line_details (system_specs_[sys].prob_, book_->paper_)
1003 cached_line_details_ = compress_lines (uncompressed_line_details_);
1004 compute_line_heights ();
1009 Page_breaking::clear_line_details_cache ()
1011 cached_configuration_index_ = VPOS;
1012 cached_line_details_.clear ();
1013 uncompressed_line_details_.clear ();
1017 Page_breaking::line_divisions_rec (vsize system_count,
1018 Line_division const &min_sys,
1019 Line_division const &max_sys,
1020 Line_division *cur_division)
1022 vsize my_index = cur_division->size ();
1026 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1028 others_min += min_sys[i];
1029 others_max += max_sys[i];
1031 others_max = min (others_max, (int) system_count);
1032 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
1033 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
1035 if (real_min > real_max || real_min < 0)
1037 /* this should never happen within a recursive call. If it happens
1038 at all, it means that we were called with an unsolvable problem
1039 and we should return an empty result */
1040 assert (my_index == 0);
1044 for (int i = real_min; i <= real_max; i++)
1046 cur_division->push_back (i);
1047 if (my_index == min_sys.size () - 1)
1048 current_configurations_.push_back (*cur_division);
1050 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1051 cur_division->pop_back ();
1056 Page_breaking::compute_line_heights ()
1058 Real prev_hanging = 0;
1059 Real prev_hanging_begin = 0;
1060 Real prev_hanging_rest = 0;
1062 // refpoint_hanging is the y coordinate of the origin of this system.
1063 // It may not be the same as refpoint_extent[UP], which is the
1064 // refpoint of the first spaceable staff in this system.
1065 Real prev_refpoint_hanging = 0;
1066 for (vsize i = 0; i < cached_line_details_.size (); i++)
1068 Line_details &cur = cached_line_details_[i];
1069 Line_shape shape = cur.shape_;
1070 Real a = shape.begin_[UP];
1071 Real b = shape.rest_[UP];
1072 bool title = cur.title_;
1073 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1078 Line_details const &prev = cached_line_details_[i - 1];
1079 if (!cur.tight_spacing_)
1081 ? prev.title_padding_
1083 Real min_dist = title
1084 ? prev.title_min_distance_
1085 : prev.min_distance_;
1086 refpoint_hanging = max (refpoint_hanging + padding,
1087 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1088 + cur.refpoint_extent_[UP] + min_dist);
1091 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1092 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1093 Real hanging = max (hanging_begin, hanging_rest);
1094 cur.tallness_ = hanging - prev_hanging;
1095 prev_hanging = hanging;
1096 prev_hanging_begin = hanging_begin;
1097 prev_hanging_rest = hanging_rest;
1098 prev_refpoint_hanging = refpoint_hanging;
1103 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1106 vsize page_starter = 0;
1107 Real cur_rod_height = 0;
1108 Real cur_spring_height = 0;
1109 Real cur_page_height = page_height (first_page_num, false);
1112 cache_line_details (configuration);
1114 if (cached_line_details_.size ())
1115 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1117 for (vsize i = 0; i < cached_line_details_.size (); i++)
1119 Line_details const &cur = cached_line_details_[i];
1120 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1122 if (cur_rod_height > 0)
1123 ext_len = cur.tallness_;
1125 ext_len = cur.full_height ();
1127 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1128 Real next_rod_height = cur_rod_height + ext_len;
1129 Real next_spring_height = cur_spring_height + spring_len;
1130 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1131 + min_whitespace_at_bottom_of_page (cur);
1132 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1134 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1135 || too_many_lines (next_line_count)
1136 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1138 line_count = cur.compressed_nontitle_lines_count_;
1139 cur_rod_height = cur.full_height ();
1140 cur_spring_height = 0;
1143 cur_page_height = page_height (first_page_num + ret, false);
1144 cur_page_height -= min_whitespace_at_top_of_page (cur);
1150 cur_rod_height = next_rod_height;
1151 cur_spring_height = next_spring_height;
1152 line_count = next_line_count;
1156 /* there are two potential problems with the last page (because we didn't know
1157 it was the last page until after we managed to fit all the systems to it):
1158 - we are ragged-last but the last page has a compressed spring
1159 - the value returned by page_height (num, true) is smaller than the
1160 value returned by page_height (num, false) and it causes the page not to
1163 In either case, we just need to add one more page. This is because the last
1164 line will always fit on the extra page and by adding one more page to the
1165 end, the previous page is no longer the last page, so our previous
1166 calculations that treated it as a non-last page were ok.
1171 cur_page_height = page_height (first_page_num + ret - 1, true);
1172 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1173 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1175 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1176 && cur_rod_height > cur_page_height
1177 /* don't increase the page count if the last page had only one system */
1178 && cur_rod_height > cached_line_details_.back ().full_height ())
1180 assert (ret <= cached_line_details_.size ());
1186 // If systems_per_page_ is positive, we don't really try to space on N pages;
1187 // we just put the requested number of systems on each page and penalize
1188 // if the result doesn't have N pages.
1190 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1192 Page_spacing_result ret;
1194 if (systems_per_page_ > 0)
1196 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1197 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1201 cache_line_details (configuration);
1202 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1203 && n <= cached_line_details_.size ());
1206 programming_error ("number of pages is out of bounds");
1208 if (n == 1 && valid_n)
1209 ret = space_systems_on_1_page (cached_line_details_,
1210 page_height (first_page_num, is_last ()),
1211 ragged () || (is_last () && ragged_last ()));
1212 else if (n == 2 && valid_n)
1213 ret = space_systems_on_2_pages (configuration, first_page_num);
1216 Page_spacer ps (cached_line_details_, first_page_num, this);
1220 return finalize_spacing_result (configuration, ret);
1224 Page_breaking::blank_page_penalty () const
1229 penalty_sym = ly_symbol2scm ("blank-last-page-penalty");
1230 else if (ends_score ())
1231 penalty_sym = ly_symbol2scm ("blank-after-score-page-penalty");
1233 penalty_sym = ly_symbol2scm ("blank-page-penalty");
1235 Break_position const &pos = breaks_[current_end_breakpoint_];
1236 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1237 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1239 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1242 // If systems_per_page_ is positive, we don't really try to space on N
1243 // or N+1 pages; see the comment to space_systems_on_n_pages.
1245 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1246 Real penalty_for_fewer_pages)
1248 Page_spacing_result n_res;
1249 Page_spacing_result m_res;
1251 if (systems_per_page_ > 0)
1253 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1254 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1258 cache_line_details (configuration);
1259 vsize min_p_count = min_page_count (configuration, first_page_num);
1260 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1263 programming_error ("both page counts are out of bounds");
1265 if (n == 1 && valid_n)
1267 bool rag = ragged () || (is_last () && ragged_last ());
1268 Real height = page_height (first_page_num, is_last ());
1270 if (1 >= min_p_count)
1271 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1272 if (1 < cached_line_details_.size ())
1273 m_res = space_systems_on_2_pages (configuration, first_page_num);
1277 Page_spacer ps (cached_line_details_, first_page_num, this);
1279 if (n >= min_p_count || !valid_n)
1280 n_res = ps.solve (n);
1281 if (n < cached_line_details_.size () || !valid_n)
1282 m_res = ps.solve (n + 1);
1285 m_res = finalize_spacing_result (configuration, m_res);
1286 n_res = finalize_spacing_result (configuration, n_res);
1288 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1289 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1291 if (n_res.force_.size ())
1292 n_res.force_.back () += penalty_for_fewer_pages;
1294 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1298 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1300 if (systems_per_page_ > 0)
1301 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1303 cache_line_details (configuration);
1304 Page_spacer ps (cached_line_details_, first_page_num, this);
1306 return finalize_spacing_result (configuration, ps.solve ());
1310 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1311 vsize first_page_num)
1313 Page_spacing_result res;
1314 Page_spacing space (page_height (first_page_num, false), this);
1317 vsize page_first_line = 0;
1319 cache_line_details (configuration);
1320 while (line < cached_line_details_.size ())
1324 space.resize (page_height (first_page_num + page, false));
1326 int system_count_on_this_page = 0;
1327 while (system_count_on_this_page < systems_per_page_
1328 && line < cached_line_details_.size ())
1330 Line_details const &cur_line = cached_line_details_[line];
1331 space.append_system (cur_line);
1332 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1335 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1339 res.systems_per_page_.push_back (line - page_first_line);
1341 res.force_.push_back (space.force_);
1342 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1343 if (system_count_on_this_page != systems_per_page_)
1345 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1346 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1347 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1350 page_first_line = line;
1353 /* Recalculate forces for the last page because we know now that is
1354 really the last page. */
1355 space.resize (page_height (first_page_num + page, true));
1356 res.force_.back () = space.force_;
1357 return finalize_spacing_result (configuration, res);
1361 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1363 // TODO: add support for min/max-systems-per-page.
1364 Page_spacing_result res;
1366 vsize page_first_line = 0;
1367 Page_spacing space (page_height (first_page_num, false), this);
1369 cache_line_details (configuration);
1370 for (vsize line = 0; line < cached_line_details_.size (); line++)
1372 Real prev_force = space.force_;
1373 space.append_system (cached_line_details_[line]);
1374 if ((line > page_first_line)
1375 && (isinf (space.force_)
1377 && (cached_line_details_[line - 1].page_permission_ == ly_symbol2scm ("force")))))
1379 res.systems_per_page_.push_back (line - page_first_line);
1380 res.force_.push_back (prev_force);
1381 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1383 space.resize (page_height (first_page_num + page, false));
1385 space.append_system (cached_line_details_[line]);
1386 page_first_line = line;
1389 if (line == cached_line_details_.size () - 1)
1391 /* This is the last line */
1392 /* When the last page height was computed, we did not know yet that it
1393 * was the last one. If the systems put on it don't fit anymore, the last
1394 * system is moved to a new page */
1395 space.resize (page_height (first_page_num + page, true));
1396 if ((line > page_first_line) && (isinf (space.force_)))
1398 res.systems_per_page_.push_back (line - page_first_line);
1399 res.force_.push_back (prev_force);
1400 /* the last page containing the last line */
1401 space.resize (page_height (first_page_num + page + 1, true));
1403 space.append_system (cached_line_details_[line]);
1404 res.systems_per_page_.push_back (1);
1405 res.force_.push_back (space.force_);
1406 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1407 res.penalty_ += cached_line_details_[line].page_penalty_;
1411 res.systems_per_page_.push_back (line + 1 - page_first_line);
1412 res.force_.push_back (space.force_);
1413 res.penalty_ += cached_line_details_[line].page_penalty_;
1417 return finalize_spacing_result (configuration, res);
1420 /* Calculate demerits and fix res.systems_per_page_ so that
1421 it refers to the original line numbers, not the ones given by compress_lines (). */
1423 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1425 if (res.force_.empty ())
1428 cache_line_details (configuration);
1429 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1431 Real line_force = 0;
1432 Real line_penalty = 0;
1433 Real page_demerits = res.penalty_;
1434 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1436 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1438 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1439 line_penalty += uncompressed_line_details_[i].break_penalty_;
1442 for (vsize i = ragged () ? res.force_.size () - 1 : 0;
1443 i < res.force_.size () - ragged_last ();
1446 Real f = res.force_[i];
1448 page_demerits += min (f * f, BAD_SPACING_PENALTY);
1451 /* for a while we tried averaging page and line forces across pages instead
1452 of summing them, but it caused a problem: if there is a single page
1453 with a very bad page force (for example because of a forced page break),
1454 the page breaker will put in a _lot_ of pages so that the bad force
1455 becomes averaged out over many pages. */
1456 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1461 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1462 are by far the most common cases, we have special functions for them.
1464 space_systems_on_1_page has a different calling convention than most of the
1465 space_systems functions. This is because space_systems_on_1_page is (unlike
1466 the other space_systems functions) sometimes called on subsets of a full
1469 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1471 Page_spacing space (page_height, this);
1472 Page_spacing_result ret;
1475 for (vsize i = 0; i < lines.size (); i++)
1477 space.append_system (lines[i]);
1478 line_count += lines[i].compressed_nontitle_lines_count_;
1481 ret.systems_per_page_.push_back (lines.size ());
1482 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1483 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1484 ret.system_count_status_ |= line_count_status (line_count);
1486 /* don't do finalize_spacing_result () because we are only an internal function */
1491 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1493 Real page1_height = page_height (first_page_num, false);
1494 Real page2_height = page_height (first_page_num + 1, is_last ());
1495 bool ragged1 = ragged ();
1496 bool ragged2 = ragged () || (is_last () && ragged_last ());
1498 /* if there is a forced break, this reduces to 2 1-page problems */
1499 cache_line_details (configuration);
1500 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1501 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1503 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1504 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1505 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1506 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1508 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1509 p1.force_.push_back (p2.force_[0]);
1510 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1511 p1.system_count_status_ |= p2.system_count_status_;
1515 vector<Real> page1_force;
1516 vector<Real> page2_force;
1518 // page1_penalty and page2_penalty store the penalties based
1519 // on min-systems-per-page and max-systems-per-page.
1520 vector<Real> page1_penalty;
1521 vector<Real> page2_penalty;
1523 // page1_status and page2_status keep track of whether the min-systems-per-page
1524 // and max-systems-per-page constraints are satisfied.
1525 vector<int> page1_status;
1526 vector<int> page2_status;
1528 Page_spacing page1 (page1_height, this);
1529 Page_spacing page2 (page2_height, this);
1530 int page1_line_count = 0;
1531 int page2_line_count = 0;
1533 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1534 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1535 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1536 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1537 page1_status.resize (cached_line_details_.size () - 1, 0);
1538 page2_status.resize (cached_line_details_.size () - 1, 0);
1540 /* find the page 1 and page 2 forces for each page-breaking position */
1541 for (vsize i = 0; i < page1_force.size (); i++)
1543 page1.append_system (cached_line_details_[i]);
1544 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1545 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1546 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1548 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1549 page1_penalty[i] = line_count_penalty (page1_line_count);
1550 page1_status[i] = line_count_status (page1_line_count);
1553 page2_force[page2_force.size () - 1 - i]
1554 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1555 else if (ragged2 && page2.force_ > 0)
1556 page2_force[page2_force.size () - 1 - i] = 0.0;
1558 page2_force[page2_force.size () - 1 - i] = page2.force_;
1559 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1560 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1563 /* find the position that minimises the sum of the page forces */
1564 vsize best_sys_count = 1;
1565 Real best_demerits = infinity_f;
1566 for (vsize i = 0; i < page1_force.size (); i++)
1568 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1570 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1571 // constraints. That is, we penalize harshly when they don't happen
1572 // but we don't completely reject.
1574 + page1_penalty[i] + page2_penalty[i]
1575 + cached_line_details_[i + 1].page_penalty_
1576 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1577 if (dem < best_demerits)
1579 best_demerits = dem;
1580 best_sys_count = i + 1;
1584 Page_spacing_result ret;
1585 ret.systems_per_page_.push_back (best_sys_count);
1586 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1587 ret.force_.push_back (page1_force[best_sys_count - 1]);
1588 ret.force_.push_back (page2_force[best_sys_count - 1]);
1589 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1590 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1591 + cached_line_details_.back ().page_penalty_
1592 + cached_line_details_.back ().turn_penalty_
1593 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1595 /* don't do finalize_spacing_result () because we are only an internal function */
1600 Page_breaking::all_lines_stretched (vsize configuration)
1602 cache_line_details (configuration);
1603 for (vsize i = 0; i < cached_line_details_.size (); i++)
1604 if (cached_line_details_[i].force_ < 0)
1610 Page_breaking::Line_division
1611 Page_breaking::current_configuration (vsize configuration_index) const
1613 return current_configurations_[configuration_index];
1617 Page_breaking::is_last () const
1619 return current_end_breakpoint_ == last_break_position ();
1623 Page_breaking::ends_score () const
1625 return breaks_[current_end_breakpoint_].score_ender_;
1629 Page_breaking::last_break_position () const
1631 return breaks_.size () - 1;
1634 // This gives the minimum distance between the top of the
1635 // printable area (ie. the bottom of the top-margin) and
1636 // the extent box of the topmost system.
1638 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1640 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1642 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1644 Real min_distance = -infinity_f;
1647 Page_layout_problem::read_spacing_spec (first_system_spacing,
1649 ly_symbol2scm ("minimum-distance"));
1650 Page_layout_problem::read_spacing_spec (first_system_spacing,
1652 ly_symbol2scm ("padding"));
1654 // FIXME: take into account the height of the header
1655 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1656 return max (0.0, max (padding, min_distance - translate));
1660 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1662 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1663 Real min_distance = -infinity_f;
1666 Page_layout_problem::read_spacing_spec (last_system_spacing,
1668 ly_symbol2scm ("minimum-distance"));
1669 Page_layout_problem::read_spacing_spec (last_system_spacing,
1671 ly_symbol2scm ("padding"));
1673 // FIXME: take into account the height of the footer
1674 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1675 return max (0.0, max (padding, min_distance + translate));
1679 Page_breaking::orphan_penalty () const
1681 return orphan_penalty_;