2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2010 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.
76 #include "page-breaking.hh"
78 #include "international.hh"
80 #include "output-def.hh"
81 #include "page-layout-problem.hh"
82 #include "page-spacing.hh"
83 #include "paper-book.hh"
84 #include "paper-score.hh"
85 #include "paper-system.hh"
89 /* for each forbidden page break, merge the systems around it into one
91 static vector<Line_details>
92 compress_lines (const vector<Line_details> &orig)
94 vector<Line_details> ret;
96 for (vsize i = 0; i < orig.size (); i++)
98 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
100 Line_details const &old = ret.back ();
101 Line_details compressed = orig[i];
103 We must account for the padding between the lines that we are compressing.
104 The padding values come from "old," which is the upper system here. Note
105 the meaning of tight-spacing: if a system has tight-spacing, then the padding
106 _before_ it is ignored.
109 if (!orig[i].tight_spacing_)
110 padding = orig[i].title_ ? old.title_padding_ : old.padding_;
112 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
113 compressed.first_refpoint_offset_ += compressed.shape_.rest_[UP] - old.shape_.rest_[UP];
114 compressed.space_ += old.space_;
115 compressed.inverse_hooke_ += old.inverse_hooke_;
117 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
118 compressed.compressed_nontitle_lines_count_ =
119 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
121 // compressed.title_ is true if and only if the first of its
122 // compressed lines was a title.
123 compressed.title_ = old.title_;
124 ret.back () = compressed;
128 ret.push_back (orig[i]);
129 ret.back ().force_ = 0;
135 /* translate the number of systems-per-page into something meaningful for
136 the uncompressed lines.
139 uncompress_solution (vector<vsize> const &systems_per_page,
140 vector<Line_details> const &compressed)
145 for (vsize i = 0; i < systems_per_page.size (); i++)
147 int compressed_count = 0;
148 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
149 compressed_count += compressed[j].compressed_lines_count_ - 1;
151 ret.push_back (systems_per_page[i] + compressed_count);
152 start_sys += systems_per_page[i];
157 /* for Page_breaking, the start index (when we are dealing with the stuff
158 between a pair of breakpoints) refers to the break_ index of the end of
159 the previous page. So the system index of the start of the current page
160 could either be the same as the end of the previous page or one more than
163 /* Turn a break index into the sys index that starts the next page */
165 Page_breaking::next_system (Break_position const &break_pos) const
167 vsize sys = break_pos.system_spec_index_;
169 if (sys == VPOS) /* beginning of the book */
171 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
172 return sys; /* the score overflows the previous page */
173 return sys + 1; /* this page starts with a new System_spec */
176 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
180 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
181 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
182 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
183 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
184 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
185 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
187 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
189 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
190 min_systems_per_page_ = max_systems_per_page_ = 0;
192 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
194 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
195 min_systems_per_page_ = max_systems_per_page_ = 0;
198 create_system_list ();
199 find_chunks_and_breaks (is_break, prob_break);
202 Page_breaking::~Page_breaking ()
207 Page_breaking::ragged () const
213 Page_breaking::ragged_last () const
219 Page_breaking::systems_per_page () const
221 return systems_per_page_;
225 Page_breaking::max_systems_per_page () const
227 return max_systems_per_page_;
231 Page_breaking::min_systems_per_page () const
233 return min_systems_per_page_;
237 Page_breaking::system_count () const
239 return system_count_;
243 Page_breaking::too_many_lines (int line_count) const
245 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
249 Page_breaking::too_few_lines (int line_count) const
251 return line_count < min_systems_per_page ();
255 Page_breaking::line_count_penalty (int line_count) const
257 if (too_many_lines (line_count))
258 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
259 if (too_few_lines (line_count))
260 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
266 Page_breaking::line_count_status (int line_count) const
268 if (too_many_lines (line_count))
269 return SYSTEM_COUNT_TOO_MANY;
270 if (too_few_lines (line_count))
271 return SYSTEM_COUNT_TOO_FEW;
273 return SYSTEM_COUNT_OK;
276 /* translate indices into breaks_ into start-end parameters for the line breaker */
278 Page_breaking::line_breaker_args (vsize sys,
279 Break_position const &start,
280 Break_position const &end,
281 vsize *line_breaker_start,
282 vsize *line_breaker_end)
284 assert (system_specs_[sys].pscore_);
285 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
287 if (start.system_spec_index_ == sys)
288 *line_breaker_start = start.score_break_;
290 *line_breaker_start = 0;
292 if (end.system_spec_index_ == sys)
293 *line_breaker_end = end.score_break_;
295 *line_breaker_end = VPOS;
299 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
300 Line_division const &div)
302 vector<Break_position> chunks = chunk_list (start_break, end_break);
303 bool ignore_div = false;
304 if (chunks.size () != div.size () + 1)
306 programming_error ("did not find a valid page breaking configuration");
310 for (vsize i = 0; i + 1 < chunks.size (); i++)
312 vsize sys = next_system (chunks[i]);
313 if (system_specs_[sys].pscore_)
317 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
319 vector<Column_x_positions> pos = ignore_div
320 ? line_breaking_[sys].best_solution (start, end)
321 : line_breaking_[sys].solve (start, end, div[i]);
322 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
328 Page_breaking::systems ()
331 for (vsize sys = 0; sys < system_specs_.size (); sys++)
333 if (system_specs_[sys].pscore_)
335 system_specs_[sys].pscore_->root_system ()
336 ->do_break_substitution_and_fixup_refpoints ();
337 SCM lines = system_specs_[sys].pscore_->root_system ()
338 ->get_broken_system_grobs ();
339 ret = scm_cons (lines, ret);
343 Prob *pb = system_specs_[sys].prob_;
344 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
348 return scm_append (scm_reverse (ret));
352 Page_breaking::make_page (int page_num, bool last) const
354 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
355 SCM mod = scm_c_resolve_module ("scm page");
356 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
358 make_page_scm = scm_variable_ref (make_page_scm);
360 return scm_apply_0 (make_page_scm,
361 scm_list_n (book_->self_scm (),
362 ly_symbol2scm ("page-number"), scm_from_int (page_num),
363 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
364 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
369 Page_breaking::page_height (int page_num, bool last) const
371 // The caches allow us to store the page heights for any
372 // non-negative page numbers. We use a negative value in the
373 // cache to signal that that position has not yet been initialized.
374 // This means that we won't cache properly if page_num is negative or
375 // if calc_height returns a negative number. But that's likely to
376 // be rare, so it shouldn't affect performance.
377 vector<Real>& cache = last ? last_page_height_cache_ : page_height_cache_;
378 if (page_num >= 0 && (int) cache.size () > page_num && cache[page_num] >= 0)
379 return cache[page_num];
382 SCM mod = scm_c_resolve_module ("scm page");
383 SCM page = make_page (page_num, last);
384 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
385 calc_height = scm_variable_ref (calc_height);
387 SCM height_scm = scm_apply_1 (calc_height, page, SCM_EOL);
388 Real height = scm_to_double (height_scm);
392 if ((int) cache.size () <= page_num)
393 cache.resize (page_num + 1, -1);
394 cache[page_num] = height;
401 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
403 Break_position const &pos = breaks_[breakpoint];
405 if (pos.system_spec_index_ == VPOS)
407 if (system_specs_[pos.system_spec_index_].pscore_)
408 return pos.col_->get_property (str);
409 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
413 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
415 SCM dummy_page = make_page (page_num, last);
416 Page_layout_problem layout (book_, dummy_page, systems);
417 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
421 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
423 // Create a stencil for each system.
424 SCM paper_systems = SCM_EOL;
425 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
427 SCM paper_system = scm_car (s);
428 if (Grob *g = unsmob_grob (scm_car (s)))
430 System *sys = dynamic_cast<System*> (g);
431 paper_system = sys->get_paper_system ();
434 paper_systems = scm_cons (paper_system, paper_systems);
437 // Create the page and draw it.
438 SCM page = make_page (page_num, last);
439 SCM page_module = scm_c_resolve_module ("scm page");
440 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
441 page_stencil = scm_variable_ref (page_stencil);
443 Prob *p = unsmob_prob (page);
444 p->set_property ("lines", paper_systems);
445 p->set_property ("configuration", configuration);
446 scm_apply_1 (page_stencil, page, SCM_EOL);
452 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
454 int first_page_number
455 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
457 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
458 if (label_page_table == SCM_UNDEFINED)
459 label_page_table = SCM_EOL;
461 // Build a list of (systems . configuration) pairs. Note that we lay out
462 // the staves and find the configurations before drawing anything. Some
463 // grobs (like tuplet brackets) look at their neighbours while drawing
464 // themselves. If this happens before the neighbouring staves have
465 // been laid out, bad side-effects could happen (in particular,
466 // Align_interface::align_to_ideal_distances might be called).
467 SCM systems_and_configs = SCM_EOL;
469 for (vsize i = 0; i < lines_per_page.size (); i++)
471 int page_num = i + first_page_number;
472 bool bookpart_last_page = (i == lines_per_page.size () - 1);
473 bool rag = ragged () || (bookpart_last_page && ragged_last ());
474 SCM line_count = scm_from_int (lines_per_page[i]);
475 SCM lines = scm_list_head (systems, line_count);
476 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
478 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
479 systems = scm_list_tail (systems, line_count);
482 // Now it's safe to make the pages.
483 int page_num = first_page_number + lines_per_page.size () - 1;
484 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
486 SCM lines = scm_caar (s);
487 SCM config = scm_cdar (s);
488 bool bookpart_last_page = (s == systems_and_configs);
489 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
492 SCM page_num_scm = scm_from_int (page_num);
493 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
495 SCM labels = SCM_EOL;
496 if (Grob * line = unsmob_grob (scm_car (l)))
498 System *system = dynamic_cast<System*> (line);
499 labels = system->get_property ("labels");
501 else if (Prob *prob = unsmob_prob (scm_car (l)))
502 labels = prob->get_property ("labels");
504 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
505 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
509 ret = scm_cons (page, ret);
512 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
516 /* The page-turn-page-breaker needs to have a line-breaker between any two
517 columns with non-NULL page-turn-permission.
519 The optimal-breaker needs to have a line-breaker between any two columns
520 with page-break-permission = 'force.
522 By using a grob predicate, we can accommodate both of these uses.
525 Page_breaking::create_system_list ()
527 SCM specs = book_->get_system_specs ();
528 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
530 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
532 system_specs_.push_back (System_spec (ps));
536 Prob *pb = unsmob_prob (scm_car (s));
540 system_specs_.push_back (System_spec (pb));
546 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
548 SCM force_sym = ly_symbol2scm ("force");
550 chunks_.push_back (Break_position ());
551 breaks_.push_back (Break_position ());
553 for (vsize i = 0; i < system_specs_.size (); i++)
555 if (system_specs_[i].pscore_)
557 vector<Grob*> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
558 vector<Grob*> forced_line_break_cols;
560 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
561 if (scm_is_number (system_count))
563 // With system-count given, the line configuration for
564 // this score is fixed. We need to ensure that chunk
565 // boundaries only occur at line breaks.
566 Constrained_breaking breaking (system_specs_[i].pscore_);
567 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
569 for (vsize j = 0; j < details.size (); j++)
570 forced_line_break_cols.push_back (details[j].last_column_);
573 int last_forced_line_break_idx = 0;
574 vsize forced_line_break_idx = 0;
575 vector<vsize> line_breaker_columns;
576 line_breaker_columns.push_back (0);
578 for (vsize j = 1; j < cols.size (); j++)
580 if (forced_line_break_cols.size ())
582 if (forced_line_break_idx >= forced_line_break_cols.size ()
583 || forced_line_break_cols[forced_line_break_idx] != cols[j])
586 forced_line_break_idx++;
589 bool last = (j == cols.size () - 1);
590 bool break_point = is_break && is_break (cols[j]);
591 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
592 Break_position cur_pos = Break_position (i,
593 line_breaker_columns.size (),
597 // NOTE: even in the breaks_ list, forced_line_count_
598 // refers to the number of lines between a
599 // Break_position and the start of that /chunk/. This
600 // is needed for system_count_bounds to work correctly,
601 // since it mixes Break_positions from breaks_ and
603 if (scm_is_number (system_count))
604 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
606 if (break_point || (i == system_specs_.size () - 1 && last))
607 breaks_.push_back (cur_pos);
608 if (chunk_end || last)
610 chunks_.push_back (cur_pos);
611 last_forced_line_break_idx = forced_line_break_idx;
614 if ((break_point || chunk_end) && !last)
615 line_breaker_columns.push_back (j);
617 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
621 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
622 if (break_point || i == system_specs_.size () - 1)
623 breaks_.push_back (Break_position (i));
625 chunks_.push_back (Break_position (i));
627 /* FIXME: shouldn't we push a Null_breaker or similar dummy
629 line_breaking_.push_back (Constrained_breaking (NULL));
634 vector<Break_position>
635 Page_breaking::chunk_list (vsize start_index, vsize end_index)
637 Break_position start = breaks_[start_index];
638 Break_position end = breaks_[end_index];
641 for (; i < chunks_.size () && chunks_[i] <= start; i++)
644 vector<Break_position> ret;
645 ret.push_back (start);
646 for (; i < chunks_.size () && chunks_[i] < end; i++)
647 ret.push_back (chunks_[i]);
653 Page_breaking::min_system_count (vsize start, vsize end)
655 vector<Break_position> chunks = chunk_list (start, end);
656 Line_division div = system_count_bounds (chunks, true);
659 for (vsize i = 0; i < div.size (); i++)
665 Page_breaking::max_system_count (vsize start, vsize end)
667 vector<Break_position> chunks = chunk_list (start, end);
668 Line_division div = system_count_bounds (chunks, false);
671 for (vsize i = 0; i < div.size (); i++)
676 Page_breaking::Line_division
677 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
680 assert (chunks.size () >= 2);
683 ret.resize (chunks.size () - 1, 1);
685 for (vsize i = 0; i + 1 < chunks.size (); i++)
687 vsize sys = next_system (chunks[i]);
689 if (chunks[i+1].forced_line_count_)
690 ret[i] = chunks[i+1].forced_line_count_;
691 else if (system_specs_[sys].pscore_)
695 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
697 ? line_breaking_[sys].min_system_count (start, end)
698 : line_breaking_[sys].max_system_count (start, end);
706 Page_breaking::set_current_breakpoints (vsize start,
709 Line_division lower_bound,
710 Line_division upper_bound)
712 system_count_ = system_count;
713 current_chunks_ = chunk_list (start, end);
714 current_start_breakpoint_ = start;
715 current_end_breakpoint_ = end;
716 clear_line_details_cache ();
718 if (!lower_bound.size ())
719 lower_bound = system_count_bounds (current_chunks_, true);
720 if (!upper_bound.size ())
721 upper_bound = system_count_bounds (current_chunks_, false);
723 assert (lower_bound.size () == current_chunks_.size () - 1);
724 assert (upper_bound.size () == current_chunks_.size () - 1);
726 Line_division work_in_progress;
727 current_configurations_.clear ();
728 line_divisions_rec (system_count,
733 /* we only consider a constant number of configurations. Otherwise,
734 this becomes slow when there are many small scores. The constant
735 5 is somewhat arbitrary. */
736 if (current_configurations_.size () > 5)
738 vector<pair<Real,vsize> > dems_and_indices;
740 for (vsize i = 0; i < current_configurations_.size (); i++)
742 cache_line_details (i);
744 for (vsize j = 0; j < cached_line_details_.size (); j++)
745 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
746 + cached_line_details_[j].break_penalty_;
748 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
750 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
752 vector<Line_division> best_5_configurations;
753 for (vsize i = 0; i < 5; i++)
754 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
756 clear_line_details_cache ();
757 current_configurations_ = best_5_configurations;
762 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
764 current_chunks_ = chunk_list (start, end);
765 current_start_breakpoint_ = start;
766 current_end_breakpoint_ = end;
767 clear_line_details_cache ();
771 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
773 vsize sys = next_system (current_chunks_[i]);
775 if (current_chunks_[i+1].forced_line_count_)
776 div.push_back (current_chunks_[i+1].forced_line_count_);
777 else if (system_specs_[sys].pscore_)
779 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
780 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
785 system_count_ += div.back ();
787 current_configurations_.clear ();
788 current_configurations_.push_back (div);
792 Page_breaking::current_configuration_count () const
794 return current_configurations_.size ();
798 Page_breaking::cache_line_details (vsize configuration_index)
800 if (cached_configuration_index_ != configuration_index)
802 cached_configuration_index_ = configuration_index;
804 Line_division &div = current_configurations_[configuration_index];
805 uncompressed_line_details_.clear ();
806 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
808 vsize sys = next_system (current_chunks_[i]);
809 if (system_specs_[sys].pscore_)
813 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
815 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
816 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
820 assert (div[i] == 1);
821 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_, book_->paper_));
824 cached_line_details_ = compress_lines (uncompressed_line_details_);
825 compute_line_heights ();
830 Page_breaking::clear_line_details_cache ()
832 cached_configuration_index_ = VPOS;
833 cached_line_details_.clear ();
834 uncompressed_line_details_.clear ();
838 Page_breaking::line_divisions_rec (vsize system_count,
839 Line_division const &min_sys,
840 Line_division const &max_sys,
841 Line_division *cur_division)
843 vsize my_index = cur_division->size ();
844 vsize others_min = 0;
845 vsize others_max = 0;
847 for (vsize i = my_index + 1; i < min_sys.size (); i++)
849 others_min += min_sys[i];
850 others_max += max_sys[i];
852 others_max = min (others_max, system_count);
853 vsize real_min = max (min_sys[my_index], system_count - others_max);
854 vsize real_max = min (max_sys[my_index], system_count - others_min);
856 if (real_min > real_max || real_min <= 0)
858 /* this should never happen within a recursive call. If it happens
859 at all, it means that we were called with an unsolvable problem
860 and we should return an empty result */
861 assert (my_index == 0);
865 for (vsize i = real_min; i <= real_max; i++)
867 cur_division->push_back (i);
868 if (my_index == min_sys.size () - 1)
869 current_configurations_.push_back (*cur_division);
871 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
872 cur_division->pop_back ();
877 Page_breaking::compute_line_heights ()
879 Real prev_hanging = 0;
880 Real prev_hanging_begin = 0;
881 Real prev_hanging_rest = 0;
882 Real prev_refpoint_hanging = 0;
883 for (vsize i = 0; i < cached_line_details_.size (); i++)
885 Line_shape shape = cached_line_details_[i].shape_;
886 Real a = shape.begin_[UP];
887 Real b = shape.rest_[UP];
888 bool title = cached_line_details_[i].title_;
889 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
894 if (!cached_line_details_[i].tight_spacing_)
896 ? cached_line_details_[i-1].title_padding_
897 : cached_line_details_[i-1].padding_;
898 Real min_dist = title
899 ? cached_line_details_[i-1].title_min_distance_
900 : cached_line_details_[i-1].min_distance_;
901 refpoint_hanging = max (refpoint_hanging + padding,
902 prev_refpoint_hanging + min_dist
903 + cached_line_details_[i].first_refpoint_offset_);
906 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
907 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
908 Real hanging = max (hanging_begin, hanging_rest);
909 cached_line_details_[i].tallness_ = hanging - prev_hanging;
910 prev_hanging = hanging;
911 prev_hanging_begin = hanging_begin;
912 prev_hanging_rest = hanging_rest;
913 prev_refpoint_hanging = refpoint_hanging;
918 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
921 vsize page_starter = 0;
922 Real cur_rod_height = 0;
923 Real cur_spring_height = 0;
924 Real cur_page_height = page_height (first_page_num, false);
927 cache_line_details (configuration);
929 if (cached_line_details_.size ())
930 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
932 for (vsize i = 0; i < cached_line_details_.size (); i++)
935 if (cur_rod_height > 0)
936 ext_len = cached_line_details_[i].tallness_;
938 ext_len = cached_line_details_[i].full_height();
940 Real next_rod_height = cur_rod_height + ext_len;
941 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
942 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
943 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
944 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
946 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
947 || too_many_lines (next_line_count)
949 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
951 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
952 cur_rod_height = cached_line_details_[i].full_height();
953 cur_spring_height = cached_line_details_[i].space_;
956 cur_page_height = page_height (first_page_num + ret, false);
957 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
963 cur_rod_height = next_rod_height;
964 cur_spring_height = next_spring_height;
965 line_count = next_line_count;
969 /* there are two potential problems with the last page (because we didn't know
970 it was the last page until after we managed to fit all the systems to it):
971 - we are ragged-last but the last page has a compressed spring
972 - the value returned by page_height (num, true) is smaller than the
973 value returned by page_height (num, false) and it causes the page not to
976 In either case, we just need to add one more page. This is because the last
977 line will always fit on the extra page and by adding one more page to the
978 end, the previous page is no longer the last page, so our previous
979 calculations that treated it as a non-last page were ok.
982 cur_page_height = page_height (first_page_num + ret - 1, true);
983 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
984 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
986 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
987 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
988 && cur_height > cur_page_height
989 /* don't increase the page count if the last page had only one system */
990 && cur_rod_height > cached_line_details_.back ().full_height ())
993 assert (ret <= cached_line_details_.size ());
997 // If systems_per_page_ is positive, we don't really try to space on N pages;
998 // we just put the requested number of systems on each page and penalize
999 // if the result doesn't have N pages.
1001 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
1003 Page_spacing_result ret;
1005 if (systems_per_page_ > 0)
1007 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1008 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
1012 cache_line_details (configuration);
1013 bool valid_n = (n >= min_page_count (configuration, first_page_num)
1014 && n <= cached_line_details_.size ());
1017 programming_error ("number of pages is out of bounds");
1019 if (n == 1 && valid_n)
1020 ret = space_systems_on_1_page (cached_line_details_,
1021 page_height (first_page_num, is_last ()),
1022 ragged () || (is_last () && ragged_last ()));
1023 else if (n == 2 && valid_n)
1024 ret = space_systems_on_2_pages (configuration, first_page_num);
1027 Page_spacer ps (cached_line_details_, first_page_num, this);
1031 return finalize_spacing_result (configuration, ret);
1035 Page_breaking::blank_page_penalty () const
1040 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1041 else if (ends_score ())
1042 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1044 penalty_sym = ly_symbol2scm ("blank-page-force");
1046 Break_position const &pos = breaks_[current_end_breakpoint_];
1047 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1048 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1050 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1053 // If systems_per_page_ is positive, we don't really try to space on N
1054 // or N+1 pages; see the comment to space_systems_on_n_pages.
1056 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1057 Real penalty_for_fewer_pages)
1059 Page_spacing_result n_res;
1060 Page_spacing_result m_res;
1062 if (systems_per_page_ > 0)
1064 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1065 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
1069 cache_line_details (configuration);
1070 vsize min_p_count = min_page_count (configuration, first_page_num);
1071 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1074 programming_error ("both page counts are out of bounds");
1076 if (n == 1 && valid_n)
1078 bool rag = ragged () || (is_last () && ragged_last ());
1079 Real height = page_height (first_page_num, is_last ());
1081 if (1 >= min_p_count)
1082 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1083 if (1 < cached_line_details_.size ())
1084 m_res = space_systems_on_2_pages (configuration, first_page_num);
1088 Page_spacer ps (cached_line_details_, first_page_num, this);
1090 if (n >= min_p_count || !valid_n)
1091 n_res = ps.solve (n);
1092 if (n < cached_line_details_.size () || !valid_n)
1093 m_res = ps.solve (n+1);
1096 m_res = finalize_spacing_result (configuration, m_res);
1097 n_res = finalize_spacing_result (configuration, n_res);
1099 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1100 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1102 if (n_res.force_.size ())
1103 n_res.force_.back () += penalty_for_fewer_pages;
1105 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1109 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1111 cache_line_details (configuration);
1112 Page_spacer ps (cached_line_details_, first_page_num, this);
1114 return finalize_spacing_result (configuration, ps.solve ());
1118 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1119 vsize first_page_num)
1121 Page_spacing_result res;
1122 Page_spacing space (page_height (first_page_num, false), this);
1125 vsize page_first_line = 0;
1127 cache_line_details (configuration);
1128 while (line < cached_line_details_.size ())
1132 space.resize (page_height (first_page_num + page, false));
1134 int system_count_on_this_page = 0;
1135 while (system_count_on_this_page < systems_per_page_
1136 && line < cached_line_details_.size ())
1138 Line_details const &cur_line = cached_line_details_[line];
1139 space.append_system (cur_line);
1140 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1143 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1147 res.systems_per_page_.push_back (line - page_first_line);
1149 res.force_.push_back (space.force_);
1150 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1151 if (system_count_on_this_page != systems_per_page_)
1153 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1154 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1155 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1158 page_first_line = line;
1161 /* Recalculate forces for the last page because we know now that is
1162 really the last page. */
1163 space.resize (page_height (first_page_num + page, true));
1164 res.force_.back () = space.force_;
1165 return finalize_spacing_result (configuration, res);
1169 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1171 // TODO: add support for min/max-systems-per-page.
1172 Page_spacing_result res;
1174 vsize page_first_line = 0;
1175 Page_spacing space (page_height (first_page_num, false), this);
1177 cache_line_details (configuration);
1178 for (vsize line = 0; line < cached_line_details_.size (); line++)
1180 Real prev_force = space.force_;
1181 space.append_system (cached_line_details_[line]);
1182 if ((line > page_first_line)
1183 && (isinf (space.force_)
1185 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1187 res.systems_per_page_.push_back (line - page_first_line);
1188 res.force_.push_back (prev_force);
1189 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1191 space.resize (page_height (first_page_num + page, false));
1193 space.append_system (cached_line_details_[line]);
1194 page_first_line = line;
1197 if (line == cached_line_details_.size () - 1)
1199 /* This is the last line */
1200 /* When the last page height was computed, we did not know yet that it
1201 * was the last one. If the systems put on it don't fit anymore, the last
1202 * system is moved to a new page */
1203 space.resize (page_height (first_page_num + page, true));
1204 if ((line > page_first_line) && (isinf (space.force_)))
1206 res.systems_per_page_.push_back (line - page_first_line);
1207 res.force_.push_back (prev_force);
1208 /* the last page containing the last line */
1209 space.resize (page_height (first_page_num + page + 1, true));
1211 space.append_system (cached_line_details_[line]);
1212 res.systems_per_page_.push_back (1);
1213 res.force_.push_back (space.force_);
1214 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1215 res.penalty_ += cached_line_details_[line].page_penalty_;
1219 res.systems_per_page_.push_back (line + 1 - page_first_line);
1220 res.force_.push_back (space.force_);
1221 res.penalty_ += cached_line_details_[line].page_penalty_;
1225 return finalize_spacing_result (configuration, res);
1228 /* Calculate demerits and fix res.systems_per_page_ so that
1229 it refers to the original line numbers, not the ones given by compress_lines (). */
1231 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1233 if (res.force_.empty ())
1236 cache_line_details (configuration);
1237 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1239 Real line_force = 0;
1240 Real line_penalty = 0;
1241 Real page_demerits = res.penalty_;
1242 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1244 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1246 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1247 line_penalty += uncompressed_line_details_[i].break_penalty_;
1250 for (vsize i = 0; i < res.force_.size (); i++)
1252 Real f = res.force_[i];
1254 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1257 /* for a while we tried averaging page and line forces across pages instead
1258 of summing them, but it caused a problem: if there is a single page
1259 with a very bad page force (for example because of a forced page break),
1260 the page breaker will put in a _lot_ of pages so that the bad force
1261 becomes averaged out over many pages. */
1262 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1267 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1268 are by far the most common cases, we have special functions for them.
1270 space_systems_on_1_page has a different calling convention than most of the
1271 space_systems functions. This is because space_systems_on_1_page is (unlike
1272 the other space_systems functions) sometimes called on subsets of a full
1275 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1277 Page_spacing space (page_height, this);
1278 Page_spacing_result ret;
1281 for (vsize i = 0; i < lines.size (); i++)
1283 space.append_system (lines[i]);
1284 line_count += lines[i].compressed_nontitle_lines_count_;
1287 ret.systems_per_page_.push_back (lines.size ());
1288 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1289 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1290 ret.system_count_status_ |= line_count_status (line_count);
1292 /* don't do finalize_spacing_result () because we are only an internal function */
1297 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1299 Real page1_height = page_height (first_page_num, false);
1300 Real page2_height = page_height (first_page_num + 1, is_last ());
1301 bool ragged1 = ragged ();
1302 bool ragged2 = ragged () || (is_last () && ragged_last ());
1304 /* if there is a forced break, this reduces to 2 1-page problems */
1305 cache_line_details (configuration);
1306 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1307 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1309 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1310 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1311 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1312 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1314 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1315 p1.force_.push_back (p2.force_[0]);
1316 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1317 p1.system_count_status_ |= p2.system_count_status_;
1321 vector<Real> page1_force;
1322 vector<Real> page2_force;
1324 // page1_penalty and page2_penalty store the penalties based
1325 // on min-systems-per-page and max-systems-per-page.
1326 vector<Real> page1_penalty;
1327 vector<Real> page2_penalty;
1329 // page1_status and page2_status keep track of whether the min-systems-per-page
1330 // and max-systems-per-page constraints are satisfied.
1331 vector<int> page1_status;
1332 vector<int> page2_status;
1334 Page_spacing page1 (page1_height, this);
1335 Page_spacing page2 (page2_height, this);
1336 int page1_line_count = 0;
1337 int page2_line_count = 0;
1339 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1340 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1341 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1342 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1343 page1_status.resize (cached_line_details_.size () - 1, 0);
1344 page2_status.resize (cached_line_details_.size () - 1, 0);
1346 /* find the page 1 and page 2 forces for each page-breaking position */
1347 for (vsize i = 0; i < page1_force.size (); i++)
1349 page1.append_system (cached_line_details_[i]);
1350 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1351 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1352 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1354 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1355 page1_penalty[i] = line_count_penalty (page1_line_count);
1356 page1_status[i] = line_count_status (page1_line_count);
1359 page2_force[page2_force.size () - 1 - i] =
1360 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1362 page2_force[page2_force.size () - 1 - i] = page2.force_;
1363 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1364 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1367 /* find the position that minimises the sum of the page forces */
1368 vsize best_sys_count = 1;
1369 Real best_demerits = infinity_f;
1370 for (vsize i = 0; i < page1_force.size (); i++)
1372 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1374 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1375 // constraints. That is, we penalize harshly when they don't happen
1376 // but we don't completely reject.
1378 + page1_penalty[i] + page2_penalty[i]
1379 + cached_line_details_[i+1].page_penalty_
1380 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1381 if (dem < best_demerits)
1383 best_demerits = dem;
1384 best_sys_count = i+1;
1388 Page_spacing_result ret;
1389 ret.systems_per_page_.push_back (best_sys_count);
1390 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1391 ret.force_.push_back (page1_force[best_sys_count-1]);
1392 ret.force_.push_back (page2_force[best_sys_count-1]);
1393 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1394 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1395 + cached_line_details_.back ().page_penalty_
1396 + cached_line_details_.back ().turn_penalty_
1397 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1399 /* don't do finalize_spacing_result () because we are only an internal function */
1404 Page_breaking::all_lines_stretched (vsize configuration)
1406 cache_line_details (configuration);
1407 for (vsize i = 0; i < cached_line_details_.size (); i++)
1408 if (cached_line_details_[i].force_ < 0)
1414 Page_breaking::Line_division
1415 Page_breaking::current_configuration (vsize configuration_index) const
1417 return current_configurations_[configuration_index];
1421 Page_breaking::is_last () const
1423 return current_end_breakpoint_ == last_break_position ();
1427 Page_breaking::ends_score () const
1429 return breaks_[current_end_breakpoint_].score_ender_;
1433 Page_breaking::last_break_position () const
1435 return breaks_.size () - 1;
1438 // This gives the minimum distance between the top of the
1439 // printable area (ie. the bottom of the top-margin) and
1440 // the extent box of the topmost system.
1442 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1444 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1446 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1448 Real min_distance = -infinity_f;
1451 Page_layout_problem::read_spacing_spec (first_system_spacing,
1453 ly_symbol2scm ("minimum-distance"));
1454 Page_layout_problem::read_spacing_spec (first_system_spacing,
1456 ly_symbol2scm ("padding"));
1458 // FIXME: take into account the height of the header
1459 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1460 return max (0.0, max (padding, min_distance - translate));
1464 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1466 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1467 Real min_distance = -infinity_f;
1470 Page_layout_problem::read_spacing_spec (last_system_spacing,
1472 ly_symbol2scm ("minimum-distance"));
1473 Page_layout_problem::read_spacing_spec (last_system_spacing,
1475 ly_symbol2scm ("padding"));
1477 // FIXME: take into account the height of the footer
1478 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1479 return max (0.0, max (padding, min_distance + translate));
1483 Page_breaking::orphan_penalty () const
1485 return orphan_penalty_;