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 cols.push_back (system_specs_[i].pscore_->root_system ()->used_columns ()[0]);
528 for (vsize j = 0; j < details.size (); j++)
529 cols.push_back (details[j].last_column_);
532 cols = system_specs_[i].pscore_->root_system ()->used_columns ();
534 int last_chunk_idx = 0;
535 vector<vsize> line_breaker_columns;
536 line_breaker_columns.push_back (0);
538 for (vsize j = 1; j < cols.size (); j++)
540 bool last = (j == cols.size () - 1);
541 bool break_point = is_break (cols[j]);
542 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
543 Break_position cur_pos = Break_position (i,
544 line_breaker_columns.size (),
548 // NOTE: even in the breaks_ list, forced_line_count_
549 // refers to the number of lines between a
550 // Break_position and the start of that /chunk/. This
551 // is needed for system_count_bounds to work correctly,
552 // since it mixes Break_positions from breaks_ and
554 if (scm_is_number (system_count))
555 cur_pos.forced_line_count_ = j - last_chunk_idx;
557 if (break_point || (i == system_specs_.size () - 1 && last))
558 breaks_.push_back (cur_pos);
559 if (chunk_end || last)
561 chunks_.push_back (cur_pos);
565 if ((break_point || chunk_end) && !last)
566 line_breaker_columns.push_back (j);
568 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
572 /* TODO: we want some way of applying Break_p to a prob? */
573 if (i == system_specs_.size () - 1)
574 breaks_.push_back (Break_position (i));
576 chunks_.push_back (Break_position (i));
578 /* FIXME: shouldn't we push a Null_breaker or similar dummy
580 line_breaking_.push_back (Constrained_breaking (NULL));
585 vector<Break_position>
586 Page_breaking::chunk_list (vsize start_index, vsize end_index)
588 Break_position start = breaks_[start_index];
589 Break_position end = breaks_[end_index];
592 for (; i < chunks_.size () && chunks_[i] <= start; i++)
595 vector<Break_position> ret;
596 ret.push_back (start);
597 for (; i < chunks_.size () && chunks_[i] < end; i++)
598 ret.push_back (chunks_[i]);
604 Page_breaking::min_system_count (vsize start, vsize end)
606 vector<Break_position> chunks = chunk_list (start, end);
607 Line_division div = system_count_bounds (chunks, true);
610 for (vsize i = 0; i < div.size (); i++)
616 Page_breaking::max_system_count (vsize start, vsize end)
618 vector<Break_position> chunks = chunk_list (start, end);
619 Line_division div = system_count_bounds (chunks, false);
622 for (vsize i = 0; i < div.size (); i++)
627 Page_breaking::Line_division
628 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
631 assert (chunks.size () >= 2);
634 ret.resize (chunks.size () - 1, 1);
636 for (vsize i = 0; i + 1 < chunks.size (); i++)
638 vsize sys = next_system (chunks[i]);
640 if (chunks[i+1].forced_line_count_)
641 ret[i] = chunks[i+1].forced_line_count_;
642 else if (system_specs_[sys].pscore_)
646 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
648 ? line_breaking_[sys].min_system_count (start, end)
649 : line_breaking_[sys].max_system_count (start, end);
657 Page_breaking::set_current_breakpoints (vsize start,
660 Line_division lower_bound,
661 Line_division upper_bound)
663 system_count_ = system_count;
664 current_chunks_ = chunk_list (start, end);
665 current_start_breakpoint_ = start;
666 current_end_breakpoint_ = end;
667 clear_line_details_cache ();
669 if (!lower_bound.size ())
670 lower_bound = system_count_bounds (current_chunks_, true);
671 if (!upper_bound.size ())
672 upper_bound = system_count_bounds (current_chunks_, false);
674 assert (lower_bound.size () == current_chunks_.size () - 1);
675 assert (upper_bound.size () == current_chunks_.size () - 1);
677 Line_division work_in_progress;
678 current_configurations_.clear ();
679 line_divisions_rec (system_count,
684 /* we only consider a constant number of configurations. Otherwise,
685 this becomes slow when there are many small scores. The constant
686 5 is somewhat arbitrary. */
687 if (current_configurations_.size () > 5)
689 vector<pair<Real,vsize> > dems_and_indices;
691 for (vsize i = 0; i < current_configurations_.size (); i++)
693 cache_line_details (i);
695 for (vsize j = 0; j < cached_line_details_.size (); j++)
696 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
697 + cached_line_details_[j].break_penalty_;
699 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
701 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
703 vector<Line_division> best_5_configurations;
704 for (vsize i = 0; i < 5; i++)
705 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
707 clear_line_details_cache ();
708 current_configurations_ = best_5_configurations;
713 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
715 current_chunks_ = chunk_list (start, end);
716 current_start_breakpoint_ = start;
717 current_end_breakpoint_ = end;
718 clear_line_details_cache ();
722 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
724 vsize sys = next_system (current_chunks_[i]);
726 if (current_chunks_[i+1].forced_line_count_)
727 div.push_back (current_chunks_[i+1].forced_line_count_);
728 else if (system_specs_[sys].pscore_)
730 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
731 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
736 system_count_ += div.back ();
738 current_configurations_.clear ();
739 current_configurations_.push_back (div);
743 Page_breaking::current_configuration_count () const
745 return current_configurations_.size ();
749 Page_breaking::cache_line_details (vsize configuration_index)
751 if (cached_configuration_index_ != configuration_index)
753 cached_configuration_index_ = configuration_index;
755 SCM spacing_spec = book_->paper_->c_variable ("between-system-spacing");
756 SCM page_breaking_spacing_spec = book_->paper_->c_variable ("page-breaking-between-system-spacing");
757 Page_layout_problem::read_spacing_spec (spacing_spec, &padding, ly_symbol2scm ("padding"));
758 Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec, &padding, ly_symbol2scm ("padding"));
760 Line_division &div = current_configurations_[configuration_index];
761 uncompressed_line_details_.clear ();
762 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
764 vsize sys = next_system (current_chunks_[i]);
765 if (system_specs_[sys].pscore_)
769 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
771 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
772 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
776 assert (div[i] == 1);
777 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
778 uncompressed_line_details_.back ().padding_ =
779 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
783 cached_line_details_ = compress_lines (uncompressed_line_details_);
788 Page_breaking::clear_line_details_cache ()
790 cached_configuration_index_ = VPOS;
791 cached_line_details_.clear ();
792 uncompressed_line_details_.clear ();
796 Page_breaking::line_divisions_rec (vsize system_count,
797 Line_division const &min_sys,
798 Line_division const &max_sys,
799 Line_division *cur_division)
801 vsize my_index = cur_division->size ();
802 vsize others_min = 0;
803 vsize others_max = 0;
805 for (vsize i = my_index + 1; i < min_sys.size (); i++)
807 others_min += min_sys[i];
808 others_max += max_sys[i];
810 others_max = min (others_max, system_count);
811 vsize real_min = max (min_sys[my_index], system_count - others_max);
812 vsize real_max = min (max_sys[my_index], system_count - others_min);
814 if (real_min > real_max || real_min <= 0)
816 /* this should never happen within a recursive call. If it happens
817 at all, it means that we were called with an unsolvable problem
818 and we should return an empty result */
819 assert (my_index == 0);
823 for (vsize i = real_min; i <= real_max; i++)
825 cur_division->push_back (i);
826 if (my_index == min_sys.size () - 1)
827 current_configurations_.push_back (*cur_division);
829 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
830 cur_division->pop_back ();
835 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
838 vsize page_starter = 0;
839 Real cur_rod_height = 0;
840 Real cur_spring_height = 0;
841 Real cur_page_height = page_height (first_page_num, false);
844 cache_line_details (configuration);
846 if (cached_line_details_.size ())
847 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
849 for (vsize i = 0; i < cached_line_details_.size (); i++)
851 Real ext_len = cached_line_details_[i].extent_.length ();
852 Real next_rod_height = cur_rod_height + ext_len
853 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
854 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
855 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
856 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
857 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
859 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
860 || too_many_lines (next_line_count)
862 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
864 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
865 cur_rod_height = ext_len;
866 cur_spring_height = cached_line_details_[i].space_;
869 cur_page_height = page_height (first_page_num + ret, false);
870 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
876 cur_rod_height = next_rod_height;
877 cur_spring_height = next_spring_height;
878 line_count = next_line_count;
882 /* there are two potential problems with the last page (because we didn't know
883 it was the last page until after we managed to fit all the systems to it):
884 - we are ragged-last but the last page has a compressed spring
885 - the value returned by page_height (num, true) is smaller than the
886 value returned by page_height (num, false) and it causes the page not to
889 In either case, we just need to add one more page. This is because the last
890 line will always fit on the extra page and by adding one more page to the
891 end, the previous page is no longer the last page, so our previous
892 calculations that treated it as a non-last page were ok.
895 cur_page_height = page_height (first_page_num + ret - 1, true);
896 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
897 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
899 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
900 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
901 && cur_height > cur_page_height
902 /* don't increase the page count if the last page had only one system */
903 && cur_rod_height > cached_line_details_.back ().extent_.length ())
906 assert (ret <= cached_line_details_.size ());
910 // If systems_per_page_ is positive, we don't really try to space on N pages;
911 // we just put the requested number of systems on each page and penalize
912 // if the result doesn't have N pages.
914 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
916 Page_spacing_result ret;
918 if (systems_per_page_ > 0)
920 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
921 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
925 cache_line_details (configuration);
926 bool valid_n = (n >= min_page_count (configuration, first_page_num)
927 && n <= cached_line_details_.size ());
930 programming_error ("number of pages is out of bounds");
932 if (n == 1 && valid_n)
933 ret = space_systems_on_1_page (cached_line_details_,
934 page_height (first_page_num, is_last ()),
935 ragged () || (is_last () && ragged_last ()));
936 else if (n == 2 && valid_n)
937 ret = space_systems_on_2_pages (configuration, first_page_num);
940 Page_spacer ps (cached_line_details_, first_page_num, this);
944 return finalize_spacing_result (configuration, ret);
948 Page_breaking::blank_page_penalty () const
953 penalty_sym = ly_symbol2scm ("blank-last-page-force");
954 else if (ends_score ())
955 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
957 penalty_sym = ly_symbol2scm ("blank-page-force");
959 Break_position const &pos = breaks_[current_end_breakpoint_];
960 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
961 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
963 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
966 // If systems_per_page_ is positive, we don't really try to space on N
967 // or N+1 pages; see the comment to space_systems_on_n_pages.
969 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
971 Page_spacing_result n_res;
972 Page_spacing_result m_res;
974 if (systems_per_page_ > 0)
976 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
977 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
981 cache_line_details (configuration);
982 vsize min_p_count = min_page_count (configuration, first_page_num);
983 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
986 programming_error ("both page counts are out of bounds");
988 if (n == 1 && valid_n)
990 bool rag = ragged () || (is_last () && ragged_last ());
991 Real height = page_height (first_page_num, is_last ());
993 if (1 >= min_p_count)
994 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
995 if (1 < cached_line_details_.size ())
996 m_res = space_systems_on_2_pages (configuration, first_page_num);
1000 Page_spacer ps (cached_line_details_, first_page_num, this);
1002 if (n >= min_p_count || !valid_n)
1003 n_res = ps.solve (n);
1004 if (n < cached_line_details_.size () || !valid_n)
1005 m_res = ps.solve (n+1);
1008 m_res = finalize_spacing_result (configuration, m_res);
1009 n_res = finalize_spacing_result (configuration, n_res);
1011 Real penalty = blank_page_penalty ();
1012 n_res.demerits_ += penalty;
1014 if (n_res.force_.size ())
1015 n_res.force_.back () += penalty;
1017 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1021 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1023 vsize min_p_count = min_page_count (configuration, first_page_num);
1024 Real odd_pages_penalty = blank_page_penalty ();
1026 cache_line_details (configuration);
1027 Page_spacer ps (cached_line_details_, first_page_num, this);
1028 Page_spacing_result best = ps.solve (min_p_count);
1029 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
1030 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
1032 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1034 Page_spacing_result cur = ps.solve (i);
1035 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
1036 if (cur.demerits_ < best.demerits_)
1040 return finalize_spacing_result (configuration, best);
1044 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1045 vsize first_page_num)
1047 Page_spacing_result res;
1048 Page_spacing space (page_height (first_page_num, false), this);
1051 vsize page_first_line = 0;
1053 cache_line_details (configuration);
1054 while (line < cached_line_details_.size ())
1058 space.resize (page_height (first_page_num + page, false));
1060 int system_count_on_this_page = 0;
1061 while (system_count_on_this_page < systems_per_page_
1062 && line < cached_line_details_.size ())
1064 Line_details const &cur_line = cached_line_details_[line];
1065 space.append_system (cur_line);
1066 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1069 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1073 res.systems_per_page_.push_back (line - page_first_line);
1075 res.force_.push_back (space.force_);
1076 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1077 if (system_count_on_this_page != systems_per_page_)
1079 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1080 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1081 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1084 page_first_line = line;
1087 /* Recalculate forces for the last page because we know now that is
1088 really the last page. */
1089 space.resize (page_height (first_page_num + page, true));
1090 res.force_.back () = space.force_;
1091 return finalize_spacing_result (configuration, res);
1095 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1097 // TODO: add support for min/max-systems-per-page.
1098 Page_spacing_result res;
1100 vsize page_first_line = 0;
1101 Page_spacing space (page_height (first_page_num, false), this);
1103 cache_line_details (configuration);
1104 for (vsize line = 0; line < cached_line_details_.size (); line++)
1106 Real prev_force = space.force_;
1107 space.append_system (cached_line_details_[line]);
1108 if ((line > page_first_line)
1109 && (isinf (space.force_)
1111 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1113 res.systems_per_page_.push_back (line - page_first_line);
1114 res.force_.push_back (prev_force);
1115 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1117 space.resize (page_height (first_page_num + page, false));
1119 space.append_system (cached_line_details_[line]);
1120 page_first_line = line;
1123 if (line == cached_line_details_.size () - 1)
1125 /* This is the last line */
1126 /* When the last page height was computed, we did not know yet that it
1127 * was the last one. If the systems put on it don't fit anymore, the last
1128 * system is moved to a new page */
1129 space.resize (page_height (first_page_num + page, true));
1130 if ((line > page_first_line) && (isinf (space.force_)))
1132 res.systems_per_page_.push_back (line - page_first_line);
1133 res.force_.push_back (prev_force);
1134 /* the last page containing the last line */
1135 space.resize (page_height (first_page_num + page + 1, true));
1137 space.append_system (cached_line_details_[line]);
1138 res.systems_per_page_.push_back (1);
1139 res.force_.push_back (space.force_);
1140 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1141 res.penalty_ += cached_line_details_[line].page_penalty_;
1145 res.systems_per_page_.push_back (line + 1 - page_first_line);
1146 res.force_.push_back (space.force_);
1147 res.penalty_ += cached_line_details_[line].page_penalty_;
1151 return finalize_spacing_result (configuration, res);
1154 /* Calculate demerits and fix res.systems_per_page_ so that
1155 it refers to the original line numbers, not the ones given by compress_lines (). */
1157 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1159 if (res.force_.empty ())
1162 cache_line_details (configuration);
1163 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1165 Real line_force = 0;
1166 Real line_penalty = 0;
1167 Real page_demerits = res.penalty_;
1168 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1170 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1172 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1173 line_penalty += uncompressed_line_details_[i].break_penalty_;
1176 for (vsize i = 0; i < res.force_.size (); i++)
1178 Real f = res.force_[i];
1180 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1183 /* for a while we tried averaging page and line forces across pages instead
1184 of summing them, but it caused a problem: if there is a single page
1185 with a very bad page force (for example because of a forced page break),
1186 the page breaker will put in a _lot_ of pages so that the bad force
1187 becomes averaged out over many pages. */
1188 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1193 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1194 are by far the most common cases, we have special functions for them.
1196 space_systems_on_1_page has a different calling convention than most of the
1197 space_systems functions. This is because space_systems_on_1_page is (unlike
1198 the other space_systems functions) sometimes called on subsets of a full
1201 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1203 Page_spacing space (page_height, this);
1204 Page_spacing_result ret;
1207 for (vsize i = 0; i < lines.size (); i++)
1209 space.append_system (lines[i]);
1210 line_count += lines[i].compressed_nontitle_lines_count_;
1213 ret.systems_per_page_.push_back (lines.size ());
1214 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1215 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1216 ret.system_count_status_ |= line_count_status (line_count);
1218 /* don't do finalize_spacing_result () because we are only an internal function */
1223 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1225 Real page1_height = page_height (first_page_num, false);
1226 Real page2_height = page_height (first_page_num + 1, is_last ());
1227 bool ragged1 = ragged ();
1228 bool ragged2 = ragged () || (is_last () && ragged_last ());
1230 /* if there is a forced break, this reduces to 2 1-page problems */
1231 cache_line_details (configuration);
1232 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1233 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1235 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1236 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1237 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1238 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1240 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1241 p1.force_.push_back (p2.force_[0]);
1242 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1246 vector<Real> page1_force;
1247 vector<Real> page2_force;
1249 // page1_penalty and page2_penalty store the penalties based
1250 // on min-systems-per-page and max-systems-per-page.
1251 vector<Real> page1_penalty;
1252 vector<Real> page2_penalty;
1254 // page1_status and page2_status keep track of whether the min-systems-per-page
1255 // and max-systems-per-page constraints are satisfied.
1256 vector<int> page1_status;
1257 vector<int> page2_status;
1259 Page_spacing page1 (page1_height, this);
1260 Page_spacing page2 (page2_height, this);
1261 int page1_line_count = 0;
1262 int page2_line_count = 0;
1264 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1265 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1266 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1267 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1268 page1_status.resize (cached_line_details_.size () - 1, 0);
1269 page2_status.resize (cached_line_details_.size () - 1, 0);
1271 /* find the page 1 and page 2 forces for each page-breaking position */
1272 for (vsize i = 0; i < page1_force.size (); i++)
1274 page1.append_system (cached_line_details_[i]);
1275 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1276 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1277 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1279 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1280 page1_penalty[i] = line_count_penalty (page1_line_count);
1281 page1_status[i] = line_count_status (page1_line_count);
1284 page2_force[page2_force.size () - 1 - i] =
1285 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1287 page2_force[page2_force.size () - 1 - i] = page2.force_;
1288 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1289 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1292 /* find the position that minimises the sum of the page forces */
1293 vsize best_sys_count = 1;
1294 Real best_demerits = infinity_f;
1295 for (vsize i = 0; i < page1_force.size (); i++)
1297 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1299 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1300 // constraints. That is, we penalize harshly when they don't happen
1301 // but we don't completely reject.
1303 + page1_penalty[i] + page2_penalty[i]
1304 + cached_line_details_[i+1].page_penalty_
1305 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1306 if (dem < best_demerits)
1308 best_demerits = dem;
1309 best_sys_count = i+1;
1313 Page_spacing_result ret;
1314 ret.systems_per_page_.push_back (best_sys_count);
1315 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1316 ret.force_.push_back (page1_force[best_sys_count-1]);
1317 ret.force_.push_back (page2_force[best_sys_count-1]);
1318 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1319 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1320 + cached_line_details_.back ().page_penalty_
1321 + cached_line_details_.back ().turn_penalty_
1322 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1324 /* don't do finalize_spacing_result () because we are only an internal function */
1329 Page_breaking::all_lines_stretched (vsize configuration)
1331 cache_line_details (configuration);
1332 for (vsize i = 0; i < cached_line_details_.size (); i++)
1333 if (cached_line_details_[i].force_ < 0)
1339 Page_breaking::Line_division
1340 Page_breaking::current_configuration (vsize configuration_index) const
1342 return current_configurations_[configuration_index];
1346 Page_breaking::is_last () const
1348 return current_end_breakpoint_ == last_break_position ();
1352 Page_breaking::ends_score () const
1354 return breaks_[current_end_breakpoint_].score_ender_;
1358 Page_breaking::last_break_position () const
1360 return breaks_.size () - 1;
1363 // This gives the minimum distance between the top of the
1364 // printable area (ie. the bottom of the top-margin) and
1365 // the extent box of the topmost system.
1367 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1369 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1371 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1373 Real min_distance = -infinity_f;
1376 Page_layout_problem::read_spacing_spec (first_system_spacing,
1378 ly_symbol2scm ("minimum-distance"));
1379 Page_layout_problem::read_spacing_spec (first_system_spacing,
1381 ly_symbol2scm ("padding"));
1383 // FIXME: take into account the height of the header
1384 return max (0.0, max (padding, min_distance - line.extent_[UP]));
1388 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1390 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1391 Real min_distance = -infinity_f;
1394 Page_layout_problem::read_spacing_spec (last_system_spacing,
1396 ly_symbol2scm ("minimum-distance"));
1397 Page_layout_problem::read_spacing_spec (last_system_spacing,
1399 ly_symbol2scm ("padding"));
1401 // FIXME: take into account the height of the footer
1402 return max (0.0, max (padding, min_distance + line.extent_[DOWN]));