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];
102 Real padding = orig[i].title_ ? old.title_padding_ : old.padding_;
104 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
105 compressed.space_ += old.space_;
106 compressed.inverse_hooke_ += old.inverse_hooke_;
108 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
109 compressed.compressed_nontitle_lines_count_ =
110 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
112 // compressed.title_ is true if and only if the first of its
113 // compressed lines was a title.
114 compressed.title_ = old.title_;
115 ret.back () = compressed;
119 ret.push_back (orig[i]);
120 ret.back ().force_ = 0;
126 /* translate the number of systems-per-page into something meaningful for
127 the uncompressed lines.
130 uncompress_solution (vector<vsize> const &systems_per_page,
131 vector<Line_details> const &compressed)
136 for (vsize i = 0; i < systems_per_page.size (); i++)
138 int compressed_count = 0;
139 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
140 compressed_count += compressed[j].compressed_lines_count_ - 1;
142 ret.push_back (systems_per_page[i] + compressed_count);
143 start_sys += systems_per_page[i];
148 /* for Page_breaking, the start index (when we are dealing with the stuff
149 between a pair of breakpoints) refers to the break_ index of the end of
150 the previous page. So the system index of the start of the current page
151 could either be the same as the end of the previous page or one more than
154 /* Turn a break index into the sys index that starts the next page */
156 Page_breaking::next_system (Break_position const &break_pos) const
158 vsize sys = break_pos.system_spec_index_;
160 if (sys == VPOS) /* beginning of the book */
162 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
163 return sys; /* the score overflows the previous page */
164 return sys + 1; /* this page starts with a new System_spec */
167 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
171 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
172 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
173 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
174 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
175 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
176 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
178 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
180 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
181 min_systems_per_page_ = max_systems_per_page_ = 0;
183 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
185 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
186 min_systems_per_page_ = max_systems_per_page_ = 0;
189 create_system_list ();
190 find_chunks_and_breaks (is_break);
193 Page_breaking::~Page_breaking ()
198 Page_breaking::ragged () const
204 Page_breaking::ragged_last () const
210 Page_breaking::systems_per_page () const
212 return systems_per_page_;
216 Page_breaking::max_systems_per_page () const
218 return max_systems_per_page_;
222 Page_breaking::min_systems_per_page () const
224 return min_systems_per_page_;
228 Page_breaking::system_count () const
230 return system_count_;
234 Page_breaking::too_many_lines (int line_count) const
236 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
240 Page_breaking::too_few_lines (int line_count) const
242 return line_count < min_systems_per_page ();
246 Page_breaking::line_count_penalty (int line_count) const
248 if (too_many_lines (line_count))
249 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
250 if (too_few_lines (line_count))
251 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
257 Page_breaking::line_count_status (int line_count) const
259 if (too_many_lines (line_count))
260 return SYSTEM_COUNT_TOO_MANY;
261 if (too_few_lines (line_count))
262 return SYSTEM_COUNT_TOO_FEW;
264 return SYSTEM_COUNT_OK;
267 /* translate indices into breaks_ into start-end parameters for the line breaker */
269 Page_breaking::line_breaker_args (vsize sys,
270 Break_position const &start,
271 Break_position const &end,
272 vsize *line_breaker_start,
273 vsize *line_breaker_end)
275 assert (system_specs_[sys].pscore_);
276 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
278 if (start.system_spec_index_ == sys)
279 *line_breaker_start = start.score_break_;
281 *line_breaker_start = 0;
283 if (end.system_spec_index_ == sys)
284 *line_breaker_end = end.score_break_;
286 *line_breaker_end = VPOS;
290 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
291 Line_division const &div)
293 vector<Break_position> chunks = chunk_list (start_break, end_break);
294 bool ignore_div = false;
295 if (chunks.size () != div.size () + 1)
297 programming_error ("did not find a valid page breaking configuration");
301 for (vsize i = 0; i + 1 < chunks.size (); i++)
303 vsize sys = next_system (chunks[i]);
304 if (system_specs_[sys].pscore_)
308 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
310 vector<Column_x_positions> pos = ignore_div
311 ? line_breaking_[sys].best_solution (start, end)
312 : line_breaking_[sys].solve (start, end, div[i]);
313 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
319 Page_breaking::systems ()
322 for (vsize sys = 0; sys < system_specs_.size (); sys++)
324 if (system_specs_[sys].pscore_)
326 system_specs_[sys].pscore_->root_system ()
327 ->do_break_substitution_and_fixup_refpoints ();
328 SCM lines = system_specs_[sys].pscore_->root_system ()
329 ->get_broken_system_grobs ();
330 ret = scm_cons (lines, ret);
334 Prob *pb = system_specs_[sys].prob_;
335 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
339 return scm_append (scm_reverse (ret));
343 Page_breaking::make_page (int page_num, bool last) const
345 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
346 SCM mod = scm_c_resolve_module ("scm page");
347 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
349 make_page_scm = scm_variable_ref (make_page_scm);
351 return scm_apply_0 (make_page_scm,
352 scm_list_n (book_->self_scm (),
353 ly_symbol2scm ("page-number"), scm_from_int (page_num),
354 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
355 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
360 Page_breaking::page_height (int page_num, bool last) const
362 SCM mod = scm_c_resolve_module ("scm page");
363 SCM page = make_page (page_num, last);
364 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
365 calc_height = scm_variable_ref (calc_height);
367 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
368 return scm_to_double (height);
372 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
374 Break_position const &pos = breaks_[breakpoint];
376 if (pos.system_spec_index_ == VPOS)
378 if (system_specs_[pos.system_spec_index_].pscore_)
379 return pos.col_->get_property (str);
380 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
384 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
386 SCM dummy_page = make_page (page_num, last);
387 Page_layout_problem layout (book_, dummy_page, systems);
388 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
392 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
394 // Create a stencil for each system.
395 SCM paper_systems = SCM_EOL;
396 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
398 SCM paper_system = scm_car (s);
399 if (Grob *g = unsmob_grob (scm_car (s)))
401 System *sys = dynamic_cast<System*> (g);
402 paper_system = sys->get_paper_system ();
405 paper_systems = scm_cons (paper_system, paper_systems);
408 // Create the page and draw it.
409 SCM page = make_page (page_num, last);
410 SCM page_module = scm_c_resolve_module ("scm page");
411 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
412 page_stencil = scm_variable_ref (page_stencil);
414 Prob *p = unsmob_prob (page);
415 p->set_property ("lines", paper_systems);
416 p->set_property ("configuration", configuration);
417 scm_apply_1 (page_stencil, page, SCM_EOL);
423 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
425 int first_page_number
426 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
428 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
429 if (label_page_table == SCM_UNDEFINED)
430 label_page_table = SCM_EOL;
432 // Build a list of (systems . configuration) pairs. Note that we lay out
433 // the staves and find the configurations before drawing anything. Some
434 // grobs (like tuplet brackets) look at their neighbours while drawing
435 // themselves. If this happens before the neighbouring staves have
436 // been laid out, bad side-effects could happen (in particular,
437 // Align_interface::align_to_ideal_distances might be called).
438 SCM systems_and_configs = SCM_EOL;
440 for (vsize i = 0; i < lines_per_page.size (); i++)
442 int page_num = i + first_page_number;
443 bool bookpart_last_page = (i == lines_per_page.size () - 1);
444 bool rag = ragged () || (bookpart_last_page && ragged_last ());
445 SCM line_count = scm_from_int (lines_per_page[i]);
446 SCM lines = scm_list_head (systems, line_count);
447 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
449 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
450 systems = scm_list_tail (systems, line_count);
453 // Now it's safe to make the pages.
454 int page_num = first_page_number + lines_per_page.size () - 1;
455 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
457 SCM lines = scm_caar (s);
458 SCM config = scm_cdar (s);
459 bool bookpart_last_page = (s == systems_and_configs);
460 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
463 SCM page_num_scm = scm_from_int (page_num);
464 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
466 SCM labels = SCM_EOL;
467 if (Grob * line = unsmob_grob (scm_car (l)))
469 System *system = dynamic_cast<System*> (line);
470 labels = system->get_property ("labels");
472 else if (Prob *prob = unsmob_prob (scm_car (l)))
473 labels = prob->get_property ("labels");
475 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
476 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
480 ret = scm_cons (page, ret);
483 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
487 /* The page-turn-page-breaker needs to have a line-breaker between any two
488 columns with non-NULL page-turn-permission.
490 The optimal-breaker needs to have a line-breaker between any two columns
491 with page-break-permission = 'force.
493 By using a grob predicate, we can accommodate both of these uses.
496 Page_breaking::create_system_list ()
498 SCM specs = book_->get_system_specs ();
499 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
501 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
503 system_specs_.push_back (System_spec (ps));
507 Prob *pb = unsmob_prob (scm_car (s));
511 system_specs_.push_back (System_spec (pb));
517 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
519 SCM force_sym = ly_symbol2scm ("force");
521 chunks_.push_back (Break_position ());
522 breaks_.push_back (Break_position ());
524 for (vsize i = 0; i < system_specs_.size (); i++)
526 if (system_specs_[i].pscore_)
530 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
531 if (scm_is_number (system_count))
533 // With system-count given, the line configuration for
534 // this score is fixed. We need to ensure that chunk
535 // boundaries only occur at line breaks.
536 Constrained_breaking breaking (system_specs_[i].pscore_);
537 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
539 cols.push_back (system_specs_[i].pscore_->root_system ()->used_columns ()[0]);
540 for (vsize j = 0; j < details.size (); j++)
541 cols.push_back (details[j].last_column_);
544 cols = system_specs_[i].pscore_->root_system ()->used_columns ();
546 int last_chunk_idx = 0;
547 vector<vsize> line_breaker_columns;
548 line_breaker_columns.push_back (0);
550 for (vsize j = 1; j < cols.size (); j++)
552 bool last = (j == cols.size () - 1);
553 bool break_point = is_break (cols[j]);
554 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
555 Break_position cur_pos = Break_position (i,
556 line_breaker_columns.size (),
560 // NOTE: even in the breaks_ list, forced_line_count_
561 // refers to the number of lines between a
562 // Break_position and the start of that /chunk/. This
563 // is needed for system_count_bounds to work correctly,
564 // since it mixes Break_positions from breaks_ and
566 if (scm_is_number (system_count))
567 cur_pos.forced_line_count_ = j - last_chunk_idx;
569 if (break_point || (i == system_specs_.size () - 1 && last))
570 breaks_.push_back (cur_pos);
571 if (chunk_end || last)
573 chunks_.push_back (cur_pos);
577 if ((break_point || chunk_end) && !last)
578 line_breaker_columns.push_back (j);
580 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
584 /* TODO: we want some way of applying Break_p to a prob? */
585 if (i == system_specs_.size () - 1)
586 breaks_.push_back (Break_position (i));
588 chunks_.push_back (Break_position (i));
590 /* FIXME: shouldn't we push a Null_breaker or similar dummy
592 line_breaking_.push_back (Constrained_breaking (NULL));
597 vector<Break_position>
598 Page_breaking::chunk_list (vsize start_index, vsize end_index)
600 Break_position start = breaks_[start_index];
601 Break_position end = breaks_[end_index];
604 for (; i < chunks_.size () && chunks_[i] <= start; i++)
607 vector<Break_position> ret;
608 ret.push_back (start);
609 for (; i < chunks_.size () && chunks_[i] < end; i++)
610 ret.push_back (chunks_[i]);
616 Page_breaking::min_system_count (vsize start, vsize end)
618 vector<Break_position> chunks = chunk_list (start, end);
619 Line_division div = system_count_bounds (chunks, true);
622 for (vsize i = 0; i < div.size (); i++)
628 Page_breaking::max_system_count (vsize start, vsize end)
630 vector<Break_position> chunks = chunk_list (start, end);
631 Line_division div = system_count_bounds (chunks, false);
634 for (vsize i = 0; i < div.size (); i++)
639 Page_breaking::Line_division
640 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
643 assert (chunks.size () >= 2);
646 ret.resize (chunks.size () - 1, 1);
648 for (vsize i = 0; i + 1 < chunks.size (); i++)
650 vsize sys = next_system (chunks[i]);
652 if (chunks[i+1].forced_line_count_)
653 ret[i] = chunks[i+1].forced_line_count_;
654 else if (system_specs_[sys].pscore_)
658 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
660 ? line_breaking_[sys].min_system_count (start, end)
661 : line_breaking_[sys].max_system_count (start, end);
669 Page_breaking::set_current_breakpoints (vsize start,
672 Line_division lower_bound,
673 Line_division upper_bound)
675 system_count_ = system_count;
676 current_chunks_ = chunk_list (start, end);
677 current_start_breakpoint_ = start;
678 current_end_breakpoint_ = end;
679 clear_line_details_cache ();
681 if (!lower_bound.size ())
682 lower_bound = system_count_bounds (current_chunks_, true);
683 if (!upper_bound.size ())
684 upper_bound = system_count_bounds (current_chunks_, false);
686 assert (lower_bound.size () == current_chunks_.size () - 1);
687 assert (upper_bound.size () == current_chunks_.size () - 1);
689 Line_division work_in_progress;
690 current_configurations_.clear ();
691 line_divisions_rec (system_count,
696 /* we only consider a constant number of configurations. Otherwise,
697 this becomes slow when there are many small scores. The constant
698 5 is somewhat arbitrary. */
699 if (current_configurations_.size () > 5)
701 vector<pair<Real,vsize> > dems_and_indices;
703 for (vsize i = 0; i < current_configurations_.size (); i++)
705 cache_line_details (i);
707 for (vsize j = 0; j < cached_line_details_.size (); j++)
708 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
709 + cached_line_details_[j].break_penalty_;
711 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
713 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
715 vector<Line_division> best_5_configurations;
716 for (vsize i = 0; i < 5; i++)
717 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
719 clear_line_details_cache ();
720 current_configurations_ = best_5_configurations;
725 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
727 current_chunks_ = chunk_list (start, end);
728 current_start_breakpoint_ = start;
729 current_end_breakpoint_ = end;
730 clear_line_details_cache ();
734 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
736 vsize sys = next_system (current_chunks_[i]);
738 if (current_chunks_[i+1].forced_line_count_)
739 div.push_back (current_chunks_[i+1].forced_line_count_);
740 else if (system_specs_[sys].pscore_)
742 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
743 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
748 system_count_ += div.back ();
750 current_configurations_.clear ();
751 current_configurations_.push_back (div);
755 Page_breaking::current_configuration_count () const
757 return current_configurations_.size ();
761 Page_breaking::cache_line_details (vsize configuration_index)
763 if (cached_configuration_index_ != configuration_index)
765 cached_configuration_index_ = configuration_index;
767 Line_division &div = current_configurations_[configuration_index];
768 uncompressed_line_details_.clear ();
769 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
771 vsize sys = next_system (current_chunks_[i]);
772 if (system_specs_[sys].pscore_)
776 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
778 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
779 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
783 assert (div[i] == 1);
784 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_, book_->paper_));
787 cached_line_details_ = compress_lines (uncompressed_line_details_);
792 Page_breaking::clear_line_details_cache ()
794 cached_configuration_index_ = VPOS;
795 cached_line_details_.clear ();
796 uncompressed_line_details_.clear ();
800 Page_breaking::line_divisions_rec (vsize system_count,
801 Line_division const &min_sys,
802 Line_division const &max_sys,
803 Line_division *cur_division)
805 vsize my_index = cur_division->size ();
806 vsize others_min = 0;
807 vsize others_max = 0;
809 for (vsize i = my_index + 1; i < min_sys.size (); i++)
811 others_min += min_sys[i];
812 others_max += max_sys[i];
814 others_max = min (others_max, system_count);
815 vsize real_min = max (min_sys[my_index], system_count - others_max);
816 vsize real_max = min (max_sys[my_index], system_count - others_min);
818 if (real_min > real_max || real_min <= 0)
820 /* this should never happen within a recursive call. If it happens
821 at all, it means that we were called with an unsolvable problem
822 and we should return an empty result */
823 assert (my_index == 0);
827 for (vsize i = real_min; i <= real_max; i++)
829 cur_division->push_back (i);
830 if (my_index == min_sys.size () - 1)
831 current_configurations_.push_back (*cur_division);
833 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
834 cur_division->pop_back ();
839 Page_breaking::compute_line_heights ()
841 Real prev_hanging = 0;
842 Real prev_hanging_begin = 0;
843 Real prev_hanging_rest = 0;
844 for (vsize i = 0; i < cached_line_details_.size (); i++)
846 Line_shape shape = cached_line_details_[i].shape_;
847 Real a = shape.begin_[UP];
848 Real b = shape.rest_[UP];
849 Real midline_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
850 Real hanging_begin = midline_hanging - shape.begin_[DOWN];
851 Real hanging_rest = midline_hanging - shape.rest_[DOWN];
852 Real hanging = max (hanging_begin, hanging_rest);
853 cached_line_details_[i].tallness_ = hanging - prev_hanging;
854 prev_hanging = hanging;
855 prev_hanging_begin = hanging_begin;
856 prev_hanging_rest = hanging_rest;
861 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
864 vsize page_starter = 0;
865 Real cur_rod_height = 0;
866 Real cur_spring_height = 0;
867 Real cur_page_height = page_height (first_page_num, false);
870 cache_line_details (configuration);
871 compute_line_heights ();
873 if (cached_line_details_.size ())
874 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
876 for (vsize i = 0; i < cached_line_details_.size (); i++)
880 if (cur_rod_height > 0)
882 padding = cached_line_details_[i].title_ ?
883 cached_line_details_[i-1].title_padding_ :
884 cached_line_details_[i-1].padding_;
885 ext_len = cached_line_details_[i].tallness_;
889 ext_len = cached_line_details_[i].full_height();
891 Real next_rod_height = cur_rod_height + ext_len + padding;
892 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
893 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
894 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
895 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
897 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
898 || too_many_lines (next_line_count)
900 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
902 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
903 cur_rod_height = cached_line_details_[i].full_height();
904 cur_spring_height = cached_line_details_[i].space_;
907 cur_page_height = page_height (first_page_num + ret, false);
908 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
914 cur_rod_height = next_rod_height;
915 cur_spring_height = next_spring_height;
916 line_count = next_line_count;
920 /* there are two potential problems with the last page (because we didn't know
921 it was the last page until after we managed to fit all the systems to it):
922 - we are ragged-last but the last page has a compressed spring
923 - the value returned by page_height (num, true) is smaller than the
924 value returned by page_height (num, false) and it causes the page not to
927 In either case, we just need to add one more page. This is because the last
928 line will always fit on the extra page and by adding one more page to the
929 end, the previous page is no longer the last page, so our previous
930 calculations that treated it as a non-last page were ok.
933 cur_page_height = page_height (first_page_num + ret - 1, true);
934 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
935 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
937 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
938 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
939 && cur_height > cur_page_height
940 /* don't increase the page count if the last page had only one system */
941 && cur_rod_height > cached_line_details_.back ().full_height ())
944 assert (ret <= cached_line_details_.size ());
948 // If systems_per_page_ is positive, we don't really try to space on N pages;
949 // we just put the requested number of systems on each page and penalize
950 // if the result doesn't have N pages.
952 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
954 Page_spacing_result ret;
956 if (systems_per_page_ > 0)
958 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
959 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
963 cache_line_details (configuration);
964 bool valid_n = (n >= min_page_count (configuration, first_page_num)
965 && n <= cached_line_details_.size ());
968 programming_error ("number of pages is out of bounds");
970 if (n == 1 && valid_n)
971 ret = space_systems_on_1_page (cached_line_details_,
972 page_height (first_page_num, is_last ()),
973 ragged () || (is_last () && ragged_last ()));
974 else if (n == 2 && valid_n)
975 ret = space_systems_on_2_pages (configuration, first_page_num);
978 Page_spacer ps (cached_line_details_, first_page_num, this);
982 return finalize_spacing_result (configuration, ret);
986 Page_breaking::blank_page_penalty () const
991 penalty_sym = ly_symbol2scm ("blank-last-page-force");
992 else if (ends_score ())
993 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
995 penalty_sym = ly_symbol2scm ("blank-page-force");
997 Break_position const &pos = breaks_[current_end_breakpoint_];
998 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
999 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1001 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1004 // If systems_per_page_ is positive, we don't really try to space on N
1005 // or N+1 pages; see the comment to space_systems_on_n_pages.
1007 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1008 Real penalty_for_fewer_pages)
1010 Page_spacing_result n_res;
1011 Page_spacing_result m_res;
1013 if (systems_per_page_ > 0)
1015 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1016 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
1020 cache_line_details (configuration);
1021 vsize min_p_count = min_page_count (configuration, first_page_num);
1022 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1025 programming_error ("both page counts are out of bounds");
1027 if (n == 1 && valid_n)
1029 bool rag = ragged () || (is_last () && ragged_last ());
1030 Real height = page_height (first_page_num, is_last ());
1032 if (1 >= min_p_count)
1033 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1034 if (1 < cached_line_details_.size ())
1035 m_res = space_systems_on_2_pages (configuration, first_page_num);
1039 Page_spacer ps (cached_line_details_, first_page_num, this);
1041 if (n >= min_p_count || !valid_n)
1042 n_res = ps.solve (n);
1043 if (n < cached_line_details_.size () || !valid_n)
1044 m_res = ps.solve (n+1);
1047 m_res = finalize_spacing_result (configuration, m_res);
1048 n_res = finalize_spacing_result (configuration, n_res);
1050 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1051 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1053 if (n_res.force_.size ())
1054 n_res.force_.back () += penalty_for_fewer_pages;
1056 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1060 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1062 vsize min_p_count = min_page_count (configuration, first_page_num);
1064 cache_line_details (configuration);
1065 Page_spacer ps (cached_line_details_, first_page_num, this);
1066 Page_spacing_result best = ps.solve (min_p_count);
1068 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1070 Page_spacing_result cur = ps.solve (i);
1071 if (cur.demerits_ < best.demerits_)
1075 Page_spacing_result ret = finalize_spacing_result (configuration, best);
1080 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1081 vsize first_page_num)
1083 Page_spacing_result res;
1084 Page_spacing space (page_height (first_page_num, false), this);
1087 vsize page_first_line = 0;
1089 cache_line_details (configuration);
1090 while (line < cached_line_details_.size ())
1094 space.resize (page_height (first_page_num + page, false));
1096 int system_count_on_this_page = 0;
1097 while (system_count_on_this_page < systems_per_page_
1098 && line < cached_line_details_.size ())
1100 Line_details const &cur_line = cached_line_details_[line];
1101 space.append_system (cur_line);
1102 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1105 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1109 res.systems_per_page_.push_back (line - page_first_line);
1111 res.force_.push_back (space.force_);
1112 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1113 if (system_count_on_this_page != systems_per_page_)
1115 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1116 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1117 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1120 page_first_line = line;
1123 /* Recalculate forces for the last page because we know now that is
1124 really the last page. */
1125 space.resize (page_height (first_page_num + page, true));
1126 res.force_.back () = space.force_;
1127 return finalize_spacing_result (configuration, res);
1131 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1133 // TODO: add support for min/max-systems-per-page.
1134 Page_spacing_result res;
1136 vsize page_first_line = 0;
1137 Page_spacing space (page_height (first_page_num, false), this);
1139 cache_line_details (configuration);
1140 for (vsize line = 0; line < cached_line_details_.size (); line++)
1142 Real prev_force = space.force_;
1143 space.append_system (cached_line_details_[line]);
1144 if ((line > page_first_line)
1145 && (isinf (space.force_)
1147 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1149 res.systems_per_page_.push_back (line - page_first_line);
1150 res.force_.push_back (prev_force);
1151 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1153 space.resize (page_height (first_page_num + page, false));
1155 space.append_system (cached_line_details_[line]);
1156 page_first_line = line;
1159 if (line == cached_line_details_.size () - 1)
1161 /* This is the last line */
1162 /* When the last page height was computed, we did not know yet that it
1163 * was the last one. If the systems put on it don't fit anymore, the last
1164 * system is moved to a new page */
1165 space.resize (page_height (first_page_num + page, true));
1166 if ((line > page_first_line) && (isinf (space.force_)))
1168 res.systems_per_page_.push_back (line - page_first_line);
1169 res.force_.push_back (prev_force);
1170 /* the last page containing the last line */
1171 space.resize (page_height (first_page_num + page + 1, true));
1173 space.append_system (cached_line_details_[line]);
1174 res.systems_per_page_.push_back (1);
1175 res.force_.push_back (space.force_);
1176 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1177 res.penalty_ += cached_line_details_[line].page_penalty_;
1181 res.systems_per_page_.push_back (line + 1 - page_first_line);
1182 res.force_.push_back (space.force_);
1183 res.penalty_ += cached_line_details_[line].page_penalty_;
1187 return finalize_spacing_result (configuration, res);
1190 /* Calculate demerits and fix res.systems_per_page_ so that
1191 it refers to the original line numbers, not the ones given by compress_lines (). */
1193 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1195 if (res.force_.empty ())
1198 cache_line_details (configuration);
1199 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1201 Real line_force = 0;
1202 Real line_penalty = 0;
1203 Real page_demerits = res.penalty_;
1204 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1206 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1208 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1209 line_penalty += uncompressed_line_details_[i].break_penalty_;
1212 for (vsize i = 0; i < res.force_.size (); i++)
1214 Real f = res.force_[i];
1216 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1219 /* for a while we tried averaging page and line forces across pages instead
1220 of summing them, but it caused a problem: if there is a single page
1221 with a very bad page force (for example because of a forced page break),
1222 the page breaker will put in a _lot_ of pages so that the bad force
1223 becomes averaged out over many pages. */
1224 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1229 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1230 are by far the most common cases, we have special functions for them.
1232 space_systems_on_1_page has a different calling convention than most of the
1233 space_systems functions. This is because space_systems_on_1_page is (unlike
1234 the other space_systems functions) sometimes called on subsets of a full
1237 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1239 Page_spacing space (page_height, this);
1240 Page_spacing_result ret;
1243 for (vsize i = 0; i < lines.size (); i++)
1245 space.append_system (lines[i]);
1246 line_count += lines[i].compressed_nontitle_lines_count_;
1249 ret.systems_per_page_.push_back (lines.size ());
1250 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1251 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1252 ret.system_count_status_ |= line_count_status (line_count);
1254 /* don't do finalize_spacing_result () because we are only an internal function */
1259 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1261 Real page1_height = page_height (first_page_num, false);
1262 Real page2_height = page_height (first_page_num + 1, is_last ());
1263 bool ragged1 = ragged ();
1264 bool ragged2 = ragged () || (is_last () && ragged_last ());
1266 /* if there is a forced break, this reduces to 2 1-page problems */
1267 cache_line_details (configuration);
1268 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1269 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1271 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1272 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1273 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1274 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1276 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1277 p1.force_.push_back (p2.force_[0]);
1278 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1282 vector<Real> page1_force;
1283 vector<Real> page2_force;
1285 // page1_penalty and page2_penalty store the penalties based
1286 // on min-systems-per-page and max-systems-per-page.
1287 vector<Real> page1_penalty;
1288 vector<Real> page2_penalty;
1290 // page1_status and page2_status keep track of whether the min-systems-per-page
1291 // and max-systems-per-page constraints are satisfied.
1292 vector<int> page1_status;
1293 vector<int> page2_status;
1295 Page_spacing page1 (page1_height, this);
1296 Page_spacing page2 (page2_height, this);
1297 int page1_line_count = 0;
1298 int page2_line_count = 0;
1300 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1301 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1302 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1303 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1304 page1_status.resize (cached_line_details_.size () - 1, 0);
1305 page2_status.resize (cached_line_details_.size () - 1, 0);
1307 /* find the page 1 and page 2 forces for each page-breaking position */
1308 for (vsize i = 0; i < page1_force.size (); i++)
1310 page1.append_system (cached_line_details_[i]);
1311 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1312 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1313 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1315 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1316 page1_penalty[i] = line_count_penalty (page1_line_count);
1317 page1_status[i] = line_count_status (page1_line_count);
1320 page2_force[page2_force.size () - 1 - i] =
1321 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1323 page2_force[page2_force.size () - 1 - i] = page2.force_;
1324 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1325 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1328 /* find the position that minimises the sum of the page forces */
1329 vsize best_sys_count = 1;
1330 Real best_demerits = infinity_f;
1331 for (vsize i = 0; i < page1_force.size (); i++)
1333 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1335 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1336 // constraints. That is, we penalize harshly when they don't happen
1337 // but we don't completely reject.
1339 + page1_penalty[i] + page2_penalty[i]
1340 + cached_line_details_[i+1].page_penalty_
1341 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1342 if (dem < best_demerits)
1344 best_demerits = dem;
1345 best_sys_count = i+1;
1349 Page_spacing_result ret;
1350 ret.systems_per_page_.push_back (best_sys_count);
1351 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1352 ret.force_.push_back (page1_force[best_sys_count-1]);
1353 ret.force_.push_back (page2_force[best_sys_count-1]);
1354 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1355 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1356 + cached_line_details_.back ().page_penalty_
1357 + cached_line_details_.back ().turn_penalty_
1358 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1360 /* don't do finalize_spacing_result () because we are only an internal function */
1365 Page_breaking::all_lines_stretched (vsize configuration)
1367 cache_line_details (configuration);
1368 for (vsize i = 0; i < cached_line_details_.size (); i++)
1369 if (cached_line_details_[i].force_ < 0)
1375 Page_breaking::Line_division
1376 Page_breaking::current_configuration (vsize configuration_index) const
1378 return current_configurations_[configuration_index];
1382 Page_breaking::is_last () const
1384 return current_end_breakpoint_ == last_break_position ();
1388 Page_breaking::ends_score () const
1390 return breaks_[current_end_breakpoint_].score_ender_;
1394 Page_breaking::last_break_position () const
1396 return breaks_.size () - 1;
1399 // This gives the minimum distance between the top of the
1400 // printable area (ie. the bottom of the top-margin) and
1401 // the extent box of the topmost system.
1403 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1405 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1407 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1409 Real min_distance = -infinity_f;
1412 Page_layout_problem::read_spacing_spec (first_system_spacing,
1414 ly_symbol2scm ("minimum-distance"));
1415 Page_layout_problem::read_spacing_spec (first_system_spacing,
1417 ly_symbol2scm ("padding"));
1419 // FIXME: take into account the height of the header
1420 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1421 return max (0.0, max (padding, min_distance - translate));
1425 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1427 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1428 Real min_distance = -infinity_f;
1431 Page_layout_problem::read_spacing_spec (last_system_spacing,
1433 ly_symbol2scm ("minimum-distance"));
1434 Page_layout_problem::read_spacing_spec (last_system_spacing,
1436 ly_symbol2scm ("padding"));
1438 // FIXME: take into account the height of the footer
1439 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1440 return max (0.0, max (padding, min_distance + translate));
1444 Page_breaking::orphan_penalty () const
1446 return orphan_penalty_;