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 n_res.demerits_ += penalty;
1022 if (n_res.force_.size ())
1023 n_res.force_.back () += penalty;
1025 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1029 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1031 vsize min_p_count = min_page_count (configuration, first_page_num);
1032 Real odd_pages_penalty = blank_page_penalty ();
1034 cache_line_details (configuration);
1035 Page_spacer ps (cached_line_details_, first_page_num, this);
1036 Page_spacing_result best = ps.solve (min_p_count);
1037 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
1038 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
1040 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1042 Page_spacing_result cur = ps.solve (i);
1043 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
1044 if (cur.demerits_ < best.demerits_)
1048 return finalize_spacing_result (configuration, best);
1052 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1053 vsize first_page_num)
1055 Page_spacing_result res;
1056 Page_spacing space (page_height (first_page_num, false), this);
1059 vsize page_first_line = 0;
1061 cache_line_details (configuration);
1062 while (line < cached_line_details_.size ())
1066 space.resize (page_height (first_page_num + page, false));
1068 int system_count_on_this_page = 0;
1069 while (system_count_on_this_page < systems_per_page_
1070 && line < cached_line_details_.size ())
1072 Line_details const &cur_line = cached_line_details_[line];
1073 space.append_system (cur_line);
1074 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1077 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1081 res.systems_per_page_.push_back (line - page_first_line);
1083 res.force_.push_back (space.force_);
1084 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1085 if (system_count_on_this_page != systems_per_page_)
1087 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1088 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1089 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1092 page_first_line = line;
1095 /* Recalculate forces for the last page because we know now that is
1096 really the last page. */
1097 space.resize (page_height (first_page_num + page, true));
1098 res.force_.back () = space.force_;
1099 return finalize_spacing_result (configuration, res);
1103 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1105 // TODO: add support for min/max-systems-per-page.
1106 Page_spacing_result res;
1108 vsize page_first_line = 0;
1109 Page_spacing space (page_height (first_page_num, false), this);
1111 cache_line_details (configuration);
1112 for (vsize line = 0; line < cached_line_details_.size (); line++)
1114 Real prev_force = space.force_;
1115 space.append_system (cached_line_details_[line]);
1116 if ((line > page_first_line)
1117 && (isinf (space.force_)
1119 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1121 res.systems_per_page_.push_back (line - page_first_line);
1122 res.force_.push_back (prev_force);
1123 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1125 space.resize (page_height (first_page_num + page, false));
1127 space.append_system (cached_line_details_[line]);
1128 page_first_line = line;
1131 if (line == cached_line_details_.size () - 1)
1133 /* This is the last line */
1134 /* When the last page height was computed, we did not know yet that it
1135 * was the last one. If the systems put on it don't fit anymore, the last
1136 * system is moved to a new page */
1137 space.resize (page_height (first_page_num + page, true));
1138 if ((line > page_first_line) && (isinf (space.force_)))
1140 res.systems_per_page_.push_back (line - page_first_line);
1141 res.force_.push_back (prev_force);
1142 /* the last page containing the last line */
1143 space.resize (page_height (first_page_num + page + 1, true));
1145 space.append_system (cached_line_details_[line]);
1146 res.systems_per_page_.push_back (1);
1147 res.force_.push_back (space.force_);
1148 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1149 res.penalty_ += cached_line_details_[line].page_penalty_;
1153 res.systems_per_page_.push_back (line + 1 - page_first_line);
1154 res.force_.push_back (space.force_);
1155 res.penalty_ += cached_line_details_[line].page_penalty_;
1159 return finalize_spacing_result (configuration, res);
1162 /* Calculate demerits and fix res.systems_per_page_ so that
1163 it refers to the original line numbers, not the ones given by compress_lines (). */
1165 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1167 if (res.force_.empty ())
1170 cache_line_details (configuration);
1171 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1173 Real line_force = 0;
1174 Real line_penalty = 0;
1175 Real page_demerits = res.penalty_;
1176 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1178 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1180 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1181 line_penalty += uncompressed_line_details_[i].break_penalty_;
1184 for (vsize i = 0; i < res.force_.size (); i++)
1186 Real f = res.force_[i];
1188 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1191 /* for a while we tried averaging page and line forces across pages instead
1192 of summing them, but it caused a problem: if there is a single page
1193 with a very bad page force (for example because of a forced page break),
1194 the page breaker will put in a _lot_ of pages so that the bad force
1195 becomes averaged out over many pages. */
1196 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1201 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1202 are by far the most common cases, we have special functions for them.
1204 space_systems_on_1_page has a different calling convention than most of the
1205 space_systems functions. This is because space_systems_on_1_page is (unlike
1206 the other space_systems functions) sometimes called on subsets of a full
1209 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1211 Page_spacing space (page_height, this);
1212 Page_spacing_result ret;
1215 for (vsize i = 0; i < lines.size (); i++)
1217 space.append_system (lines[i]);
1218 line_count += lines[i].compressed_nontitle_lines_count_;
1221 ret.systems_per_page_.push_back (lines.size ());
1222 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1223 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1224 ret.system_count_status_ |= line_count_status (line_count);
1226 /* don't do finalize_spacing_result () because we are only an internal function */
1231 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1233 Real page1_height = page_height (first_page_num, false);
1234 Real page2_height = page_height (first_page_num + 1, is_last ());
1235 bool ragged1 = ragged ();
1236 bool ragged2 = ragged () || (is_last () && ragged_last ());
1238 /* if there is a forced break, this reduces to 2 1-page problems */
1239 cache_line_details (configuration);
1240 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1241 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1243 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1244 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1245 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1246 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1248 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1249 p1.force_.push_back (p2.force_[0]);
1250 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1254 vector<Real> page1_force;
1255 vector<Real> page2_force;
1257 // page1_penalty and page2_penalty store the penalties based
1258 // on min-systems-per-page and max-systems-per-page.
1259 vector<Real> page1_penalty;
1260 vector<Real> page2_penalty;
1262 // page1_status and page2_status keep track of whether the min-systems-per-page
1263 // and max-systems-per-page constraints are satisfied.
1264 vector<int> page1_status;
1265 vector<int> page2_status;
1267 Page_spacing page1 (page1_height, this);
1268 Page_spacing page2 (page2_height, this);
1269 int page1_line_count = 0;
1270 int page2_line_count = 0;
1272 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1273 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1274 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1275 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1276 page1_status.resize (cached_line_details_.size () - 1, 0);
1277 page2_status.resize (cached_line_details_.size () - 1, 0);
1279 /* find the page 1 and page 2 forces for each page-breaking position */
1280 for (vsize i = 0; i < page1_force.size (); i++)
1282 page1.append_system (cached_line_details_[i]);
1283 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1284 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1285 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1287 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1288 page1_penalty[i] = line_count_penalty (page1_line_count);
1289 page1_status[i] = line_count_status (page1_line_count);
1292 page2_force[page2_force.size () - 1 - i] =
1293 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1295 page2_force[page2_force.size () - 1 - i] = page2.force_;
1296 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1297 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1300 /* find the position that minimises the sum of the page forces */
1301 vsize best_sys_count = 1;
1302 Real best_demerits = infinity_f;
1303 for (vsize i = 0; i < page1_force.size (); i++)
1305 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1307 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1308 // constraints. That is, we penalize harshly when they don't happen
1309 // but we don't completely reject.
1311 + page1_penalty[i] + page2_penalty[i]
1312 + cached_line_details_[i+1].page_penalty_
1313 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1314 if (dem < best_demerits)
1316 best_demerits = dem;
1317 best_sys_count = i+1;
1321 Page_spacing_result ret;
1322 ret.systems_per_page_.push_back (best_sys_count);
1323 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1324 ret.force_.push_back (page1_force[best_sys_count-1]);
1325 ret.force_.push_back (page2_force[best_sys_count-1]);
1326 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1327 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1328 + cached_line_details_.back ().page_penalty_
1329 + cached_line_details_.back ().turn_penalty_
1330 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1332 /* don't do finalize_spacing_result () because we are only an internal function */
1337 Page_breaking::all_lines_stretched (vsize configuration)
1339 cache_line_details (configuration);
1340 for (vsize i = 0; i < cached_line_details_.size (); i++)
1341 if (cached_line_details_[i].force_ < 0)
1347 Page_breaking::Line_division
1348 Page_breaking::current_configuration (vsize configuration_index) const
1350 return current_configurations_[configuration_index];
1354 Page_breaking::is_last () const
1356 return current_end_breakpoint_ == last_break_position ();
1360 Page_breaking::ends_score () const
1362 return breaks_[current_end_breakpoint_].score_ender_;
1366 Page_breaking::last_break_position () const
1368 return breaks_.size () - 1;
1371 // This gives the minimum distance between the top of the
1372 // printable area (ie. the bottom of the top-margin) and
1373 // the extent box of the topmost system.
1375 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1377 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1379 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1381 Real min_distance = -infinity_f;
1384 Page_layout_problem::read_spacing_spec (first_system_spacing,
1386 ly_symbol2scm ("minimum-distance"));
1387 Page_layout_problem::read_spacing_spec (first_system_spacing,
1389 ly_symbol2scm ("padding"));
1391 // FIXME: take into account the height of the header
1392 return max (0.0, max (padding, min_distance - line.extent_[UP]));
1396 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1398 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1399 Real min_distance = -infinity_f;
1402 Page_layout_problem::read_spacing_spec (last_system_spacing,
1404 ly_symbol2scm ("minimum-distance"));
1405 Page_layout_problem::read_spacing_spec (last_system_spacing,
1407 ly_symbol2scm ("padding"));
1409 // FIXME: take into account the height of the footer
1410 return max (0.0, max (padding, min_distance + line.extent_[DOWN]));