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 "padding" is the padding below the current line. The padding below
104 "old" (taking into account whether "old" is a title) is already
105 accounted for in the extent of the compressed line. The padding
106 below the compressed line, therefore, should depend on whether its
107 bottom-most line is a title or not.
110 if (!orig[i].tight_spacing_)
111 padding = orig[i].title_ ? old.title_padding_ : old.padding_;
113 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
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)
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);
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 SCM mod = scm_c_resolve_module ("scm page");
372 SCM page = make_page (page_num, last);
373 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
374 calc_height = scm_variable_ref (calc_height);
376 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
377 return scm_to_double (height);
381 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
383 Break_position const &pos = breaks_[breakpoint];
385 if (pos.system_spec_index_ == VPOS)
387 if (system_specs_[pos.system_spec_index_].pscore_)
388 return pos.col_->get_property (str);
389 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
393 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
395 SCM dummy_page = make_page (page_num, last);
396 Page_layout_problem layout (book_, dummy_page, systems);
397 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
401 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
403 // Create a stencil for each system.
404 SCM paper_systems = SCM_EOL;
405 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
407 SCM paper_system = scm_car (s);
408 if (Grob *g = unsmob_grob (scm_car (s)))
410 System *sys = dynamic_cast<System*> (g);
411 paper_system = sys->get_paper_system ();
414 paper_systems = scm_cons (paper_system, paper_systems);
417 // Create the page and draw it.
418 SCM page = make_page (page_num, last);
419 SCM page_module = scm_c_resolve_module ("scm page");
420 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
421 page_stencil = scm_variable_ref (page_stencil);
423 Prob *p = unsmob_prob (page);
424 p->set_property ("lines", paper_systems);
425 p->set_property ("configuration", configuration);
426 scm_apply_1 (page_stencil, page, SCM_EOL);
432 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
434 int first_page_number
435 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
437 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
438 if (label_page_table == SCM_UNDEFINED)
439 label_page_table = SCM_EOL;
441 // Build a list of (systems . configuration) pairs. Note that we lay out
442 // the staves and find the configurations before drawing anything. Some
443 // grobs (like tuplet brackets) look at their neighbours while drawing
444 // themselves. If this happens before the neighbouring staves have
445 // been laid out, bad side-effects could happen (in particular,
446 // Align_interface::align_to_ideal_distances might be called).
447 SCM systems_and_configs = SCM_EOL;
449 for (vsize i = 0; i < lines_per_page.size (); i++)
451 int page_num = i + first_page_number;
452 bool bookpart_last_page = (i == lines_per_page.size () - 1);
453 bool rag = ragged () || (bookpart_last_page && ragged_last ());
454 SCM line_count = scm_from_int (lines_per_page[i]);
455 SCM lines = scm_list_head (systems, line_count);
456 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
458 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
459 systems = scm_list_tail (systems, line_count);
462 // Now it's safe to make the pages.
463 int page_num = first_page_number + lines_per_page.size () - 1;
464 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
466 SCM lines = scm_caar (s);
467 SCM config = scm_cdar (s);
468 bool bookpart_last_page = (s == systems_and_configs);
469 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
472 SCM page_num_scm = scm_from_int (page_num);
473 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
475 SCM labels = SCM_EOL;
476 if (Grob * line = unsmob_grob (scm_car (l)))
478 System *system = dynamic_cast<System*> (line);
479 labels = system->get_property ("labels");
481 else if (Prob *prob = unsmob_prob (scm_car (l)))
482 labels = prob->get_property ("labels");
484 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
485 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
489 ret = scm_cons (page, ret);
492 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
496 /* The page-turn-page-breaker needs to have a line-breaker between any two
497 columns with non-NULL page-turn-permission.
499 The optimal-breaker needs to have a line-breaker between any two columns
500 with page-break-permission = 'force.
502 By using a grob predicate, we can accommodate both of these uses.
505 Page_breaking::create_system_list ()
507 SCM specs = book_->get_system_specs ();
508 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
510 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
512 system_specs_.push_back (System_spec (ps));
516 Prob *pb = unsmob_prob (scm_car (s));
520 system_specs_.push_back (System_spec (pb));
526 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
528 SCM force_sym = ly_symbol2scm ("force");
530 chunks_.push_back (Break_position ());
531 breaks_.push_back (Break_position ());
533 for (vsize i = 0; i < system_specs_.size (); i++)
535 if (system_specs_[i].pscore_)
539 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
540 if (scm_is_number (system_count))
542 // With system-count given, the line configuration for
543 // this score is fixed. We need to ensure that chunk
544 // boundaries only occur at line breaks.
545 Constrained_breaking breaking (system_specs_[i].pscore_);
546 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
548 cols.push_back (system_specs_[i].pscore_->root_system ()->used_columns ()[0]);
549 for (vsize j = 0; j < details.size (); j++)
550 cols.push_back (details[j].last_column_);
553 cols = system_specs_[i].pscore_->root_system ()->used_columns ();
555 int last_chunk_idx = 0;
556 vector<vsize> line_breaker_columns;
557 line_breaker_columns.push_back (0);
559 for (vsize j = 1; j < cols.size (); j++)
561 bool last = (j == cols.size () - 1);
562 bool break_point = is_break (cols[j]);
563 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
564 Break_position cur_pos = Break_position (i,
565 line_breaker_columns.size (),
569 // NOTE: even in the breaks_ list, forced_line_count_
570 // refers to the number of lines between a
571 // Break_position and the start of that /chunk/. This
572 // is needed for system_count_bounds to work correctly,
573 // since it mixes Break_positions from breaks_ and
575 if (scm_is_number (system_count))
576 cur_pos.forced_line_count_ = j - last_chunk_idx;
578 if (break_point || (i == system_specs_.size () - 1 && last))
579 breaks_.push_back (cur_pos);
580 if (chunk_end || last)
582 chunks_.push_back (cur_pos);
586 if ((break_point || chunk_end) && !last)
587 line_breaker_columns.push_back (j);
589 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
593 /* TODO: we want some way of applying Break_p to a prob? */
594 if (i == system_specs_.size () - 1)
595 breaks_.push_back (Break_position (i));
597 chunks_.push_back (Break_position (i));
599 /* FIXME: shouldn't we push a Null_breaker or similar dummy
601 line_breaking_.push_back (Constrained_breaking (NULL));
606 vector<Break_position>
607 Page_breaking::chunk_list (vsize start_index, vsize end_index)
609 Break_position start = breaks_[start_index];
610 Break_position end = breaks_[end_index];
613 for (; i < chunks_.size () && chunks_[i] <= start; i++)
616 vector<Break_position> ret;
617 ret.push_back (start);
618 for (; i < chunks_.size () && chunks_[i] < end; i++)
619 ret.push_back (chunks_[i]);
625 Page_breaking::min_system_count (vsize start, vsize end)
627 vector<Break_position> chunks = chunk_list (start, end);
628 Line_division div = system_count_bounds (chunks, true);
631 for (vsize i = 0; i < div.size (); i++)
637 Page_breaking::max_system_count (vsize start, vsize end)
639 vector<Break_position> chunks = chunk_list (start, end);
640 Line_division div = system_count_bounds (chunks, false);
643 for (vsize i = 0; i < div.size (); i++)
648 Page_breaking::Line_division
649 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
652 assert (chunks.size () >= 2);
655 ret.resize (chunks.size () - 1, 1);
657 for (vsize i = 0; i + 1 < chunks.size (); i++)
659 vsize sys = next_system (chunks[i]);
661 if (chunks[i+1].forced_line_count_)
662 ret[i] = chunks[i+1].forced_line_count_;
663 else if (system_specs_[sys].pscore_)
667 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
669 ? line_breaking_[sys].min_system_count (start, end)
670 : line_breaking_[sys].max_system_count (start, end);
678 Page_breaking::set_current_breakpoints (vsize start,
681 Line_division lower_bound,
682 Line_division upper_bound)
684 system_count_ = system_count;
685 current_chunks_ = chunk_list (start, end);
686 current_start_breakpoint_ = start;
687 current_end_breakpoint_ = end;
688 clear_line_details_cache ();
690 if (!lower_bound.size ())
691 lower_bound = system_count_bounds (current_chunks_, true);
692 if (!upper_bound.size ())
693 upper_bound = system_count_bounds (current_chunks_, false);
695 assert (lower_bound.size () == current_chunks_.size () - 1);
696 assert (upper_bound.size () == current_chunks_.size () - 1);
698 Line_division work_in_progress;
699 current_configurations_.clear ();
700 line_divisions_rec (system_count,
705 /* we only consider a constant number of configurations. Otherwise,
706 this becomes slow when there are many small scores. The constant
707 5 is somewhat arbitrary. */
708 if (current_configurations_.size () > 5)
710 vector<pair<Real,vsize> > dems_and_indices;
712 for (vsize i = 0; i < current_configurations_.size (); i++)
714 cache_line_details (i);
716 for (vsize j = 0; j < cached_line_details_.size (); j++)
717 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
718 + cached_line_details_[j].break_penalty_;
720 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
722 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
724 vector<Line_division> best_5_configurations;
725 for (vsize i = 0; i < 5; i++)
726 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
728 clear_line_details_cache ();
729 current_configurations_ = best_5_configurations;
734 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
736 current_chunks_ = chunk_list (start, end);
737 current_start_breakpoint_ = start;
738 current_end_breakpoint_ = end;
739 clear_line_details_cache ();
743 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
745 vsize sys = next_system (current_chunks_[i]);
747 if (current_chunks_[i+1].forced_line_count_)
748 div.push_back (current_chunks_[i+1].forced_line_count_);
749 else if (system_specs_[sys].pscore_)
751 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
752 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
757 system_count_ += div.back ();
759 current_configurations_.clear ();
760 current_configurations_.push_back (div);
764 Page_breaking::current_configuration_count () const
766 return current_configurations_.size ();
770 Page_breaking::cache_line_details (vsize configuration_index)
772 if (cached_configuration_index_ != configuration_index)
774 cached_configuration_index_ = configuration_index;
776 Line_division &div = current_configurations_[configuration_index];
777 uncompressed_line_details_.clear ();
778 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
780 vsize sys = next_system (current_chunks_[i]);
781 if (system_specs_[sys].pscore_)
785 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
787 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
788 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
792 assert (div[i] == 1);
793 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_, book_->paper_));
796 cached_line_details_ = compress_lines (uncompressed_line_details_);
801 Page_breaking::clear_line_details_cache ()
803 cached_configuration_index_ = VPOS;
804 cached_line_details_.clear ();
805 uncompressed_line_details_.clear ();
809 Page_breaking::line_divisions_rec (vsize system_count,
810 Line_division const &min_sys,
811 Line_division const &max_sys,
812 Line_division *cur_division)
814 vsize my_index = cur_division->size ();
815 vsize others_min = 0;
816 vsize others_max = 0;
818 for (vsize i = my_index + 1; i < min_sys.size (); i++)
820 others_min += min_sys[i];
821 others_max += max_sys[i];
823 others_max = min (others_max, system_count);
824 vsize real_min = max (min_sys[my_index], system_count - others_max);
825 vsize real_max = min (max_sys[my_index], system_count - others_min);
827 if (real_min > real_max || real_min <= 0)
829 /* this should never happen within a recursive call. If it happens
830 at all, it means that we were called with an unsolvable problem
831 and we should return an empty result */
832 assert (my_index == 0);
836 for (vsize i = real_min; i <= real_max; i++)
838 cur_division->push_back (i);
839 if (my_index == min_sys.size () - 1)
840 current_configurations_.push_back (*cur_division);
842 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
843 cur_division->pop_back ();
848 Page_breaking::compute_line_heights ()
850 Real prev_hanging = 0;
851 Real prev_hanging_begin = 0;
852 Real prev_hanging_rest = 0;
853 for (vsize i = 0; i < cached_line_details_.size (); i++)
855 Line_shape shape = cached_line_details_[i].shape_;
856 Real a = shape.begin_[UP];
857 Real b = shape.rest_[UP];
858 Real midline_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
859 Real hanging_begin = midline_hanging - shape.begin_[DOWN];
860 Real hanging_rest = midline_hanging - shape.rest_[DOWN];
861 Real hanging = max (hanging_begin, hanging_rest);
862 cached_line_details_[i].tallness_ = hanging - prev_hanging;
863 prev_hanging = hanging;
864 prev_hanging_begin = hanging_begin;
865 prev_hanging_rest = hanging_rest;
870 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
873 vsize page_starter = 0;
874 Real cur_rod_height = 0;
875 Real cur_spring_height = 0;
876 Real cur_page_height = page_height (first_page_num, false);
879 cache_line_details (configuration);
880 compute_line_heights ();
882 if (cached_line_details_.size ())
883 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
885 for (vsize i = 0; i < cached_line_details_.size (); i++)
889 if (cur_rod_height > 0)
891 if (!cached_line_details_[i].tight_spacing_)
892 padding = (cached_line_details_[i].title_
893 ? cached_line_details_[i - 1].title_padding_
894 : cached_line_details_[i - 1].padding_);
895 ext_len = cached_line_details_[i].tallness_;
899 ext_len = cached_line_details_[i].full_height();
901 Real next_rod_height = cur_rod_height + ext_len + padding;
902 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
903 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
904 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
905 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
907 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
908 || too_many_lines (next_line_count)
910 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
912 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
913 cur_rod_height = cached_line_details_[i].full_height();
914 cur_spring_height = cached_line_details_[i].space_;
917 cur_page_height = page_height (first_page_num + ret, false);
918 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
924 cur_rod_height = next_rod_height;
925 cur_spring_height = next_spring_height;
926 line_count = next_line_count;
930 /* there are two potential problems with the last page (because we didn't know
931 it was the last page until after we managed to fit all the systems to it):
932 - we are ragged-last but the last page has a compressed spring
933 - the value returned by page_height (num, true) is smaller than the
934 value returned by page_height (num, false) and it causes the page not to
937 In either case, we just need to add one more page. This is because the last
938 line will always fit on the extra page and by adding one more page to the
939 end, the previous page is no longer the last page, so our previous
940 calculations that treated it as a non-last page were ok.
943 cur_page_height = page_height (first_page_num + ret - 1, true);
944 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
945 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
947 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
948 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
949 && cur_height > cur_page_height
950 /* don't increase the page count if the last page had only one system */
951 && cur_rod_height > cached_line_details_.back ().full_height ())
954 assert (ret <= cached_line_details_.size ());
958 // If systems_per_page_ is positive, we don't really try to space on N pages;
959 // we just put the requested number of systems on each page and penalize
960 // if the result doesn't have N pages.
962 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
964 Page_spacing_result ret;
966 if (systems_per_page_ > 0)
968 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
969 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
973 cache_line_details (configuration);
974 bool valid_n = (n >= min_page_count (configuration, first_page_num)
975 && n <= cached_line_details_.size ());
978 programming_error ("number of pages is out of bounds");
980 if (n == 1 && valid_n)
981 ret = space_systems_on_1_page (cached_line_details_,
982 page_height (first_page_num, is_last ()),
983 ragged () || (is_last () && ragged_last ()));
984 else if (n == 2 && valid_n)
985 ret = space_systems_on_2_pages (configuration, first_page_num);
988 Page_spacer ps (cached_line_details_, first_page_num, this);
992 return finalize_spacing_result (configuration, ret);
996 Page_breaking::blank_page_penalty () const
1001 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1002 else if (ends_score ())
1003 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1005 penalty_sym = ly_symbol2scm ("blank-page-force");
1007 Break_position const &pos = breaks_[current_end_breakpoint_];
1008 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1009 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1011 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1014 // If systems_per_page_ is positive, we don't really try to space on N
1015 // or N+1 pages; see the comment to space_systems_on_n_pages.
1017 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1018 Real penalty_for_fewer_pages)
1020 Page_spacing_result n_res;
1021 Page_spacing_result m_res;
1023 if (systems_per_page_ > 0)
1025 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1026 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
1030 cache_line_details (configuration);
1031 vsize min_p_count = min_page_count (configuration, first_page_num);
1032 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1035 programming_error ("both page counts are out of bounds");
1037 if (n == 1 && valid_n)
1039 bool rag = ragged () || (is_last () && ragged_last ());
1040 Real height = page_height (first_page_num, is_last ());
1042 if (1 >= min_p_count)
1043 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1044 if (1 < cached_line_details_.size ())
1045 m_res = space_systems_on_2_pages (configuration, first_page_num);
1049 Page_spacer ps (cached_line_details_, first_page_num, this);
1051 if (n >= min_p_count || !valid_n)
1052 n_res = ps.solve (n);
1053 if (n < cached_line_details_.size () || !valid_n)
1054 m_res = ps.solve (n+1);
1057 m_res = finalize_spacing_result (configuration, m_res);
1058 n_res = finalize_spacing_result (configuration, n_res);
1060 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1061 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1063 if (n_res.force_.size ())
1064 n_res.force_.back () += penalty_for_fewer_pages;
1066 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1070 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1072 vsize min_p_count = min_page_count (configuration, first_page_num);
1074 cache_line_details (configuration);
1075 Page_spacer ps (cached_line_details_, first_page_num, this);
1076 Page_spacing_result best = ps.solve (min_p_count);
1078 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1080 Page_spacing_result cur = ps.solve (i);
1081 if (cur.demerits_ < best.demerits_)
1085 Page_spacing_result ret = finalize_spacing_result (configuration, best);
1090 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1091 vsize first_page_num)
1093 Page_spacing_result res;
1094 Page_spacing space (page_height (first_page_num, false), this);
1097 vsize page_first_line = 0;
1099 cache_line_details (configuration);
1100 while (line < cached_line_details_.size ())
1104 space.resize (page_height (first_page_num + page, false));
1106 int system_count_on_this_page = 0;
1107 while (system_count_on_this_page < systems_per_page_
1108 && line < cached_line_details_.size ())
1110 Line_details const &cur_line = cached_line_details_[line];
1111 space.append_system (cur_line);
1112 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1115 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1119 res.systems_per_page_.push_back (line - page_first_line);
1121 res.force_.push_back (space.force_);
1122 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1123 if (system_count_on_this_page != systems_per_page_)
1125 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1126 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1127 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1130 page_first_line = line;
1133 /* Recalculate forces for the last page because we know now that is
1134 really the last page. */
1135 space.resize (page_height (first_page_num + page, true));
1136 res.force_.back () = space.force_;
1137 return finalize_spacing_result (configuration, res);
1141 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1143 // TODO: add support for min/max-systems-per-page.
1144 Page_spacing_result res;
1146 vsize page_first_line = 0;
1147 Page_spacing space (page_height (first_page_num, false), this);
1149 cache_line_details (configuration);
1150 compute_line_heights ();
1151 for (vsize line = 0; line < cached_line_details_.size (); line++)
1153 Real prev_force = space.force_;
1154 space.append_system (cached_line_details_[line]);
1155 if ((line > page_first_line)
1156 && (isinf (space.force_)
1158 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1160 res.systems_per_page_.push_back (line - page_first_line);
1161 res.force_.push_back (prev_force);
1162 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1164 space.resize (page_height (first_page_num + page, false));
1166 space.append_system (cached_line_details_[line]);
1167 page_first_line = line;
1170 if (line == cached_line_details_.size () - 1)
1172 /* This is the last line */
1173 /* When the last page height was computed, we did not know yet that it
1174 * was the last one. If the systems put on it don't fit anymore, the last
1175 * system is moved to a new page */
1176 space.resize (page_height (first_page_num + page, true));
1177 if ((line > page_first_line) && (isinf (space.force_)))
1179 res.systems_per_page_.push_back (line - page_first_line);
1180 res.force_.push_back (prev_force);
1181 /* the last page containing the last line */
1182 space.resize (page_height (first_page_num + page + 1, true));
1184 space.append_system (cached_line_details_[line]);
1185 res.systems_per_page_.push_back (1);
1186 res.force_.push_back (space.force_);
1187 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1188 res.penalty_ += cached_line_details_[line].page_penalty_;
1192 res.systems_per_page_.push_back (line + 1 - page_first_line);
1193 res.force_.push_back (space.force_);
1194 res.penalty_ += cached_line_details_[line].page_penalty_;
1198 return finalize_spacing_result (configuration, res);
1201 /* Calculate demerits and fix res.systems_per_page_ so that
1202 it refers to the original line numbers, not the ones given by compress_lines (). */
1204 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1206 if (res.force_.empty ())
1209 cache_line_details (configuration);
1210 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1212 Real line_force = 0;
1213 Real line_penalty = 0;
1214 Real page_demerits = res.penalty_;
1215 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1217 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1219 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1220 line_penalty += uncompressed_line_details_[i].break_penalty_;
1223 for (vsize i = 0; i < res.force_.size (); i++)
1225 Real f = res.force_[i];
1227 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1230 /* for a while we tried averaging page and line forces across pages instead
1231 of summing them, but it caused a problem: if there is a single page
1232 with a very bad page force (for example because of a forced page break),
1233 the page breaker will put in a _lot_ of pages so that the bad force
1234 becomes averaged out over many pages. */
1235 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1240 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1241 are by far the most common cases, we have special functions for them.
1243 space_systems_on_1_page has a different calling convention than most of the
1244 space_systems functions. This is because space_systems_on_1_page is (unlike
1245 the other space_systems functions) sometimes called on subsets of a full
1248 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1250 Page_spacing space (page_height, this);
1251 Page_spacing_result ret;
1254 for (vsize i = 0; i < lines.size (); i++)
1256 space.append_system (lines[i]);
1257 line_count += lines[i].compressed_nontitle_lines_count_;
1260 ret.systems_per_page_.push_back (lines.size ());
1261 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1262 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1263 ret.system_count_status_ |= line_count_status (line_count);
1265 /* don't do finalize_spacing_result () because we are only an internal function */
1270 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1272 Real page1_height = page_height (first_page_num, false);
1273 Real page2_height = page_height (first_page_num + 1, is_last ());
1274 bool ragged1 = ragged ();
1275 bool ragged2 = ragged () || (is_last () && ragged_last ());
1277 /* if there is a forced break, this reduces to 2 1-page problems */
1278 cache_line_details (configuration);
1279 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1280 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1282 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1283 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1284 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1285 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1287 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1288 p1.force_.push_back (p2.force_[0]);
1289 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1293 vector<Real> page1_force;
1294 vector<Real> page2_force;
1296 // page1_penalty and page2_penalty store the penalties based
1297 // on min-systems-per-page and max-systems-per-page.
1298 vector<Real> page1_penalty;
1299 vector<Real> page2_penalty;
1301 // page1_status and page2_status keep track of whether the min-systems-per-page
1302 // and max-systems-per-page constraints are satisfied.
1303 vector<int> page1_status;
1304 vector<int> page2_status;
1306 Page_spacing page1 (page1_height, this);
1307 Page_spacing page2 (page2_height, this);
1308 int page1_line_count = 0;
1309 int page2_line_count = 0;
1311 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1312 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1313 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1314 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1315 page1_status.resize (cached_line_details_.size () - 1, 0);
1316 page2_status.resize (cached_line_details_.size () - 1, 0);
1318 /* find the page 1 and page 2 forces for each page-breaking position */
1319 for (vsize i = 0; i < page1_force.size (); i++)
1321 page1.append_system (cached_line_details_[i]);
1322 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1323 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1324 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1326 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1327 page1_penalty[i] = line_count_penalty (page1_line_count);
1328 page1_status[i] = line_count_status (page1_line_count);
1331 page2_force[page2_force.size () - 1 - i] =
1332 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1334 page2_force[page2_force.size () - 1 - i] = page2.force_;
1335 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1336 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1339 /* find the position that minimises the sum of the page forces */
1340 vsize best_sys_count = 1;
1341 Real best_demerits = infinity_f;
1342 for (vsize i = 0; i < page1_force.size (); i++)
1344 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1346 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1347 // constraints. That is, we penalize harshly when they don't happen
1348 // but we don't completely reject.
1350 + page1_penalty[i] + page2_penalty[i]
1351 + cached_line_details_[i+1].page_penalty_
1352 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1353 if (dem < best_demerits)
1355 best_demerits = dem;
1356 best_sys_count = i+1;
1360 Page_spacing_result ret;
1361 ret.systems_per_page_.push_back (best_sys_count);
1362 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1363 ret.force_.push_back (page1_force[best_sys_count-1]);
1364 ret.force_.push_back (page2_force[best_sys_count-1]);
1365 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1366 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1367 + cached_line_details_.back ().page_penalty_
1368 + cached_line_details_.back ().turn_penalty_
1369 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1371 /* don't do finalize_spacing_result () because we are only an internal function */
1376 Page_breaking::all_lines_stretched (vsize configuration)
1378 cache_line_details (configuration);
1379 for (vsize i = 0; i < cached_line_details_.size (); i++)
1380 if (cached_line_details_[i].force_ < 0)
1386 Page_breaking::Line_division
1387 Page_breaking::current_configuration (vsize configuration_index) const
1389 return current_configurations_[configuration_index];
1393 Page_breaking::is_last () const
1395 return current_end_breakpoint_ == last_break_position ();
1399 Page_breaking::ends_score () const
1401 return breaks_[current_end_breakpoint_].score_ender_;
1405 Page_breaking::last_break_position () const
1407 return breaks_.size () - 1;
1410 // This gives the minimum distance between the top of the
1411 // printable area (ie. the bottom of the top-margin) and
1412 // the extent box of the topmost system.
1414 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1416 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1418 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1420 Real min_distance = -infinity_f;
1423 Page_layout_problem::read_spacing_spec (first_system_spacing,
1425 ly_symbol2scm ("minimum-distance"));
1426 Page_layout_problem::read_spacing_spec (first_system_spacing,
1428 ly_symbol2scm ("padding"));
1430 // FIXME: take into account the height of the header
1431 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1432 return max (0.0, max (padding, min_distance - translate));
1436 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1438 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1439 Real min_distance = -infinity_f;
1442 Page_layout_problem::read_spacing_spec (last_system_spacing,
1444 ly_symbol2scm ("minimum-distance"));
1445 Page_layout_problem::read_spacing_spec (last_system_spacing,
1447 ly_symbol2scm ("padding"));
1449 // FIXME: take into account the height of the footer
1450 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1451 return max (0.0, max (padding, min_distance + translate));
1455 Page_breaking::orphan_penalty () const
1457 return orphan_penalty_;