2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2009 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.extent_[DOWN] = old.extent_[DOWN];
105 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + padding;
106 compressed.space_ += old.space_;
107 compressed.inverse_hooke_ += old.inverse_hooke_;
109 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
110 compressed.compressed_nontitle_lines_count_ =
111 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
113 // compressed.title_ is true if and only if the first of its
114 // compressed lines was a title.
115 compressed.title_ = old.title_;
116 ret.back () = compressed;
120 ret.push_back (orig[i]);
121 ret.back ().force_ = 0;
127 /* translate the number of systems-per-page into something meaningful for
128 the uncompressed lines.
131 uncompress_solution (vector<vsize> const &systems_per_page,
132 vector<Line_details> const &compressed)
137 for (vsize i = 0; i < systems_per_page.size (); i++)
139 int compressed_count = 0;
140 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
141 compressed_count += compressed[j].compressed_lines_count_ - 1;
143 ret.push_back (systems_per_page[i] + compressed_count);
144 start_sys += systems_per_page[i];
149 /* for Page_breaking, the start index (when we are dealing with the stuff
150 between a pair of breakpoints) refers to the break_ index of the end of
151 the previous page. So the system index of the start of the current page
152 could either be the same as the end of the previous page or one more than
155 /* Turn a break index into the sys index that starts the next page */
157 Page_breaking::next_system (Break_position const &break_pos) const
159 vsize sys = break_pos.system_spec_index_;
161 if (sys == VPOS) /* beginning of the book */
163 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
164 return sys; /* the score overflows the previous page */
165 return sys + 1; /* this page starts with a new System_spec */
168 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
172 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
173 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
174 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
175 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
176 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
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::min_page_count (vsize configuration, vsize first_page_num)
842 vsize page_starter = 0;
843 Real cur_rod_height = 0;
844 Real cur_spring_height = 0;
845 Real cur_page_height = page_height (first_page_num, false);
848 cache_line_details (configuration);
850 if (cached_line_details_.size ())
851 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
853 for (vsize i = 0; i < cached_line_details_.size (); i++)
855 Real ext_len = cached_line_details_[i].extent_.length ();
857 if (cur_rod_height > 0)
858 padding = cached_line_details_[i].title_ ?
859 cached_line_details_[i-1].title_padding_ : cached_line_details_[i-1].padding_;
861 Real next_rod_height = cur_rod_height + ext_len + padding;
862 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
863 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
864 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
865 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
867 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
868 || too_many_lines (next_line_count)
870 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
872 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
873 cur_rod_height = ext_len;
874 cur_spring_height = cached_line_details_[i].space_;
877 cur_page_height = page_height (first_page_num + ret, false);
878 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
884 cur_rod_height = next_rod_height;
885 cur_spring_height = next_spring_height;
886 line_count = next_line_count;
890 /* there are two potential problems with the last page (because we didn't know
891 it was the last page until after we managed to fit all the systems to it):
892 - we are ragged-last but the last page has a compressed spring
893 - the value returned by page_height (num, true) is smaller than the
894 value returned by page_height (num, false) and it causes the page not to
897 In either case, we just need to add one more page. This is because the last
898 line will always fit on the extra page and by adding one more page to the
899 end, the previous page is no longer the last page, so our previous
900 calculations that treated it as a non-last page were ok.
903 cur_page_height = page_height (first_page_num + ret - 1, true);
904 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
905 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
907 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
908 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
909 && cur_height > cur_page_height
910 /* don't increase the page count if the last page had only one system */
911 && cur_rod_height > cached_line_details_.back ().extent_.length ())
914 assert (ret <= cached_line_details_.size ());
918 // If systems_per_page_ is positive, we don't really try to space on N pages;
919 // we just put the requested number of systems on each page and penalize
920 // if the result doesn't have N pages.
922 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
924 Page_spacing_result ret;
926 if (systems_per_page_ > 0)
928 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
929 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
933 cache_line_details (configuration);
934 bool valid_n = (n >= min_page_count (configuration, first_page_num)
935 && n <= cached_line_details_.size ());
938 programming_error ("number of pages is out of bounds");
940 if (n == 1 && valid_n)
941 ret = space_systems_on_1_page (cached_line_details_,
942 page_height (first_page_num, is_last ()),
943 ragged () || (is_last () && ragged_last ()));
944 else if (n == 2 && valid_n)
945 ret = space_systems_on_2_pages (configuration, first_page_num);
948 Page_spacer ps (cached_line_details_, first_page_num, this);
952 return finalize_spacing_result (configuration, ret);
956 Page_breaking::blank_page_penalty () const
961 penalty_sym = ly_symbol2scm ("blank-last-page-force");
962 else if (ends_score ())
963 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
965 penalty_sym = ly_symbol2scm ("blank-page-force");
967 Break_position const &pos = breaks_[current_end_breakpoint_];
968 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
969 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
971 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
974 // If systems_per_page_ is positive, we don't really try to space on N
975 // or N+1 pages; see the comment to space_systems_on_n_pages.
977 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
979 Page_spacing_result n_res;
980 Page_spacing_result m_res;
982 if (systems_per_page_ > 0)
984 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
985 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
989 cache_line_details (configuration);
990 vsize min_p_count = min_page_count (configuration, first_page_num);
991 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
994 programming_error ("both page counts are out of bounds");
996 if (n == 1 && valid_n)
998 bool rag = ragged () || (is_last () && ragged_last ());
999 Real height = page_height (first_page_num, is_last ());
1001 if (1 >= min_p_count)
1002 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1003 if (1 < cached_line_details_.size ())
1004 m_res = space_systems_on_2_pages (configuration, first_page_num);
1008 Page_spacer ps (cached_line_details_, first_page_num, this);
1010 if (n >= min_p_count || !valid_n)
1011 n_res = ps.solve (n);
1012 if (n < cached_line_details_.size () || !valid_n)
1013 m_res = ps.solve (n+1);
1016 m_res = finalize_spacing_result (configuration, m_res);
1017 n_res = finalize_spacing_result (configuration, n_res);
1019 Real penalty = blank_page_penalty ();
1020 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1021 n_res.demerits_ += penalty * page_spacing_weight;
1023 if (n_res.force_.size ())
1024 n_res.force_.back () += penalty;
1026 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1030 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1032 vsize min_p_count = min_page_count (configuration, first_page_num);
1033 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1034 Real odd_pages_penalty = blank_page_penalty () * page_spacing_weight;
1036 cache_line_details (configuration);
1037 Page_spacer ps (cached_line_details_, first_page_num, this);
1038 Page_spacing_result best = ps.solve (min_p_count);
1039 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
1040 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
1042 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1044 Page_spacing_result cur = ps.solve (i);
1045 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
1046 if (cur.demerits_ < best.demerits_)
1050 Page_spacing_result ret = finalize_spacing_result (configuration, best);
1051 ret.demerits_ += (ret.force_.size () % 2) ? odd_pages_penalty : 0;
1052 if (ret.force_.size ())
1053 ret.force_.back () += odd_pages_penalty;
1058 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1059 vsize first_page_num)
1061 Page_spacing_result res;
1062 Page_spacing space (page_height (first_page_num, false), this);
1065 vsize page_first_line = 0;
1067 cache_line_details (configuration);
1068 while (line < cached_line_details_.size ())
1072 space.resize (page_height (first_page_num + page, false));
1074 int system_count_on_this_page = 0;
1075 while (system_count_on_this_page < systems_per_page_
1076 && line < cached_line_details_.size ())
1078 Line_details const &cur_line = cached_line_details_[line];
1079 space.append_system (cur_line);
1080 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1083 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1087 res.systems_per_page_.push_back (line - page_first_line);
1089 res.force_.push_back (space.force_);
1090 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1091 if (system_count_on_this_page != systems_per_page_)
1093 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1094 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1095 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1098 page_first_line = line;
1101 /* Recalculate forces for the last page because we know now that is
1102 really the last page. */
1103 space.resize (page_height (first_page_num + page, true));
1104 res.force_.back () = space.force_;
1105 return finalize_spacing_result (configuration, res);
1109 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1111 // TODO: add support for min/max-systems-per-page.
1112 Page_spacing_result res;
1114 vsize page_first_line = 0;
1115 Page_spacing space (page_height (first_page_num, false), this);
1117 cache_line_details (configuration);
1118 for (vsize line = 0; line < cached_line_details_.size (); line++)
1120 Real prev_force = space.force_;
1121 space.append_system (cached_line_details_[line]);
1122 if ((line > page_first_line)
1123 && (isinf (space.force_)
1125 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1127 res.systems_per_page_.push_back (line - page_first_line);
1128 res.force_.push_back (prev_force);
1129 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1131 space.resize (page_height (first_page_num + page, false));
1133 space.append_system (cached_line_details_[line]);
1134 page_first_line = line;
1137 if (line == cached_line_details_.size () - 1)
1139 /* This is the last line */
1140 /* When the last page height was computed, we did not know yet that it
1141 * was the last one. If the systems put on it don't fit anymore, the last
1142 * system is moved to a new page */
1143 space.resize (page_height (first_page_num + page, true));
1144 if ((line > page_first_line) && (isinf (space.force_)))
1146 res.systems_per_page_.push_back (line - page_first_line);
1147 res.force_.push_back (prev_force);
1148 /* the last page containing the last line */
1149 space.resize (page_height (first_page_num + page + 1, true));
1151 space.append_system (cached_line_details_[line]);
1152 res.systems_per_page_.push_back (1);
1153 res.force_.push_back (space.force_);
1154 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1155 res.penalty_ += cached_line_details_[line].page_penalty_;
1159 res.systems_per_page_.push_back (line + 1 - page_first_line);
1160 res.force_.push_back (space.force_);
1161 res.penalty_ += cached_line_details_[line].page_penalty_;
1165 return finalize_spacing_result (configuration, res);
1168 /* Calculate demerits and fix res.systems_per_page_ so that
1169 it refers to the original line numbers, not the ones given by compress_lines (). */
1171 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1173 if (res.force_.empty ())
1176 cache_line_details (configuration);
1177 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1179 Real line_force = 0;
1180 Real line_penalty = 0;
1181 Real page_demerits = res.penalty_;
1182 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1184 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1186 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1187 line_penalty += uncompressed_line_details_[i].break_penalty_;
1190 for (vsize i = 0; i < res.force_.size (); i++)
1192 Real f = res.force_[i];
1194 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1197 /* for a while we tried averaging page and line forces across pages instead
1198 of summing them, but it caused a problem: if there is a single page
1199 with a very bad page force (for example because of a forced page break),
1200 the page breaker will put in a _lot_ of pages so that the bad force
1201 becomes averaged out over many pages. */
1202 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1207 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1208 are by far the most common cases, we have special functions for them.
1210 space_systems_on_1_page has a different calling convention than most of the
1211 space_systems functions. This is because space_systems_on_1_page is (unlike
1212 the other space_systems functions) sometimes called on subsets of a full
1215 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1217 Page_spacing space (page_height, this);
1218 Page_spacing_result ret;
1221 for (vsize i = 0; i < lines.size (); i++)
1223 space.append_system (lines[i]);
1224 line_count += lines[i].compressed_nontitle_lines_count_;
1227 ret.systems_per_page_.push_back (lines.size ());
1228 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1229 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1230 ret.system_count_status_ |= line_count_status (line_count);
1232 /* don't do finalize_spacing_result () because we are only an internal function */
1237 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1239 Real page1_height = page_height (first_page_num, false);
1240 Real page2_height = page_height (first_page_num + 1, is_last ());
1241 bool ragged1 = ragged ();
1242 bool ragged2 = ragged () || (is_last () && ragged_last ());
1244 /* if there is a forced break, this reduces to 2 1-page problems */
1245 cache_line_details (configuration);
1246 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1247 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1249 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1250 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1251 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1252 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1254 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1255 p1.force_.push_back (p2.force_[0]);
1256 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1260 vector<Real> page1_force;
1261 vector<Real> page2_force;
1263 // page1_penalty and page2_penalty store the penalties based
1264 // on min-systems-per-page and max-systems-per-page.
1265 vector<Real> page1_penalty;
1266 vector<Real> page2_penalty;
1268 // page1_status and page2_status keep track of whether the min-systems-per-page
1269 // and max-systems-per-page constraints are satisfied.
1270 vector<int> page1_status;
1271 vector<int> page2_status;
1273 Page_spacing page1 (page1_height, this);
1274 Page_spacing page2 (page2_height, this);
1275 int page1_line_count = 0;
1276 int page2_line_count = 0;
1278 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1279 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1280 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1281 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1282 page1_status.resize (cached_line_details_.size () - 1, 0);
1283 page2_status.resize (cached_line_details_.size () - 1, 0);
1285 /* find the page 1 and page 2 forces for each page-breaking position */
1286 for (vsize i = 0; i < page1_force.size (); i++)
1288 page1.append_system (cached_line_details_[i]);
1289 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1290 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1291 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1293 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1294 page1_penalty[i] = line_count_penalty (page1_line_count);
1295 page1_status[i] = line_count_status (page1_line_count);
1298 page2_force[page2_force.size () - 1 - i] =
1299 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1301 page2_force[page2_force.size () - 1 - i] = page2.force_;
1302 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1303 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1306 /* find the position that minimises the sum of the page forces */
1307 vsize best_sys_count = 1;
1308 Real best_demerits = infinity_f;
1309 for (vsize i = 0; i < page1_force.size (); i++)
1311 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1313 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1314 // constraints. That is, we penalize harshly when they don't happen
1315 // but we don't completely reject.
1317 + page1_penalty[i] + page2_penalty[i]
1318 + cached_line_details_[i+1].page_penalty_
1319 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1320 if (dem < best_demerits)
1322 best_demerits = dem;
1323 best_sys_count = i+1;
1327 Page_spacing_result ret;
1328 ret.systems_per_page_.push_back (best_sys_count);
1329 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1330 ret.force_.push_back (page1_force[best_sys_count-1]);
1331 ret.force_.push_back (page2_force[best_sys_count-1]);
1332 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1333 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1334 + cached_line_details_.back ().page_penalty_
1335 + cached_line_details_.back ().turn_penalty_
1336 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1338 /* don't do finalize_spacing_result () because we are only an internal function */
1343 Page_breaking::all_lines_stretched (vsize configuration)
1345 cache_line_details (configuration);
1346 for (vsize i = 0; i < cached_line_details_.size (); i++)
1347 if (cached_line_details_[i].force_ < 0)
1353 Page_breaking::Line_division
1354 Page_breaking::current_configuration (vsize configuration_index) const
1356 return current_configurations_[configuration_index];
1360 Page_breaking::is_last () const
1362 return current_end_breakpoint_ == last_break_position ();
1366 Page_breaking::ends_score () const
1368 return breaks_[current_end_breakpoint_].score_ender_;
1372 Page_breaking::last_break_position () const
1374 return breaks_.size () - 1;
1377 // This gives the minimum distance between the top of the
1378 // printable area (ie. the bottom of the top-margin) and
1379 // the extent box of the topmost system.
1381 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1383 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1385 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1387 Real min_distance = -infinity_f;
1390 Page_layout_problem::read_spacing_spec (first_system_spacing,
1392 ly_symbol2scm ("minimum-distance"));
1393 Page_layout_problem::read_spacing_spec (first_system_spacing,
1395 ly_symbol2scm ("padding"));
1397 // FIXME: take into account the height of the header
1398 return max (0.0, max (padding, min_distance - line.extent_[UP]));
1402 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1404 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1405 Real min_distance = -infinity_f;
1408 Page_layout_problem::read_spacing_spec (last_system_spacing,
1410 ly_symbol2scm ("minimum-distance"));
1411 Page_layout_problem::read_spacing_spec (last_system_spacing,
1413 ly_symbol2scm ("padding"));
1415 // FIXME: take into account the height of the footer
1416 return max (0.0, max (padding, min_distance + line.extent_[DOWN]));