2 page-breaking.cc -- implement a superclass and utility
3 functions shared by various page-breaking algorithms
5 source file of the GNU LilyPond music typesetter
7 (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
11 This is a utility class for page-breaking algorithms. There are some complex
12 parts of this class, some of which are useful to understand if you intend
13 to write a page breaking algorithm (ie. a subclass of Page_breaking). Most
14 of these complexities were introduced in order to break the problem of
15 page-breaking into simpler subproblems and to hide some of the bookkeeping
16 complexities of page breaking from the page breaking algorithms.
19 There are several functions that actually distribute systems across pages
20 (for example, the space_systems_XXX and pack_systems_XXX functions). If
21 each of these functions had to handle \noPageBreak, it would be a mess.
22 Therefore, we handle \noPageBreak by "compressing" the list of systems
23 before doing any layout: we concatenate any two systems separated by a
24 \noPageBreak into a single system. The page-breaking functions can do their
25 magic without encountering a \noPageBreak; we then "uncompress" the systems
26 at the end. We almost always work with cached_line_details_, which are
30 The basic operation of a page breaking algorithm is to repeatedly request
31 some systems from the line-breaker and place those systems on some pages.
32 With each repetition, the page breaking algorithm asks the line-breaker for
33 some systems that it thinks will help it achieve a better layout. The
34 Page_breaking class provides functionality to facilitate this in the case
35 that the page breaking algorithm only cares about the number of systems.
37 Even if a page breaking algorithm only cares number of systems, there may
38 be many ways to satisfy its request. For example, in a piece with 2 scores
39 and a request for 10 systems, we could return 5 systems from each score or
40 4 from the first and 6 from the second. Even within a score, we might
41 want to try several different line breaking configurations with a fixed
42 system count; if there is a forced \pageBreak, for example, we might wish
43 to tweak the number of systems on both sides of the \pageBreak independently.
45 The Page_breaking class takes care of finding these configurations. It
46 divides the piece into "chunks" and sets up the line-breaker in such a way
47 that the number of systems in each chunk can be modified independently.
48 Chunks never cross score boundaries; each title and markup is its own chunk.
49 When a page breaking algorithm requests a number of systems, the Page_breaker
50 stores an array of potential configurations, which the page breaking
51 algorithm can iterate over using current_configuration(vsize).
54 A Line_division is simply a way of storing the exact way in which the
55 total number of systems is distributed among chunks. Note that a
56 Line_division may not (in fact, usually will not) describe all of the chunks
57 in the entire book. Rather, it will describe the subset of chunks that lie
58 between some fixed starting and ending point. This subset of chunks changes
59 whenever a page breaking algorithm asks to consider a different pair of
60 starting and ending breakpoints. In particular, a Line_division should be
61 discarded after a call to set_current_breakpoints, since that Line_division
62 refers to a subset of chunks which might be different from the current
63 subset of chunks under consideration.
66 #include "page-breaking.hh"
68 #include "international.hh"
70 #include "output-def.hh"
71 #include "page-layout-problem.hh"
72 #include "page-spacing.hh"
73 #include "paper-book.hh"
74 #include "paper-score.hh"
75 #include "paper-system.hh"
79 /* for each forbidden page break, merge the systems around it into one
81 static vector<Line_details>
82 compress_lines (const vector<Line_details> &orig)
84 vector<Line_details> ret;
86 for (vsize i = 0; i < orig.size (); i++)
88 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
90 Line_details const &old = ret.back ();
91 Line_details compressed = orig[i];
92 compressed.extent_[DOWN] = old.extent_[DOWN];
93 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
94 compressed.space_ += old.space_;
95 compressed.inverse_hooke_ += old.inverse_hooke_;
97 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
98 compressed.compressed_nontitle_lines_count_ =
99 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
101 // compressed.title_ is true if and only if the first of its
102 // compressed lines was a title.
103 compressed.title_ = old.title_;
104 ret.back () = compressed;
108 ret.push_back (orig[i]);
109 ret.back ().force_ = 0;
115 /* translate the number of systems-per-page into something meaningful for
116 the uncompressed lines.
119 uncompress_solution (vector<vsize> const &systems_per_page,
120 vector<Line_details> const &compressed)
125 for (vsize i = 0; i < systems_per_page.size (); i++)
127 int compressed_count = 0;
128 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
129 compressed_count += compressed[j].compressed_lines_count_ - 1;
131 ret.push_back (systems_per_page[i] + compressed_count);
132 start_sys += systems_per_page[i];
137 /* for Page_breaking, the start index (when we are dealing with the stuff
138 between a pair of breakpoints) refers to the break_ index of the end of
139 the previous page. So the system index of the start of the current page
140 could either be the same as the end of the previous page or one more than
143 /* Turn a break index into the sys index that starts the next page */
145 Page_breaking::next_system (Break_position const &break_pos) const
147 vsize sys = break_pos.system_spec_index_;
149 if (sys == VPOS) /* beginning of the book */
151 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
152 return sys; /* the score overflows the previous page */
153 return sys + 1; /* this page starts with a new System_spec */
156 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
160 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
161 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
162 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
163 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
164 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
166 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
168 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
169 min_systems_per_page_ = max_systems_per_page_ = 0;
171 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
173 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
174 min_systems_per_page_ = max_systems_per_page_ = 0;
177 create_system_list ();
178 find_chunks_and_breaks (is_break);
181 Page_breaking::~Page_breaking ()
186 Page_breaking::ragged () const
192 Page_breaking::ragged_last () const
198 Page_breaking::systems_per_page () const
200 return systems_per_page_;
204 Page_breaking::max_systems_per_page () const
206 return max_systems_per_page_;
210 Page_breaking::min_systems_per_page () const
212 return min_systems_per_page_;
216 Page_breaking::system_count () const
218 return system_count_;
222 Page_breaking::too_many_lines (int line_count) const
224 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
228 Page_breaking::too_few_lines (int line_count) const
230 return line_count < min_systems_per_page ();
234 Page_breaking::line_count_penalty (int line_count) const
236 if (too_many_lines (line_count))
237 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
238 if (too_few_lines (line_count))
239 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
245 Page_breaking::line_count_status (int line_count) const
247 if (too_many_lines (line_count))
248 return SYSTEM_COUNT_TOO_MANY;
249 if (too_few_lines (line_count))
250 return SYSTEM_COUNT_TOO_FEW;
252 return SYSTEM_COUNT_OK;
255 /* translate indices into breaks_ into start-end parameters for the line breaker */
257 Page_breaking::line_breaker_args (vsize sys,
258 Break_position const &start,
259 Break_position const &end,
260 vsize *line_breaker_start,
261 vsize *line_breaker_end)
263 assert (system_specs_[sys].pscore_);
264 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
266 if (start.system_spec_index_ == sys)
267 *line_breaker_start = start.score_break_;
269 *line_breaker_start = 0;
271 if (end.system_spec_index_ == sys)
272 *line_breaker_end = end.score_break_;
274 *line_breaker_end = VPOS;
278 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
279 Line_division const &div)
281 vector<Break_position> chunks = chunk_list (start_break, end_break);
282 bool ignore_div = false;
283 if (chunks.size () != div.size () + 1)
285 programming_error ("did not find a valid page breaking configuration");
289 for (vsize i = 0; i + 1 < chunks.size (); i++)
291 vsize sys = next_system (chunks[i]);
292 if (system_specs_[sys].pscore_)
296 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
298 vector<Column_x_positions> pos = ignore_div
299 ? line_breaking_[sys].best_solution (start, end)
300 : line_breaking_[sys].solve (start, end, div[i]);
301 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
307 Page_breaking::systems ()
310 for (vsize sys = 0; sys < system_specs_.size (); sys++)
312 if (system_specs_[sys].pscore_)
314 system_specs_[sys].pscore_->root_system ()
315 ->do_break_substitution_and_fixup_refpoints ();
316 SCM lines = system_specs_[sys].pscore_->root_system ()
317 ->get_broken_system_grobs ();
318 ret = scm_cons (lines, ret);
322 Prob *pb = system_specs_[sys].prob_;
323 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
327 return scm_append (scm_reverse (ret));
331 Page_breaking::make_page (int page_num, bool last) const
333 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
334 SCM mod = scm_c_resolve_module ("scm page");
335 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
337 make_page_scm = scm_variable_ref (make_page_scm);
339 return scm_apply_0 (make_page_scm,
340 scm_list_n (book_->self_scm (),
341 ly_symbol2scm ("page-number"), scm_from_int (page_num),
342 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
343 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
348 Page_breaking::page_height (int page_num, bool last) const
350 SCM mod = scm_c_resolve_module ("scm page");
351 SCM page = make_page (page_num, last);
352 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
353 calc_height = scm_variable_ref (calc_height);
355 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
356 return scm_to_double (height);
360 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
362 Break_position const &pos = breaks_[breakpoint];
364 if (pos.system_spec_index_ == VPOS)
366 if (system_specs_[pos.system_spec_index_].pscore_)
367 return pos.col_->get_property (str);
368 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
372 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
374 SCM dummy_page = make_page (page_num, last);
375 Page_layout_problem layout (book_, dummy_page, systems);
376 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
380 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
382 // Create a stencil for each system.
383 SCM paper_systems = SCM_EOL;
384 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
386 SCM paper_system = scm_car (s);
387 if (Grob *g = unsmob_grob (scm_car (s)))
389 System *sys = dynamic_cast<System*> (g);
390 paper_system = sys->get_paper_system ();
393 paper_systems = scm_cons (paper_system, paper_systems);
396 // Create the page and draw it.
397 SCM page = make_page (page_num, last);
398 SCM page_module = scm_c_resolve_module ("scm page");
399 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
400 page_stencil = scm_variable_ref (page_stencil);
402 Prob *p = unsmob_prob (page);
403 p->set_property ("lines", paper_systems);
404 p->set_property ("configuration", configuration);
405 scm_apply_1 (page_stencil, page, SCM_EOL);
411 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
413 int first_page_number
414 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
416 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
417 if (label_page_table == SCM_UNDEFINED)
418 label_page_table = SCM_EOL;
420 // Build a list of (systems . configuration) pairs. Note that we lay out
421 // the staves and find the configurations before drawing anything. Some
422 // grobs (like tuplet brackets) look at their neighbours while drawing
423 // themselves. If this happens before the neighbouring staves have
424 // been laid out, bad side-effects could happen (in particular,
425 // Align_interface::align_to_ideal_distances might be called).
426 SCM systems_and_configs = SCM_EOL;
428 for (vsize i = 0; i < lines_per_page.size (); i++)
430 int page_num = i + first_page_number;
431 bool bookpart_last_page = (i == lines_per_page.size () - 1);
432 bool rag = ragged () || (bookpart_last_page && ragged_last ());
433 SCM line_count = scm_from_int (lines_per_page[i]);
434 SCM lines = scm_list_head (systems, line_count);
435 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
437 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
438 systems = scm_list_tail (systems, line_count);
441 // Now it's safe to make the pages.
442 int page_num = first_page_number + lines_per_page.size () - 1;
443 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
445 SCM lines = scm_caar (s);
446 SCM config = scm_cdar (s);
447 bool bookpart_last_page = (s == systems_and_configs);
448 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
451 SCM page_num_scm = scm_from_int (page_num);
452 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
454 SCM labels = SCM_EOL;
455 if (Grob * line = unsmob_grob (scm_car (l)))
457 System *system = dynamic_cast<System*> (line);
458 labels = system->get_property ("labels");
460 else if (Prob *prob = unsmob_prob (scm_car (l)))
461 labels = prob->get_property ("labels");
463 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
464 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
468 ret = scm_cons (page, ret);
471 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
475 /* The page-turn-page-breaker needs to have a line-breaker between any two
476 columns with non-NULL page-turn-permission.
478 The optimal-breaker needs to have a line-breaker between any two columns
479 with page-break-permission = 'force.
481 By using a grob predicate, we can accommodate both of these uses.
484 Page_breaking::create_system_list ()
486 SCM specs = book_->get_system_specs ();
487 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
489 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
491 system_specs_.push_back (System_spec (ps));
495 Prob *pb = unsmob_prob (scm_car (s));
499 system_specs_.push_back (System_spec (pb));
505 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
507 SCM force_sym = ly_symbol2scm ("force");
509 chunks_.push_back (Break_position ());
510 breaks_.push_back (Break_position ());
512 for (vsize i = 0; i < system_specs_.size (); i++)
514 if (system_specs_[i].pscore_)
518 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
519 if (scm_is_number (system_count))
521 // With system-count given, the line configuration for
522 // this score is fixed. We need to ensure that chunk
523 // boundaries only occur at line breaks.
524 Constrained_breaking breaking (system_specs_[i].pscore_);
525 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
527 for (vsize j = 0; j < details.size (); j++)
528 cols.push_back (details[j].last_column_);
531 cols = system_specs_[i].pscore_->root_system ()->used_columns ();
533 int last_chunk_idx = -1;
534 vector<vsize> line_breaker_columns;
535 line_breaker_columns.push_back (0);
537 for (vsize j = 1; j < cols.size (); j++)
539 bool last = (j == cols.size () - 1);
540 bool break_point = is_break (cols[j]);
541 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
542 Break_position cur_pos = Break_position (i,
543 line_breaker_columns.size (),
547 // NOTE: even in the breaks_ list, forced_line_count_
548 // refers to the number of lines between a
549 // Break_position and the start of that /chunk/. This
550 // is needed for system_count_bounds to work correctly,
551 // since it mixes Break_positions from breaks_ and
553 if (scm_is_number (system_count))
554 cur_pos.forced_line_count_ = j - last_chunk_idx;
556 if (break_point || (i == system_specs_.size () - 1 && last))
557 breaks_.push_back (cur_pos);
558 if (chunk_end || last)
560 chunks_.push_back (cur_pos);
564 if ((break_point || chunk_end) && !last)
565 line_breaker_columns.push_back (j);
567 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
571 /* TODO: we want some way of applying Break_p to a prob? */
572 if (i == system_specs_.size () - 1)
573 breaks_.push_back (Break_position (i));
575 chunks_.push_back (Break_position (i));
577 /* FIXME: shouldn't we push a Null_breaker or similar dummy
579 line_breaking_.push_back (Constrained_breaking (NULL));
584 vector<Break_position>
585 Page_breaking::chunk_list (vsize start_index, vsize end_index)
587 Break_position start = breaks_[start_index];
588 Break_position end = breaks_[end_index];
591 for (; i < chunks_.size () && chunks_[i] <= start; i++)
594 vector<Break_position> ret;
595 ret.push_back (start);
596 for (; i < chunks_.size () && chunks_[i] < end; i++)
597 ret.push_back (chunks_[i]);
603 Page_breaking::min_system_count (vsize start, vsize end)
605 vector<Break_position> chunks = chunk_list (start, end);
606 Line_division div = system_count_bounds (chunks, true);
609 for (vsize i = 0; i < div.size (); i++)
615 Page_breaking::max_system_count (vsize start, vsize end)
617 vector<Break_position> chunks = chunk_list (start, end);
618 Line_division div = system_count_bounds (chunks, false);
621 for (vsize i = 0; i < div.size (); i++)
626 Page_breaking::Line_division
627 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
630 assert (chunks.size () >= 2);
633 ret.resize (chunks.size () - 1, 1);
635 for (vsize i = 0; i + 1 < chunks.size (); i++)
637 vsize sys = next_system (chunks[i]);
639 if (chunks[i+1].forced_line_count_)
640 ret[i] = chunks[i+1].forced_line_count_;
641 else if (system_specs_[sys].pscore_)
645 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
647 ? line_breaking_[sys].min_system_count (start, end)
648 : line_breaking_[sys].max_system_count (start, end);
656 Page_breaking::set_current_breakpoints (vsize start,
659 Line_division lower_bound,
660 Line_division upper_bound)
662 system_count_ = system_count;
663 current_chunks_ = chunk_list (start, end);
664 current_start_breakpoint_ = start;
665 current_end_breakpoint_ = end;
666 clear_line_details_cache ();
668 if (!lower_bound.size ())
669 lower_bound = system_count_bounds (current_chunks_, true);
670 if (!upper_bound.size ())
671 upper_bound = system_count_bounds (current_chunks_, false);
673 assert (lower_bound.size () == current_chunks_.size () - 1);
674 assert (upper_bound.size () == current_chunks_.size () - 1);
676 Line_division work_in_progress;
677 current_configurations_.clear ();
678 line_divisions_rec (system_count,
683 /* we only consider a constant number of configurations. Otherwise,
684 this becomes slow when there are many small scores. The constant
685 5 is somewhat arbitrary. */
686 if (current_configurations_.size () > 5)
688 vector<pair<Real,vsize> > dems_and_indices;
690 for (vsize i = 0; i < current_configurations_.size (); i++)
692 cache_line_details (i);
694 for (vsize j = 0; j < cached_line_details_.size (); j++)
695 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
696 + cached_line_details_[j].break_penalty_;
698 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
700 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
702 vector<Line_division> best_5_configurations;
703 for (vsize i = 0; i < 5; i++)
704 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
706 clear_line_details_cache ();
707 current_configurations_ = best_5_configurations;
712 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
714 current_chunks_ = chunk_list (start, end);
715 current_start_breakpoint_ = start;
716 current_end_breakpoint_ = end;
717 clear_line_details_cache ();
721 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
723 vsize sys = next_system (current_chunks_[i]);
725 if (current_chunks_[i+1].forced_line_count_)
726 div.push_back (current_chunks_[i+1].forced_line_count_);
727 else if (system_specs_[sys].pscore_)
729 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
730 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
735 system_count_ += div.back ();
737 current_configurations_.clear ();
738 current_configurations_.push_back (div);
742 Page_breaking::current_configuration_count () const
744 return current_configurations_.size ();
748 Page_breaking::cache_line_details (vsize configuration_index)
750 if (cached_configuration_index_ != configuration_index)
752 cached_configuration_index_ = configuration_index;
754 SCM spacing_spec = book_->paper_->c_variable ("between-system-spacing");
755 SCM page_breaking_spacing_spec = book_->paper_->c_variable ("page-breaking-between-system-spacing");
756 Page_layout_problem::read_spacing_spec (spacing_spec, &padding, ly_symbol2scm ("padding"));
757 Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec, &padding, ly_symbol2scm ("padding"));
759 Line_division &div = current_configurations_[configuration_index];
760 uncompressed_line_details_.clear ();
761 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
763 vsize sys = next_system (current_chunks_[i]);
764 if (system_specs_[sys].pscore_)
768 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
770 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
771 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
775 assert (div[i] == 1);
776 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
777 uncompressed_line_details_.back ().padding_ =
778 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
782 cached_line_details_ = compress_lines (uncompressed_line_details_);
787 Page_breaking::clear_line_details_cache ()
789 cached_configuration_index_ = VPOS;
790 cached_line_details_.clear ();
791 uncompressed_line_details_.clear ();
795 Page_breaking::line_divisions_rec (vsize system_count,
796 Line_division const &min_sys,
797 Line_division const &max_sys,
798 Line_division *cur_division)
800 vsize my_index = cur_division->size ();
801 vsize others_min = 0;
802 vsize others_max = 0;
804 for (vsize i = my_index + 1; i < min_sys.size (); i++)
806 others_min += min_sys[i];
807 others_max += max_sys[i];
809 others_max = min (others_max, system_count);
810 vsize real_min = max (min_sys[my_index], system_count - others_max);
811 vsize real_max = min (max_sys[my_index], system_count - others_min);
813 if (real_min > real_max || real_min <= 0)
815 /* this should never happen within a recursive call. If it happens
816 at all, it means that we were called with an unsolvable problem
817 and we should return an empty result */
818 assert (my_index == 0);
822 for (vsize i = real_min; i <= real_max; i++)
824 cur_division->push_back (i);
825 if (my_index == min_sys.size () - 1)
826 current_configurations_.push_back (*cur_division);
828 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
829 cur_division->pop_back ();
834 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
837 vsize page_starter = 0;
838 Real cur_rod_height = 0;
839 Real cur_spring_height = 0;
840 Real cur_page_height = page_height (first_page_num, false);
843 cache_line_details (configuration);
845 if (cached_line_details_.size ())
846 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
848 for (vsize i = 0; i < cached_line_details_.size (); i++)
850 Real ext_len = cached_line_details_[i].extent_.length ();
851 Real next_rod_height = cur_rod_height + ext_len
852 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
853 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
854 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
855 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
856 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
858 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
859 || too_many_lines (next_line_count)
861 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
863 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
864 cur_rod_height = ext_len;
865 cur_spring_height = cached_line_details_[i].space_;
868 cur_page_height = page_height (first_page_num + ret, false);
869 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
875 cur_rod_height = next_rod_height;
876 cur_spring_height = next_spring_height;
877 line_count = next_line_count;
881 /* there are two potential problems with the last page (because we didn't know
882 it was the last page until after we managed to fit all the systems to it):
883 - we are ragged-last but the last page has a compressed spring
884 - the value returned by page_height (num, true) is smaller than the
885 value returned by page_height (num, false) and it causes the page not to
888 In either case, we just need to add one more page. This is because the last
889 line will always fit on the extra page and by adding one more page to the
890 end, the previous page is no longer the last page, so our previous
891 calculations that treated it as a non-last page were ok.
894 cur_page_height = page_height (first_page_num + ret - 1, true);
895 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
896 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
898 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
899 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
900 && cur_height > cur_page_height
901 /* don't increase the page count if the last page had only one system */
902 && cur_rod_height > cached_line_details_.back ().extent_.length ())
905 assert (ret <= cached_line_details_.size ());
909 // If systems_per_page_ is positive, we don't really try to space on N pages;
910 // we just put the requested number of systems on each page and penalize
911 // if the result doesn't have N pages.
913 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
915 Page_spacing_result ret;
917 if (systems_per_page_ > 0)
919 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
920 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
924 cache_line_details (configuration);
925 bool valid_n = (n >= min_page_count (configuration, first_page_num)
926 && n <= cached_line_details_.size ());
929 programming_error ("number of pages is out of bounds");
931 if (n == 1 && valid_n)
932 ret = space_systems_on_1_page (cached_line_details_,
933 page_height (first_page_num, is_last ()),
934 ragged () || (is_last () && ragged_last ()));
935 else if (n == 2 && valid_n)
936 ret = space_systems_on_2_pages (configuration, first_page_num);
939 Page_spacer ps (cached_line_details_, first_page_num, this);
943 return finalize_spacing_result (configuration, ret);
947 Page_breaking::blank_page_penalty () const
952 penalty_sym = ly_symbol2scm ("blank-last-page-force");
953 else if (ends_score ())
954 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
956 penalty_sym = ly_symbol2scm ("blank-page-force");
958 Break_position const &pos = breaks_[current_end_breakpoint_];
959 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
960 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
962 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
965 // If systems_per_page_ is positive, we don't really try to space on N
966 // or N+1 pages; see the comment to space_systems_on_n_pages.
968 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
970 Page_spacing_result n_res;
971 Page_spacing_result m_res;
973 if (systems_per_page_ > 0)
975 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
976 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
980 cache_line_details (configuration);
981 vsize min_p_count = min_page_count (configuration, first_page_num);
982 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
985 programming_error ("both page counts are out of bounds");
987 if (n == 1 && valid_n)
989 bool rag = ragged () || (is_last () && ragged_last ());
990 Real height = page_height (first_page_num, is_last ());
992 if (1 >= min_p_count)
993 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
994 if (1 < cached_line_details_.size ())
995 m_res = space_systems_on_2_pages (configuration, first_page_num);
999 Page_spacer ps (cached_line_details_, first_page_num, this);
1001 if (n >= min_p_count || !valid_n)
1002 n_res = ps.solve (n);
1003 if (n < cached_line_details_.size () || !valid_n)
1004 m_res = ps.solve (n+1);
1007 m_res = finalize_spacing_result (configuration, m_res);
1008 n_res = finalize_spacing_result (configuration, n_res);
1010 Real penalty = blank_page_penalty ();
1011 n_res.demerits_ += penalty;
1013 if (n_res.force_.size ())
1014 n_res.force_.back () += penalty;
1016 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1020 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1022 vsize min_p_count = min_page_count (configuration, first_page_num);
1023 Real odd_pages_penalty = blank_page_penalty ();
1025 cache_line_details (configuration);
1026 Page_spacer ps (cached_line_details_, first_page_num, this);
1027 Page_spacing_result best = ps.solve (min_p_count);
1028 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
1029 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
1031 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1033 Page_spacing_result cur = ps.solve (i);
1034 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
1035 if (cur.demerits_ < best.demerits_)
1039 return finalize_spacing_result (configuration, best);
1043 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1044 vsize first_page_num)
1046 Page_spacing_result res;
1047 Page_spacing space (page_height (first_page_num, false), this);
1050 vsize page_first_line = 0;
1052 cache_line_details (configuration);
1053 while (line < cached_line_details_.size ())
1057 space.resize (page_height (first_page_num + page, false));
1059 int system_count_on_this_page = 0;
1060 while (system_count_on_this_page < systems_per_page_
1061 && line < cached_line_details_.size ())
1063 Line_details const &cur_line = cached_line_details_[line];
1064 space.append_system (cur_line);
1065 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1068 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1072 res.systems_per_page_.push_back (line - page_first_line);
1074 res.force_.push_back (space.force_);
1075 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1076 if (system_count_on_this_page != systems_per_page_)
1078 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1079 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1080 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1083 page_first_line = line;
1086 /* Recalculate forces for the last page because we know now that is
1087 really the last page. */
1088 space.resize (page_height (first_page_num + page, true));
1089 res.force_.back () = space.force_;
1090 return finalize_spacing_result (configuration, res);
1094 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1096 // TODO: add support for min/max-systems-per-page.
1097 Page_spacing_result res;
1099 vsize page_first_line = 0;
1100 Page_spacing space (page_height (first_page_num, false), this);
1102 cache_line_details (configuration);
1103 for (vsize line = 0; line < cached_line_details_.size (); line++)
1105 Real prev_force = space.force_;
1106 space.append_system (cached_line_details_[line]);
1107 if ((line > page_first_line)
1108 && (isinf (space.force_)
1110 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1112 res.systems_per_page_.push_back (line - page_first_line);
1113 res.force_.push_back (prev_force);
1114 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1116 space.resize (page_height (first_page_num + page, false));
1118 space.append_system (cached_line_details_[line]);
1119 page_first_line = line;
1122 if (line == cached_line_details_.size () - 1)
1124 /* This is the last line */
1125 /* When the last page height was computed, we did not know yet that it
1126 * was the last one. If the systems put on it don't fit anymore, the last
1127 * system is moved to a new page */
1128 space.resize (page_height (first_page_num + page, true));
1129 if ((line > page_first_line) && (isinf (space.force_)))
1131 res.systems_per_page_.push_back (line - page_first_line);
1132 res.force_.push_back (prev_force);
1133 /* the last page containing the last line */
1134 space.resize (page_height (first_page_num + page + 1, true));
1136 space.append_system (cached_line_details_[line]);
1137 res.systems_per_page_.push_back (1);
1138 res.force_.push_back (space.force_);
1139 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1140 res.penalty_ += cached_line_details_[line].page_penalty_;
1144 res.systems_per_page_.push_back (line + 1 - page_first_line);
1145 res.force_.push_back (space.force_);
1146 res.penalty_ += cached_line_details_[line].page_penalty_;
1150 return finalize_spacing_result (configuration, res);
1153 /* Calculate demerits and fix res.systems_per_page_ so that
1154 it refers to the original line numbers, not the ones given by compress_lines (). */
1156 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1158 if (res.force_.empty ())
1161 cache_line_details (configuration);
1162 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1164 Real line_force = 0;
1165 Real line_penalty = 0;
1166 Real page_demerits = res.penalty_;
1167 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1169 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1171 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1172 line_penalty += uncompressed_line_details_[i].break_penalty_;
1175 for (vsize i = 0; i < res.force_.size (); i++)
1177 Real f = res.force_[i];
1179 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1182 /* for a while we tried averaging page and line forces across pages instead
1183 of summing them, but it caused a problem: if there is a single page
1184 with a very bad page force (for example because of a forced page break),
1185 the page breaker will put in a _lot_ of pages so that the bad force
1186 becomes averaged out over many pages. */
1187 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1192 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1193 are by far the most common cases, we have special functions for them.
1195 space_systems_on_1_page has a different calling convention than most of the
1196 space_systems functions. This is because space_systems_on_1_page is (unlike
1197 the other space_systems functions) sometimes called on subsets of a full
1200 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1202 Page_spacing space (page_height, this);
1203 Page_spacing_result ret;
1206 for (vsize i = 0; i < lines.size (); i++)
1208 space.append_system (lines[i]);
1209 line_count += lines[i].compressed_nontitle_lines_count_;
1212 ret.systems_per_page_.push_back (lines.size ());
1213 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1214 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1215 ret.system_count_status_ |= line_count_status (line_count);
1217 /* don't do finalize_spacing_result () because we are only an internal function */
1222 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1224 Real page1_height = page_height (first_page_num, false);
1225 Real page2_height = page_height (first_page_num + 1, is_last ());
1226 bool ragged1 = ragged ();
1227 bool ragged2 = ragged () || (is_last () && ragged_last ());
1229 /* if there is a forced break, this reduces to 2 1-page problems */
1230 cache_line_details (configuration);
1231 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1232 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1234 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1235 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1236 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1237 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1239 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1240 p1.force_.push_back (p2.force_[0]);
1241 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1245 vector<Real> page1_force;
1246 vector<Real> page2_force;
1248 // page1_penalty and page2_penalty store the penalties based
1249 // on min-systems-per-page and max-systems-per-page.
1250 vector<Real> page1_penalty;
1251 vector<Real> page2_penalty;
1253 // page1_status and page2_status keep track of whether the min-systems-per-page
1254 // and max-systems-per-page constraints are satisfied.
1255 vector<int> page1_status;
1256 vector<int> page2_status;
1258 Page_spacing page1 (page1_height, this);
1259 Page_spacing page2 (page2_height, this);
1260 int page1_line_count = 0;
1261 int page2_line_count = 0;
1263 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1264 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1265 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1266 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1267 page1_status.resize (cached_line_details_.size () - 1, 0);
1268 page2_status.resize (cached_line_details_.size () - 1, 0);
1270 /* find the page 1 and page 2 forces for each page-breaking position */
1271 for (vsize i = 0; i < page1_force.size (); i++)
1273 page1.append_system (cached_line_details_[i]);
1274 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1275 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1276 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1278 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1279 page1_penalty[i] = line_count_penalty (page1_line_count);
1280 page1_status[i] = line_count_status (page1_line_count);
1283 page2_force[page2_force.size () - 1 - i] =
1284 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1286 page2_force[page2_force.size () - 1 - i] = page2.force_;
1287 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1288 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1291 /* find the position that minimises the sum of the page forces */
1292 vsize best_sys_count = 1;
1293 Real best_demerits = infinity_f;
1294 for (vsize i = 0; i < page1_force.size (); i++)
1296 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1298 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1299 // constraints. That is, we penalize harshly when they don't happen
1300 // but we don't completely reject.
1302 + page1_penalty[i] + page2_penalty[i]
1303 + cached_line_details_[i+1].page_penalty_
1304 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1305 if (dem < best_demerits)
1307 best_demerits = dem;
1308 best_sys_count = i+1;
1312 Page_spacing_result ret;
1313 ret.systems_per_page_.push_back (best_sys_count);
1314 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1315 ret.force_.push_back (page1_force[best_sys_count-1]);
1316 ret.force_.push_back (page2_force[best_sys_count-1]);
1317 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1318 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1319 + cached_line_details_.back ().page_penalty_
1320 + cached_line_details_.back ().turn_penalty_
1321 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1323 /* don't do finalize_spacing_result () because we are only an internal function */
1328 Page_breaking::all_lines_stretched (vsize configuration)
1330 cache_line_details (configuration);
1331 for (vsize i = 0; i < cached_line_details_.size (); i++)
1332 if (cached_line_details_[i].force_ < 0)
1338 Page_breaking::Line_division
1339 Page_breaking::current_configuration (vsize configuration_index) const
1341 return current_configurations_[configuration_index];
1345 Page_breaking::is_last () const
1347 return current_end_breakpoint_ == last_break_position ();
1351 Page_breaking::ends_score () const
1353 return breaks_[current_end_breakpoint_].score_ender_;
1357 Page_breaking::last_break_position () const
1359 return breaks_.size () - 1;
1362 // This gives the minimum distance between the top of the
1363 // printable area (ie. the bottom of the top-margin) and
1364 // the extent box of the topmost system.
1366 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1368 SCM first_system_spacing = book_->paper_->c_variable ("first-system-spacing");
1370 first_system_spacing = book_->paper_->c_variable ("first-system-title-spacing");
1372 Real min_distance = -infinity_f;
1375 Page_layout_problem::read_spacing_spec (first_system_spacing,
1377 ly_symbol2scm ("minimum-distance"));
1378 Page_layout_problem::read_spacing_spec (first_system_spacing,
1380 ly_symbol2scm ("padding"));
1382 // FIXME: take into account the height of the header
1383 return max (0.0, max (padding, min_distance - line.extent_[UP]));
1387 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1389 SCM last_system_spacing = book_->paper_->c_variable ("last-system-spacing");
1390 Real min_distance = -infinity_f;
1393 Page_layout_problem::read_spacing_spec (last_system_spacing,
1395 ly_symbol2scm ("minimum-distance"));
1396 Page_layout_problem::read_spacing_spec (last_system_spacing,
1398 ly_symbol2scm ("padding"));
1400 // FIXME: take into account the height of the footer
1401 return max (0.0, max (padding, min_distance + line.extent_[DOWN]));