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--2007 Joe Neeman <joeneeman@gmail.com>
10 #include "page-breaking.hh"
12 #include "international.hh"
14 #include "output-def.hh"
15 #include "page-spacing.hh"
16 #include "paper-book.hh"
17 #include "paper-score.hh"
18 #include "paper-system.hh"
22 /* for each forbidden page break, merge the systems around it into one system. */
23 static vector<Line_details>
24 compress_lines (const vector<Line_details> &orig)
26 vector<Line_details> ret;
28 for (vsize i = 0; i < orig.size (); i++)
30 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
32 Line_details const &old = ret.back ();
33 Line_details compressed = orig[i];
34 compressed.extent_[DOWN] = old.extent_[DOWN];
35 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
36 compressed.space_ += old.space_;
37 compressed.inverse_hooke_ += old.inverse_hooke_;
39 /* we don't need the force_ field for the vertical spacing,
40 so we use force_ = n to signal that the line was compressed,
41 reducing the number of lines by n (and force_ = 0 otherwise).
42 This makes uncompression much easier. */
43 compressed.force_ = old.force_ + 1;
44 ret.back () = compressed;
48 ret.push_back (orig[i]);
49 ret.back ().force_ = 0;
55 /* translate the number of systems-per-page into something meaningful for
56 the uncompressed lines.
59 uncompress_solution (vector<vsize> const &systems_per_page,
60 vector<Line_details> const &compressed)
65 for (vsize i = 0; i < systems_per_page.size (); i++)
67 int compressed_count = 0;
68 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
69 compressed_count += (int)compressed[j].force_;
71 ret.push_back (systems_per_page[i] + compressed_count);
72 start_sys += systems_per_page[i];
77 /* for Page_breaking, the start index (when we are dealing with the stuff
78 between a pair of breakpoints) refers to the break_ index of the end of
79 the previous page. So the system index of the start of the current page
80 could either be the same as the end of the previous page or one more than
83 /* Turn a break index into the sys index that starts the next page */
85 Page_breaking::next_system (Break_position const &break_pos) const
87 vsize sys = break_pos.sys_;
89 if (sys == VPOS) /* beginning of the book */
91 if (all_[sys].pscore_ && !break_pos.score_ender_)
92 return sys; /* the score overflows the previous page */
93 return sys + 1; /* this page starts with a new sys */
96 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
99 ragged_ = to_boolean (pb->paper_->c_variable ("ragged"));
100 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last"));
101 create_system_list ();
102 find_chunks_and_breaks (is_break);
105 Page_breaking::~Page_breaking ()
110 Page_breaking::ragged () const
116 Page_breaking::ragged_last () const
121 /* translate indices into breaks_ into start-end parameters for the line breaker */
123 Page_breaking::line_breaker_args (vsize sys,
124 Break_position const &start,
125 Break_position const &end,
126 vsize *line_breaker_start,
127 vsize *line_breaker_end)
129 assert (all_[sys].pscore_);
130 assert (next_system (start) <= sys && sys <= end.sys_);
132 if (start.sys_ == sys)
133 *line_breaker_start = start.score_break_;
135 *line_breaker_start = 0;
138 *line_breaker_end = end.score_break_;
140 *line_breaker_end = VPOS;
144 Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div)
146 vector<Break_position> chunks = chunk_list (start_break, end_break);
147 bool ignore_div = false;
148 if (chunks.size () != div.size () + 1)
150 programming_error ("did not find a valid page breaking configuration");
154 for (vsize i = 0; i + 1 < chunks.size (); i++)
156 vsize sys = next_system (chunks[i]);
157 if (all_[sys].pscore_)
161 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
163 vector<Column_x_positions> pos = ignore_div
164 ? line_breaking_[sys].best_solution (start, end)
165 : line_breaking_[sys].solve (start, end, div[i]);
166 all_[sys].pscore_->root_system ()->break_into_pieces (pos);
172 Page_breaking::systems ()
175 for (vsize sys = 0; sys < all_.size (); sys++)
177 if (all_[sys].pscore_)
179 all_[sys].pscore_->root_system ()->do_break_substitution_and_fixup_refpoints ();
180 SCM lines = all_[sys].pscore_->root_system ()->get_broken_system_grobs ();
181 ret = scm_cons (lines, ret);
185 Prob *pb = all_[sys].prob_;
186 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
190 return scm_append (scm_reverse (ret));
194 Page_breaking::page_height (int page_num, bool last) const
196 SCM mod = scm_c_resolve_module ("scm page");
197 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
198 SCM make_page = scm_c_module_lookup (mod, "make-page");
200 calc_height = scm_variable_ref (calc_height);
201 make_page = scm_variable_ref (make_page);
203 SCM page = scm_apply_0 (make_page, scm_list_n (
205 ly_symbol2scm ("page-number"), scm_from_int (page_num),
206 ly_symbol2scm ("is-last"), scm_from_bool (last),
208 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
209 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
213 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
215 Break_position const &pos = breaks_[breakpoint];
217 if (pos.sys_ == VPOS)
219 if (all_[pos.sys_].pscore_)
220 return pos.col_->get_property (str);
221 return all_[pos.sys_].prob_->get_property (str);
225 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
227 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
228 SCM page_module = scm_c_resolve_module ("scm page");
230 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
231 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
232 make_page = scm_variable_ref (make_page);
233 page_stencil = scm_variable_ref (page_stencil);
235 SCM book = book_->self_scm ();
236 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
237 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
238 int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
241 for (vsize i = 0; i < lines_per_page.size (); i++)
243 SCM page_num = scm_from_int (i + first_page_number);
244 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
245 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
246 SCM line_count = scm_from_int (lines_per_page[i]);
247 SCM lines = scm_list_head (systems, line_count);
248 SCM page = scm_apply_0 (make_page,
249 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
251 scm_apply_1 (page_stencil, page, SCM_EOL);
252 ret = scm_cons (page, ret);
253 systems = scm_list_tail (systems, line_count);
255 ret = scm_reverse (ret);
259 /* The page-turn-page-breaker needs to have a line-breaker between any two
260 columns with non-NULL page-turn-permission.
262 The optimal-breaker needs to have a line-breaker between any two columns
263 with page-break-permission = 'force.
265 By using a grob predicate, we can accommodate both of these uses.
268 Page_breaking::create_system_list ()
270 SCM specs = book_->get_system_specs ();
271 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
273 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
275 SCM system_count = ps->layout ()->c_variable ("system-count");
277 if (scm_is_number (system_count))
278 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
279 scm_vector_to_list (ps->get_paper_systems ()),
282 all_.push_back (System_spec (ps));
286 Prob *pb = unsmob_prob (scm_car (s));
290 all_.push_back (System_spec (pb));
296 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
298 SCM force_sym = ly_symbol2scm ("force");
300 chunks_.push_back (Break_position ());
301 breaks_.push_back (Break_position ());
303 for (vsize i = 0; i < all_.size (); i++)
307 vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
308 vector<vsize> line_breaker_columns;
309 line_breaker_columns.push_back (0);
311 for (vsize j = 1; j < cols.size (); j++)
313 bool last = j == cols.size () - 1;
314 bool break_point = is_break (cols[j]);
315 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
316 Break_position cur_pos = Break_position (i,
317 line_breaker_columns.size (),
321 if (break_point || (i == all_.size () - 1 && last))
322 breaks_.push_back (cur_pos);
323 if (chunk_end || last)
324 chunks_.push_back (cur_pos);
326 if ((break_point || chunk_end) && !last)
327 line_breaker_columns.push_back (j);
329 line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
333 /* TODO: we want some way of applying Break_p to a prob? */
334 if (i == all_.size () - 1)
335 breaks_.push_back (Break_position (i));
337 chunks_.push_back (Break_position (i));
338 line_breaking_.push_back (Constrained_breaking (NULL));
343 vector<Break_position>
344 Page_breaking::chunk_list (vsize start_index, vsize end_index)
346 Break_position start = breaks_[start_index];
347 Break_position end = breaks_[end_index];
350 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
353 vector<Break_position> ret;
354 ret.push_back (start);
355 for (; i < chunks_.size () && chunks_[i] < end; i++)
356 ret.push_back (chunks_[i]);
362 Page_breaking::min_system_count (vsize start, vsize end)
364 vector<Break_position> chunks = chunk_list (start, end);
365 Line_division div = system_count_bounds (chunks, true);
368 for (vsize i = 0; i < div.size (); i++)
374 Page_breaking::max_system_count (vsize start, vsize end)
376 vector<Break_position> chunks = chunk_list (start, end);
377 Line_division div = system_count_bounds (chunks, false);
380 for (vsize i = 0; i < div.size (); i++)
385 Page_breaking::Line_division
386 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
388 assert (chunks.size () >= 2);
391 ret.resize (chunks.size () - 1, 1);
393 for (vsize i = 0; i + 1 < chunks.size (); i++)
395 vsize sys = next_system (chunks[i]);
396 if (all_[sys].pscore_)
400 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
402 ? line_breaking_[sys].min_system_count (start, end)
403 : line_breaking_[sys].max_system_count (start, end);
411 Page_breaking::set_current_breakpoints (vsize start,
414 Line_division lower_bound,
415 Line_division upper_bound)
417 current_chunks_ = chunk_list (start, end);
418 current_start_breakpoint_ = start;
419 current_end_breakpoint_ = end;
420 clear_line_details_cache ();
422 if (!lower_bound.size ())
423 lower_bound = system_count_bounds (current_chunks_, true);
424 if (!upper_bound.size ())
425 upper_bound = system_count_bounds (current_chunks_, false);
427 assert (lower_bound.size () == current_chunks_.size () - 1);
428 assert (upper_bound.size () == current_chunks_.size () - 1);
430 Line_division work_in_progress;
431 current_configurations_.clear ();
432 line_divisions_rec (system_count,
439 Page_breaking::current_configuration_count () const
441 return current_configurations_.size ();
445 Page_breaking::cache_line_details (vsize configuration_index)
447 if (cached_configuration_index_ != configuration_index)
449 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
450 if (!scm_is_number (padding_scm))
451 padding_scm = book_->paper_->c_variable ("between-system-padding");
452 Real padding = robust_scm2double (padding_scm, 0.0);
454 Line_division &div = current_configurations_[configuration_index];
455 cached_line_details_.clear ();
456 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
458 vsize sys = next_system (current_chunks_[i]);
459 if (all_[sys].pscore_)
463 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
465 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
466 cached_line_details_.insert (cached_line_details_.end (), details.begin (), details.end ());
470 assert (div[i] == 1);
471 cached_line_details_.push_back (Line_details (all_[sys].prob_));
472 cached_line_details_.back ().padding_ = padding;
475 cached_line_details_ = compress_lines (cached_line_details_);
480 Page_breaking::clear_line_details_cache ()
482 cached_configuration_index_ = VPOS;
483 cached_line_details_.clear ();
487 Page_breaking::line_divisions_rec (vsize system_count,
488 Line_division const &min_sys,
489 Line_division const &max_sys,
490 Line_division *cur_division)
492 vsize my_index = cur_division->size ();
493 vsize others_min = 0;
494 vsize others_max = 0;
496 for (vsize i = my_index + 1; i < min_sys.size (); i++)
498 others_min += min_sys[i];
499 others_max += max_sys[i];
501 others_max = min (others_max, system_count);
502 vsize real_min = max (min_sys[my_index], system_count - others_max);
503 vsize real_max = min (max_sys[my_index], system_count - others_min);
505 if (real_min > real_max || real_min <= 0)
507 /* this should never happen within a recursive call. If it happens
508 at all, it means that we were called with an unsolvable problem
509 and we should return an empty result */
510 assert (my_index == 0);
514 for (vsize i = real_min; i <= real_max; i++)
516 cur_division->push_back (i);
517 if (my_index == min_sys.size () - 1)
518 current_configurations_.push_back (*cur_division);
520 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
521 cur_division->pop_back ();
526 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
529 Real cur_rod_height = 0;
530 Real cur_spring_height = 0;
531 Real cur_page_height = page_height (first_page_num, false);
533 cache_line_details (configuration);
534 for (vsize i = 0; i < cached_line_details_.size (); i++)
536 Real ext_len = cached_line_details_[i].extent_.length ();
537 Real next_rod_height = cur_rod_height + ext_len
538 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
539 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
540 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
543 if ((next_height > cur_page_height && cur_rod_height > 0)
544 || (i + 1 < cached_line_details_.size ()
545 && cached_line_details_[i].page_permission_ == ly_symbol2scm ("force")))
547 cur_rod_height = ext_len;
548 cur_spring_height = line_space (cached_line_details_[i]);
549 cur_page_height = page_height (first_page_num + ret, false);
554 cur_rod_height = next_rod_height;
555 cur_spring_height = next_spring_height;
559 /* there are two potential problems with the last page (because we didn't know
560 it was the last page until after we managed to fit all the systems to it):
561 - we are ragged-last but the last page has a compressed spring
562 - the value returned by page_height (num, true) is smaller than the
563 value returned by page_height (num, false) and it causes the page not to
566 In either case, we just need to add one more page. This is because the last
567 line will always fit on the extra page and by adding one more page to the
568 end, the previous page is no longer the last page, so our previous
569 calculations that treated it as a non-last page were ok.
572 cur_page_height = page_height (first_page_num + ret - 1, true);
573 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
574 if (cur_height > cur_page_height)
580 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
583 assert (n >= min_page_count (configuration, first_page_num));
585 cache_line_details (configuration);
586 if (n > cached_line_details_.size ())
587 return Spacing_result ();
589 ret = space_systems_on_1_page (cached_line_details_,
590 page_height (first_page_num, last ()),
591 ragged () || (last () && ragged_last ()));
593 ret = space_systems_on_2_pages (configuration, first_page_num);
596 Page_spacer ps (cached_line_details_, first_page_num, this);
600 return finalize_spacing_result (configuration, ret);
604 Page_breaking::blank_page_penalty () const
606 SCM penalty_sym = last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
607 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
611 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
613 Spacing_result n_res = space_systems_on_n_pages (configuration, n, first_page_num);
614 Spacing_result m_res = space_systems_on_n_pages (configuration, n+1, first_page_num);
615 Real penalty = blank_page_penalty ();
616 n_res.demerits_ += penalty;
617 n_res.force_.back () += penalty;
619 if (n_res.demerits_ < m_res.demerits_)
625 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
627 vsize min_p_count = min_page_count (configuration, first_page_num);
628 Real odd_pages_penalty = blank_page_penalty ();
630 cache_line_details (configuration);
631 Page_spacer ps (cached_line_details_, first_page_num, this);
632 Spacing_result best = ps.solve (min_p_count);
633 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
634 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
636 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
638 Spacing_result cur = ps.solve (i);
639 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
640 if (cur.demerits_ < best.demerits_)
644 return finalize_spacing_result (configuration, best);
647 /* Calculate demerits and fix res.systems_per_page_ so that
648 it refers to the original line numbers, not the ones given by compress_lines (). */
650 Page_breaking::finalize_spacing_result (vsize configuration, Spacing_result res)
652 cache_line_details (configuration);
653 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
656 Real line_penalty = 0;
658 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
660 for (vsize i = 0; i < cached_line_details_.size (); i++)
662 line_force += cached_line_details_[i].force_ * cached_line_details_[i].force_;
663 line_penalty += cached_line_details_[i].break_penalty_;
666 for (vsize i = 0; i < res.force_.size (); i++)
667 page_force += res.force_[i] * res.force_[i];
669 /* for a while we tried averaging page and line forces across pages instead
670 of summing them, but it caused a problem: if there is a single page
671 with a very bad page force (for example because of a forced page break),
672 the page breaker will put in a _lot_ of pages so that the bad force
673 becomes averaged out over many pages. */
674 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
679 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
680 are by far the most common cases, we have special functions for them.
682 space_systems_on_1_page has a different calling convention than most of the
683 space_systems functions. This is because space_systems_on_1_page is (unlike
684 the other space_systems functions) sometimes called on subsets of a full
687 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
689 Page_spacing space (page_height);
692 for (vsize i = 0; i < lines.size (); i++)
693 space.append_system (lines[i]);
695 ret.systems_per_page_.push_back (lines.size ());
696 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
697 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
699 /* don't do finalize_spacing_result () because we are only an internal function */
704 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
706 Real page1_height = page_height (first_page_num, false);
707 Real page2_height = page_height (first_page_num+1, last ());
708 bool ragged1 = ragged ();
709 bool ragged2 = ragged () || (last () && ragged_last ());
711 /* if there is a forced break, this reduces to 2 1-page problems */
712 cache_line_details (configuration);
713 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
714 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
716 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
717 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
718 Spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
719 Spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
721 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
722 p1.force_.push_back (p2.force_[0]);
723 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
727 vector<Real> page1_force;
728 vector<Real> page2_force;
729 Page_spacing page1 (page1_height);
730 Page_spacing page2 (page2_height);
732 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
733 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
735 /* find the page 1 and page 2 forces for each page-breaking position */
736 for (vsize i = 0; i < page1_force.size (); i++)
738 page1.append_system (cached_line_details_[i]);
739 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
740 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
743 page2_force[page2_force.size () - 1 - i] =
744 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
746 page2_force[page2_force.size () - 1 - i] = page2.force_;
749 /* find the position that minimises the sum of the page forces */
750 vsize best_sys_count = 1;
751 Real best_demerits = infinity_f;
752 for (vsize i = 0; i < page1_force.size (); i++)
754 Real dem = page1_force[i] * page1_force[i]
755 + page2_force[i] * page2_force[i]
756 + cached_line_details_[i+1].page_penalty_
757 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
758 if (dem < best_demerits)
761 best_sys_count = i+1;
766 ret.systems_per_page_.push_back (best_sys_count);
767 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
768 ret.force_.push_back (page1_force[best_sys_count-1]);
769 ret.force_.push_back (page2_force[best_sys_count-1]);
770 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
771 + cached_line_details_.back ().page_penalty_
772 + cached_line_details_.back ().turn_penalty_;
774 /* don't do finalize_spacing_result () because we are only an internal function */
779 Page_breaking::all_lines_stretched (vsize configuration)
781 cache_line_details (configuration);
782 for (vsize i = 0; i < cached_line_details_.size (); i++)
783 if (cached_line_details_[i].force_ < 0)
789 Page_breaking::Line_division
790 Page_breaking::current_configuration (vsize configuration_index) const
792 return current_configurations_[configuration_index];
795 bool Page_breaking::last () const
797 return current_end_breakpoint_ == breaks_.size () - 1;