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_);
581 p->set_property ("foot-stencil", foot->smobbed_copy ());
582 scm_apply_1 (page_stencil, page, SCM_EOL);
588 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
590 if (scm_is_null (systems))
593 int first_page_number
594 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
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) pairs. Note that we lay out
601 // the staves and find the configurations before drawing anything. Some
602 // grobs (like tuplet brackets) look at their neighbours while drawing
603 // themselves. If this happens before the neighbouring staves have
604 // been laid out, bad side-effects could happen (in particular,
605 // Align_interface::align_to_ideal_distances might be called).
606 SCM systems_configs_fncounts = SCM_EOL;
607 vsize footnote_count = 0;
609 for (vsize i = 0; i < lines_per_page.size (); i++)
611 int page_num = i + first_page_number;
612 bool bookpart_last_page = (i == lines_per_page.size () - 1);
613 bool rag = ragged () || (bookpart_last_page && ragged_last ());
614 SCM line_count = scm_from_int (lines_per_page[i]);
615 SCM lines = scm_list_head (systems, line_count);
616 int fn_lines = Page_layout_problem::get_footnote_count (lines);
617 SCM config = get_page_configuration (lines, page_num, footnote_count, rag, bookpart_last_page);
619 systems_configs_fncounts = scm_cons (scm_list_3 (lines, config, scm_from_int ((int)footnote_count)), systems_configs_fncounts);
620 footnote_count += fn_lines;
621 systems = scm_list_tail (systems, line_count);
624 // Now it's safe to make the pages.
625 int page_num = first_page_number + lines_per_page.size () - 1;
626 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
628 SCM lines = scm_caar (s);
629 SCM config = scm_cadar (s);
630 int footnote_num = scm_to_int (scm_caddar (s));
632 bool bookpart_last_page = (s == systems_configs_fncounts);
633 SCM page = draw_page (lines, config, page_num, footnote_num, bookpart_last_page);
635 SCM page_num_scm = scm_from_int (page_num);
636 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
638 SCM labels = SCM_EOL;
639 if (Grob *line = unsmob_grob (scm_car (l)))
641 System *system = dynamic_cast<System *> (line);
642 labels = system->get_property ("labels");
644 else if (Prob *prob = unsmob_prob (scm_car (l)))
645 labels = prob->get_property ("labels");
647 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
648 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
652 ret = scm_cons (page, ret);
656 // By reversing the table, we ensure that duplicated labels (eg. those
657 // straddling a page turn) will appear in the table with their last
659 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
660 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
664 /* The page-turn-page-breaker needs to have a line-breaker between any two
665 columns with non-NULL page-turn-permission.
667 The optimal-breaker needs to have a line-breaker between any two columns
668 with page-break-permission = 'force.
670 By using a grob predicate, we can accommodate both of these uses.
673 Page_breaking::create_system_list ()
675 SCM specs = book_->get_system_specs ();
676 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
678 if (Paper_score *ps = dynamic_cast<Paper_score *> (unsmob_music_output (scm_car (s))))
680 system_specs_.push_back (System_spec (ps));
684 Prob *pb = unsmob_prob (scm_car (s));
688 system_specs_.push_back (System_spec (pb));
691 if (!system_specs_.size ())
692 system_specs_.push_back (System_spec ());
696 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
698 SCM force_sym = ly_symbol2scm ("force");
700 chunks_.push_back (Break_position ());
701 breaks_.push_back (Break_position ());
703 for (vsize i = 0; i < system_specs_.size (); i++)
705 if (system_specs_[i].pscore_)
707 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
708 vector<Grob *> forced_line_break_cols;
710 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
711 if (scm_is_number (system_count))
713 // With system-count given, the line configuration for
714 // this score is fixed. We need to ensure that chunk
715 // boundaries only occur at line breaks.
716 Constrained_breaking breaking (system_specs_[i].pscore_);
717 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
719 for (vsize j = 0; j < details.size (); j++)
720 forced_line_break_cols.push_back (details[j].last_column_);
723 int last_forced_line_break_idx = 0;
724 vsize forced_line_break_idx = 0;
725 vector<vsize> line_breaker_columns;
726 line_breaker_columns.push_back (0);
728 for (vsize j = 1; j < cols.size (); j++)
730 if (forced_line_break_cols.size ())
732 if (forced_line_break_idx >= forced_line_break_cols.size ()
733 || forced_line_break_cols[forced_line_break_idx] != cols[j])
736 forced_line_break_idx++;
739 bool last = (j == cols.size () - 1);
740 bool break_point = is_break && is_break (cols[j]);
741 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
742 Break_position cur_pos = Break_position (i,
743 line_breaker_columns.size (),
747 // NOTE: even in the breaks_ list, forced_line_count_
748 // refers to the number of lines between a
749 // Break_position and the start of that /chunk/. This
750 // is needed for system_count_bounds to work correctly,
751 // since it mixes Break_positions from breaks_ and
753 if (scm_is_number (system_count))
754 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
756 if (break_point || (i == system_specs_.size () - 1 && last))
757 breaks_.push_back (cur_pos);
758 if (chunk_end || last)
760 chunks_.push_back (cur_pos);
761 last_forced_line_break_idx = forced_line_break_idx;
764 if ((break_point || chunk_end) && !last)
765 line_breaker_columns.push_back (j);
767 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
769 else if (system_specs_[i].prob_)
771 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
772 if (break_point || i == system_specs_.size () - 1)
773 breaks_.push_back (Break_position (i));
775 chunks_.push_back (Break_position (i));
777 /* FIXME: shouldn't we push a Null_breaker or similar dummy
779 line_breaking_.push_back (Constrained_breaking (NULL));
784 vector<Break_position>
785 Page_breaking::chunk_list (vsize start_index, vsize end_index)
787 Break_position start = breaks_[start_index];
788 Break_position end = breaks_[end_index];
791 for (; i < chunks_.size () && chunks_[i] <= start; i++)
794 vector<Break_position> ret;
795 ret.push_back (start);
796 for (; i < chunks_.size () && chunks_[i] < end; i++)
797 ret.push_back (chunks_[i]);
802 // Returns the minimum number of _non-title_ lines.
804 Page_breaking::min_system_count (vsize start, vsize end)
806 vector<Break_position> chunks = chunk_list (start, end);
807 Line_division div = system_count_bounds (chunks, true);
810 for (vsize i = 0; i < div.size (); i++)
815 // Returns the maximum number of _non-title_ lines.
817 Page_breaking::max_system_count (vsize start, vsize end)
819 vector<Break_position> chunks = chunk_list (start, end);
820 Line_division div = system_count_bounds (chunks, false);
823 for (vsize i = 0; i < div.size (); i++)
828 // The numbers returned by this function represent either
829 // the maximum or minimum number of _non-title_ lines
831 Page_breaking::Line_division
832 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
835 assert (chunks.size () >= 2);
838 ret.resize (chunks.size () - 1, 0);
840 for (vsize i = 0; i + 1 < chunks.size (); i++)
842 vsize sys = next_system (chunks[i]);
844 if (chunks[i + 1].forced_line_count_)
845 ret[i] = chunks[i + 1].forced_line_count_;
846 else if (system_specs_[sys].pscore_)
850 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
852 ? line_breaking_[sys].min_system_count (start, end)
853 : line_breaking_[sys].max_system_count (start, end);
861 Page_breaking::set_current_breakpoints (vsize start,
864 Line_division lower_bound,
865 Line_division upper_bound)
867 system_count_ = system_count;
868 current_chunks_ = chunk_list (start, end);
869 current_start_breakpoint_ = start;
870 current_end_breakpoint_ = end;
871 clear_line_details_cache ();
873 if (!lower_bound.size ())
874 lower_bound = system_count_bounds (current_chunks_, true);
875 if (!upper_bound.size ())
876 upper_bound = system_count_bounds (current_chunks_, false);
878 assert (lower_bound.size () == current_chunks_.size () - 1);
879 assert (upper_bound.size () == current_chunks_.size () - 1);
881 Line_division work_in_progress;
882 current_configurations_.clear ();
883 line_divisions_rec (system_count,
888 /* we only consider a constant number of configurations. Otherwise,
889 this becomes slow when there are many small scores. The constant
890 5 is somewhat arbitrary. */
891 if (current_configurations_.size () > 5)
893 vector<pair<Real, vsize> > dems_and_indices;
895 for (vsize i = 0; i < current_configurations_.size (); i++)
897 cache_line_details (i);
899 for (vsize j = 0; j < cached_line_details_.size (); j++)
900 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
901 + cached_line_details_[j].break_penalty_;
903 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
905 vector_sort (dems_and_indices, less<pair<Real, vsize> > ());
907 vector<Line_division> best_5_configurations;
908 for (vsize i = 0; i < 5; i++)
909 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
911 clear_line_details_cache ();
912 current_configurations_ = best_5_configurations;
917 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
919 current_chunks_ = chunk_list (start, end);
920 current_start_breakpoint_ = start;
921 current_end_breakpoint_ = end;
922 clear_line_details_cache ();
926 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
928 vsize sys = next_system (current_chunks_[i]);
930 if (current_chunks_[i + 1].forced_line_count_)
931 div.push_back (current_chunks_[i + 1].forced_line_count_);
932 else if (system_specs_[sys].pscore_)
934 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
935 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
940 system_count_ += div.back ();
942 current_configurations_.clear ();
943 current_configurations_.push_back (div);
947 Page_breaking::current_configuration_count () const
949 return current_configurations_.size ();
953 Page_breaking::cache_line_details (vsize configuration_index)
955 if (cached_configuration_index_ != configuration_index)
957 cached_configuration_index_ = configuration_index;
959 Line_division &div = current_configurations_[configuration_index];
960 uncompressed_line_details_.clear ();
961 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
963 vsize sys = next_system (current_chunks_[i]);
964 if (system_specs_[sys].pscore_)
968 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
970 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
971 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
975 assert (div[i] == 0);
976 uncompressed_line_details_.push_back (system_specs_[sys].prob_
977 ? Line_details (system_specs_[sys].prob_, book_->paper_)
981 cached_line_details_ = compress_lines (uncompressed_line_details_);
982 compute_line_heights ();
987 Page_breaking::clear_line_details_cache ()
989 cached_configuration_index_ = VPOS;
990 cached_line_details_.clear ();
991 uncompressed_line_details_.clear ();
995 Page_breaking::line_divisions_rec (vsize system_count,
996 Line_division const &min_sys,
997 Line_division const &max_sys,
998 Line_division *cur_division)
1000 vsize my_index = cur_division->size ();
1004 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1006 others_min += min_sys[i];
1007 others_max += max_sys[i];
1009 others_max = min (others_max, (int) system_count);
1010 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
1011 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
1013 if (real_min > real_max || real_min < 0)
1015 /* this should never happen within a recursive call. If it happens
1016 at all, it means that we were called with an unsolvable problem
1017 and we should return an empty result */
1018 assert (my_index == 0);
1022 for (int i = real_min; i <= real_max; i++)
1024 cur_division->push_back (i);
1025 if (my_index == min_sys.size () - 1)
1026 current_configurations_.push_back (*cur_division);
1028 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1029 cur_division->pop_back ();
1034 Page_breaking::compute_line_heights ()
1036 Real prev_hanging = 0;
1037 Real prev_hanging_begin = 0;
1038 Real prev_hanging_rest = 0;
1040 // refpoint_hanging is the y coordinate of the origin of this system.
1041 // It may not be the same as refpoint_extent[UP], which is the
1042 // refpoint of the first spaceable staff in this system.
1043 Real prev_refpoint_hanging = 0;
1044 for (vsize i = 0; i < cached_line_details_.size (); i++)
1046 Line_details &cur = cached_line_details_[i];
1047 Line_shape shape = cur.shape_;
1048 Real a = shape.begin_[UP];
1049 Real b = shape.rest_[UP];
1050 bool title = cur.title_;
1051 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1056 Line_details const &prev = cached_line_details_[i - 1];
1057 if (!cur.tight_spacing_)
1059 ? prev.title_padding_
1061 Real min_dist = title
1062 ? prev.title_min_distance_
1063 : prev.min_distance_;
1064 refpoint_hanging = max (refpoint_hanging + padding,
1065 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1066 + cur.refpoint_extent_[UP] + min_dist);
1069 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1070 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1071 Real hanging = max (hanging_begin, hanging_rest);
1072 cur.tallness_ = hanging - prev_hanging;
1073 prev_hanging = hanging;
1074 prev_hanging_begin = hanging_begin;
1075 prev_hanging_rest = hanging_rest;
1076 prev_refpoint_hanging = refpoint_hanging;
1081 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1084 vsize page_starter = 0;
1085 Real cur_rod_height = 0;
1086 Real cur_spring_height = 0;
1087 Real cur_page_height = page_height (first_page_num, false);
1090 cache_line_details (configuration);
1092 if (cached_line_details_.size ())
1093 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1095 for (vsize i = 0; i < cached_line_details_.size (); i++)
1097 Line_details const &cur = cached_line_details_[i];
1098 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1100 if (cur_rod_height > 0)
1101 ext_len = cur.tallness_;
1103 ext_len = cur.full_height ();
1105 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1106 Real next_rod_height = cur_rod_height + ext_len;
1107 Real next_spring_height = cur_spring_height + spring_len;
1108 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1109 + min_whitespace_at_bottom_of_page (cur);
1110 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1112 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1113 || too_many_lines (next_line_count)
1114 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1116 line_count = cur.compressed_nontitle_lines_count_;
1117 cur_rod_height = cur.full_height ();
1118 cur_spring_height = 0;
1121 cur_page_height = page_height (first_page_num + ret, false);
1122 cur_page_height -= min_whitespace_at_top_of_page (cur);
1128 cur_rod_height = next_rod_height;
1129 cur_spring_height = next_spring_height;
1130 line_count = next_line_count;
1134 /* there are two potential problems with the last page (because we didn't know
1135 it was the last page until after we managed to fit all the systems to it):
1136 - we are ragged-last but the last page has a compressed spring
1137 - the value returned by page_height (num, true) is smaller than the
1138 value returned by page_height (num, false) and it causes the page not to
1141 In either case, we just need to add one more page. This is because the last
1142 line will always fit on the extra page and by adding one more page to the
1143 end, the previous page is no longer the last page, so our previous
1144 calculations that treated it as a non-last page were ok.
1149 cur_page_height = page_height (first_page_num + ret - 1, true);
1150 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1151 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1153 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1154 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1155 && cur_height > cur_page_height
1156 /* don't increase the page count if the last page had only one system */
1157 && cur_rod_height > cached_line_details_.back ().full_height ())
1159 assert (ret <= cached_line_details_.size ());
1165 // If systems_per_page_ is positive, we don't really try to space on N pages;
1166 // we just put the requested number of systems on each page and penalize
1167 // if the result doesn't have N pages.
1169 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1171 Page_spacing_result ret;
1173 if (systems_per_page_ > 0)
1175 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1176 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1180 cache_line_details (configuration);
1181 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1182 && n <= cached_line_details_.size ());
1185 programming_error ("number of pages is out of bounds");
1187 if (n == 1 && valid_n)
1188 ret = space_systems_on_1_page (cached_line_details_,
1189 page_height (first_page_num, is_last ()),
1190 ragged () || (is_last () && ragged_last ()));
1191 else if (n == 2 && valid_n)
1192 ret = space_systems_on_2_pages (configuration, first_page_num);
1195 Page_spacer ps (cached_line_details_, first_page_num, this);
1199 return finalize_spacing_result (configuration, ret);
1203 Page_breaking::blank_page_penalty () const
1208 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1209 else if (ends_score ())
1210 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1212 penalty_sym = ly_symbol2scm ("blank-page-force");
1214 Break_position const &pos = breaks_[current_end_breakpoint_];
1215 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1216 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1218 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1221 // If systems_per_page_ is positive, we don't really try to space on N
1222 // or N+1 pages; see the comment to space_systems_on_n_pages.
1224 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1225 Real penalty_for_fewer_pages)
1227 Page_spacing_result n_res;
1228 Page_spacing_result m_res;
1230 if (systems_per_page_ > 0)
1232 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1233 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1237 cache_line_details (configuration);
1238 vsize min_p_count = min_page_count (configuration, first_page_num);
1239 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1242 programming_error ("both page counts are out of bounds");
1244 if (n == 1 && valid_n)
1246 bool rag = ragged () || (is_last () && ragged_last ());
1247 Real height = page_height (first_page_num, is_last ());
1249 if (1 >= min_p_count)
1250 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1251 if (1 < cached_line_details_.size ())
1252 m_res = space_systems_on_2_pages (configuration, first_page_num);
1256 Page_spacer ps (cached_line_details_, first_page_num, this);
1258 if (n >= min_p_count || !valid_n)
1259 n_res = ps.solve (n);
1260 if (n < cached_line_details_.size () || !valid_n)
1261 m_res = ps.solve (n + 1);
1264 m_res = finalize_spacing_result (configuration, m_res);
1265 n_res = finalize_spacing_result (configuration, n_res);
1267 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1268 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1270 if (n_res.force_.size ())
1271 n_res.force_.back () += penalty_for_fewer_pages;
1273 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1277 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1279 if (systems_per_page_ > 0)
1280 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1282 cache_line_details (configuration);
1283 Page_spacer ps (cached_line_details_, first_page_num, this);
1285 return finalize_spacing_result (configuration, ps.solve ());
1289 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1290 vsize first_page_num)
1292 Page_spacing_result res;
1293 Page_spacing space (page_height (first_page_num, false), this);
1296 vsize page_first_line = 0;
1298 cache_line_details (configuration);
1299 while (line < cached_line_details_.size ())
1303 space.resize (page_height (first_page_num + page, false));
1305 int system_count_on_this_page = 0;
1306 while (system_count_on_this_page < systems_per_page_
1307 && line < cached_line_details_.size ())
1309 Line_details const &cur_line = cached_line_details_[line];
1310 space.append_system (cur_line);
1311 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1314 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1318 res.systems_per_page_.push_back (line - page_first_line);
1320 res.force_.push_back (space.force_);
1321 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1322 if (system_count_on_this_page != systems_per_page_)
1324 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1325 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1326 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1329 page_first_line = line;
1332 /* Recalculate forces for the last page because we know now that is
1333 really the last page. */
1334 space.resize (page_height (first_page_num + page, true));
1335 res.force_.back () = space.force_;
1336 return finalize_spacing_result (configuration, res);
1340 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1342 // TODO: add support for min/max-systems-per-page.
1343 Page_spacing_result res;
1345 vsize page_first_line = 0;
1346 Page_spacing space (page_height (first_page_num, false), this);
1348 cache_line_details (configuration);
1349 for (vsize line = 0; line < cached_line_details_.size (); line++)
1351 Real prev_force = space.force_;
1352 space.append_system (cached_line_details_[line]);
1353 if ((line > page_first_line)
1354 && (isinf (space.force_)
1356 && (cached_line_details_[line - 1].page_permission_ == ly_symbol2scm ("force")))))
1358 res.systems_per_page_.push_back (line - page_first_line);
1359 res.force_.push_back (prev_force);
1360 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1362 space.resize (page_height (first_page_num + page, false));
1364 space.append_system (cached_line_details_[line]);
1365 page_first_line = line;
1368 if (line == cached_line_details_.size () - 1)
1370 /* This is the last line */
1371 /* When the last page height was computed, we did not know yet that it
1372 * was the last one. If the systems put on it don't fit anymore, the last
1373 * system is moved to a new page */
1374 space.resize (page_height (first_page_num + page, true));
1375 if ((line > page_first_line) && (isinf (space.force_)))
1377 res.systems_per_page_.push_back (line - page_first_line);
1378 res.force_.push_back (prev_force);
1379 /* the last page containing the last line */
1380 space.resize (page_height (first_page_num + page + 1, true));
1382 space.append_system (cached_line_details_[line]);
1383 res.systems_per_page_.push_back (1);
1384 res.force_.push_back (space.force_);
1385 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1386 res.penalty_ += cached_line_details_[line].page_penalty_;
1390 res.systems_per_page_.push_back (line + 1 - page_first_line);
1391 res.force_.push_back (space.force_);
1392 res.penalty_ += cached_line_details_[line].page_penalty_;
1396 return finalize_spacing_result (configuration, res);
1399 /* Calculate demerits and fix res.systems_per_page_ so that
1400 it refers to the original line numbers, not the ones given by compress_lines (). */
1402 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1404 if (res.force_.empty ())
1407 cache_line_details (configuration);
1408 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1410 Real line_force = 0;
1411 Real line_penalty = 0;
1412 Real page_demerits = res.penalty_;
1413 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1415 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1417 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1418 line_penalty += uncompressed_line_details_[i].break_penalty_;
1421 for (vsize i = 0; i < res.force_.size (); i++)
1423 Real f = res.force_[i];
1425 page_demerits += min (f * f, BAD_SPACING_PENALTY);
1428 /* for a while we tried averaging page and line forces across pages instead
1429 of summing them, but it caused a problem: if there is a single page
1430 with a very bad page force (for example because of a forced page break),
1431 the page breaker will put in a _lot_ of pages so that the bad force
1432 becomes averaged out over many pages. */
1433 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1438 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1439 are by far the most common cases, we have special functions for them.
1441 space_systems_on_1_page has a different calling convention than most of the
1442 space_systems functions. This is because space_systems_on_1_page is (unlike
1443 the other space_systems functions) sometimes called on subsets of a full
1446 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1448 Page_spacing space (page_height, this);
1449 Page_spacing_result ret;
1452 for (vsize i = 0; i < lines.size (); i++)
1454 space.append_system (lines[i]);
1455 line_count += lines[i].compressed_nontitle_lines_count_;
1458 ret.systems_per_page_.push_back (lines.size ());
1459 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1460 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1461 ret.system_count_status_ |= line_count_status (line_count);
1463 /* don't do finalize_spacing_result () because we are only an internal function */
1468 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1470 Real page1_height = page_height (first_page_num, false);
1471 Real page2_height = page_height (first_page_num + 1, is_last ());
1472 bool ragged1 = ragged ();
1473 bool ragged2 = ragged () || (is_last () && ragged_last ());
1475 /* if there is a forced break, this reduces to 2 1-page problems */
1476 cache_line_details (configuration);
1477 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1478 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1480 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1481 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1482 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1483 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1485 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1486 p1.force_.push_back (p2.force_[0]);
1487 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1488 p1.system_count_status_ |= p2.system_count_status_;
1492 vector<Real> page1_force;
1493 vector<Real> page2_force;
1495 // page1_penalty and page2_penalty store the penalties based
1496 // on min-systems-per-page and max-systems-per-page.
1497 vector<Real> page1_penalty;
1498 vector<Real> page2_penalty;
1500 // page1_status and page2_status keep track of whether the min-systems-per-page
1501 // and max-systems-per-page constraints are satisfied.
1502 vector<int> page1_status;
1503 vector<int> page2_status;
1505 Page_spacing page1 (page1_height, this);
1506 Page_spacing page2 (page2_height, this);
1507 int page1_line_count = 0;
1508 int page2_line_count = 0;
1510 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1511 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1512 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1513 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1514 page1_status.resize (cached_line_details_.size () - 1, 0);
1515 page2_status.resize (cached_line_details_.size () - 1, 0);
1517 /* find the page 1 and page 2 forces for each page-breaking position */
1518 for (vsize i = 0; i < page1_force.size (); i++)
1520 page1.append_system (cached_line_details_[i]);
1521 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1522 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1523 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1525 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1526 page1_penalty[i] = line_count_penalty (page1_line_count);
1527 page1_status[i] = line_count_status (page1_line_count);
1530 page2_force[page2_force.size () - 1 - i]
1531 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1533 page2_force[page2_force.size () - 1 - i] = page2.force_;
1534 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1535 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1538 /* find the position that minimises the sum of the page forces */
1539 vsize best_sys_count = 1;
1540 Real best_demerits = infinity_f;
1541 for (vsize i = 0; i < page1_force.size (); i++)
1543 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1545 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1546 // constraints. That is, we penalize harshly when they don't happen
1547 // but we don't completely reject.
1549 + page1_penalty[i] + page2_penalty[i]
1550 + cached_line_details_[i + 1].page_penalty_
1551 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1552 if (dem < best_demerits)
1554 best_demerits = dem;
1555 best_sys_count = i + 1;
1559 Page_spacing_result ret;
1560 ret.systems_per_page_.push_back (best_sys_count);
1561 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1562 ret.force_.push_back (page1_force[best_sys_count - 1]);
1563 ret.force_.push_back (page2_force[best_sys_count - 1]);
1564 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1565 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1566 + cached_line_details_.back ().page_penalty_
1567 + cached_line_details_.back ().turn_penalty_
1568 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1570 /* don't do finalize_spacing_result () because we are only an internal function */
1575 Page_breaking::all_lines_stretched (vsize configuration)
1577 cache_line_details (configuration);
1578 for (vsize i = 0; i < cached_line_details_.size (); i++)
1579 if (cached_line_details_[i].force_ < 0)
1585 Page_breaking::Line_division
1586 Page_breaking::current_configuration (vsize configuration_index) const
1588 return current_configurations_[configuration_index];
1592 Page_breaking::is_last () const
1594 return current_end_breakpoint_ == last_break_position ();
1598 Page_breaking::ends_score () const
1600 return breaks_[current_end_breakpoint_].score_ender_;
1604 Page_breaking::last_break_position () const
1606 return breaks_.size () - 1;
1609 // This gives the minimum distance between the top of the
1610 // printable area (ie. the bottom of the top-margin) and
1611 // the extent box of the topmost system.
1613 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1615 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1617 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1619 Real min_distance = -infinity_f;
1622 Page_layout_problem::read_spacing_spec (first_system_spacing,
1624 ly_symbol2scm ("minimum-distance"));
1625 Page_layout_problem::read_spacing_spec (first_system_spacing,
1627 ly_symbol2scm ("padding"));
1629 // FIXME: take into account the height of the header
1630 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1631 return max (0.0, max (padding, min_distance - translate));
1635 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1637 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1638 Real min_distance = -infinity_f;
1641 Page_layout_problem::read_spacing_spec (last_system_spacing,
1643 ly_symbol2scm ("minimum-distance"));
1644 Page_layout_problem::read_spacing_spec (last_system_spacing,
1646 ly_symbol2scm ("padding"));
1648 // FIXME: take into account the height of the footer
1649 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1650 return max (0.0, max (padding, min_distance + translate));
1654 Page_breaking::orphan_penalty () const
1656 return orphan_penalty_;