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.footnote_heights_.insert (compressed.footnote_heights_.begin (),
187 old.footnote_heights_.begin (),
188 old.footnote_heights_.end ());
189 compressed.in_note_heights_.insert (compressed.in_note_heights_.begin (),
190 old.in_note_heights_.begin (),
191 old.in_note_heights_.end ());
193 ret.back () = compressed;
197 ret.push_back (orig[i]);
198 ret.back ().force_ = 0;
204 /* translate the number of systems-per-page into something meaningful for
205 the uncompressed lines.
208 uncompress_solution (vector<vsize> const &systems_per_page,
209 vector<Line_details> const &compressed)
214 for (vsize i = 0; i < systems_per_page.size (); i++)
216 int compressed_count = 0;
217 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
218 compressed_count += compressed[j].compressed_lines_count_ - 1;
220 ret.push_back (systems_per_page[i] + compressed_count);
221 start_sys += systems_per_page[i];
226 /* for Page_breaking, the start index (when we are dealing with the stuff
227 between a pair of breakpoints) refers to the break_ index of the end of
228 the previous page. So the system index of the start of the current page
229 could either be the same as the end of the previous page or one more than
232 /* Turn a break index into the sys index that starts the next page */
234 Page_breaking::next_system (Break_position const &break_pos) const
236 vsize sys = break_pos.system_spec_index_;
238 if (sys == VPOS) /* beginning of the book */
240 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
241 return sys; /* the score overflows the previous page */
242 return sys + 1; /* this page starts with a new System_spec */
245 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
249 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
250 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
251 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
252 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
253 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
254 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
255 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
257 Stencil *footnote_separator = Page_layout_problem::get_footnote_separator_stencil (pb->paper_);
259 if (footnote_separator)
261 Interval separator_extent = footnote_separator->extent (Y_AXIS);
262 Real separator_span = separator_extent.length ();
264 footnote_separator_stencil_height_ = separator_span;
267 footnote_separator_stencil_height_ = 0.0;
269 footnote_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
270 in_note_padding_ = robust_scm2double (pb->paper_->c_variable ("in-note-padding"), 0.0);
271 footnote_footer_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-footer-padding"), 0.0);
273 footnote_number_raise_ = robust_scm2double (pb->paper_->c_variable ("footnote-number-raise"), 0.0);
275 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
277 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
278 min_systems_per_page_ = max_systems_per_page_ = 0;
280 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
282 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
283 min_systems_per_page_ = max_systems_per_page_ = 0;
286 create_system_list ();
287 find_chunks_and_breaks (is_break, prob_break);
290 Page_breaking::~Page_breaking ()
295 Page_breaking::ragged () const
301 Page_breaking::ragged_last () const
307 Page_breaking::systems_per_page () const
309 return systems_per_page_;
313 Page_breaking::max_systems_per_page () const
315 if (systems_per_page_)
316 return systems_per_page_;
317 return max_systems_per_page_;
321 Page_breaking::min_systems_per_page () const
323 if (systems_per_page_)
324 return systems_per_page_;
325 return min_systems_per_page_;
329 Page_breaking::system_count () const
331 return system_count_;
335 Page_breaking::footnote_separator_stencil_height () const
337 return footnote_separator_stencil_height_;
341 Page_breaking::in_note_padding () const
343 return in_note_padding_;
347 Page_breaking::footnote_padding () const
349 return footnote_padding_;
353 Page_breaking::footnote_footer_padding () const
355 return footnote_footer_padding_;
359 Page_breaking::footnote_number_raise () const
361 return footnote_number_raise_;
365 Page_breaking::too_many_lines (int line_count) const
367 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
371 Page_breaking::too_few_lines (int line_count) const
373 return line_count < min_systems_per_page ();
377 Page_breaking::line_count_penalty (int line_count) const
379 if (too_many_lines (line_count))
380 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
381 if (too_few_lines (line_count))
382 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
388 Page_breaking::line_count_status (int line_count) const
390 if (too_many_lines (line_count))
391 return SYSTEM_COUNT_TOO_MANY;
392 if (too_few_lines (line_count))
393 return SYSTEM_COUNT_TOO_FEW;
395 return SYSTEM_COUNT_OK;
398 /* translate indices into breaks_ into start-end parameters for the line breaker */
400 Page_breaking::line_breaker_args (vsize sys,
401 Break_position const &start,
402 Break_position const &end,
403 vsize *line_breaker_start,
404 vsize *line_breaker_end)
406 assert (system_specs_[sys].pscore_);
407 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
409 if (start.system_spec_index_ == sys)
410 *line_breaker_start = start.score_break_;
412 *line_breaker_start = 0;
414 if (end.system_spec_index_ == sys)
415 *line_breaker_end = end.score_break_;
417 *line_breaker_end = VPOS;
421 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
422 Line_division const &div)
424 vector<Break_position> chunks = chunk_list (start_break, end_break);
425 bool ignore_div = false;
426 if (chunks.size () != div.size () + 1)
428 programming_error ("did not find a valid page breaking configuration");
432 for (vsize i = 0; i + 1 < chunks.size (); i++)
434 vsize sys = next_system (chunks[i]);
435 if (system_specs_[sys].pscore_)
439 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
441 vector<Column_x_positions> pos = ignore_div
442 ? line_breaking_[sys].best_solution (start, end)
443 : line_breaking_[sys].solve (start, end, div[i]);
444 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
450 Page_breaking::systems ()
453 for (vsize sys = 0; sys < system_specs_.size (); sys++)
455 if (system_specs_[sys].pscore_)
457 system_specs_[sys].pscore_->root_system ()
458 ->do_break_substitution_and_fixup_refpoints ();
459 SCM lines = system_specs_[sys].pscore_->root_system ()
460 ->get_broken_system_grobs ();
461 ret = scm_cons (lines, ret);
463 else if (Prob *pb = system_specs_[sys].prob_)
465 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
469 return scm_append (scm_reverse (ret));
473 Page_breaking::make_page (int page_num, bool last) const
475 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
476 SCM mod = scm_c_resolve_module ("scm page");
477 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
479 make_page_scm = scm_variable_ref (make_page_scm);
481 return scm_apply_0 (make_page_scm,
482 scm_list_n (book_->self_scm (),
483 ly_symbol2scm ("page-number"), scm_from_int (page_num),
484 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
485 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
489 // Returns the total height of the paper, including margins and
490 // space for the header/footer. This is an upper bound on
491 // page_height, and it doesn't depend on the current page.
493 Page_breaking::paper_height () const
495 return paper_height_;
499 Page_breaking::page_height (int page_num, bool last) const
501 // The caches allow us to store the page heights for any
502 // non-negative page numbers. We use a negative value in the
503 // cache to signal that that position has not yet been initialized.
504 // This means that we won't cache properly if page_num is negative or
505 // if calc_height returns a negative number. But that's likely to
506 // be rare, so it shouldn't affect performance.
507 vector<Real>& cache = last ? last_page_height_cache_ : page_height_cache_;
508 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
509 return cache[page_num];
512 SCM mod = scm_c_resolve_module ("scm page");
513 SCM page = make_page (page_num, last);
514 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
515 calc_height = scm_variable_ref (calc_height);
517 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
518 Real height = scm_to_double (height_scm);
522 if ((int) cache.size () <= page_num)
523 cache.resize (page_num + 1, -1);
524 cache[page_num] = height;
531 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
533 Break_position const &pos = breaks_[breakpoint];
535 if (pos.system_spec_index_ == VPOS)
537 if (system_specs_[pos.system_spec_index_].pscore_)
538 return pos.col_->get_property (str);
539 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
543 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
545 SCM dummy_page = make_page (page_num, last);
546 Page_layout_problem layout (book_, dummy_page, systems);
547 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
551 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
553 // Create a stencil for each system.
554 SCM paper_systems = SCM_EOL;
555 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
557 SCM paper_system = scm_car (s);
558 if (Grob *g = unsmob_grob (scm_car (s)))
560 System *sys = dynamic_cast<System *> (g);
561 paper_system = sys->get_paper_system ();
564 paper_systems = scm_cons (paper_system, paper_systems);
567 // Create the page and draw it.
568 SCM page = make_page (page_num, last);
569 SCM page_module = scm_c_resolve_module ("scm page");
570 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
571 page_stencil = scm_variable_ref (page_stencil);
573 Prob *p = unsmob_prob (page);
574 p->set_property ("lines", paper_systems);
575 p->set_property ("configuration", configuration);
577 Stencil *foot = unsmob_stencil (p->get_property ("foot-stencil"));
579 SCM footnotes = Page_layout_problem::get_footnotes_from_lines (systems);
581 Page_layout_problem::add_footnotes_to_footer (footnotes, foot, book_);
584 p->set_property ("foot-stencil", foot->smobbed_copy ());
585 scm_apply_1 (page_stencil, page, SCM_EOL);
591 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
593 if (scm_is_null (systems))
596 int first_page_number
597 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
599 bool reset_footnotes_on_new_page = to_boolean (book_->top_paper ()->c_variable ("reset-footnotes-on-new-page"));
600 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
601 if (label_page_table == SCM_UNDEFINED)
602 label_page_table = SCM_EOL;
604 // Build a list of (systems . configuration) pairs. Note that we lay out
605 // the staves and find the configurations before drawing anything. Some
606 // grobs (like tuplet brackets) look at their neighbours while drawing
607 // themselves. If this happens before the neighbouring staves have
608 // been laid out, bad side-effects could happen (in particular,
609 // Align_interface::align_to_ideal_distances might be called).
610 SCM systems_configs_fncounts = SCM_EOL;
611 vsize footnote_count = 0;
613 for (vsize i = 0; i < lines_per_page.size (); i++)
615 int page_num = i + first_page_number;
616 bool bookpart_last_page = (i == lines_per_page.size () - 1);
617 bool rag = ragged () || (bookpart_last_page && ragged_last ());
618 SCM line_count = scm_from_int (lines_per_page[i]);
619 SCM lines = scm_list_head (systems, line_count);
620 int fn_lines = Page_layout_problem::get_footnote_count (lines);
621 Page_layout_problem::add_footnotes_to_lines (lines, reset_footnotes_on_new_page ? 0 : footnote_count, book_);
623 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
625 systems_configs_fncounts = scm_cons (scm_cons (lines, config), systems_configs_fncounts);
626 footnote_count += fn_lines;
627 systems = scm_list_tail (systems, line_count);
630 // Now it's safe to make the pages.
631 int page_num = first_page_number + lines_per_page.size () - 1;
632 for (SCM s = systems_configs_fncounts; scm_is_pair (s); s = scm_cdr (s))
634 SCM lines = scm_caar (s);
635 SCM config = scm_cdar (s);
637 bool bookpart_last_page = (s == systems_configs_fncounts);
638 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
640 SCM page_num_scm = scm_from_int (page_num);
641 for (SCM l = lines; scm_is_pair (l); l = scm_cdr (l))
643 SCM labels = SCM_EOL;
644 if (Grob *line = unsmob_grob (scm_car (l)))
646 System *system = dynamic_cast<System *> (line);
647 labels = system->get_property ("labels");
649 else if (Prob *prob = unsmob_prob (scm_car (l)))
650 labels = prob->get_property ("labels");
652 for (SCM lbls = labels; scm_is_pair (lbls); lbls = scm_cdr (lbls))
653 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
657 ret = scm_cons (page, ret);
661 // By reversing the table, we ensure that duplicated labels (eg. those
662 // straddling a page turn) will appear in the table with their last
664 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
665 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
669 /* The page-turn-page-breaker needs to have a line-breaker between any two
670 columns with non-NULL page-turn-permission.
672 The optimal-breaker needs to have a line-breaker between any two columns
673 with page-break-permission = 'force.
675 By using a grob predicate, we can accommodate both of these uses.
678 Page_breaking::create_system_list ()
680 SCM specs = book_->get_system_specs ();
681 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
683 if (Paper_score *ps = dynamic_cast<Paper_score *> (unsmob_music_output (scm_car (s))))
685 system_specs_.push_back (System_spec (ps));
689 Prob *pb = unsmob_prob (scm_car (s));
693 system_specs_.push_back (System_spec (pb));
696 if (!system_specs_.size ())
697 system_specs_.push_back (System_spec ());
701 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
703 SCM force_sym = ly_symbol2scm ("force");
705 chunks_.push_back (Break_position ());
706 breaks_.push_back (Break_position ());
708 for (vsize i = 0; i < system_specs_.size (); i++)
710 if (system_specs_[i].pscore_)
712 vector<Grob *> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
713 vector<Grob *> forced_line_break_cols;
715 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
716 if (scm_is_number (system_count))
718 // With system-count given, the line configuration for
719 // this score is fixed. We need to ensure that chunk
720 // boundaries only occur at line breaks.
721 Constrained_breaking breaking (system_specs_[i].pscore_);
722 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
724 for (vsize j = 0; j < details.size (); j++)
725 forced_line_break_cols.push_back (details[j].last_column_);
728 int last_forced_line_break_idx = 0;
729 vsize forced_line_break_idx = 0;
730 vector<vsize> line_breaker_columns;
731 line_breaker_columns.push_back (0);
733 for (vsize j = 1; j < cols.size (); j++)
735 if (forced_line_break_cols.size ())
737 if (forced_line_break_idx >= forced_line_break_cols.size ()
738 || forced_line_break_cols[forced_line_break_idx] != cols[j])
741 forced_line_break_idx++;
744 bool last = (j == cols.size () - 1);
745 bool break_point = is_break && is_break (cols[j]);
746 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
747 Break_position cur_pos = Break_position (i,
748 line_breaker_columns.size (),
752 // NOTE: even in the breaks_ list, forced_line_count_
753 // refers to the number of lines between a
754 // Break_position and the start of that /chunk/. This
755 // is needed for system_count_bounds to work correctly,
756 // since it mixes Break_positions from breaks_ and
758 if (scm_is_number (system_count))
759 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
761 if (break_point || (i == system_specs_.size () - 1 && last))
762 breaks_.push_back (cur_pos);
763 if (chunk_end || last)
765 chunks_.push_back (cur_pos);
766 last_forced_line_break_idx = forced_line_break_idx;
769 if ((break_point || chunk_end) && !last)
770 line_breaker_columns.push_back (j);
772 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
774 else if (system_specs_[i].prob_)
776 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
777 if (break_point || i == system_specs_.size () - 1)
778 breaks_.push_back (Break_position (i));
780 chunks_.push_back (Break_position (i));
782 /* FIXME: shouldn't we push a Null_breaker or similar dummy
784 line_breaking_.push_back (Constrained_breaking (NULL));
789 vector<Break_position>
790 Page_breaking::chunk_list (vsize start_index, vsize end_index)
792 Break_position start = breaks_[start_index];
793 Break_position end = breaks_[end_index];
796 for (; i < chunks_.size () && chunks_[i] <= start; i++)
799 vector<Break_position> ret;
800 ret.push_back (start);
801 for (; i < chunks_.size () && chunks_[i] < end; i++)
802 ret.push_back (chunks_[i]);
807 // Returns the minimum number of _non-title_ lines.
809 Page_breaking::min_system_count (vsize start, vsize end)
811 vector<Break_position> chunks = chunk_list (start, end);
812 Line_division div = system_count_bounds (chunks, true);
815 for (vsize i = 0; i < div.size (); i++)
820 // Returns the maximum number of _non-title_ lines.
822 Page_breaking::max_system_count (vsize start, vsize end)
824 vector<Break_position> chunks = chunk_list (start, end);
825 Line_division div = system_count_bounds (chunks, false);
828 for (vsize i = 0; i < div.size (); i++)
833 // The numbers returned by this function represent either
834 // the maximum or minimum number of _non-title_ lines
836 Page_breaking::Line_division
837 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
840 assert (chunks.size () >= 2);
843 ret.resize (chunks.size () - 1, 0);
845 for (vsize i = 0; i + 1 < chunks.size (); i++)
847 vsize sys = next_system (chunks[i]);
849 if (chunks[i + 1].forced_line_count_)
850 ret[i] = chunks[i + 1].forced_line_count_;
851 else if (system_specs_[sys].pscore_)
855 line_breaker_args (sys, chunks[i], chunks[i + 1], &start, &end);
857 ? line_breaking_[sys].min_system_count (start, end)
858 : line_breaking_[sys].max_system_count (start, end);
866 Page_breaking::set_current_breakpoints (vsize start,
869 Line_division lower_bound,
870 Line_division upper_bound)
872 system_count_ = system_count;
873 current_chunks_ = chunk_list (start, end);
874 current_start_breakpoint_ = start;
875 current_end_breakpoint_ = end;
876 clear_line_details_cache ();
878 if (!lower_bound.size ())
879 lower_bound = system_count_bounds (current_chunks_, true);
880 if (!upper_bound.size ())
881 upper_bound = system_count_bounds (current_chunks_, false);
883 assert (lower_bound.size () == current_chunks_.size () - 1);
884 assert (upper_bound.size () == current_chunks_.size () - 1);
886 Line_division work_in_progress;
887 current_configurations_.clear ();
888 line_divisions_rec (system_count,
893 /* we only consider a constant number of configurations. Otherwise,
894 this becomes slow when there are many small scores. The constant
895 5 is somewhat arbitrary. */
896 if (current_configurations_.size () > 5)
898 vector<pair<Real, vsize> > dems_and_indices;
900 for (vsize i = 0; i < current_configurations_.size (); i++)
902 cache_line_details (i);
904 for (vsize j = 0; j < cached_line_details_.size (); j++)
905 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
906 + cached_line_details_[j].break_penalty_;
908 dems_and_indices.push_back (pair<Real, vsize> (dem, i));
910 vector_sort (dems_and_indices, less<pair<Real, vsize> > ());
912 vector<Line_division> best_5_configurations;
913 for (vsize i = 0; i < 5; i++)
914 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
916 clear_line_details_cache ();
917 current_configurations_ = best_5_configurations;
922 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
924 current_chunks_ = chunk_list (start, end);
925 current_start_breakpoint_ = start;
926 current_end_breakpoint_ = end;
927 clear_line_details_cache ();
931 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
933 vsize sys = next_system (current_chunks_[i]);
935 if (current_chunks_[i + 1].forced_line_count_)
936 div.push_back (current_chunks_[i + 1].forced_line_count_);
937 else if (system_specs_[sys].pscore_)
939 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
940 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
945 system_count_ += div.back ();
947 current_configurations_.clear ();
948 current_configurations_.push_back (div);
952 Page_breaking::current_configuration_count () const
954 return current_configurations_.size ();
958 Page_breaking::cache_line_details (vsize configuration_index)
960 if (cached_configuration_index_ != configuration_index)
962 cached_configuration_index_ = configuration_index;
964 Line_division &div = current_configurations_[configuration_index];
965 uncompressed_line_details_.clear ();
966 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
968 vsize sys = next_system (current_chunks_[i]);
969 if (system_specs_[sys].pscore_)
973 line_breaker_args (sys, current_chunks_[i], current_chunks_[i + 1], &start, &end);
975 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
976 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
980 assert (div[i] == 0);
981 uncompressed_line_details_.push_back (system_specs_[sys].prob_
982 ? Line_details (system_specs_[sys].prob_, book_->paper_)
986 cached_line_details_ = compress_lines (uncompressed_line_details_);
987 compute_line_heights ();
992 Page_breaking::clear_line_details_cache ()
994 cached_configuration_index_ = VPOS;
995 cached_line_details_.clear ();
996 uncompressed_line_details_.clear ();
1000 Page_breaking::line_divisions_rec (vsize system_count,
1001 Line_division const &min_sys,
1002 Line_division const &max_sys,
1003 Line_division *cur_division)
1005 vsize my_index = cur_division->size ();
1009 for (vsize i = my_index + 1; i < min_sys.size (); i++)
1011 others_min += min_sys[i];
1012 others_max += max_sys[i];
1014 others_max = min (others_max, (int) system_count);
1015 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
1016 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
1018 if (real_min > real_max || real_min < 0)
1020 /* this should never happen within a recursive call. If it happens
1021 at all, it means that we were called with an unsolvable problem
1022 and we should return an empty result */
1023 assert (my_index == 0);
1027 for (int i = real_min; i <= real_max; i++)
1029 cur_division->push_back (i);
1030 if (my_index == min_sys.size () - 1)
1031 current_configurations_.push_back (*cur_division);
1033 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1034 cur_division->pop_back ();
1039 Page_breaking::compute_line_heights ()
1041 Real prev_hanging = 0;
1042 Real prev_hanging_begin = 0;
1043 Real prev_hanging_rest = 0;
1045 // refpoint_hanging is the y coordinate of the origin of this system.
1046 // It may not be the same as refpoint_extent[UP], which is the
1047 // refpoint of the first spaceable staff in this system.
1048 Real prev_refpoint_hanging = 0;
1049 for (vsize i = 0; i < cached_line_details_.size (); i++)
1051 Line_details &cur = cached_line_details_[i];
1052 Line_shape shape = cur.shape_;
1053 Real a = shape.begin_[UP];
1054 Real b = shape.rest_[UP];
1055 bool title = cur.title_;
1056 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1061 Line_details const &prev = cached_line_details_[i - 1];
1062 if (!cur.tight_spacing_)
1064 ? prev.title_padding_
1066 Real min_dist = title
1067 ? prev.title_min_distance_
1068 : prev.min_distance_;
1069 refpoint_hanging = max (refpoint_hanging + padding,
1070 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1071 + cur.refpoint_extent_[UP] + min_dist);
1074 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1075 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1076 Real hanging = max (hanging_begin, hanging_rest);
1077 cur.tallness_ = hanging - prev_hanging;
1078 prev_hanging = hanging;
1079 prev_hanging_begin = hanging_begin;
1080 prev_hanging_rest = hanging_rest;
1081 prev_refpoint_hanging = refpoint_hanging;
1086 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1089 vsize page_starter = 0;
1090 Real cur_rod_height = 0;
1091 Real cur_spring_height = 0;
1092 Real cur_page_height = page_height (first_page_num, false);
1095 cache_line_details (configuration);
1097 if (cached_line_details_.size ())
1098 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1100 for (vsize i = 0; i < cached_line_details_.size (); i++)
1102 Line_details const &cur = cached_line_details_[i];
1103 Line_details const *const prev = (i > 0) ? &cached_line_details_[i - 1] : 0;
1105 if (cur_rod_height > 0)
1106 ext_len = cur.tallness_;
1108 ext_len = cur.full_height ();
1110 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1111 Real next_rod_height = cur_rod_height + ext_len;
1112 Real next_spring_height = cur_spring_height + spring_len;
1113 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1114 + min_whitespace_at_bottom_of_page (cur);
1115 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1117 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1118 || too_many_lines (next_line_count)
1119 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1121 line_count = cur.compressed_nontitle_lines_count_;
1122 cur_rod_height = cur.full_height ();
1123 cur_spring_height = 0;
1126 cur_page_height = page_height (first_page_num + ret, false);
1127 cur_page_height -= min_whitespace_at_top_of_page (cur);
1133 cur_rod_height = next_rod_height;
1134 cur_spring_height = next_spring_height;
1135 line_count = next_line_count;
1139 /* there are two potential problems with the last page (because we didn't know
1140 it was the last page until after we managed to fit all the systems to it):
1141 - we are ragged-last but the last page has a compressed spring
1142 - the value returned by page_height (num, true) is smaller than the
1143 value returned by page_height (num, false) and it causes the page not to
1146 In either case, we just need to add one more page. This is because the last
1147 line will always fit on the extra page and by adding one more page to the
1148 end, the previous page is no longer the last page, so our previous
1149 calculations that treated it as a non-last page were ok.
1154 cur_page_height = page_height (first_page_num + ret - 1, true);
1155 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1156 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1158 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1159 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1160 && cur_height > cur_page_height
1161 /* don't increase the page count if the last page had only one system */
1162 && cur_rod_height > cached_line_details_.back ().full_height ())
1164 assert (ret <= cached_line_details_.size ());
1170 // If systems_per_page_ is positive, we don't really try to space on N pages;
1171 // we just put the requested number of systems on each page and penalize
1172 // if the result doesn't have N pages.
1174 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1176 Page_spacing_result ret;
1178 if (systems_per_page_ > 0)
1180 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1181 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1185 cache_line_details (configuration);
1186 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1187 && n <= cached_line_details_.size ());
1190 programming_error ("number of pages is out of bounds");
1192 if (n == 1 && valid_n)
1193 ret = space_systems_on_1_page (cached_line_details_,
1194 page_height (first_page_num, is_last ()),
1195 ragged () || (is_last () && ragged_last ()));
1196 else if (n == 2 && valid_n)
1197 ret = space_systems_on_2_pages (configuration, first_page_num);
1200 Page_spacer ps (cached_line_details_, first_page_num, this);
1204 return finalize_spacing_result (configuration, ret);
1208 Page_breaking::blank_page_penalty () const
1213 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1214 else if (ends_score ())
1215 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1217 penalty_sym = ly_symbol2scm ("blank-page-force");
1219 Break_position const &pos = breaks_[current_end_breakpoint_];
1220 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1221 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1223 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1226 // If systems_per_page_ is positive, we don't really try to space on N
1227 // or N+1 pages; see the comment to space_systems_on_n_pages.
1229 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1230 Real penalty_for_fewer_pages)
1232 Page_spacing_result n_res;
1233 Page_spacing_result m_res;
1235 if (systems_per_page_ > 0)
1237 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1238 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n - 1)) ? 0 : BAD_SPACING_PENALTY;
1242 cache_line_details (configuration);
1243 vsize min_p_count = min_page_count (configuration, first_page_num);
1244 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1247 programming_error ("both page counts are out of bounds");
1249 if (n == 1 && valid_n)
1251 bool rag = ragged () || (is_last () && ragged_last ());
1252 Real height = page_height (first_page_num, is_last ());
1254 if (1 >= min_p_count)
1255 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1256 if (1 < cached_line_details_.size ())
1257 m_res = space_systems_on_2_pages (configuration, first_page_num);
1261 Page_spacer ps (cached_line_details_, first_page_num, this);
1263 if (n >= min_p_count || !valid_n)
1264 n_res = ps.solve (n);
1265 if (n < cached_line_details_.size () || !valid_n)
1266 m_res = ps.solve (n + 1);
1269 m_res = finalize_spacing_result (configuration, m_res);
1270 n_res = finalize_spacing_result (configuration, n_res);
1272 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1273 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1275 if (n_res.force_.size ())
1276 n_res.force_.back () += penalty_for_fewer_pages;
1278 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1282 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1284 if (systems_per_page_ > 0)
1285 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1287 cache_line_details (configuration);
1288 Page_spacer ps (cached_line_details_, first_page_num, this);
1290 return finalize_spacing_result (configuration, ps.solve ());
1294 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1295 vsize first_page_num)
1297 Page_spacing_result res;
1298 Page_spacing space (page_height (first_page_num, false), this);
1301 vsize page_first_line = 0;
1303 cache_line_details (configuration);
1304 while (line < cached_line_details_.size ())
1308 space.resize (page_height (first_page_num + page, false));
1310 int system_count_on_this_page = 0;
1311 while (system_count_on_this_page < systems_per_page_
1312 && line < cached_line_details_.size ())
1314 Line_details const &cur_line = cached_line_details_[line];
1315 space.append_system (cur_line);
1316 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1319 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1323 res.systems_per_page_.push_back (line - page_first_line);
1325 res.force_.push_back (space.force_);
1326 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1327 if (system_count_on_this_page != systems_per_page_)
1329 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1330 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1331 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1334 page_first_line = line;
1337 /* Recalculate forces for the last page because we know now that is
1338 really the last page. */
1339 space.resize (page_height (first_page_num + page, true));
1340 res.force_.back () = space.force_;
1341 return finalize_spacing_result (configuration, res);
1345 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1347 // TODO: add support for min/max-systems-per-page.
1348 Page_spacing_result res;
1350 vsize page_first_line = 0;
1351 Page_spacing space (page_height (first_page_num, false), this);
1353 cache_line_details (configuration);
1354 for (vsize line = 0; line < cached_line_details_.size (); line++)
1356 Real prev_force = space.force_;
1357 space.append_system (cached_line_details_[line]);
1358 if ((line > page_first_line)
1359 && (isinf (space.force_)
1361 && (cached_line_details_[line - 1].page_permission_ == ly_symbol2scm ("force")))))
1363 res.systems_per_page_.push_back (line - page_first_line);
1364 res.force_.push_back (prev_force);
1365 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1367 space.resize (page_height (first_page_num + page, false));
1369 space.append_system (cached_line_details_[line]);
1370 page_first_line = line;
1373 if (line == cached_line_details_.size () - 1)
1375 /* This is the last line */
1376 /* When the last page height was computed, we did not know yet that it
1377 * was the last one. If the systems put on it don't fit anymore, the last
1378 * system is moved to a new page */
1379 space.resize (page_height (first_page_num + page, true));
1380 if ((line > page_first_line) && (isinf (space.force_)))
1382 res.systems_per_page_.push_back (line - page_first_line);
1383 res.force_.push_back (prev_force);
1384 /* the last page containing the last line */
1385 space.resize (page_height (first_page_num + page + 1, true));
1387 space.append_system (cached_line_details_[line]);
1388 res.systems_per_page_.push_back (1);
1389 res.force_.push_back (space.force_);
1390 res.penalty_ += cached_line_details_[line - 1].page_penalty_;
1391 res.penalty_ += cached_line_details_[line].page_penalty_;
1395 res.systems_per_page_.push_back (line + 1 - page_first_line);
1396 res.force_.push_back (space.force_);
1397 res.penalty_ += cached_line_details_[line].page_penalty_;
1401 return finalize_spacing_result (configuration, res);
1404 /* Calculate demerits and fix res.systems_per_page_ so that
1405 it refers to the original line numbers, not the ones given by compress_lines (). */
1407 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1409 if (res.force_.empty ())
1412 cache_line_details (configuration);
1413 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1415 Real line_force = 0;
1416 Real line_penalty = 0;
1417 Real page_demerits = res.penalty_;
1418 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1420 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1422 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1423 line_penalty += uncompressed_line_details_[i].break_penalty_;
1426 for (vsize i = 0; i < res.force_.size (); i++)
1428 Real f = res.force_[i];
1430 page_demerits += min (f * f, BAD_SPACING_PENALTY);
1433 /* for a while we tried averaging page and line forces across pages instead
1434 of summing them, but it caused a problem: if there is a single page
1435 with a very bad page force (for example because of a forced page break),
1436 the page breaker will put in a _lot_ of pages so that the bad force
1437 becomes averaged out over many pages. */
1438 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1443 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1444 are by far the most common cases, we have special functions for them.
1446 space_systems_on_1_page has a different calling convention than most of the
1447 space_systems functions. This is because space_systems_on_1_page is (unlike
1448 the other space_systems functions) sometimes called on subsets of a full
1451 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1453 Page_spacing space (page_height, this);
1454 Page_spacing_result ret;
1457 for (vsize i = 0; i < lines.size (); i++)
1459 space.append_system (lines[i]);
1460 line_count += lines[i].compressed_nontitle_lines_count_;
1463 ret.systems_per_page_.push_back (lines.size ());
1464 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1465 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1466 ret.system_count_status_ |= line_count_status (line_count);
1468 /* don't do finalize_spacing_result () because we are only an internal function */
1473 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1475 Real page1_height = page_height (first_page_num, false);
1476 Real page2_height = page_height (first_page_num + 1, is_last ());
1477 bool ragged1 = ragged ();
1478 bool ragged2 = ragged () || (is_last () && ragged_last ());
1480 /* if there is a forced break, this reduces to 2 1-page problems */
1481 cache_line_details (configuration);
1482 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1483 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1485 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1486 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1487 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1488 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1490 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1491 p1.force_.push_back (p2.force_[0]);
1492 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1493 p1.system_count_status_ |= p2.system_count_status_;
1497 vector<Real> page1_force;
1498 vector<Real> page2_force;
1500 // page1_penalty and page2_penalty store the penalties based
1501 // on min-systems-per-page and max-systems-per-page.
1502 vector<Real> page1_penalty;
1503 vector<Real> page2_penalty;
1505 // page1_status and page2_status keep track of whether the min-systems-per-page
1506 // and max-systems-per-page constraints are satisfied.
1507 vector<int> page1_status;
1508 vector<int> page2_status;
1510 Page_spacing page1 (page1_height, this);
1511 Page_spacing page2 (page2_height, this);
1512 int page1_line_count = 0;
1513 int page2_line_count = 0;
1515 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1516 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1517 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1518 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1519 page1_status.resize (cached_line_details_.size () - 1, 0);
1520 page2_status.resize (cached_line_details_.size () - 1, 0);
1522 /* find the page 1 and page 2 forces for each page-breaking position */
1523 for (vsize i = 0; i < page1_force.size (); i++)
1525 page1.append_system (cached_line_details_[i]);
1526 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1527 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1528 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1530 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1531 page1_penalty[i] = line_count_penalty (page1_line_count);
1532 page1_status[i] = line_count_status (page1_line_count);
1535 page2_force[page2_force.size () - 1 - i]
1536 = (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1538 page2_force[page2_force.size () - 1 - i] = page2.force_;
1539 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1540 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1543 /* find the position that minimises the sum of the page forces */
1544 vsize best_sys_count = 1;
1545 Real best_demerits = infinity_f;
1546 for (vsize i = 0; i < page1_force.size (); i++)
1548 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1550 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1551 // constraints. That is, we penalize harshly when they don't happen
1552 // but we don't completely reject.
1554 + page1_penalty[i] + page2_penalty[i]
1555 + cached_line_details_[i + 1].page_penalty_
1556 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1557 if (dem < best_demerits)
1559 best_demerits = dem;
1560 best_sys_count = i + 1;
1564 Page_spacing_result ret;
1565 ret.systems_per_page_.push_back (best_sys_count);
1566 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1567 ret.force_.push_back (page1_force[best_sys_count - 1]);
1568 ret.force_.push_back (page2_force[best_sys_count - 1]);
1569 ret.system_count_status_ = page1_status[best_sys_count - 1] | page2_status[best_sys_count - 1];
1570 ret.penalty_ = cached_line_details_[best_sys_count - 1].page_penalty_
1571 + cached_line_details_.back ().page_penalty_
1572 + cached_line_details_.back ().turn_penalty_
1573 + page1_penalty[best_sys_count - 1] + page2_penalty[best_sys_count - 1];
1575 /* don't do finalize_spacing_result () because we are only an internal function */
1580 Page_breaking::all_lines_stretched (vsize configuration)
1582 cache_line_details (configuration);
1583 for (vsize i = 0; i < cached_line_details_.size (); i++)
1584 if (cached_line_details_[i].force_ < 0)
1590 Page_breaking::Line_division
1591 Page_breaking::current_configuration (vsize configuration_index) const
1593 return current_configurations_[configuration_index];
1597 Page_breaking::is_last () const
1599 return current_end_breakpoint_ == last_break_position ();
1603 Page_breaking::ends_score () const
1605 return breaks_[current_end_breakpoint_].score_ender_;
1609 Page_breaking::last_break_position () const
1611 return breaks_.size () - 1;
1614 // This gives the minimum distance between the top of the
1615 // printable area (ie. the bottom of the top-margin) and
1616 // the extent box of the topmost system.
1618 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1620 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1622 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1624 Real min_distance = -infinity_f;
1627 Page_layout_problem::read_spacing_spec (first_system_spacing,
1629 ly_symbol2scm ("minimum-distance"));
1630 Page_layout_problem::read_spacing_spec (first_system_spacing,
1632 ly_symbol2scm ("padding"));
1634 // FIXME: take into account the height of the header
1635 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1636 return max (0.0, max (padding, min_distance - translate));
1640 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1642 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1643 Real min_distance = -infinity_f;
1646 Page_layout_problem::read_spacing_spec (last_system_spacing,
1648 ly_symbol2scm ("minimum-distance"));
1649 Page_layout_problem::read_spacing_spec (last_system_spacing,
1651 ly_symbol2scm ("padding"));
1653 // FIXME: take into account the height of the footer
1654 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1655 return max (0.0, max (padding, min_distance + translate));
1659 Page_breaking::orphan_penalty () const
1661 return orphan_penalty_;