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 compute_line_heights ();
1141 for (vsize line = 0; line < cached_line_details_.size (); line++)
1143 Real prev_force = space.force_;
1144 space.append_system (cached_line_details_[line]);
1145 if ((line > page_first_line)
1146 && (isinf (space.force_)
1148 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1150 res.systems_per_page_.push_back (line - page_first_line);
1151 res.force_.push_back (prev_force);
1152 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1154 space.resize (page_height (first_page_num + page, false));
1156 space.append_system (cached_line_details_[line]);
1157 page_first_line = line;
1160 if (line == cached_line_details_.size () - 1)
1162 /* This is the last line */
1163 /* When the last page height was computed, we did not know yet that it
1164 * was the last one. If the systems put on it don't fit anymore, the last
1165 * system is moved to a new page */
1166 space.resize (page_height (first_page_num + page, true));
1167 if ((line > page_first_line) && (isinf (space.force_)))
1169 res.systems_per_page_.push_back (line - page_first_line);
1170 res.force_.push_back (prev_force);
1171 /* the last page containing the last line */
1172 space.resize (page_height (first_page_num + page + 1, true));
1174 space.append_system (cached_line_details_[line]);
1175 res.systems_per_page_.push_back (1);
1176 res.force_.push_back (space.force_);
1177 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1178 res.penalty_ += cached_line_details_[line].page_penalty_;
1182 res.systems_per_page_.push_back (line + 1 - page_first_line);
1183 res.force_.push_back (space.force_);
1184 res.penalty_ += cached_line_details_[line].page_penalty_;
1188 return finalize_spacing_result (configuration, res);
1191 /* Calculate demerits and fix res.systems_per_page_ so that
1192 it refers to the original line numbers, not the ones given by compress_lines (). */
1194 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1196 if (res.force_.empty ())
1199 cache_line_details (configuration);
1200 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1202 Real line_force = 0;
1203 Real line_penalty = 0;
1204 Real page_demerits = res.penalty_;
1205 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1207 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1209 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1210 line_penalty += uncompressed_line_details_[i].break_penalty_;
1213 for (vsize i = 0; i < res.force_.size (); i++)
1215 Real f = res.force_[i];
1217 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1220 /* for a while we tried averaging page and line forces across pages instead
1221 of summing them, but it caused a problem: if there is a single page
1222 with a very bad page force (for example because of a forced page break),
1223 the page breaker will put in a _lot_ of pages so that the bad force
1224 becomes averaged out over many pages. */
1225 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1230 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1231 are by far the most common cases, we have special functions for them.
1233 space_systems_on_1_page has a different calling convention than most of the
1234 space_systems functions. This is because space_systems_on_1_page is (unlike
1235 the other space_systems functions) sometimes called on subsets of a full
1238 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1240 Page_spacing space (page_height, this);
1241 Page_spacing_result ret;
1244 for (vsize i = 0; i < lines.size (); i++)
1246 space.append_system (lines[i]);
1247 line_count += lines[i].compressed_nontitle_lines_count_;
1250 ret.systems_per_page_.push_back (lines.size ());
1251 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1252 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1253 ret.system_count_status_ |= line_count_status (line_count);
1255 /* don't do finalize_spacing_result () because we are only an internal function */
1260 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1262 Real page1_height = page_height (first_page_num, false);
1263 Real page2_height = page_height (first_page_num + 1, is_last ());
1264 bool ragged1 = ragged ();
1265 bool ragged2 = ragged () || (is_last () && ragged_last ());
1267 /* if there is a forced break, this reduces to 2 1-page problems */
1268 cache_line_details (configuration);
1269 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1270 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1272 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1273 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1274 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1275 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1277 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1278 p1.force_.push_back (p2.force_[0]);
1279 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1283 vector<Real> page1_force;
1284 vector<Real> page2_force;
1286 // page1_penalty and page2_penalty store the penalties based
1287 // on min-systems-per-page and max-systems-per-page.
1288 vector<Real> page1_penalty;
1289 vector<Real> page2_penalty;
1291 // page1_status and page2_status keep track of whether the min-systems-per-page
1292 // and max-systems-per-page constraints are satisfied.
1293 vector<int> page1_status;
1294 vector<int> page2_status;
1296 Page_spacing page1 (page1_height, this);
1297 Page_spacing page2 (page2_height, this);
1298 int page1_line_count = 0;
1299 int page2_line_count = 0;
1301 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1302 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1303 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1304 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1305 page1_status.resize (cached_line_details_.size () - 1, 0);
1306 page2_status.resize (cached_line_details_.size () - 1, 0);
1308 /* find the page 1 and page 2 forces for each page-breaking position */
1309 for (vsize i = 0; i < page1_force.size (); i++)
1311 page1.append_system (cached_line_details_[i]);
1312 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1313 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1314 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1316 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1317 page1_penalty[i] = line_count_penalty (page1_line_count);
1318 page1_status[i] = line_count_status (page1_line_count);
1321 page2_force[page2_force.size () - 1 - i] =
1322 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1324 page2_force[page2_force.size () - 1 - i] = page2.force_;
1325 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1326 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1329 /* find the position that minimises the sum of the page forces */
1330 vsize best_sys_count = 1;
1331 Real best_demerits = infinity_f;
1332 for (vsize i = 0; i < page1_force.size (); i++)
1334 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1336 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1337 // constraints. That is, we penalize harshly when they don't happen
1338 // but we don't completely reject.
1340 + page1_penalty[i] + page2_penalty[i]
1341 + cached_line_details_[i+1].page_penalty_
1342 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1343 if (dem < best_demerits)
1345 best_demerits = dem;
1346 best_sys_count = i+1;
1350 Page_spacing_result ret;
1351 ret.systems_per_page_.push_back (best_sys_count);
1352 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1353 ret.force_.push_back (page1_force[best_sys_count-1]);
1354 ret.force_.push_back (page2_force[best_sys_count-1]);
1355 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1356 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1357 + cached_line_details_.back ().page_penalty_
1358 + cached_line_details_.back ().turn_penalty_
1359 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1361 /* don't do finalize_spacing_result () because we are only an internal function */
1366 Page_breaking::all_lines_stretched (vsize configuration)
1368 cache_line_details (configuration);
1369 for (vsize i = 0; i < cached_line_details_.size (); i++)
1370 if (cached_line_details_[i].force_ < 0)
1376 Page_breaking::Line_division
1377 Page_breaking::current_configuration (vsize configuration_index) const
1379 return current_configurations_[configuration_index];
1383 Page_breaking::is_last () const
1385 return current_end_breakpoint_ == last_break_position ();
1389 Page_breaking::ends_score () const
1391 return breaks_[current_end_breakpoint_].score_ender_;
1395 Page_breaking::last_break_position () const
1397 return breaks_.size () - 1;
1400 // This gives the minimum distance between the top of the
1401 // printable area (ie. the bottom of the top-margin) and
1402 // the extent box of the topmost system.
1404 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1406 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1408 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1410 Real min_distance = -infinity_f;
1413 Page_layout_problem::read_spacing_spec (first_system_spacing,
1415 ly_symbol2scm ("minimum-distance"));
1416 Page_layout_problem::read_spacing_spec (first_system_spacing,
1418 ly_symbol2scm ("padding"));
1420 // FIXME: take into account the height of the header
1421 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1422 return max (0.0, max (padding, min_distance - translate));
1426 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1428 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1429 Real min_distance = -infinity_f;
1432 Page_layout_problem::read_spacing_spec (last_system_spacing,
1434 ly_symbol2scm ("minimum-distance"));
1435 Page_layout_problem::read_spacing_spec (last_system_spacing,
1437 ly_symbol2scm ("padding"));
1439 // FIXME: take into account the height of the footer
1440 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1441 return max (0.0, max (padding, min_distance + translate));
1445 Page_breaking::orphan_penalty () const
1447 return orphan_penalty_;