2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2011 Joe Neeman <joeneeman@gmail.com>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
21 This is a utility class for page-breaking algorithms. There are some complex
22 parts of this class, some of which are useful to understand if you intend
23 to write a page breaking algorithm (ie. a subclass of Page_breaking). Most
24 of these complexities were introduced in order to break the problem of
25 page-breaking into simpler subproblems and to hide some of the bookkeeping
26 complexities of page breaking from the page breaking algorithms.
29 There are several functions that actually distribute systems across pages
30 (for example, the space_systems_XXX and pack_systems_XXX functions). If
31 each of these functions had to handle \noPageBreak, it would be a mess.
32 Therefore, we handle \noPageBreak by "compressing" the list of systems
33 before doing any layout: we concatenate any two systems separated by a
34 \noPageBreak into a single system. The page-breaking functions can do their
35 magic without encountering a \noPageBreak; we then "uncompress" the systems
36 at the end. We almost always work with cached_line_details_, which are
40 The basic operation of a page breaking algorithm is to repeatedly request
41 some systems from the line-breaker and place those systems on some pages.
42 With each repetition, the page breaking algorithm asks the line-breaker for
43 some systems that it thinks will help it achieve a better layout. The
44 Page_breaking class provides functionality to facilitate this in the case
45 that the page breaking algorithm only cares about the number of systems.
47 Even if a page breaking algorithm only cares number of systems, there may
48 be many ways to satisfy its request. For example, in a piece with 2 scores
49 and a request for 10 systems, we could return 5 systems from each score or
50 4 from the first and 6 from the second. Even within a score, we might
51 want to try several different line breaking configurations with a fixed
52 system count; if there is a forced \pageBreak, for example, we might wish
53 to tweak the number of systems on both sides of the \pageBreak independently.
55 The Page_breaking class takes care of finding these configurations. It
56 divides the piece into "chunks" and sets up the line-breaker in such a way
57 that the number of systems in each chunk can be modified independently.
58 Chunks never cross score boundaries; each title and markup is its own chunk.
59 When a page breaking algorithm requests a number of systems, the Page_breaker
60 stores an array of potential configurations, which the page breaking
61 algorithm can iterate over using current_configuration(vsize).
64 A Line_division is simply a way of storing the exact way in which the
65 total number of systems is distributed among chunks. Note that a
66 Line_division may not (in fact, usually will not) describe all of the chunks
67 in the entire book. Rather, it will describe the subset of chunks that lie
68 between some fixed starting and ending point. This subset of chunks changes
69 whenever a page breaking algorithm asks to consider a different pair of
70 starting and ending breakpoints. In particular, a Line_division should be
71 discarded after a call to set_current_breakpoints, since that Line_division
72 refers to a subset of chunks which might be different from the current
73 subset of chunks under consideration.
75 HOW TO WRITE A PAGE BREAKING ALGORITHM
76 All page breakers supported by this class work more-or-less in the same way.
77 First, they request a particular number of systems by saying
78 set_current_breakpoints (0, last_break_position (), system_count)
79 (never mind what the first two arguments do, I'll get to them later).
80 Alternatively, you can do
81 set_to_ideal_line_configuration (0, last_break_position ()),
82 and the number of systems will be automatically chosen according to what
83 the line breaker wants.
85 If there are multiple scores, there will be many different ways to achieve
86 a certain number of lines. You can see how many alternatives are available
87 with current_configuration_count (). For every i from 0 to
88 current_configuration_count ()-1, you can see the line division of the
89 corresponding configuration with current_configuration (i), or you can try
90 out various page configurations with one of the space_systems_xxx or
91 pack_systems_xxx functions. The first argument to each of these functions
92 is the configuration index.
94 When you're done trying out configurations and you've picked the one
96 break_into_pieces (0, last_break_position (), line_division_that_you_want);
97 return make_pages (systems_per_page, systems ());
98 where systems_per_page is a vector of numbers telling how many systems are
99 on each page. You can get your systems_per_page vector by looking inside
100 the Page_spacing_results that are returned by space_systems_xxx or
103 A note on performance: set_current_breakpoints is EXPONENTIALLY SLOW unless
104 you constrain it by giving it a lower or an upper bound on the configurations
105 it looks for. Optimal_page_breaking, for example, works by trying
106 out a bunch of configurations, increasing the system count by one, trying
107 again and so on. Each time we increase the system count, we assume that the
108 best new configurations are going to be elementwise larger than the
109 best configuration for the previous system count (in other words, we're going
110 to get a new configuration just by adding an extra line to sone score
111 and leaving the rest the same). Therefore, we pass the best previous line
112 division as an lower bound to set_current_breakpoints.
114 Now you should be in a position to understand Optimal_page_breaking::solve.
115 Go ahead and read that before finding out, in the next paragraph,
116 what the first two arguments to set_current_breakpoints do.
119 Sometimes, it's useful to run this whole page-breaking machinery on a subset
120 of the book. To do this, you can mark certain "breaks" in the book (a poor
121 choice of name, perhaps, since a "break" here is different from a page break)
122 and you can run page breaking between any two breaks. You mark your breaks
123 by providing a Break_predicate (and, if you want, a Prob_break_predicate)
124 to Page_breaking's constructor. You then choose a subset of your book
125 by passing the starting and ending breaks to set_current_breakpoints. You
126 can see an example of this in Page_turn_page_breaking, where there is a break
127 everywhere that a page turn is allowed.
130 #include "page-breaking.hh"
132 #include "international.hh"
134 #include "line-interface.hh"
135 #include "output-def.hh"
136 #include "page-layout-problem.hh"
137 #include "page-spacing.hh"
138 #include "paper-book.hh"
139 #include "paper-score.hh"
140 #include "paper-system.hh"
141 #include "text-interface.hh"
145 /* for each forbidden page break, merge the systems around it into one
147 static vector<Line_details>
148 compress_lines (const vector<Line_details> &orig)
150 vector<Line_details> ret;
152 for (vsize i = 0; i < orig.size (); i++)
154 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
156 Line_details const &old = ret.back ();
157 Line_details compressed = orig[i];
159 We must account for the padding between the lines that we are compressing.
160 The padding values come from "old," which is the upper system here. Note
161 the meaning of tight-spacing: if a system has tight-spacing, then the padding
162 _before_ it is ignored.
165 if (!orig[i].tight_spacing_)
166 padding = orig[i].title_ ? old.title_padding_ : old.padding_;
168 // FIXME: double check these. Doesn't foo.piggyback (bar) mean
169 // that foo goes on top?
170 // TODO: break out a Line_details::piggyback from here?
171 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
172 compressed.refpoint_extent_[UP] = old.refpoint_extent_[UP];
173 compressed.refpoint_extent_[DOWN] += compressed.shape_.rest_[UP] - old.shape_.rest_[UP];
174 compressed.space_ += old.space_;
175 compressed.inverse_hooke_ += old.inverse_hooke_;
177 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
178 compressed.compressed_nontitle_lines_count_
179 = old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
181 // compressed.title_ is true if and only if the first of its
182 // compressed lines was a title.
183 compressed.title_ = old.title_;
185 // adds footnotes of one line to the footnotes of another
186 compressed.footnotes_.insert (compressed.footnotes_.begin (),
187 old.footnotes_.begin (), old.footnotes_.end ());
189 ret.back () = compressed;
193 ret.push_back (orig[i]);
194 ret.back ().force_ = 0;
200 /* translate the number of systems-per-page into something meaningful for
201 the uncompressed lines.
204 uncompress_solution (vector<vsize> const &systems_per_page,
205 vector<Line_details> const &compressed)
210 for (vsize i = 0; i < systems_per_page.size (); i++)
212 int compressed_count = 0;
213 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
214 compressed_count += compressed[j].compressed_lines_count_ - 1;
216 ret.push_back (systems_per_page[i] + compressed_count);
217 start_sys += systems_per_page[i];
222 /* for Page_breaking, the start index (when we are dealing with the stuff
223 between a pair of breakpoints) refers to the break_ index of the end of
224 the previous page. So the system index of the start of the current page
225 could either be the same as the end of the previous page or one more than
228 /* Turn a break index into the sys index that starts the next page */
230 Page_breaking::next_system (Break_position const &break_pos) const
232 vsize sys = break_pos.system_spec_index_;
234 if (sys == VPOS) /* beginning of the book */
236 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
237 return sys; /* the score overflows the previous page */
238 return sys + 1; /* this page starts with a new System_spec */
241 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
245 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
246 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
247 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
248 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
249 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
250 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
251 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
253 Stencil *footnote_separator = Page_layout_problem::get_footnote_separator_stencil (pb->paper_);
255 if (footnote_separator)
257 Interval separator_extent = footnote_separator->extent (Y_AXIS);
258 Real separator_span = separator_extent.length ();
260 footnote_separator_stencil_height_ = separator_span;
263 footnote_separator_stencil_height_ = 0.0;
265 footnote_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
266 footnote_footer_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-footer-padding"), 0.0);
268 footnote_number_raise_ = (to_boolean (pb->paper_->c_variable ("footnote-auto-numbering"))
269 ? robust_scm2double (pb->paper_->c_variable ("footnote-number-raise"), 0.0)
272 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
274 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
275 min_systems_per_page_ = max_systems_per_page_ = 0;
277 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
279 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
280 min_systems_per_page_ = max_systems_per_page_ = 0;
283 create_system_list ();
284 find_chunks_and_breaks (is_break, prob_break);
287 Page_breaking::~Page_breaking ()
292 Page_breaking::ragged () const
298 Page_breaking::ragged_last () const
304 Page_breaking::systems_per_page () const
306 return systems_per_page_;
310 Page_breaking::max_systems_per_page () const
312 if (systems_per_page_)
313 return systems_per_page_;
314 return max_systems_per_page_;
318 Page_breaking::min_systems_per_page () const
320 if (systems_per_page_)
321 return systems_per_page_;
322 return min_systems_per_page_;
326 Page_breaking::system_count () const
328 return system_count_;
332 Page_breaking::footnote_separator_stencil_height () const
334 return footnote_separator_stencil_height_;
338 Page_breaking::footnote_padding () const
340 return footnote_padding_;
344 Page_breaking::footnote_footer_padding () const
346 return footnote_footer_padding_;
350 Page_breaking::footnote_number_raise () const
352 return footnote_number_raise_;
356 Page_breaking::too_many_lines (int line_count) const
358 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
362 Page_breaking::too_few_lines (int line_count) const
364 return line_count < min_systems_per_page ();
368 Page_breaking::line_count_penalty (int line_count) const
370 if (too_many_lines (line_count))
371 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
372 if (too_few_lines (line_count))
373 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
379 Page_breaking::line_count_status (int line_count) const
381 if (too_many_lines (line_count))
382 return SYSTEM_COUNT_TOO_MANY;
383 if (too_few_lines (line_count))
384 return SYSTEM_COUNT_TOO_FEW;
386 return SYSTEM_COUNT_OK;
389 /* translate indices into breaks_ into start-end parameters for the line breaker */
391 Page_breaking::line_breaker_args (vsize sys,
392 Break_position const &start,
393 Break_position const &end,
394 vsize *line_breaker_start,
395 vsize *line_breaker_end)
397 assert (system_specs_[sys].pscore_);
398 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
400 if (start.system_spec_index_ == sys)
401 *line_breaker_start = start.score_break_;
403 *line_breaker_start = 0;
405 if (end.system_spec_index_ == sys)
406 *line_breaker_end = end.score_break_;
408 *line_breaker_end = VPOS;
412 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
413 Line_division const &div)
415 vector<Break_position> chunks = chunk_list (start_break, end_break);
416 bool ignore_div = false;
417 if (chunks.size () != div.size () + 1)
419 programming_error ("did not find a valid page breaking configuration");
423 for (vsize i = 0; i + 1 < chunks.size (); i++)
425 vsize sys = next_system (chunks[i]);
426 if (system_specs_[sys].pscore_)
430 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
432 vector<Column_x_positions> pos = ignore_div
433 ? line_breaking_[sys].best_solution (start, end)
434 : line_breaking_[sys].solve (start, end, div[i]);
435 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
441 Page_breaking::systems ()
444 for (vsize sys = 0; sys < system_specs_.size (); sys++)
446 if (system_specs_[sys].pscore_)
448 system_specs_[sys].pscore_->root_system ()
449 ->do_break_substitution_and_fixup_refpoints ();
450 SCM lines = system_specs_[sys].pscore_->root_system ()
451 ->get_broken_system_grobs ();
452 ret = scm_cons (lines, ret);
454 else if (Prob *pb = system_specs_[sys].prob_)
456 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
460 return scm_append (scm_reverse (ret));
464 Page_breaking::make_page (int page_num, bool last) const
466 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
467 SCM mod = scm_c_resolve_module ("scm page");
468 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
470 make_page_scm = scm_variable_ref (make_page_scm);
472 return scm_apply_0 (make_page_scm,
473 scm_list_n (book_->self_scm (),
474 ly_symbol2scm ("page-number"), scm_from_int (page_num),
475 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
476 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
480 // Returns the total height of the paper, including margins and
481 // space for the header/footer. This is an upper bound on
482 // page_height, and it doesn't depend on the current page.
484 Page_breaking::paper_height () const
486 return paper_height_;
490 Page_breaking::page_height (int page_num, bool last) const
492 // The caches allow us to store the page heights for any
493 // non-negative page numbers. We use a negative value in the
494 // cache to signal that that position has not yet been initialized.
495 // This means that we won't cache properly if page_num is negative or
496 // if calc_height returns a negative number. But that's likely to
497 // be rare, so it shouldn't affect performance.
498 vector<Real>& cache = last ? last_page_height_cache_ : page_height_cache_;
499 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
500 return cache[page_num];
503 SCM mod = scm_c_resolve_module ("scm page");
504 SCM page = make_page (page_num, last);
505 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
506 calc_height = scm_variable_ref (calc_height);
508 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
509 Real height = scm_to_double (height_scm);
513 if ((int) cache.size () <= page_num)
514 cache.resize (page_num + 1, -1);
515 cache[page_num] = height;
522 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
524 Break_position const &pos = breaks_[breakpoint];
526 if (pos.system_spec_index_ == VPOS)
528 if (system_specs_[pos.system_spec_index_].pscore_)
529 return pos.col_->get_property (str);
530 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
534 Page_breaking::get_page_configuration (SCM systems, int page_num, int footnote_count, bool ragged, bool last)
536 SCM dummy_page = make_page (page_num, last);
537 Page_layout_problem layout (book_, dummy_page, systems, footnote_count);
538 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
542 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, int footnote_num, bool last)
544 // Create a stencil for each system.
545 SCM paper_systems = SCM_EOL;
546 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
548 SCM paper_system = scm_car (s);
549 if (Grob *g = unsmob_grob (scm_car (s)))
551 System *sys = dynamic_cast<System *> (g);
552 paper_system = sys->get_paper_system ();
555 paper_systems = scm_cons (paper_system, paper_systems);
558 // Create the page and draw it.
559 SCM page = make_page (page_num, last);
560 SCM page_module = scm_c_resolve_module ("scm page");
561 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
562 page_stencil = scm_variable_ref (page_stencil);
564 Prob *p = unsmob_prob (page);
565 p->set_property ("lines", paper_systems);
566 p->set_property ("configuration", configuration);
568 Stencil *foot = unsmob_stencil (p->get_property ("foot-stencil"));
570 footnote_num = (to_boolean (book_->paper_->c_variable ("reset-footnotes-on-new-page"))
574 SCM footnotes = Page_layout_problem::get_footnotes_from_lines (systems,
578 Page_layout_problem::add_footnotes_to_footer (footnotes, foot, book_);
580 p->set_property ("foot-stencil", foot->smobbed_copy ());
581 scm_apply_1 (page_stencil, page, SCM_EOL);
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 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
596 if (label_page_table == SCM_UNDEFINED)
597 label_page_table = SCM_EOL;
599 // Build a list of (systems . configuration) pairs. Note that we lay out
600 // the staves and find the configurations before drawing anything. Some
601 // grobs (like tuplet brackets) look at their neighbours while drawing
602 // themselves. If this happens before the neighbouring staves have
603 // been laid out, bad side-effects could happen (in particular,
604 // Align_interface::align_to_ideal_distances might be called).
605 SCM systems_configs_fncounts = SCM_EOL;
606 vsize footnote_count = 0;
608 for (vsize i = 0; i < lines_per_page.size (); i++)
610 int page_num = i + first_page_number;
611 bool bookpart_last_page = (i == lines_per_page.size () - 1);
612 bool rag = ragged () || (bookpart_last_page && ragged_last ());
613 SCM line_count = scm_from_int (lines_per_page[i]);
614 SCM lines = scm_list_head (systems, line_count);
615 int fn_lines = Page_layout_problem::get_footnote_count (lines);
616 SCM config = get_page_configuration (lines, page_num, footnote_count, rag, bookpart_last_page);
618 systems_configs_fncounts = scm_cons (scm_list_3 (lines, config, scm_from_int ((int)footnote_count)), systems_configs_fncounts);
619 footnote_count += fn_lines;
620 systems = scm_list_tail (systems, line_count);
623 // Now it's safe to make the pages.
624 int page_num = first_page_number + lines_per_page.size () - 1;
625 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
627 SCM lines = scm_caar (s);
628 SCM config = scm_cadar (s);
629 int footnote_num = scm_to_int (scm_caddar (s));
631 bool bookpart_last_page = (s == systems_configs_fncounts);
632 SCM page = draw_page (lines, config, page_num, footnote_num, bookpart_last_page);
634 SCM page_num_scm = scm_from_int (page_num);
635 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
637 SCM labels = SCM_EOL;
638 if (Grob *line = unsmob_grob (scm_car (l)))
640 System *system = dynamic_cast<System *> (line);
641 labels = system->get_property ("labels");
643 else if (Prob *prob = unsmob_prob (scm_car (l)))
644 labels = prob->get_property ("labels");
646 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
647 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
651 ret = scm_cons (page, ret);
655 // By reversing the table, we ensure that duplicated labels (eg. those
656 // straddling a page turn) will appear in the table with their last
658 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
659 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
663 /* The page-turn-page-breaker needs to have a line-breaker between any two
664 columns with non-NULL page-turn-permission.
666 The optimal-breaker needs to have a line-breaker between any two columns
667 with page-break-permission = 'force.
669 By using a grob predicate, we can accommodate both of these uses.
672 Page_breaking::create_system_list ()
674 SCM specs = book_->get_system_specs ();
675 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
677 if (Paper_score *ps = dynamic_cast<Paper_score *> (unsmob_music_output (scm_car (s))))
679 system_specs_.push_back (System_spec (ps));
683 Prob *pb = unsmob_prob (scm_car (s));
687 system_specs_.push_back (System_spec (pb));
690 if (!system_specs_.size ())
691 system_specs_.push_back (System_spec ());
695 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
697 SCM force_sym = ly_symbol2scm ("force");
699 chunks_.push_back (Break_position ());
700 breaks_.push_back (Break_position ());
702 for (vsize i = 0; i < system_specs_.size (); i++)
704 if (system_specs_[i].pscore_)
706 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
707 vector<Grob *> forced_line_break_cols;
709 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
710 if (scm_is_number (system_count))
712 // With system-count given, the line configuration for
713 // this score is fixed. We need to ensure that chunk
714 // boundaries only occur at line breaks.
715 Constrained_breaking breaking (system_specs_[i].pscore_);
716 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
718 for (vsize j = 0; j < details.size (); j++)
719 forced_line_break_cols.push_back (details[j].last_column_);
722 int last_forced_line_break_idx = 0;
723 vsize forced_line_break_idx = 0;
724 vector<vsize> line_breaker_columns;
725 line_breaker_columns.push_back (0);
727 for (vsize j = 1; j < cols.size (); j++)
729 if (forced_line_break_cols.size ())
731 if (forced_line_break_idx >= forced_line_break_cols.size ()
732 || forced_line_break_cols[forced_line_break_idx] != cols[j])
735 forced_line_break_idx++;
738 bool last = (j == cols.size () - 1);
739 bool break_point = is_break && is_break (cols[j]);
740 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
741 Break_position cur_pos = Break_position (i,
742 line_breaker_columns.size (),
746 // NOTE: even in the breaks_ list, forced_line_count_
747 // refers to the number of lines between a
748 // Break_position and the start of that /chunk/. This
749 // is needed for system_count_bounds to work correctly,
750 // since it mixes Break_positions from breaks_ and
752 if (scm_is_number (system_count))
753 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
755 if (break_point || (i == system_specs_.size () - 1 && last))
756 breaks_.push_back (cur_pos);
757 if (chunk_end || last)
759 chunks_.push_back (cur_pos);
760 last_forced_line_break_idx = forced_line_break_idx;
763 if ((break_point || chunk_end) && !last)
764 line_breaker_columns.push_back (j);
766 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
768 else if (system_specs_[i].prob_)
770 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
771 if (break_point || i == system_specs_.size () - 1)
772 breaks_.push_back (Break_position (i));
774 chunks_.push_back (Break_position (i));
776 /* FIXME: shouldn't we push a Null_breaker or similar dummy
778 line_breaking_.push_back (Constrained_breaking (NULL));
783 vector<Break_position>
784 Page_breaking::chunk_list (vsize start_index, vsize end_index)
786 Break_position start = breaks_[start_index];
787 Break_position end = breaks_[end_index];
790 for (; i < chunks_.size () && chunks_[i] <= start; i++)
793 vector<Break_position> ret;
794 ret.push_back (start);
795 for (; i < chunks_.size () && chunks_[i] < end; i++)
796 ret.push_back (chunks_[i]);
801 // Returns the minimum number of _non-title_ lines.
803 Page_breaking::min_system_count (vsize start, vsize end)
805 vector<Break_position> chunks = chunk_list (start, end);
806 Line_division div = system_count_bounds (chunks, true);
809 for (vsize i = 0; i < div.size (); i++)
814 // Returns the maximum number of _non-title_ lines.
816 Page_breaking::max_system_count (vsize start, vsize end)
818 vector<Break_position> chunks = chunk_list (start, end);
819 Line_division div = system_count_bounds (chunks, false);
822 for (vsize i = 0; i < div.size (); i++)
827 // The numbers returned by this function represent either
828 // the maximum or minimum number of _non-title_ lines
830 Page_breaking::Line_division
831 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
834 assert (chunks.size () >= 2);
837 ret.resize (chunks.size () - 1, 0);
839 for (vsize i = 0; i + 1 < chunks.size (); i++)
841 vsize sys = next_system (chunks[i]);
843 if (chunks[i + 1].forced_line_count_)
844 ret[i] = chunks[i + 1].forced_line_count_;
845 else if (system_specs_[sys].pscore_)
849 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
851 ? line_breaking_[sys].min_system_count (start, end)
852 : line_breaking_[sys].max_system_count (start, end);
860 Page_breaking::set_current_breakpoints (vsize start,
863 Line_division lower_bound,
864 Line_division upper_bound)
866 system_count_ = system_count;
867 current_chunks_ = chunk_list (start, end);
868 current_start_breakpoint_ = start;
869 current_end_breakpoint_ = end;
870 clear_line_details_cache ();
872 if (!lower_bound.size ())
873 lower_bound = system_count_bounds (current_chunks_, true);
874 if (!upper_bound.size ())
875 upper_bound = system_count_bounds (current_chunks_, false);
877 assert (lower_bound.size () == current_chunks_.size () - 1);
878 assert (upper_bound.size () == current_chunks_.size () - 1);
880 Line_division work_in_progress;
881 current_configurations_.clear ();
882 line_divisions_rec (system_count,
887 /* we only consider a constant number of configurations. Otherwise,
888 this becomes slow when there are many small scores. The constant
889 5 is somewhat arbitrary. */
890 if (current_configurations_.size () > 5)
892 vector<pair<Real, vsize> > dems_and_indices;
894 for (vsize i = 0; i < current_configurations_.size (); i++)
896 cache_line_details (i);
898 for (vsize j = 0; j < cached_line_details_.size (); j++)
899 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
900 + cached_line_details_[j].break_penalty_;
902 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
904 vector_sort (dems_and_indices, less<pair<Real, vsize> > ());
906 vector<Line_division> best_5_configurations;
907 for (vsize i = 0; i < 5; i++)
908 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
910 clear_line_details_cache ();
911 current_configurations_ = best_5_configurations;
916 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
918 current_chunks_ = chunk_list (start, end);
919 current_start_breakpoint_ = start;
920 current_end_breakpoint_ = end;
921 clear_line_details_cache ();
925 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
927 vsize sys = next_system (current_chunks_[i]);
929 if (current_chunks_[i + 1].forced_line_count_)
930 div.push_back (current_chunks_[i + 1].forced_line_count_);
931 else if (system_specs_[sys].pscore_)
933 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
934 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
939 system_count_ += div.back ();
941 current_configurations_.clear ();
942 current_configurations_.push_back (div);
946 Page_breaking::current_configuration_count () const
948 return current_configurations_.size ();
952 Page_breaking::cache_line_details (vsize configuration_index)
954 if (cached_configuration_index_ != configuration_index)
956 cached_configuration_index_ = configuration_index;
958 Line_division &div = current_configurations_[configuration_index];
959 uncompressed_line_details_.clear ();
960 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
962 vsize sys = next_system (current_chunks_[i]);
963 if (system_specs_[sys].pscore_)
967 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
969 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
970 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
974 assert (div[i] == 0);
975 uncompressed_line_details_.push_back (system_specs_[sys].prob_
976 ? Line_details (system_specs_[sys].prob_, book_->paper_)
980 cached_line_details_ = compress_lines (uncompressed_line_details_);
981 compute_line_heights ();
986 Page_breaking::clear_line_details_cache ()
988 cached_configuration_index_ = VPOS;
989 cached_line_details_.clear ();
990 uncompressed_line_details_.clear ();
994 Page_breaking::line_divisions_rec (vsize system_count,
995 Line_division const &min_sys,
996 Line_division const &max_sys,
997 Line_division *cur_division)
999 vsize my_index = cur_division->size ();
1003 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1005 others_min += min_sys[i];
1006 others_max += max_sys[i];
1008 others_max = min (others_max, (int) system_count);
1009 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
1010 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
1012 if (real_min > real_max || real_min < 0)
1014 /* this should never happen within a recursive call. If it happens
1015 at all, it means that we were called with an unsolvable problem
1016 and we should return an empty result */
1017 assert (my_index == 0);
1021 for (int i = real_min; i <= real_max; i++)
1023 cur_division->push_back (i);
1024 if (my_index == min_sys.size () - 1)
1025 current_configurations_.push_back (*cur_division);
1027 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1028 cur_division->pop_back ();
1033 Page_breaking::compute_line_heights ()
1035 Real prev_hanging = 0;
1036 Real prev_hanging_begin = 0;
1037 Real prev_hanging_rest = 0;
1039 // refpoint_hanging is the y coordinate of the origin of this system.
1040 // It may not be the same as refpoint_extent[UP], which is the
1041 // refpoint of the first spaceable staff in this system.
1042 Real prev_refpoint_hanging = 0;
1043 for (vsize i = 0; i < cached_line_details_.size (); i++)
1045 Line_details &cur = cached_line_details_[i];
1046 Line_shape shape = cur.shape_;
1047 Real a = shape.begin_[UP];
1048 Real b = shape.rest_[UP];
1049 bool title = cur.title_;
1050 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1055 Line_details const &prev = cached_line_details_[i - 1];
1056 if (!cur.tight_spacing_)
1058 ? prev.title_padding_
1060 Real min_dist = title
1061 ? prev.title_min_distance_
1062 : prev.min_distance_;
1063 refpoint_hanging = max (refpoint_hanging + padding,
1064 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1065 + cur.refpoint_extent_[UP] + min_dist);
1068 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1069 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1070 Real hanging = max (hanging_begin, hanging_rest);
1071 cur.tallness_ = hanging - prev_hanging;
1072 prev_hanging = hanging;
1073 prev_hanging_begin = hanging_begin;
1074 prev_hanging_rest = hanging_rest;
1075 prev_refpoint_hanging = refpoint_hanging;
1080 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1083 vsize page_starter = 0;
1084 Real cur_rod_height = 0;
1085 Real cur_spring_height = 0;
1086 Real cur_page_height = page_height (first_page_num, false);
1089 cache_line_details (configuration);
1091 if (cached_line_details_.size ())
1092 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1094 for (vsize i = 0; i < cached_line_details_.size (); i++)
1096 Line_details const &cur = cached_line_details_[i];
1097 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1099 if (cur_rod_height > 0)
1100 ext_len = cur.tallness_;
1102 ext_len = cur.full_height ();
1104 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1105 Real next_rod_height = cur_rod_height + ext_len;
1106 Real next_spring_height = cur_spring_height + spring_len;
1107 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1108 + min_whitespace_at_bottom_of_page (cur);
1109 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1111 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1112 || too_many_lines (next_line_count)
1113 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1115 line_count = cur.compressed_nontitle_lines_count_;
1116 cur_rod_height = cur.full_height ();
1117 cur_spring_height = 0;
1120 cur_page_height = page_height (first_page_num + ret, false);
1121 cur_page_height -= min_whitespace_at_top_of_page (cur);
1127 cur_rod_height = next_rod_height;
1128 cur_spring_height = next_spring_height;
1129 line_count = next_line_count;
1133 /* there are two potential problems with the last page (because we didn't know
1134 it was the last page until after we managed to fit all the systems to it):
1135 - we are ragged-last but the last page has a compressed spring
1136 - the value returned by page_height (num, true) is smaller than the
1137 value returned by page_height (num, false) and it causes the page not to
1140 In either case, we just need to add one more page. This is because the last
1141 line will always fit on the extra page and by adding one more page to the
1142 end, the previous page is no longer the last page, so our previous
1143 calculations that treated it as a non-last page were ok.
1148 cur_page_height = page_height (first_page_num + ret - 1, true);
1149 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1150 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1152 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1153 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1154 && cur_height > cur_page_height
1155 /* don't increase the page count if the last page had only one system */
1156 && cur_rod_height > cached_line_details_.back ().full_height ())
1158 assert (ret <= cached_line_details_.size ());
1164 // If systems_per_page_ is positive, we don't really try to space on N pages;
1165 // we just put the requested number of systems on each page and penalize
1166 // if the result doesn't have N pages.
1168 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1170 Page_spacing_result ret;
1172 if (systems_per_page_ > 0)
1174 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1175 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1179 cache_line_details (configuration);
1180 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1181 && n <= cached_line_details_.size ());
1184 programming_error ("number of pages is out of bounds");
1186 if (n == 1 && valid_n)
1187 ret = space_systems_on_1_page (cached_line_details_,
1188 page_height (first_page_num, is_last ()),
1189 ragged () || (is_last () && ragged_last ()));
1190 else if (n == 2 && valid_n)
1191 ret = space_systems_on_2_pages (configuration, first_page_num);
1194 Page_spacer ps (cached_line_details_, first_page_num, this);
1198 return finalize_spacing_result (configuration, ret);
1202 Page_breaking::blank_page_penalty () const
1207 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1208 else if (ends_score ())
1209 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1211 penalty_sym = ly_symbol2scm ("blank-page-force");
1213 Break_position const &pos = breaks_[current_end_breakpoint_];
1214 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1215 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1217 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1220 // If systems_per_page_ is positive, we don't really try to space on N
1221 // or N+1 pages; see the comment to space_systems_on_n_pages.
1223 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1224 Real penalty_for_fewer_pages)
1226 Page_spacing_result n_res;
1227 Page_spacing_result m_res;
1229 if (systems_per_page_ > 0)
1231 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1232 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1236 cache_line_details (configuration);
1237 vsize min_p_count = min_page_count (configuration, first_page_num);
1238 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1241 programming_error ("both page counts are out of bounds");
1243 if (n == 1 && valid_n)
1245 bool rag = ragged () || (is_last () && ragged_last ());
1246 Real height = page_height (first_page_num, is_last ());
1248 if (1 >= min_p_count)
1249 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1250 if (1 < cached_line_details_.size ())
1251 m_res = space_systems_on_2_pages (configuration, first_page_num);
1255 Page_spacer ps (cached_line_details_, first_page_num, this);
1257 if (n >= min_p_count || !valid_n)
1258 n_res = ps.solve (n);
1259 if (n < cached_line_details_.size () || !valid_n)
1260 m_res = ps.solve (n + 1);
1263 m_res = finalize_spacing_result (configuration, m_res);
1264 n_res = finalize_spacing_result (configuration, n_res);
1266 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1267 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1269 if (n_res.force_.size ())
1270 n_res.force_.back () += penalty_for_fewer_pages;
1272 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1276 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1278 if (systems_per_page_ > 0)
1279 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1281 cache_line_details (configuration);
1282 Page_spacer ps (cached_line_details_, first_page_num, this);
1284 return finalize_spacing_result (configuration, ps.solve ());
1288 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1289 vsize first_page_num)
1291 Page_spacing_result res;
1292 Page_spacing space (page_height (first_page_num, false), this);
1295 vsize page_first_line = 0;
1297 cache_line_details (configuration);
1298 while (line < cached_line_details_.size ())
1302 space.resize (page_height (first_page_num + page, false));
1304 int system_count_on_this_page = 0;
1305 while (system_count_on_this_page < systems_per_page_
1306 && line < cached_line_details_.size ())
1308 Line_details const &cur_line = cached_line_details_[line];
1309 space.append_system (cur_line);
1310 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1313 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1317 res.systems_per_page_.push_back (line - page_first_line);
1319 res.force_.push_back (space.force_);
1320 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1321 if (system_count_on_this_page != systems_per_page_)
1323 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1324 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1325 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1328 page_first_line = line;
1331 /* Recalculate forces for the last page because we know now that is
1332 really the last page. */
1333 space.resize (page_height (first_page_num + page, true));
1334 res.force_.back () = space.force_;
1335 return finalize_spacing_result (configuration, res);
1339 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1341 // TODO: add support for min/max-systems-per-page.
1342 Page_spacing_result res;
1344 vsize page_first_line = 0;
1345 Page_spacing space (page_height (first_page_num, false), this);
1347 cache_line_details (configuration);
1348 for (vsize line = 0; line < cached_line_details_.size (); line++)
1350 Real prev_force = space.force_;
1351 space.append_system (cached_line_details_[line]);
1352 if ((line > page_first_line)
1353 && (isinf (space.force_)
1355 && (cached_line_details_[line - 1].page_permission_ == ly_symbol2scm ("force")))))
1357 res.systems_per_page_.push_back (line - page_first_line);
1358 res.force_.push_back (prev_force);
1359 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1361 space.resize (page_height (first_page_num + page, false));
1363 space.append_system (cached_line_details_[line]);
1364 page_first_line = line;
1367 if (line == cached_line_details_.size () - 1)
1369 /* This is the last line */
1370 /* When the last page height was computed, we did not know yet that it
1371 * was the last one. If the systems put on it don't fit anymore, the last
1372 * system is moved to a new page */
1373 space.resize (page_height (first_page_num + page, true));
1374 if ((line > page_first_line) && (isinf (space.force_)))
1376 res.systems_per_page_.push_back (line - page_first_line);
1377 res.force_.push_back (prev_force);
1378 /* the last page containing the last line */
1379 space.resize (page_height (first_page_num + page + 1, true));
1381 space.append_system (cached_line_details_[line]);
1382 res.systems_per_page_.push_back (1);
1383 res.force_.push_back (space.force_);
1384 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1385 res.penalty_ += cached_line_details_[line].page_penalty_;
1389 res.systems_per_page_.push_back (line + 1 - page_first_line);
1390 res.force_.push_back (space.force_);
1391 res.penalty_ += cached_line_details_[line].page_penalty_;
1395 return finalize_spacing_result (configuration, res);
1398 /* Calculate demerits and fix res.systems_per_page_ so that
1399 it refers to the original line numbers, not the ones given by compress_lines (). */
1401 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1403 if (res.force_.empty ())
1406 cache_line_details (configuration);
1407 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1409 Real line_force = 0;
1410 Real line_penalty = 0;
1411 Real page_demerits = res.penalty_;
1412 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1414 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1416 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1417 line_penalty += uncompressed_line_details_[i].break_penalty_;
1420 for (vsize i = 0; i < res.force_.size (); i++)
1422 Real f = res.force_[i];
1424 page_demerits += min (f * f, BAD_SPACING_PENALTY);
1427 /* for a while we tried averaging page and line forces across pages instead
1428 of summing them, but it caused a problem: if there is a single page
1429 with a very bad page force (for example because of a forced page break),
1430 the page breaker will put in a _lot_ of pages so that the bad force
1431 becomes averaged out over many pages. */
1432 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1437 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1438 are by far the most common cases, we have special functions for them.
1440 space_systems_on_1_page has a different calling convention than most of the
1441 space_systems functions. This is because space_systems_on_1_page is (unlike
1442 the other space_systems functions) sometimes called on subsets of a full
1445 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1447 Page_spacing space (page_height, this);
1448 Page_spacing_result ret;
1451 for (vsize i = 0; i < lines.size (); i++)
1453 space.append_system (lines[i]);
1454 line_count += lines[i].compressed_nontitle_lines_count_;
1457 ret.systems_per_page_.push_back (lines.size ());
1458 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1459 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1460 ret.system_count_status_ |= line_count_status (line_count);
1462 /* don't do finalize_spacing_result () because we are only an internal function */
1467 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1469 Real page1_height = page_height (first_page_num, false);
1470 Real page2_height = page_height (first_page_num + 1, is_last ());
1471 bool ragged1 = ragged ();
1472 bool ragged2 = ragged () || (is_last () && ragged_last ());
1474 /* if there is a forced break, this reduces to 2 1-page problems */
1475 cache_line_details (configuration);
1476 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1477 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1479 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1480 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1481 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1482 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1484 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1485 p1.force_.push_back (p2.force_[0]);
1486 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1487 p1.system_count_status_ |= p2.system_count_status_;
1491 vector<Real> page1_force;
1492 vector<Real> page2_force;
1494 // page1_penalty and page2_penalty store the penalties based
1495 // on min-systems-per-page and max-systems-per-page.
1496 vector<Real> page1_penalty;
1497 vector<Real> page2_penalty;
1499 // page1_status and page2_status keep track of whether the min-systems-per-page
1500 // and max-systems-per-page constraints are satisfied.
1501 vector<int> page1_status;
1502 vector<int> page2_status;
1504 Page_spacing page1 (page1_height, this);
1505 Page_spacing page2 (page2_height, this);
1506 int page1_line_count = 0;
1507 int page2_line_count = 0;
1509 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1510 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1511 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1512 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1513 page1_status.resize (cached_line_details_.size () - 1, 0);
1514 page2_status.resize (cached_line_details_.size () - 1, 0);
1516 /* find the page 1 and page 2 forces for each page-breaking position */
1517 for (vsize i = 0; i < page1_force.size (); i++)
1519 page1.append_system (cached_line_details_[i]);
1520 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1521 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1522 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1524 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1525 page1_penalty[i] = line_count_penalty (page1_line_count);
1526 page1_status[i] = line_count_status (page1_line_count);
1529 page2_force[page2_force.size () - 1 - i]
1530 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1532 page2_force[page2_force.size () - 1 - i] = page2.force_;
1533 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1534 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1537 /* find the position that minimises the sum of the page forces */
1538 vsize best_sys_count = 1;
1539 Real best_demerits = infinity_f;
1540 for (vsize i = 0; i < page1_force.size (); i++)
1542 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1544 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1545 // constraints. That is, we penalize harshly when they don't happen
1546 // but we don't completely reject.
1548 + page1_penalty[i] + page2_penalty[i]
1549 + cached_line_details_[i + 1].page_penalty_
1550 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1551 if (dem < best_demerits)
1553 best_demerits = dem;
1554 best_sys_count = i + 1;
1558 Page_spacing_result ret;
1559 ret.systems_per_page_.push_back (best_sys_count);
1560 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1561 ret.force_.push_back (page1_force[best_sys_count - 1]);
1562 ret.force_.push_back (page2_force[best_sys_count - 1]);
1563 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1564 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1565 + cached_line_details_.back ().page_penalty_
1566 + cached_line_details_.back ().turn_penalty_
1567 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1569 /* don't do finalize_spacing_result () because we are only an internal function */
1574 Page_breaking::all_lines_stretched (vsize configuration)
1576 cache_line_details (configuration);
1577 for (vsize i = 0; i < cached_line_details_.size (); i++)
1578 if (cached_line_details_[i].force_ < 0)
1584 Page_breaking::Line_division
1585 Page_breaking::current_configuration (vsize configuration_index) const
1587 return current_configurations_[configuration_index];
1591 Page_breaking::is_last () const
1593 return current_end_breakpoint_ == last_break_position ();
1597 Page_breaking::ends_score () const
1599 return breaks_[current_end_breakpoint_].score_ender_;
1603 Page_breaking::last_break_position () const
1605 return breaks_.size () - 1;
1608 // This gives the minimum distance between the top of the
1609 // printable area (ie. the bottom of the top-margin) and
1610 // the extent box of the topmost system.
1612 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1614 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1616 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1618 Real min_distance = -infinity_f;
1621 Page_layout_problem::read_spacing_spec (first_system_spacing,
1623 ly_symbol2scm ("minimum-distance"));
1624 Page_layout_problem::read_spacing_spec (first_system_spacing,
1626 ly_symbol2scm ("padding"));
1628 // FIXME: take into account the height of the header
1629 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1630 return max (0.0, max (padding, min_distance - translate));
1634 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1636 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1637 Real min_distance = -infinity_f;
1640 Page_layout_problem::read_spacing_spec (last_system_spacing,
1642 ly_symbol2scm ("minimum-distance"));
1643 Page_layout_problem::read_spacing_spec (last_system_spacing,
1645 ly_symbol2scm ("padding"));
1647 // FIXME: take into account the height of the footer
1648 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1649 return max (0.0, max (padding, min_distance + translate));
1653 Page_breaking::orphan_penalty () const
1655 return orphan_penalty_;