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 "output-def.hh"
135 #include "page-layout-problem.hh"
136 #include "page-spacing.hh"
137 #include "paper-book.hh"
138 #include "paper-score.hh"
139 #include "paper-system.hh"
143 /* for each forbidden page break, merge the systems around it into one
145 static vector<Line_details>
146 compress_lines (const vector<Line_details> &orig)
148 vector<Line_details> ret;
150 for (vsize i = 0; i < orig.size (); i++)
152 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
154 Line_details const &old = ret.back ();
155 Line_details compressed = orig[i];
157 We must account for the padding between the lines that we are compressing.
158 The padding values come from "old," which is the upper system here. Note
159 the meaning of tight-spacing: if a system has tight-spacing, then the padding
160 _before_ it is ignored.
163 if (!orig[i].tight_spacing_)
164 padding = orig[i].title_ ? old.title_padding_ : old.padding_;
166 // FIXME: double check these. Doesn't foo.piggyback (bar) mean
167 // that foo goes on top?
168 // TODO: break out a Line_details::piggyback from here?
169 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
170 compressed.refpoint_extent_[UP] = old.refpoint_extent_[UP];
171 compressed.refpoint_extent_[DOWN] += compressed.shape_.rest_[UP] - old.shape_.rest_[UP];
172 compressed.space_ += old.space_;
173 compressed.inverse_hooke_ += old.inverse_hooke_;
175 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
176 compressed.compressed_nontitle_lines_count_ =
177 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
179 // compressed.title_ is true if and only if the first of its
180 // compressed lines was a title.
181 compressed.title_ = old.title_;
182 ret.back () = compressed;
186 ret.push_back (orig[i]);
187 ret.back ().force_ = 0;
193 /* translate the number of systems-per-page into something meaningful for
194 the uncompressed lines.
197 uncompress_solution (vector<vsize> const &systems_per_page,
198 vector<Line_details> const &compressed)
203 for (vsize i = 0; i < systems_per_page.size (); i++)
205 int compressed_count = 0;
206 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
207 compressed_count += compressed[j].compressed_lines_count_ - 1;
209 ret.push_back (systems_per_page[i] + compressed_count);
210 start_sys += systems_per_page[i];
215 /* for Page_breaking, the start index (when we are dealing with the stuff
216 between a pair of breakpoints) refers to the break_ index of the end of
217 the previous page. So the system index of the start of the current page
218 could either be the same as the end of the previous page or one more than
221 /* Turn a break index into the sys index that starts the next page */
223 Page_breaking::next_system (Break_position const &break_pos) const
225 vsize sys = break_pos.system_spec_index_;
227 if (sys == VPOS) /* beginning of the book */
229 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
230 return sys; /* the score overflows the previous page */
231 return sys + 1; /* this page starts with a new System_spec */
234 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
238 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
239 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
240 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
241 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
242 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
243 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
244 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
246 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
248 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
249 min_systems_per_page_ = max_systems_per_page_ = 0;
251 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
253 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
254 min_systems_per_page_ = max_systems_per_page_ = 0;
257 create_system_list ();
258 find_chunks_and_breaks (is_break, prob_break);
261 Page_breaking::~Page_breaking ()
266 Page_breaking::ragged () const
272 Page_breaking::ragged_last () const
278 Page_breaking::systems_per_page () const
280 return systems_per_page_;
284 Page_breaking::max_systems_per_page () const
286 if (systems_per_page_)
287 return systems_per_page_;
288 return max_systems_per_page_;
292 Page_breaking::min_systems_per_page () const
294 if (systems_per_page_)
295 return systems_per_page_;
296 return min_systems_per_page_;
300 Page_breaking::system_count () const
302 return system_count_;
306 Page_breaking::too_many_lines (int line_count) const
308 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
312 Page_breaking::too_few_lines (int line_count) const
314 return line_count < min_systems_per_page ();
318 Page_breaking::line_count_penalty (int line_count) const
320 if (too_many_lines (line_count))
321 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
322 if (too_few_lines (line_count))
323 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
329 Page_breaking::line_count_status (int line_count) const
331 if (too_many_lines (line_count))
332 return SYSTEM_COUNT_TOO_MANY;
333 if (too_few_lines (line_count))
334 return SYSTEM_COUNT_TOO_FEW;
336 return SYSTEM_COUNT_OK;
339 /* translate indices into breaks_ into start-end parameters for the line breaker */
341 Page_breaking::line_breaker_args (vsize sys,
342 Break_position const &start,
343 Break_position const &end,
344 vsize *line_breaker_start,
345 vsize *line_breaker_end)
347 assert (system_specs_[sys].pscore_);
348 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
350 if (start.system_spec_index_ == sys)
351 *line_breaker_start = start.score_break_;
353 *line_breaker_start = 0;
355 if (end.system_spec_index_ == sys)
356 *line_breaker_end = end.score_break_;
358 *line_breaker_end = VPOS;
362 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
363 Line_division const &div)
365 vector<Break_position> chunks = chunk_list (start_break, end_break);
366 bool ignore_div = false;
367 if (chunks.size () != div.size () + 1)
369 programming_error ("did not find a valid page breaking configuration");
373 for (vsize i = 0; i + 1 < chunks.size (); i++)
375 vsize sys = next_system (chunks[i]);
376 if (system_specs_[sys].pscore_)
380 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
382 vector<Column_x_positions> pos = ignore_div
383 ? line_breaking_[sys].best_solution (start, end)
384 : line_breaking_[sys].solve (start, end, div[i]);
385 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
391 Page_breaking::systems ()
394 for (vsize sys = 0; sys < system_specs_.size (); sys++)
396 if (system_specs_[sys].pscore_)
398 system_specs_[sys].pscore_->root_system ()
399 ->do_break_substitution_and_fixup_refpoints ();
400 SCM lines = system_specs_[sys].pscore_->root_system ()
401 ->get_broken_system_grobs ();
402 ret = scm_cons (lines, ret);
404 else if (Prob *pb = system_specs_[sys].prob_)
406 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
410 return scm_append (scm_reverse (ret));
414 Page_breaking::make_page (int page_num, bool last) const
416 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
417 SCM mod = scm_c_resolve_module ("scm page");
418 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
420 make_page_scm = scm_variable_ref (make_page_scm);
422 return scm_apply_0 (make_page_scm,
423 scm_list_n (book_->self_scm (),
424 ly_symbol2scm ("page-number"), scm_from_int (page_num),
425 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
426 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
430 // Returns the total height of the paper, including margins and
431 // space for the header/footer. This is an upper bound on
432 // page_height, and it doesn't depend on the current page.
434 Page_breaking::paper_height () const
436 return paper_height_;
440 Page_breaking::page_height (int page_num, bool last) const
442 // The caches allow us to store the page heights for any
443 // non-negative page numbers. We use a negative value in the
444 // cache to signal that that position has not yet been initialized.
445 // This means that we won't cache properly if page_num is negative or
446 // if calc_height returns a negative number. But that's likely to
447 // be rare, so it shouldn't affect performance.
448 vector<Real>& cache = last ? last_page_height_cache_ : page_height_cache_;
449 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
450 return cache[page_num];
453 SCM mod = scm_c_resolve_module ("scm page");
454 SCM page = make_page (page_num, last);
455 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
456 calc_height = scm_variable_ref (calc_height);
458 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
459 Real height = scm_to_double (height_scm);
463 if ((int) cache.size () <= page_num)
464 cache.resize (page_num + 1, -1);
465 cache[page_num] = height;
472 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
474 Break_position const &pos = breaks_[breakpoint];
476 if (pos.system_spec_index_ == VPOS)
478 if (system_specs_[pos.system_spec_index_].pscore_)
479 return pos.col_->get_property (str);
480 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
484 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
486 SCM dummy_page = make_page (page_num, last);
487 Page_layout_problem layout (book_, dummy_page, systems);
488 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
492 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
494 // Create a stencil for each system.
495 SCM paper_systems = SCM_EOL;
496 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
498 SCM paper_system = scm_car (s);
499 if (Grob *g = unsmob_grob (scm_car (s)))
501 System *sys = dynamic_cast<System*> (g);
502 paper_system = sys->get_paper_system ();
505 paper_systems = scm_cons (paper_system, paper_systems);
508 // Create the page and draw it.
509 SCM page = make_page (page_num, last);
510 SCM page_module = scm_c_resolve_module ("scm page");
511 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
512 page_stencil = scm_variable_ref (page_stencil);
514 Prob *p = unsmob_prob (page);
515 p->set_property ("lines", paper_systems);
516 p->set_property ("configuration", configuration);
517 scm_apply_1 (page_stencil, page, SCM_EOL);
523 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
525 if (scm_is_null (systems))
528 int first_page_number
529 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
531 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
532 if (label_page_table == SCM_UNDEFINED)
533 label_page_table = SCM_EOL;
535 // Build a list of (systems . configuration) pairs. Note that we lay out
536 // the staves and find the configurations before drawing anything. Some
537 // grobs (like tuplet brackets) look at their neighbours while drawing
538 // themselves. If this happens before the neighbouring staves have
539 // been laid out, bad side-effects could happen (in particular,
540 // Align_interface::align_to_ideal_distances might be called).
541 SCM systems_and_configs = SCM_EOL;
543 for (vsize i = 0; i < lines_per_page.size (); i++)
545 int page_num = i + first_page_number;
546 bool bookpart_last_page = (i == lines_per_page.size () - 1);
547 bool rag = ragged () || (bookpart_last_page && ragged_last ());
548 SCM line_count = scm_from_int (lines_per_page[i]);
549 SCM lines = scm_list_head (systems, line_count);
550 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
552 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
553 systems = scm_list_tail (systems, line_count);
556 // Now it's safe to make the pages.
557 int page_num = first_page_number + lines_per_page.size () - 1;
558 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
560 SCM lines = scm_caar (s);
561 SCM config = scm_cdar (s);
562 bool bookpart_last_page = (s == systems_and_configs);
563 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
566 SCM page_num_scm = scm_from_int (page_num);
567 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
569 SCM labels = SCM_EOL;
570 if (Grob * line = unsmob_grob (scm_car (l)))
572 System *system = dynamic_cast<System*> (line);
573 labels = system->get_property ("labels");
575 else if (Prob *prob = unsmob_prob (scm_car (l)))
576 labels = prob->get_property ("labels");
578 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
579 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
583 ret = scm_cons (page, ret);
587 // By reversing the table, we ensure that duplicated labels (eg. those
588 // straddling a page turn) will appear in the table with their last
590 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
591 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
595 /* The page-turn-page-breaker needs to have a line-breaker between any two
596 columns with non-NULL page-turn-permission.
598 The optimal-breaker needs to have a line-breaker between any two columns
599 with page-break-permission = 'force.
601 By using a grob predicate, we can accommodate both of these uses.
604 Page_breaking::create_system_list ()
606 SCM specs = book_->get_system_specs ();
607 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
609 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
611 system_specs_.push_back (System_spec (ps));
615 Prob *pb = unsmob_prob (scm_car (s));
619 system_specs_.push_back (System_spec (pb));
622 if (!system_specs_.size ())
623 system_specs_.push_back (System_spec ());
627 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
629 SCM force_sym = ly_symbol2scm ("force");
631 chunks_.push_back (Break_position ());
632 breaks_.push_back (Break_position ());
634 for (vsize i = 0; i < system_specs_.size (); i++)
636 if (system_specs_[i].pscore_)
638 vector<Grob*> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
639 vector<Grob*> forced_line_break_cols;
641 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
642 if (scm_is_number (system_count))
644 // With system-count given, the line configuration for
645 // this score is fixed. We need to ensure that chunk
646 // boundaries only occur at line breaks.
647 Constrained_breaking breaking (system_specs_[i].pscore_);
648 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
650 for (vsize j = 0; j < details.size (); j++)
651 forced_line_break_cols.push_back (details[j].last_column_);
654 int last_forced_line_break_idx = 0;
655 vsize forced_line_break_idx = 0;
656 vector<vsize> line_breaker_columns;
657 line_breaker_columns.push_back (0);
659 for (vsize j = 1; j < cols.size (); j++)
661 if (forced_line_break_cols.size ())
663 if (forced_line_break_idx >= forced_line_break_cols.size ()
664 || forced_line_break_cols[forced_line_break_idx] != cols[j])
667 forced_line_break_idx++;
670 bool last = (j == cols.size () - 1);
671 bool break_point = is_break && is_break (cols[j]);
672 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
673 Break_position cur_pos = Break_position (i,
674 line_breaker_columns.size (),
678 // NOTE: even in the breaks_ list, forced_line_count_
679 // refers to the number of lines between a
680 // Break_position and the start of that /chunk/. This
681 // is needed for system_count_bounds to work correctly,
682 // since it mixes Break_positions from breaks_ and
684 if (scm_is_number (system_count))
685 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
687 if (break_point || (i == system_specs_.size () - 1 && last))
688 breaks_.push_back (cur_pos);
689 if (chunk_end || last)
691 chunks_.push_back (cur_pos);
692 last_forced_line_break_idx = forced_line_break_idx;
695 if ((break_point || chunk_end) && !last)
696 line_breaker_columns.push_back (j);
698 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
700 else if (system_specs_[i].prob_)
702 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
703 if (break_point || i == system_specs_.size () - 1)
704 breaks_.push_back (Break_position (i));
706 chunks_.push_back (Break_position (i));
708 /* FIXME: shouldn't we push a Null_breaker or similar dummy
710 line_breaking_.push_back (Constrained_breaking (NULL));
715 vector<Break_position>
716 Page_breaking::chunk_list (vsize start_index, vsize end_index)
718 Break_position start = breaks_[start_index];
719 Break_position end = breaks_[end_index];
722 for (; i < chunks_.size () && chunks_[i] <= start; i++)
725 vector<Break_position> ret;
726 ret.push_back (start);
727 for (; i < chunks_.size () && chunks_[i] < end; i++)
728 ret.push_back (chunks_[i]);
733 // Returns the minimum number of _non-title_ lines.
735 Page_breaking::min_system_count (vsize start, vsize end)
737 vector<Break_position> chunks = chunk_list (start, end);
738 Line_division div = system_count_bounds (chunks, true);
741 for (vsize i = 0; i < div.size (); i++)
746 // Returns the maximum number of _non-title_ lines.
748 Page_breaking::max_system_count (vsize start, vsize end)
750 vector<Break_position> chunks = chunk_list (start, end);
751 Line_division div = system_count_bounds (chunks, false);
754 for (vsize i = 0; i < div.size (); i++)
759 // The numbers returned by this function represent either
760 // the maximum or minimum number of _non-title_ lines
762 Page_breaking::Line_division
763 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
766 assert (chunks.size () >= 2);
769 ret.resize (chunks.size () - 1, 0);
771 for (vsize i = 0; i + 1 < chunks.size (); i++)
773 vsize sys = next_system (chunks[i]);
775 if (chunks[i+1].forced_line_count_)
776 ret[i] = chunks[i+1].forced_line_count_;
777 else if (system_specs_[sys].pscore_)
781 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
783 ? line_breaking_[sys].min_system_count (start, end)
784 : line_breaking_[sys].max_system_count (start, end);
792 Page_breaking::set_current_breakpoints (vsize start,
795 Line_division lower_bound,
796 Line_division upper_bound)
798 system_count_ = system_count;
799 current_chunks_ = chunk_list (start, end);
800 current_start_breakpoint_ = start;
801 current_end_breakpoint_ = end;
802 clear_line_details_cache ();
804 if (!lower_bound.size ())
805 lower_bound = system_count_bounds (current_chunks_, true);
806 if (!upper_bound.size ())
807 upper_bound = system_count_bounds (current_chunks_, false);
809 assert (lower_bound.size () == current_chunks_.size () - 1);
810 assert (upper_bound.size () == current_chunks_.size () - 1);
812 Line_division work_in_progress;
813 current_configurations_.clear ();
814 line_divisions_rec (system_count,
819 /* we only consider a constant number of configurations. Otherwise,
820 this becomes slow when there are many small scores. The constant
821 5 is somewhat arbitrary. */
822 if (current_configurations_.size () > 5)
824 vector<pair<Real,vsize> > dems_and_indices;
826 for (vsize i = 0; i < current_configurations_.size (); i++)
828 cache_line_details (i);
830 for (vsize j = 0; j < cached_line_details_.size (); j++)
831 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
832 + cached_line_details_[j].break_penalty_;
834 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
836 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
838 vector<Line_division> best_5_configurations;
839 for (vsize i = 0; i < 5; i++)
840 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
842 clear_line_details_cache ();
843 current_configurations_ = best_5_configurations;
848 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
850 current_chunks_ = chunk_list (start, end);
851 current_start_breakpoint_ = start;
852 current_end_breakpoint_ = end;
853 clear_line_details_cache ();
857 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
859 vsize sys = next_system (current_chunks_[i]);
861 if (current_chunks_[i+1].forced_line_count_)
862 div.push_back (current_chunks_[i+1].forced_line_count_);
863 else if (system_specs_[sys].pscore_)
865 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
866 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
871 system_count_ += div.back ();
873 current_configurations_.clear ();
874 current_configurations_.push_back (div);
878 Page_breaking::current_configuration_count () const
880 return current_configurations_.size ();
884 Page_breaking::cache_line_details (vsize configuration_index)
886 if (cached_configuration_index_ != configuration_index)
888 cached_configuration_index_ = configuration_index;
890 Line_division &div = current_configurations_[configuration_index];
891 uncompressed_line_details_.clear ();
892 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
894 vsize sys = next_system (current_chunks_[i]);
895 if (system_specs_[sys].pscore_)
899 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
901 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
902 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
906 assert (div[i] == 0);
907 uncompressed_line_details_.push_back (system_specs_[sys].prob_
908 ? Line_details (system_specs_[sys].prob_, book_->paper_)
912 cached_line_details_ = compress_lines (uncompressed_line_details_);
913 compute_line_heights ();
918 Page_breaking::clear_line_details_cache ()
920 cached_configuration_index_ = VPOS;
921 cached_line_details_.clear ();
922 uncompressed_line_details_.clear ();
926 Page_breaking::line_divisions_rec (vsize system_count,
927 Line_division const &min_sys,
928 Line_division const &max_sys,
929 Line_division *cur_division)
931 vsize my_index = cur_division->size ();
935 for (vsize i = my_index + 1; i < min_sys.size (); i++)
937 others_min += min_sys[i];
938 others_max += max_sys[i];
940 others_max = min (others_max, (int) system_count);
941 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
942 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
944 if (real_min > real_max || real_min < 0)
946 /* this should never happen within a recursive call. If it happens
947 at all, it means that we were called with an unsolvable problem
948 and we should return an empty result */
949 assert (my_index == 0);
953 for (int i = real_min; i <= real_max; i++)
955 cur_division->push_back (i);
956 if (my_index == min_sys.size () - 1)
957 current_configurations_.push_back (*cur_division);
959 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
960 cur_division->pop_back ();
965 Page_breaking::compute_line_heights ()
967 Real prev_hanging = 0;
968 Real prev_hanging_begin = 0;
969 Real prev_hanging_rest = 0;
971 // refpoint_hanging is the y coordinate of the origin of this system.
972 // It may not be the same as refpoint_extent[UP], which is the
973 // refpoint of the first spaceable staff in this system.
974 Real prev_refpoint_hanging = 0;
975 for (vsize i = 0; i < cached_line_details_.size (); i++)
977 Line_details& cur = cached_line_details_[i];
978 Line_shape shape = cur.shape_;
979 Real a = shape.begin_[UP];
980 Real b = shape.rest_[UP];
981 bool title = cur.title_;
982 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
987 Line_details const& prev = cached_line_details_[i-1];
988 if (!cur.tight_spacing_)
990 ? prev.title_padding_
992 Real min_dist = title
993 ? prev.title_min_distance_
994 : prev.min_distance_;
995 refpoint_hanging = max (refpoint_hanging + padding,
996 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
997 + cur.refpoint_extent_[UP] + min_dist);
1000 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1001 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1002 Real hanging = max (hanging_begin, hanging_rest);
1003 cur.tallness_ = hanging - prev_hanging;
1004 prev_hanging = hanging;
1005 prev_hanging_begin = hanging_begin;
1006 prev_hanging_rest = hanging_rest;
1007 prev_refpoint_hanging = refpoint_hanging;
1012 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1015 vsize page_starter = 0;
1016 Real cur_rod_height = 0;
1017 Real cur_spring_height = 0;
1018 Real cur_page_height = page_height (first_page_num, false);
1021 cache_line_details (configuration);
1023 if (cached_line_details_.size ())
1024 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1026 for (vsize i = 0; i < cached_line_details_.size (); i++)
1028 Line_details const &cur = cached_line_details_[i];
1029 Line_details const *const prev = (i > 0) ? &cached_line_details_[i-1] : 0;
1031 if (cur_rod_height > 0)
1032 ext_len = cur.tallness_;
1034 ext_len = cur.full_height();
1036 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1037 Real next_rod_height = cur_rod_height + ext_len;
1038 Real next_spring_height = cur_spring_height + spring_len;
1039 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1040 + min_whitespace_at_bottom_of_page (cur);
1041 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1043 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1044 || too_many_lines (next_line_count)
1045 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1047 line_count = cur.compressed_nontitle_lines_count_;
1048 cur_rod_height = cur.full_height();
1049 cur_spring_height = 0;
1052 cur_page_height = page_height (first_page_num + ret, false);
1053 cur_page_height -= min_whitespace_at_top_of_page (cur);
1059 cur_rod_height = next_rod_height;
1060 cur_spring_height = next_spring_height;
1061 line_count = next_line_count;
1065 /* there are two potential problems with the last page (because we didn't know
1066 it was the last page until after we managed to fit all the systems to it):
1067 - we are ragged-last but the last page has a compressed spring
1068 - the value returned by page_height (num, true) is smaller than the
1069 value returned by page_height (num, false) and it causes the page not to
1072 In either case, we just need to add one more page. This is because the last
1073 line will always fit on the extra page and by adding one more page to the
1074 end, the previous page is no longer the last page, so our previous
1075 calculations that treated it as a non-last page were ok.
1080 cur_page_height = page_height (first_page_num + ret - 1, true);
1081 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1082 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1084 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1085 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1086 && cur_height > cur_page_height
1087 /* don't increase the page count if the last page had only one system */
1088 && cur_rod_height > cached_line_details_.back ().full_height ())
1090 assert (ret <= cached_line_details_.size ());
1096 // If systems_per_page_ is positive, we don't really try to space on N pages;
1097 // we just put the requested number of systems on each page and penalize
1098 // if the result doesn't have N pages.
1100 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1102 Page_spacing_result ret;
1104 if (systems_per_page_ > 0)
1106 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1107 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1111 cache_line_details (configuration);
1112 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1113 && n <= cached_line_details_.size ());
1116 programming_error ("number of pages is out of bounds");
1118 if (n == 1 && valid_n)
1119 ret = space_systems_on_1_page (cached_line_details_,
1120 page_height (first_page_num, is_last ()),
1121 ragged () || (is_last () && ragged_last ()));
1122 else if (n == 2 && valid_n)
1123 ret = space_systems_on_2_pages (configuration, first_page_num);
1126 Page_spacer ps (cached_line_details_, first_page_num, this);
1130 return finalize_spacing_result (configuration, ret);
1134 Page_breaking::blank_page_penalty () const
1139 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1140 else if (ends_score ())
1141 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1143 penalty_sym = ly_symbol2scm ("blank-page-force");
1145 Break_position const &pos = breaks_[current_end_breakpoint_];
1146 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1147 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1149 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1152 // If systems_per_page_ is positive, we don't really try to space on N
1153 // or N+1 pages; see the comment to space_systems_on_n_pages.
1155 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1156 Real penalty_for_fewer_pages)
1158 Page_spacing_result n_res;
1159 Page_spacing_result m_res;
1161 if (systems_per_page_ > 0)
1163 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1164 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
1168 cache_line_details (configuration);
1169 vsize min_p_count = min_page_count (configuration, first_page_num);
1170 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1173 programming_error ("both page counts are out of bounds");
1175 if (n == 1 && valid_n)
1177 bool rag = ragged () || (is_last () && ragged_last ());
1178 Real height = page_height (first_page_num, is_last ());
1180 if (1 >= min_p_count)
1181 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1182 if (1 < cached_line_details_.size ())
1183 m_res = space_systems_on_2_pages (configuration, first_page_num);
1187 Page_spacer ps (cached_line_details_, first_page_num, this);
1189 if (n >= min_p_count || !valid_n)
1190 n_res = ps.solve (n);
1191 if (n < cached_line_details_.size () || !valid_n)
1192 m_res = ps.solve (n+1);
1195 m_res = finalize_spacing_result (configuration, m_res);
1196 n_res = finalize_spacing_result (configuration, n_res);
1198 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1199 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1201 if (n_res.force_.size ())
1202 n_res.force_.back () += penalty_for_fewer_pages;
1204 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1208 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1210 if (systems_per_page_ > 0)
1211 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1213 cache_line_details (configuration);
1214 Page_spacer ps (cached_line_details_, first_page_num, this);
1216 return finalize_spacing_result (configuration, ps.solve ());
1220 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1221 vsize first_page_num)
1223 Page_spacing_result res;
1224 Page_spacing space (page_height (first_page_num, false), this);
1227 vsize page_first_line = 0;
1229 cache_line_details (configuration);
1230 while (line < cached_line_details_.size ())
1234 space.resize (page_height (first_page_num + page, false));
1236 int system_count_on_this_page = 0;
1237 while (system_count_on_this_page < systems_per_page_
1238 && line < cached_line_details_.size ())
1240 Line_details const &cur_line = cached_line_details_[line];
1241 space.append_system (cur_line);
1242 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1245 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1249 res.systems_per_page_.push_back (line - page_first_line);
1251 res.force_.push_back (space.force_);
1252 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1253 if (system_count_on_this_page != systems_per_page_)
1255 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1256 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1257 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1260 page_first_line = line;
1263 /* Recalculate forces for the last page because we know now that is
1264 really the last page. */
1265 space.resize (page_height (first_page_num + page, true));
1266 res.force_.back () = space.force_;
1267 return finalize_spacing_result (configuration, res);
1271 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1273 // TODO: add support for min/max-systems-per-page.
1274 Page_spacing_result res;
1276 vsize page_first_line = 0;
1277 Page_spacing space (page_height (first_page_num, false), this);
1279 cache_line_details (configuration);
1280 for (vsize line = 0; line < cached_line_details_.size (); line++)
1282 Real prev_force = space.force_;
1283 space.append_system (cached_line_details_[line]);
1284 if ((line > page_first_line)
1285 && (isinf (space.force_)
1287 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1289 res.systems_per_page_.push_back (line - page_first_line);
1290 res.force_.push_back (prev_force);
1291 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1293 space.resize (page_height (first_page_num + page, false));
1295 space.append_system (cached_line_details_[line]);
1296 page_first_line = line;
1299 if (line == cached_line_details_.size () - 1)
1301 /* This is the last line */
1302 /* When the last page height was computed, we did not know yet that it
1303 * was the last one. If the systems put on it don't fit anymore, the last
1304 * system is moved to a new page */
1305 space.resize (page_height (first_page_num + page, true));
1306 if ((line > page_first_line) && (isinf (space.force_)))
1308 res.systems_per_page_.push_back (line - page_first_line);
1309 res.force_.push_back (prev_force);
1310 /* the last page containing the last line */
1311 space.resize (page_height (first_page_num + page + 1, true));
1313 space.append_system (cached_line_details_[line]);
1314 res.systems_per_page_.push_back (1);
1315 res.force_.push_back (space.force_);
1316 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1317 res.penalty_ += cached_line_details_[line].page_penalty_;
1321 res.systems_per_page_.push_back (line + 1 - page_first_line);
1322 res.force_.push_back (space.force_);
1323 res.penalty_ += cached_line_details_[line].page_penalty_;
1327 return finalize_spacing_result (configuration, res);
1330 /* Calculate demerits and fix res.systems_per_page_ so that
1331 it refers to the original line numbers, not the ones given by compress_lines (). */
1333 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1335 if (res.force_.empty ())
1338 cache_line_details (configuration);
1339 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1341 Real line_force = 0;
1342 Real line_penalty = 0;
1343 Real page_demerits = res.penalty_;
1344 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1346 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1348 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1349 line_penalty += uncompressed_line_details_[i].break_penalty_;
1352 for (vsize i = 0; i < res.force_.size (); i++)
1354 Real f = res.force_[i];
1356 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1359 /* for a while we tried averaging page and line forces across pages instead
1360 of summing them, but it caused a problem: if there is a single page
1361 with a very bad page force (for example because of a forced page break),
1362 the page breaker will put in a _lot_ of pages so that the bad force
1363 becomes averaged out over many pages. */
1364 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1369 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1370 are by far the most common cases, we have special functions for them.
1372 space_systems_on_1_page has a different calling convention than most of the
1373 space_systems functions. This is because space_systems_on_1_page is (unlike
1374 the other space_systems functions) sometimes called on subsets of a full
1377 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1379 Page_spacing space (page_height, this);
1380 Page_spacing_result ret;
1383 for (vsize i = 0; i < lines.size (); i++)
1385 space.append_system (lines[i]);
1386 line_count += lines[i].compressed_nontitle_lines_count_;
1389 ret.systems_per_page_.push_back (lines.size ());
1390 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1391 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1392 ret.system_count_status_ |= line_count_status (line_count);
1394 /* don't do finalize_spacing_result () because we are only an internal function */
1399 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1401 Real page1_height = page_height (first_page_num, false);
1402 Real page2_height = page_height (first_page_num + 1, is_last ());
1403 bool ragged1 = ragged ();
1404 bool ragged2 = ragged () || (is_last () && ragged_last ());
1406 /* if there is a forced break, this reduces to 2 1-page problems */
1407 cache_line_details (configuration);
1408 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1409 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1411 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1412 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1413 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1414 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1416 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1417 p1.force_.push_back (p2.force_[0]);
1418 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1419 p1.system_count_status_ |= p2.system_count_status_;
1423 vector<Real> page1_force;
1424 vector<Real> page2_force;
1426 // page1_penalty and page2_penalty store the penalties based
1427 // on min-systems-per-page and max-systems-per-page.
1428 vector<Real> page1_penalty;
1429 vector<Real> page2_penalty;
1431 // page1_status and page2_status keep track of whether the min-systems-per-page
1432 // and max-systems-per-page constraints are satisfied.
1433 vector<int> page1_status;
1434 vector<int> page2_status;
1436 Page_spacing page1 (page1_height, this);
1437 Page_spacing page2 (page2_height, this);
1438 int page1_line_count = 0;
1439 int page2_line_count = 0;
1441 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1442 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1443 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1444 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1445 page1_status.resize (cached_line_details_.size () - 1, 0);
1446 page2_status.resize (cached_line_details_.size () - 1, 0);
1448 /* find the page 1 and page 2 forces for each page-breaking position */
1449 for (vsize i = 0; i < page1_force.size (); i++)
1451 page1.append_system (cached_line_details_[i]);
1452 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1453 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1454 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1456 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1457 page1_penalty[i] = line_count_penalty (page1_line_count);
1458 page1_status[i] = line_count_status (page1_line_count);
1461 page2_force[page2_force.size () - 1 - i] =
1462 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1464 page2_force[page2_force.size () - 1 - i] = page2.force_;
1465 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1466 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1469 /* find the position that minimises the sum of the page forces */
1470 vsize best_sys_count = 1;
1471 Real best_demerits = infinity_f;
1472 for (vsize i = 0; i < page1_force.size (); i++)
1474 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1476 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1477 // constraints. That is, we penalize harshly when they don't happen
1478 // but we don't completely reject.
1480 + page1_penalty[i] + page2_penalty[i]
1481 + cached_line_details_[i+1].page_penalty_
1482 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1483 if (dem < best_demerits)
1485 best_demerits = dem;
1486 best_sys_count = i+1;
1490 Page_spacing_result ret;
1491 ret.systems_per_page_.push_back (best_sys_count);
1492 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1493 ret.force_.push_back (page1_force[best_sys_count-1]);
1494 ret.force_.push_back (page2_force[best_sys_count-1]);
1495 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1496 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1497 + cached_line_details_.back ().page_penalty_
1498 + cached_line_details_.back ().turn_penalty_
1499 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1501 /* don't do finalize_spacing_result () because we are only an internal function */
1506 Page_breaking::all_lines_stretched (vsize configuration)
1508 cache_line_details (configuration);
1509 for (vsize i = 0; i < cached_line_details_.size (); i++)
1510 if (cached_line_details_[i].force_ < 0)
1516 Page_breaking::Line_division
1517 Page_breaking::current_configuration (vsize configuration_index) const
1519 return current_configurations_[configuration_index];
1523 Page_breaking::is_last () const
1525 return current_end_breakpoint_ == last_break_position ();
1529 Page_breaking::ends_score () const
1531 return breaks_[current_end_breakpoint_].score_ender_;
1535 Page_breaking::last_break_position () const
1537 return breaks_.size () - 1;
1540 // This gives the minimum distance between the top of the
1541 // printable area (ie. the bottom of the top-margin) and
1542 // the extent box of the topmost system.
1544 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1546 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1548 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1550 Real min_distance = -infinity_f;
1553 Page_layout_problem::read_spacing_spec (first_system_spacing,
1555 ly_symbol2scm ("minimum-distance"));
1556 Page_layout_problem::read_spacing_spec (first_system_spacing,
1558 ly_symbol2scm ("padding"));
1560 // FIXME: take into account the height of the header
1561 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1562 return max (0.0, max (padding, min_distance - translate));
1566 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1568 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1569 Real min_distance = -infinity_f;
1572 Page_layout_problem::read_spacing_spec (last_system_spacing,
1574 ly_symbol2scm ("minimum-distance"));
1575 Page_layout_problem::read_spacing_spec (last_system_spacing,
1577 ly_symbol2scm ("padding"));
1579 // FIXME: take into account the height of the footer
1580 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1581 return max (0.0, max (padding, min_distance + translate));
1585 Page_breaking::orphan_penalty () const
1587 return orphan_penalty_;