2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2011 Joe Neeman <joeneeman@gmail.com>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
21 This is a utility class for page-breaking algorithms. There are some complex
22 parts of this class, some of which are useful to understand if you intend
23 to write a page breaking algorithm (ie. a subclass of Page_breaking). Most
24 of these complexities were introduced in order to break the problem of
25 page-breaking into simpler subproblems and to hide some of the bookkeeping
26 complexities of page breaking from the page breaking algorithms.
29 There are several functions that actually distribute systems across pages
30 (for example, the space_systems_XXX and pack_systems_XXX functions). If
31 each of these functions had to handle \noPageBreak, it would be a mess.
32 Therefore, we handle \noPageBreak by "compressing" the list of systems
33 before doing any layout: we concatenate any two systems separated by a
34 \noPageBreak into a single system. The page-breaking functions can do their
35 magic without encountering a \noPageBreak; we then "uncompress" the systems
36 at the end. We almost always work with cached_line_details_, which are
40 The basic operation of a page breaking algorithm is to repeatedly request
41 some systems from the line-breaker and place those systems on some pages.
42 With each repetition, the page breaking algorithm asks the line-breaker for
43 some systems that it thinks will help it achieve a better layout. The
44 Page_breaking class provides functionality to facilitate this in the case
45 that the page breaking algorithm only cares about the number of systems.
47 Even if a page breaking algorithm only cares number of systems, there may
48 be many ways to satisfy its request. For example, in a piece with 2 scores
49 and a request for 10 systems, we could return 5 systems from each score or
50 4 from the first and 6 from the second. Even within a score, we might
51 want to try several different line breaking configurations with a fixed
52 system count; if there is a forced \pageBreak, for example, we might wish
53 to tweak the number of systems on both sides of the \pageBreak independently.
55 The Page_breaking class takes care of finding these configurations. It
56 divides the piece into "chunks" and sets up the line-breaker in such a way
57 that the number of systems in each chunk can be modified independently.
58 Chunks never cross score boundaries; each title and markup is its own chunk.
59 When a page breaking algorithm requests a number of systems, the Page_breaker
60 stores an array of potential configurations, which the page breaking
61 algorithm can iterate over using current_configuration(vsize).
64 A Line_division is simply a way of storing the exact way in which the
65 total number of systems is distributed among chunks. Note that a
66 Line_division may not (in fact, usually will not) describe all of the chunks
67 in the entire book. Rather, it will describe the subset of chunks that lie
68 between some fixed starting and ending point. This subset of chunks changes
69 whenever a page breaking algorithm asks to consider a different pair of
70 starting and ending breakpoints. In particular, a Line_division should be
71 discarded after a call to set_current_breakpoints, since that Line_division
72 refers to a subset of chunks which might be different from the current
73 subset of chunks under consideration.
75 HOW TO WRITE A PAGE BREAKING ALGORITHM
76 All page breakers supported by this class work more-or-less in the same way.
77 First, they request a particular number of systems by saying
78 set_current_breakpoints (0, last_break_position (), system_count)
79 (never mind what the first two arguments do, I'll get to them later).
80 Alternatively, you can do
81 set_to_ideal_line_configuration (0, last_break_position ()),
82 and the number of systems will be automatically chosen according to what
83 the line breaker wants.
85 If there are multiple scores, there will be many different ways to achieve
86 a certain number of lines. You can see how many alternatives are available
87 with current_configuration_count (). For every i from 0 to
88 current_configuration_count ()-1, you can see the line division of the
89 corresponding configuration with current_configuration (i), or you can try
90 out various page configurations with one of the space_systems_xxx or
91 pack_systems_xxx functions. The first argument to each of these functions
92 is the configuration index.
94 When you're done trying out configurations and you've picked the one
96 break_into_pieces (0, last_break_position (), line_division_that_you_want);
97 return make_pages (systems_per_page, systems ());
98 where systems_per_page is a vector of numbers telling how many systems are
99 on each page. You can get your systems_per_page vector by looking inside
100 the Page_spacing_results that are returned by space_systems_xxx or
103 A note on performance: set_current_breakpoints is EXPONENTIALLY SLOW unless
104 you constrain it by giving it a lower or an upper bound on the configurations
105 it looks for. Optimal_page_breaking, for example, works by trying
106 out a bunch of configurations, increasing the system count by one, trying
107 again and so on. Each time we increase the system count, we assume that the
108 best new configurations are going to be elementwise larger than the
109 best configuration for the previous system count (in other words, we're going
110 to get a new configuration just by adding an extra line to sone score
111 and leaving the rest the same). Therefore, we pass the best previous line
112 division as an lower bound to set_current_breakpoints.
114 Now you should be in a position to understand Optimal_page_breaking::solve.
115 Go ahead and read that before finding out, in the next paragraph,
116 what the first two arguments to set_current_breakpoints do.
119 Sometimes, it's useful to run this whole page-breaking machinery on a subset
120 of the book. To do this, you can mark certain "breaks" in the book (a poor
121 choice of name, perhaps, since a "break" here is different from a page break)
122 and you can run page breaking between any two breaks. You mark your breaks
123 by providing a Break_predicate (and, if you want, a Prob_break_predicate)
124 to Page_breaking's constructor. You then choose a subset of your book
125 by passing the starting and ending breaks to set_current_breakpoints. You
126 can see an example of this in Page_turn_page_breaking, where there is a break
127 everywhere that a page turn is allowed.
130 #include "page-breaking.hh"
132 #include "international.hh"
134 #include "line-interface.hh"
135 #include "output-def.hh"
136 #include "page-layout-problem.hh"
137 #include "page-spacing.hh"
138 #include "paper-book.hh"
139 #include "paper-score.hh"
140 #include "paper-system.hh"
141 #include "text-interface.hh"
145 /* for each forbidden page break, merge the systems around it into one
147 static vector<Line_details>
148 compress_lines (const vector<Line_details> &orig)
150 vector<Line_details> ret;
152 for (vsize i = 0; i < orig.size (); i++)
154 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
156 Line_details const &old = ret.back ();
157 Line_details compressed = orig[i];
159 We must account for the padding between the lines that we are compressing.
160 The padding values come from "old," which is the upper system here. Note
161 the meaning of tight-spacing: if a system has tight-spacing, then the padding
162 _before_ it is ignored.
165 if (!orig[i].tight_spacing_)
166 padding = orig[i].title_ ? old.title_padding_ : old.padding_;
168 // FIXME: double check these. Doesn't foo.piggyback (bar) mean
169 // that foo goes on top?
170 // TODO: break out a Line_details::piggyback from here?
171 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
172 compressed.refpoint_extent_[UP] = old.refpoint_extent_[UP];
173 compressed.refpoint_extent_[DOWN] += compressed.shape_.rest_[UP] - old.shape_.rest_[UP];
174 compressed.space_ += old.space_;
175 compressed.inverse_hooke_ += old.inverse_hooke_;
177 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
178 compressed.compressed_nontitle_lines_count_ =
179 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
181 // compressed.title_ is true if and only if the first of its
182 // compressed lines was a title.
183 compressed.title_ = old.title_;
185 // adds footnotes of one line to the footnotes of another
186 compressed.footnotes_.insert (compressed.footnotes_.begin (),
187 old.footnotes_.begin (), old.footnotes_.end ());
189 ret.back () = compressed;
193 ret.push_back (orig[i]);
194 ret.back ().force_ = 0;
200 /* translate the number of systems-per-page into something meaningful for
201 the uncompressed lines.
204 uncompress_solution (vector<vsize> const &systems_per_page,
205 vector<Line_details> const &compressed)
210 for (vsize i = 0; i < systems_per_page.size (); i++)
212 int compressed_count = 0;
213 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
214 compressed_count += compressed[j].compressed_lines_count_ - 1;
216 ret.push_back (systems_per_page[i] + compressed_count);
217 start_sys += systems_per_page[i];
222 /* for Page_breaking, the start index (when we are dealing with the stuff
223 between a pair of breakpoints) refers to the break_ index of the end of
224 the previous page. So the system index of the start of the current page
225 could either be the same as the end of the previous page or one more than
228 /* Turn a break index into the sys index that starts the next page */
230 Page_breaking::next_system (Break_position const &break_pos) const
232 vsize sys = break_pos.system_spec_index_;
234 if (sys == VPOS) /* beginning of the book */
236 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
237 return sys; /* the score overflows the previous page */
238 return sys + 1; /* this page starts with a new System_spec */
241 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
245 paper_height_ = robust_scm2double (pb->paper_->c_variable ("paper-height"), 1.0);
246 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
247 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
248 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
249 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
250 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
251 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
253 Stencil *footnote_separator = Page_layout_problem::get_footnote_separator_stencil (pb->paper_);
255 if (footnote_separator)
257 Interval separator_extent = footnote_separator->extent (Y_AXIS);
258 Real separator_span = separator_extent.length ();
260 footnote_separator_stencil_height_ = separator_span;
263 footnote_separator_stencil_height_ = 0.0;
265 footnote_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
266 footnote_footer_padding_ = robust_scm2double (pb->paper_->c_variable ("footnote-footer-padding"), 0.0);
268 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
270 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
271 min_systems_per_page_ = max_systems_per_page_ = 0;
273 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
275 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
276 min_systems_per_page_ = max_systems_per_page_ = 0;
279 create_system_list ();
280 find_chunks_and_breaks (is_break, prob_break);
283 Page_breaking::~Page_breaking ()
288 Page_breaking::ragged () const
294 Page_breaking::ragged_last () const
300 Page_breaking::systems_per_page () const
302 return systems_per_page_;
306 Page_breaking::max_systems_per_page () const
308 if (systems_per_page_)
309 return systems_per_page_;
310 return max_systems_per_page_;
314 Page_breaking::min_systems_per_page () const
316 if (systems_per_page_)
317 return systems_per_page_;
318 return min_systems_per_page_;
322 Page_breaking::system_count () const
324 return system_count_;
328 Page_breaking::footnote_separator_stencil_height () const
330 return footnote_separator_stencil_height_;
334 Page_breaking::footnote_padding () const
336 return footnote_padding_;
340 Page_breaking::footnote_footer_padding () const
342 return footnote_footer_padding_;
346 Page_breaking::too_many_lines (int line_count) const
348 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
352 Page_breaking::too_few_lines (int line_count) const
354 return line_count < min_systems_per_page ();
358 Page_breaking::line_count_penalty (int line_count) const
360 if (too_many_lines (line_count))
361 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
362 if (too_few_lines (line_count))
363 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
369 Page_breaking::line_count_status (int line_count) const
371 if (too_many_lines (line_count))
372 return SYSTEM_COUNT_TOO_MANY;
373 if (too_few_lines (line_count))
374 return SYSTEM_COUNT_TOO_FEW;
376 return SYSTEM_COUNT_OK;
379 /* translate indices into breaks_ into start-end parameters for the line breaker */
381 Page_breaking::line_breaker_args (vsize sys,
382 Break_position const &start,
383 Break_position const &end,
384 vsize *line_breaker_start,
385 vsize *line_breaker_end)
387 assert (system_specs_[sys].pscore_);
388 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
390 if (start.system_spec_index_ == sys)
391 *line_breaker_start = start.score_break_;
393 *line_breaker_start = 0;
395 if (end.system_spec_index_ == sys)
396 *line_breaker_end = end.score_break_;
398 *line_breaker_end = VPOS;
402 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
403 Line_division const &div)
405 vector<Break_position> chunks = chunk_list (start_break, end_break);
406 bool ignore_div = false;
407 if (chunks.size () != div.size () + 1)
409 programming_error ("did not find a valid page breaking configuration");
413 for (vsize i = 0; i + 1 < chunks.size (); i++)
415 vsize sys = next_system (chunks[i]);
416 if (system_specs_[sys].pscore_)
420 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
422 vector<Column_x_positions> pos = ignore_div
423 ? line_breaking_[sys].best_solution (start, end)
424 : line_breaking_[sys].solve (start, end, div[i]);
425 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
431 Page_breaking::systems ()
434 for (vsize sys = 0; sys < system_specs_.size (); sys++)
436 if (system_specs_[sys].pscore_)
438 system_specs_[sys].pscore_->root_system ()
439 ->do_break_substitution_and_fixup_refpoints ();
440 SCM lines = system_specs_[sys].pscore_->root_system ()
441 ->get_broken_system_grobs ();
442 ret = scm_cons (lines, ret);
444 else if (Prob *pb = system_specs_[sys].prob_)
446 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
450 return scm_append (scm_reverse (ret));
454 Page_breaking::make_page (int page_num, bool last) const
456 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
457 SCM mod = scm_c_resolve_module ("scm page");
458 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
460 make_page_scm = scm_variable_ref (make_page_scm);
462 return scm_apply_0 (make_page_scm,
463 scm_list_n (book_->self_scm (),
464 ly_symbol2scm ("page-number"), scm_from_int (page_num),
465 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
466 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
470 // Returns the total height of the paper, including margins and
471 // space for the header/footer. This is an upper bound on
472 // page_height, and it doesn't depend on the current page.
474 Page_breaking::paper_height () const
476 return paper_height_;
480 Page_breaking::page_height (int page_num, bool last) const
482 // The caches allow us to store the page heights for any
483 // non-negative page numbers. We use a negative value in the
484 // cache to signal that that position has not yet been initialized.
485 // This means that we won't cache properly if page_num is negative or
486 // if calc_height returns a negative number. But that's likely to
487 // be rare, so it shouldn't affect performance.
488 vector<Real>& cache = last ? last_page_height_cache_ : page_height_cache_;
489 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
490 return cache[page_num];
493 SCM mod = scm_c_resolve_module ("scm page");
494 SCM page = make_page (page_num, last);
495 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
496 calc_height = scm_variable_ref (calc_height);
498 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
499 Real height = scm_to_double (height_scm);
503 if ((int) cache.size () <= page_num)
504 cache.resize (page_num + 1, -1);
505 cache[page_num] = height;
512 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
514 Break_position const &pos = breaks_[breakpoint];
516 if (pos.system_spec_index_ == VPOS)
518 if (system_specs_[pos.system_spec_index_].pscore_)
519 return pos.col_->get_property (str);
520 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
524 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
526 SCM dummy_page = make_page (page_num, last);
527 Page_layout_problem layout (book_, dummy_page, systems);
528 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
532 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
534 // Create a stencil for each system.
535 SCM paper_systems = SCM_EOL;
536 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
538 SCM paper_system = scm_car (s);
539 if (Grob *g = unsmob_grob (scm_car (s)))
541 System *sys = dynamic_cast<System*> (g);
542 paper_system = sys->get_paper_system ();
545 paper_systems = scm_cons (paper_system, paper_systems);
548 // Create the page and draw it.
549 SCM page = make_page (page_num, last);
550 SCM page_module = scm_c_resolve_module ("scm page");
551 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
552 page_stencil = scm_variable_ref (page_stencil);
554 Prob *p = unsmob_prob (page);
555 p->set_property ("lines", paper_systems);
556 p->set_property ("configuration", configuration);
558 Stencil *foot = unsmob_stencil (p->get_property ("foot-stencil"));
559 SCM footnotes = Page_layout_problem::get_footnotes_from_lines (systems, footnote_padding ());
560 Page_layout_problem::add_footnotes_to_footer (footnotes, foot, unsmob_paper_book (p->get_property ("paper-book")));
562 p->set_property ("foot-stencil", foot->smobbed_copy ());
563 scm_apply_1 (page_stencil, page, SCM_EOL);
569 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
571 if (scm_is_null (systems))
574 int first_page_number
575 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
577 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
578 if (label_page_table == SCM_UNDEFINED)
579 label_page_table = SCM_EOL;
581 // Build a list of (systems . configuration) pairs. Note that we lay out
582 // the staves and find the configurations before drawing anything. Some
583 // grobs (like tuplet brackets) look at their neighbours while drawing
584 // themselves. If this happens before the neighbouring staves have
585 // been laid out, bad side-effects could happen (in particular,
586 // Align_interface::align_to_ideal_distances might be called).
587 SCM systems_and_configs = SCM_EOL;
589 for (vsize i = 0; i < lines_per_page.size (); i++)
591 int page_num = i + first_page_number;
592 bool bookpart_last_page = (i == lines_per_page.size () - 1);
593 bool rag = ragged () || (bookpart_last_page && ragged_last ());
594 SCM line_count = scm_from_int (lines_per_page[i]);
595 SCM lines = scm_list_head (systems, line_count);
596 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
598 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
599 systems = scm_list_tail (systems, line_count);
602 // Now it's safe to make the pages.
603 int page_num = first_page_number + lines_per_page.size () - 1;
604 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
606 SCM lines = scm_caar (s);
607 SCM config = scm_cdar (s);
609 bool bookpart_last_page = (s == systems_and_configs);
610 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
613 SCM page_num_scm = scm_from_int (page_num);
614 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
616 SCM labels = SCM_EOL;
617 if (Grob * line = unsmob_grob (scm_car (l)))
619 System *system = dynamic_cast<System*> (line);
620 labels = system->get_property ("labels");
622 else if (Prob *prob = unsmob_prob (scm_car (l)))
623 labels = prob->get_property ("labels");
625 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
626 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
630 ret = scm_cons (page, ret);
634 // By reversing the table, we ensure that duplicated labels (eg. those
635 // straddling a page turn) will appear in the table with their last
637 label_page_table = scm_reverse_x (label_page_table, SCM_EOL);
638 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
642 /* The page-turn-page-breaker needs to have a line-breaker between any two
643 columns with non-NULL page-turn-permission.
645 The optimal-breaker needs to have a line-breaker between any two columns
646 with page-break-permission = 'force.
648 By using a grob predicate, we can accommodate both of these uses.
651 Page_breaking::create_system_list ()
653 SCM specs = book_->get_system_specs ();
654 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
656 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
658 system_specs_.push_back (System_spec (ps));
662 Prob *pb = unsmob_prob (scm_car (s));
666 system_specs_.push_back (System_spec (pb));
669 if (!system_specs_.size ())
670 system_specs_.push_back (System_spec ());
674 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
676 SCM force_sym = ly_symbol2scm ("force");
678 chunks_.push_back (Break_position ());
679 breaks_.push_back (Break_position ());
681 for (vsize i = 0; i < system_specs_.size (); i++)
683 if (system_specs_[i].pscore_)
685 vector<Grob*> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
686 vector<Grob*> forced_line_break_cols;
688 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
689 if (scm_is_number (system_count))
691 // With system-count given, the line configuration for
692 // this score is fixed. We need to ensure that chunk
693 // boundaries only occur at line breaks.
694 Constrained_breaking breaking (system_specs_[i].pscore_);
695 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
697 for (vsize j = 0; j < details.size (); j++)
698 forced_line_break_cols.push_back (details[j].last_column_);
701 int last_forced_line_break_idx = 0;
702 vsize forced_line_break_idx = 0;
703 vector<vsize> line_breaker_columns;
704 line_breaker_columns.push_back (0);
706 for (vsize j = 1; j < cols.size (); j++)
708 if (forced_line_break_cols.size ())
710 if (forced_line_break_idx >= forced_line_break_cols.size ()
711 || forced_line_break_cols[forced_line_break_idx] != cols[j])
714 forced_line_break_idx++;
717 bool last = (j == cols.size () - 1);
718 bool break_point = is_break && is_break (cols[j]);
719 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
720 Break_position cur_pos = Break_position (i,
721 line_breaker_columns.size (),
725 // NOTE: even in the breaks_ list, forced_line_count_
726 // refers to the number of lines between a
727 // Break_position and the start of that /chunk/. This
728 // is needed for system_count_bounds to work correctly,
729 // since it mixes Break_positions from breaks_ and
731 if (scm_is_number (system_count))
732 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
734 if (break_point || (i == system_specs_.size () - 1 && last))
735 breaks_.push_back (cur_pos);
736 if (chunk_end || last)
738 chunks_.push_back (cur_pos);
739 last_forced_line_break_idx = forced_line_break_idx;
742 if ((break_point || chunk_end) && !last)
743 line_breaker_columns.push_back (j);
745 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
747 else if (system_specs_[i].prob_)
749 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
750 if (break_point || i == system_specs_.size () - 1)
751 breaks_.push_back (Break_position (i));
753 chunks_.push_back (Break_position (i));
755 /* FIXME: shouldn't we push a Null_breaker or similar dummy
757 line_breaking_.push_back (Constrained_breaking (NULL));
762 vector<Break_position>
763 Page_breaking::chunk_list (vsize start_index, vsize end_index)
765 Break_position start = breaks_[start_index];
766 Break_position end = breaks_[end_index];
769 for (; i < chunks_.size () && chunks_[i] <= start; i++)
772 vector<Break_position> ret;
773 ret.push_back (start);
774 for (; i < chunks_.size () && chunks_[i] < end; i++)
775 ret.push_back (chunks_[i]);
780 // Returns the minimum number of _non-title_ lines.
782 Page_breaking::min_system_count (vsize start, vsize end)
784 vector<Break_position> chunks = chunk_list (start, end);
785 Line_division div = system_count_bounds (chunks, true);
788 for (vsize i = 0; i < div.size (); i++)
793 // Returns the maximum number of _non-title_ lines.
795 Page_breaking::max_system_count (vsize start, vsize end)
797 vector<Break_position> chunks = chunk_list (start, end);
798 Line_division div = system_count_bounds (chunks, false);
801 for (vsize i = 0; i < div.size (); i++)
806 // The numbers returned by this function represent either
807 // the maximum or minimum number of _non-title_ lines
809 Page_breaking::Line_division
810 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
813 assert (chunks.size () >= 2);
816 ret.resize (chunks.size () - 1, 0);
818 for (vsize i = 0; i + 1 < chunks.size (); i++)
820 vsize sys = next_system (chunks[i]);
822 if (chunks[i+1].forced_line_count_)
823 ret[i] = chunks[i+1].forced_line_count_;
824 else if (system_specs_[sys].pscore_)
828 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
830 ? line_breaking_[sys].min_system_count (start, end)
831 : line_breaking_[sys].max_system_count (start, end);
839 Page_breaking::set_current_breakpoints (vsize start,
842 Line_division lower_bound,
843 Line_division upper_bound)
845 system_count_ = system_count;
846 current_chunks_ = chunk_list (start, end);
847 current_start_breakpoint_ = start;
848 current_end_breakpoint_ = end;
849 clear_line_details_cache ();
851 if (!lower_bound.size ())
852 lower_bound = system_count_bounds (current_chunks_, true);
853 if (!upper_bound.size ())
854 upper_bound = system_count_bounds (current_chunks_, false);
856 assert (lower_bound.size () == current_chunks_.size () - 1);
857 assert (upper_bound.size () == current_chunks_.size () - 1);
859 Line_division work_in_progress;
860 current_configurations_.clear ();
861 line_divisions_rec (system_count,
866 /* we only consider a constant number of configurations. Otherwise,
867 this becomes slow when there are many small scores. The constant
868 5 is somewhat arbitrary. */
869 if (current_configurations_.size () > 5)
871 vector<pair<Real,vsize> > dems_and_indices;
873 for (vsize i = 0; i < current_configurations_.size (); i++)
875 cache_line_details (i);
877 for (vsize j = 0; j < cached_line_details_.size (); j++)
878 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
879 + cached_line_details_[j].break_penalty_;
881 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
883 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
885 vector<Line_division> best_5_configurations;
886 for (vsize i = 0; i < 5; i++)
887 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
889 clear_line_details_cache ();
890 current_configurations_ = best_5_configurations;
895 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
897 current_chunks_ = chunk_list (start, end);
898 current_start_breakpoint_ = start;
899 current_end_breakpoint_ = end;
900 clear_line_details_cache ();
904 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
906 vsize sys = next_system (current_chunks_[i]);
908 if (current_chunks_[i+1].forced_line_count_)
909 div.push_back (current_chunks_[i+1].forced_line_count_);
910 else if (system_specs_[sys].pscore_)
912 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
913 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
918 system_count_ += div.back ();
920 current_configurations_.clear ();
921 current_configurations_.push_back (div);
925 Page_breaking::current_configuration_count () const
927 return current_configurations_.size ();
931 Page_breaking::cache_line_details (vsize configuration_index)
933 if (cached_configuration_index_ != configuration_index)
935 cached_configuration_index_ = configuration_index;
937 Line_division &div = current_configurations_[configuration_index];
938 uncompressed_line_details_.clear ();
939 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
941 vsize sys = next_system (current_chunks_[i]);
942 if (system_specs_[sys].pscore_)
946 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
948 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
949 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
953 assert (div[i] == 0);
954 uncompressed_line_details_.push_back (system_specs_[sys].prob_
955 ? Line_details (system_specs_[sys].prob_, book_->paper_)
959 cached_line_details_ = compress_lines (uncompressed_line_details_);
960 compute_line_heights ();
965 Page_breaking::clear_line_details_cache ()
967 cached_configuration_index_ = VPOS;
968 cached_line_details_.clear ();
969 uncompressed_line_details_.clear ();
973 Page_breaking::line_divisions_rec (vsize system_count,
974 Line_division const &min_sys,
975 Line_division const &max_sys,
976 Line_division *cur_division)
978 vsize my_index = cur_division->size ();
982 for (vsize i = my_index + 1; i < min_sys.size (); i++)
984 others_min += min_sys[i];
985 others_max += max_sys[i];
987 others_max = min (others_max, (int) system_count);
988 int real_min = max ((int) min_sys[my_index], (int) system_count - others_max);
989 int real_max = min ((int) max_sys[my_index], (int) system_count - others_min);
991 if (real_min > real_max || real_min < 0)
993 /* this should never happen within a recursive call. If it happens
994 at all, it means that we were called with an unsolvable problem
995 and we should return an empty result */
996 assert (my_index == 0);
1000 for (int i = real_min; i <= real_max; i++)
1002 cur_division->push_back (i);
1003 if (my_index == min_sys.size () - 1)
1004 current_configurations_.push_back (*cur_division);
1006 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
1007 cur_division->pop_back ();
1012 Page_breaking::compute_line_heights ()
1014 Real prev_hanging = 0;
1015 Real prev_hanging_begin = 0;
1016 Real prev_hanging_rest = 0;
1018 // refpoint_hanging is the y coordinate of the origin of this system.
1019 // It may not be the same as refpoint_extent[UP], which is the
1020 // refpoint of the first spaceable staff in this system.
1021 Real prev_refpoint_hanging = 0;
1022 for (vsize i = 0; i < cached_line_details_.size (); i++)
1024 Line_details& cur = cached_line_details_[i];
1025 Line_shape shape = cur.shape_;
1026 Real a = shape.begin_[UP];
1027 Real b = shape.rest_[UP];
1028 bool title = cur.title_;
1029 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
1034 Line_details const& prev = cached_line_details_[i-1];
1035 if (!cur.tight_spacing_)
1037 ? prev.title_padding_
1039 Real min_dist = title
1040 ? prev.title_min_distance_
1041 : prev.min_distance_;
1042 refpoint_hanging = max (refpoint_hanging + padding,
1043 prev_refpoint_hanging - prev.refpoint_extent_[DOWN]
1044 + cur.refpoint_extent_[UP] + min_dist);
1047 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
1048 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
1049 Real hanging = max (hanging_begin, hanging_rest);
1050 cur.tallness_ = hanging - prev_hanging;
1051 prev_hanging = hanging;
1052 prev_hanging_begin = hanging_begin;
1053 prev_hanging_rest = hanging_rest;
1054 prev_refpoint_hanging = refpoint_hanging;
1059 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
1062 vsize page_starter = 0;
1063 Real cur_rod_height = 0;
1064 Real cur_spring_height = 0;
1065 Real cur_page_height = page_height (first_page_num, false);
1068 cache_line_details (configuration);
1070 if (cached_line_details_.size ())
1071 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
1073 for (vsize i = 0; i < cached_line_details_.size (); i++)
1075 Line_details const &cur = cached_line_details_[i];
1076 Line_details const *const prev = (i > 0) ? &cached_line_details_[i-1] : 0;
1078 if (cur_rod_height > 0)
1079 ext_len = cur.tallness_;
1081 ext_len = cur.full_height();
1083 Real spring_len = (i > 0) ? prev->spring_length (cur) : 0;
1084 Real next_rod_height = cur_rod_height + ext_len;
1085 Real next_spring_height = cur_spring_height + spring_len;
1086 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
1087 + min_whitespace_at_bottom_of_page (cur);
1088 int next_line_count = line_count + cur.compressed_nontitle_lines_count_;
1090 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
1091 || too_many_lines (next_line_count)
1092 || (prev && prev->page_permission_ == ly_symbol2scm ("force")))
1094 line_count = cur.compressed_nontitle_lines_count_;
1095 cur_rod_height = cur.full_height();
1096 cur_spring_height = 0;
1099 cur_page_height = page_height (first_page_num + ret, false);
1100 cur_page_height -= min_whitespace_at_top_of_page (cur);
1106 cur_rod_height = next_rod_height;
1107 cur_spring_height = next_spring_height;
1108 line_count = next_line_count;
1112 /* there are two potential problems with the last page (because we didn't know
1113 it was the last page until after we managed to fit all the systems to it):
1114 - we are ragged-last but the last page has a compressed spring
1115 - the value returned by page_height (num, true) is smaller than the
1116 value returned by page_height (num, false) and it causes the page not to
1119 In either case, we just need to add one more page. This is because the last
1120 line will always fit on the extra page and by adding one more page to the
1121 end, the previous page is no longer the last page, so our previous
1122 calculations that treated it as a non-last page were ok.
1127 cur_page_height = page_height (first_page_num + ret - 1, true);
1128 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
1129 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
1131 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
1132 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
1133 && cur_height > cur_page_height
1134 /* don't increase the page count if the last page had only one system */
1135 && cur_rod_height > cached_line_details_.back ().full_height ())
1137 assert (ret <= cached_line_details_.size ());
1143 // If systems_per_page_ is positive, we don't really try to space on N pages;
1144 // we just put the requested number of systems on each page and penalize
1145 // if the result doesn't have N pages.
1147 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1149 Page_spacing_result ret;
1151 if (systems_per_page_ > 0)
1153 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1154 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1158 cache_line_details (configuration);
1159 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1160 && n <= cached_line_details_.size ());
1163 programming_error ("number of pages is out of bounds");
1165 if (n == 1 && valid_n)
1166 ret = space_systems_on_1_page (cached_line_details_,
1167 page_height (first_page_num, is_last ()),
1168 ragged () || (is_last () && ragged_last ()));
1169 else if (n == 2 && valid_n)
1170 ret = space_systems_on_2_pages (configuration, first_page_num);
1173 Page_spacer ps (cached_line_details_, first_page_num, this);
1177 return finalize_spacing_result (configuration, ret);
1181 Page_breaking::blank_page_penalty () const
1186 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1187 else if (ends_score ())
1188 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1190 penalty_sym = ly_symbol2scm ("blank-page-force");
1192 Break_position const &pos = breaks_[current_end_breakpoint_];
1193 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1194 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1196 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1199 // If systems_per_page_ is positive, we don't really try to space on N
1200 // or N+1 pages; see the comment to space_systems_on_n_pages.
1202 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1203 Real penalty_for_fewer_pages)
1205 Page_spacing_result n_res;
1206 Page_spacing_result m_res;
1208 if (systems_per_page_ > 0)
1210 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1211 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
1215 cache_line_details (configuration);
1216 vsize min_p_count = min_page_count (configuration, first_page_num);
1217 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1220 programming_error ("both page counts are out of bounds");
1222 if (n == 1 && valid_n)
1224 bool rag = ragged () || (is_last () && ragged_last ());
1225 Real height = page_height (first_page_num, is_last ());
1227 if (1 >= min_p_count)
1228 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1229 if (1 < cached_line_details_.size ())
1230 m_res = space_systems_on_2_pages (configuration, first_page_num);
1234 Page_spacer ps (cached_line_details_, first_page_num, this);
1236 if (n >= min_p_count || !valid_n)
1237 n_res = ps.solve (n);
1238 if (n < cached_line_details_.size () || !valid_n)
1239 m_res = ps.solve (n+1);
1242 m_res = finalize_spacing_result (configuration, m_res);
1243 n_res = finalize_spacing_result (configuration, n_res);
1245 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1246 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1248 if (n_res.force_.size ())
1249 n_res.force_.back () += penalty_for_fewer_pages;
1251 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1255 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1257 if (systems_per_page_ > 0)
1258 return space_systems_with_fixed_number_per_page (configuration, first_page_num);
1260 cache_line_details (configuration);
1261 Page_spacer ps (cached_line_details_, first_page_num, this);
1263 return finalize_spacing_result (configuration, ps.solve ());
1267 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1268 vsize first_page_num)
1270 Page_spacing_result res;
1271 Page_spacing space (page_height (first_page_num, false), this);
1274 vsize page_first_line = 0;
1276 cache_line_details (configuration);
1277 while (line < cached_line_details_.size ())
1281 space.resize (page_height (first_page_num + page, false));
1283 int system_count_on_this_page = 0;
1284 while (system_count_on_this_page < systems_per_page_
1285 && line < cached_line_details_.size ())
1287 Line_details const &cur_line = cached_line_details_[line];
1288 space.append_system (cur_line);
1289 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1292 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1296 res.systems_per_page_.push_back (line - page_first_line);
1298 res.force_.push_back (space.force_);
1299 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1300 if (system_count_on_this_page != systems_per_page_)
1302 res.penalty_ += abs (system_count_on_this_page - systems_per_page_) * TERRIBLE_SPACING_PENALTY;
1303 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1304 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1307 page_first_line = line;
1310 /* Recalculate forces for the last page because we know now that is
1311 really the last page. */
1312 space.resize (page_height (first_page_num + page, true));
1313 res.force_.back () = space.force_;
1314 return finalize_spacing_result (configuration, res);
1318 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1320 // TODO: add support for min/max-systems-per-page.
1321 Page_spacing_result res;
1323 vsize page_first_line = 0;
1324 Page_spacing space (page_height (first_page_num, false), this);
1326 cache_line_details (configuration);
1327 for (vsize line = 0; line < cached_line_details_.size (); line++)
1329 Real prev_force = space.force_;
1330 space.append_system (cached_line_details_[line]);
1331 if ((line > page_first_line)
1332 && (isinf (space.force_)
1334 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1336 res.systems_per_page_.push_back (line - page_first_line);
1337 res.force_.push_back (prev_force);
1338 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1340 space.resize (page_height (first_page_num + page, false));
1342 space.append_system (cached_line_details_[line]);
1343 page_first_line = line;
1346 if (line == cached_line_details_.size () - 1)
1348 /* This is the last line */
1349 /* When the last page height was computed, we did not know yet that it
1350 * was the last one. If the systems put on it don't fit anymore, the last
1351 * system is moved to a new page */
1352 space.resize (page_height (first_page_num + page, true));
1353 if ((line > page_first_line) && (isinf (space.force_)))
1355 res.systems_per_page_.push_back (line - page_first_line);
1356 res.force_.push_back (prev_force);
1357 /* the last page containing the last line */
1358 space.resize (page_height (first_page_num + page + 1, true));
1360 space.append_system (cached_line_details_[line]);
1361 res.systems_per_page_.push_back (1);
1362 res.force_.push_back (space.force_);
1363 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1364 res.penalty_ += cached_line_details_[line].page_penalty_;
1368 res.systems_per_page_.push_back (line + 1 - page_first_line);
1369 res.force_.push_back (space.force_);
1370 res.penalty_ += cached_line_details_[line].page_penalty_;
1374 return finalize_spacing_result (configuration, res);
1377 /* Calculate demerits and fix res.systems_per_page_ so that
1378 it refers to the original line numbers, not the ones given by compress_lines (). */
1380 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1382 if (res.force_.empty ())
1385 cache_line_details (configuration);
1386 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1388 Real line_force = 0;
1389 Real line_penalty = 0;
1390 Real page_demerits = res.penalty_;
1391 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1393 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1395 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1396 line_penalty += uncompressed_line_details_[i].break_penalty_;
1399 for (vsize i = 0; i < res.force_.size (); i++)
1401 Real f = res.force_[i];
1403 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1406 /* for a while we tried averaging page and line forces across pages instead
1407 of summing them, but it caused a problem: if there is a single page
1408 with a very bad page force (for example because of a forced page break),
1409 the page breaker will put in a _lot_ of pages so that the bad force
1410 becomes averaged out over many pages. */
1411 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1416 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1417 are by far the most common cases, we have special functions for them.
1419 space_systems_on_1_page has a different calling convention than most of the
1420 space_systems functions. This is because space_systems_on_1_page is (unlike
1421 the other space_systems functions) sometimes called on subsets of a full
1424 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1426 Page_spacing space (page_height, this);
1427 Page_spacing_result ret;
1430 for (vsize i = 0; i < lines.size (); i++)
1432 space.append_system (lines[i]);
1433 line_count += lines[i].compressed_nontitle_lines_count_;
1436 ret.systems_per_page_.push_back (lines.size ());
1437 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1438 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1439 ret.system_count_status_ |= line_count_status (line_count);
1441 /* don't do finalize_spacing_result () because we are only an internal function */
1446 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1448 Real page1_height = page_height (first_page_num, false);
1449 Real page2_height = page_height (first_page_num + 1, is_last ());
1450 bool ragged1 = ragged ();
1451 bool ragged2 = ragged () || (is_last () && ragged_last ());
1453 /* if there is a forced break, this reduces to 2 1-page problems */
1454 cache_line_details (configuration);
1455 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1456 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1458 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1459 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1460 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1461 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1463 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1464 p1.force_.push_back (p2.force_[0]);
1465 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1466 p1.system_count_status_ |= p2.system_count_status_;
1470 vector<Real> page1_force;
1471 vector<Real> page2_force;
1473 // page1_penalty and page2_penalty store the penalties based
1474 // on min-systems-per-page and max-systems-per-page.
1475 vector<Real> page1_penalty;
1476 vector<Real> page2_penalty;
1478 // page1_status and page2_status keep track of whether the min-systems-per-page
1479 // and max-systems-per-page constraints are satisfied.
1480 vector<int> page1_status;
1481 vector<int> page2_status;
1483 Page_spacing page1 (page1_height, this);
1484 Page_spacing page2 (page2_height, this);
1485 int page1_line_count = 0;
1486 int page2_line_count = 0;
1488 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1489 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1490 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1491 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1492 page1_status.resize (cached_line_details_.size () - 1, 0);
1493 page2_status.resize (cached_line_details_.size () - 1, 0);
1495 /* find the page 1 and page 2 forces for each page-breaking position */
1496 for (vsize i = 0; i < page1_force.size (); i++)
1498 page1.append_system (cached_line_details_[i]);
1499 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1500 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1501 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1503 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1504 page1_penalty[i] = line_count_penalty (page1_line_count);
1505 page1_status[i] = line_count_status (page1_line_count);
1508 page2_force[page2_force.size () - 1 - i] =
1509 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1511 page2_force[page2_force.size () - 1 - i] = page2.force_;
1512 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1513 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1516 /* find the position that minimises the sum of the page forces */
1517 vsize best_sys_count = 1;
1518 Real best_demerits = infinity_f;
1519 for (vsize i = 0; i < page1_force.size (); i++)
1521 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1523 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1524 // constraints. That is, we penalize harshly when they don't happen
1525 // but we don't completely reject.
1527 + page1_penalty[i] + page2_penalty[i]
1528 + cached_line_details_[i+1].page_penalty_
1529 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1530 if (dem < best_demerits)
1532 best_demerits = dem;
1533 best_sys_count = i+1;
1537 Page_spacing_result ret;
1538 ret.systems_per_page_.push_back (best_sys_count);
1539 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1540 ret.force_.push_back (page1_force[best_sys_count-1]);
1541 ret.force_.push_back (page2_force[best_sys_count-1]);
1542 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1543 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1544 + cached_line_details_.back ().page_penalty_
1545 + cached_line_details_.back ().turn_penalty_
1546 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1548 /* don't do finalize_spacing_result () because we are only an internal function */
1553 Page_breaking::all_lines_stretched (vsize configuration)
1555 cache_line_details (configuration);
1556 for (vsize i = 0; i < cached_line_details_.size (); i++)
1557 if (cached_line_details_[i].force_ < 0)
1563 Page_breaking::Line_division
1564 Page_breaking::current_configuration (vsize configuration_index) const
1566 return current_configurations_[configuration_index];
1570 Page_breaking::is_last () const
1572 return current_end_breakpoint_ == last_break_position ();
1576 Page_breaking::ends_score () const
1578 return breaks_[current_end_breakpoint_].score_ender_;
1582 Page_breaking::last_break_position () const
1584 return breaks_.size () - 1;
1587 // This gives the minimum distance between the top of the
1588 // printable area (ie. the bottom of the top-margin) and
1589 // the extent box of the topmost system.
1591 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1593 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1595 first_system_spacing = book_->paper_->c_variable ("top-markup-spacing");
1597 Real min_distance = -infinity_f;
1600 Page_layout_problem::read_spacing_spec (first_system_spacing,
1602 ly_symbol2scm ("minimum-distance"));
1603 Page_layout_problem::read_spacing_spec (first_system_spacing,
1605 ly_symbol2scm ("padding"));
1607 // FIXME: take into account the height of the header
1608 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1609 return max (0.0, max (padding, min_distance - translate));
1613 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1615 SCM last_system_spacing = book_->paper_->c_variable ("last-bottom-spacing");
1616 Real min_distance = -infinity_f;
1619 Page_layout_problem::read_spacing_spec (last_system_spacing,
1621 ly_symbol2scm ("minimum-distance"));
1622 Page_layout_problem::read_spacing_spec (last_system_spacing,
1624 ly_symbol2scm ("padding"));
1626 // FIXME: take into account the height of the footer
1627 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1628 return max (0.0, max (padding, min_distance + translate));
1632 Page_breaking::orphan_penalty () const
1634 return orphan_penalty_;