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>
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
24 static vector<Line_details>
25 compress_lines (const vector<Line_details> &orig)
27 vector<Line_details> ret;
29 for (vsize i = 0; i < orig.size (); i++)
31 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
33 Line_details const &old = ret.back ();
34 Line_details compressed = orig[i];
35 compressed.extent_[DOWN] = old.extent_[DOWN];
36 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
37 compressed.space_ += old.space_;
38 compressed.inverse_hooke_ += old.inverse_hooke_;
40 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
41 compressed.compressed_nontitle_lines_count_ =
42 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
44 compressed.title_ = compressed.title_ && old.title_;
45 ret.back () = compressed;
49 ret.push_back (orig[i]);
50 ret.back ().force_ = 0;
56 /* translate the number of systems-per-page into something meaningful for
57 the uncompressed lines.
60 uncompress_solution (vector<vsize> const &systems_per_page,
61 vector<Line_details> const &compressed)
66 for (vsize i = 0; i < systems_per_page.size (); i++)
68 int compressed_count = 0;
69 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
70 compressed_count += compressed[j].compressed_lines_count_ - 1;
72 ret.push_back (systems_per_page[i] + compressed_count);
73 start_sys += systems_per_page[i];
78 /* for Page_breaking, the start index (when we are dealing with the stuff
79 between a pair of breakpoints) refers to the break_ index of the end of
80 the previous page. So the system index of the start of the current page
81 could either be the same as the end of the previous page or one more than
84 /* Turn a break index into the sys index that starts the next page */
86 Page_breaking::next_system (Break_position const &break_pos) const
88 vsize sys = break_pos.system_spec_index_;
90 if (sys == VPOS) /* beginning of the book */
92 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
93 return sys; /* the score overflows the previous page */
94 return sys + 1; /* this page starts with a new System_spec */
97 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
101 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
102 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
103 page_top_space_ = robust_scm2double (pb->paper_->c_variable ("page-top-space"), 0);
104 systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0);
105 max_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0);
106 min_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0);
108 create_system_list ();
109 find_chunks_and_breaks (is_break);
112 Page_breaking::~Page_breaking ()
117 Page_breaking::ragged () const
123 Page_breaking::ragged_last () const
129 Page_breaking::systems_per_page () const
131 return systems_per_page_;
135 Page_breaking::max_systems_per_page () const
137 return max_systems_per_page_;
141 Page_breaking::min_systems_per_page () const
143 return min_systems_per_page_;
147 Page_breaking::page_top_space () const
149 return page_top_space_;
153 Page_breaking::system_count () const
155 return system_count_;
159 Page_breaking::too_many_lines (int line_count) const
161 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
165 Page_breaking::too_few_lines (int line_count) const
167 return line_count < min_systems_per_page ();
171 Page_breaking::line_count_penalty (int line_count) const
173 // TODO: also check min_systems_per_page (once we support it in Page_spacer)
174 return too_many_lines (line_count) ? BAD_SPACING_PENALTY : 0;
177 /* translate indices into breaks_ into start-end parameters for the line breaker */
179 Page_breaking::line_breaker_args (vsize sys,
180 Break_position const &start,
181 Break_position const &end,
182 vsize *line_breaker_start,
183 vsize *line_breaker_end)
185 assert (system_specs_[sys].pscore_);
186 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
188 if (start.system_spec_index_ == sys)
189 *line_breaker_start = start.score_break_;
191 *line_breaker_start = 0;
193 if (end.system_spec_index_ == sys)
194 *line_breaker_end = end.score_break_;
196 *line_breaker_end = VPOS;
200 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
201 Line_division const &div)
203 vector<Break_position> chunks = chunk_list (start_break, end_break);
204 bool ignore_div = false;
205 if (chunks.size () != div.size () + 1)
207 programming_error ("did not find a valid page breaking configuration");
211 for (vsize i = 0; i + 1 < chunks.size (); i++)
213 vsize sys = next_system (chunks[i]);
214 if (system_specs_[sys].pscore_)
218 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
220 vector<Column_x_positions> pos = ignore_div
221 ? line_breaking_[sys].best_solution (start, end)
222 : line_breaking_[sys].solve (start, end, div[i]);
223 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
229 Page_breaking::systems ()
232 for (vsize sys = 0; sys < system_specs_.size (); sys++)
234 if (system_specs_[sys].pscore_)
236 system_specs_[sys].pscore_->root_system ()
237 ->do_break_substitution_and_fixup_refpoints ();
238 SCM lines = system_specs_[sys].pscore_->root_system ()
239 ->get_broken_system_grobs ();
240 ret = scm_cons (lines, ret);
244 Prob *pb = system_specs_[sys].prob_;
245 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
249 return scm_append (scm_reverse (ret));
253 Page_breaking::page_height (int page_num, bool last) const
255 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
256 SCM mod = scm_c_resolve_module ("scm page");
257 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
258 SCM make_page = scm_c_module_lookup (mod, "make-page");
260 calc_height = scm_variable_ref (calc_height);
261 make_page = scm_variable_ref (make_page);
263 SCM page = scm_apply_0 (make_page, scm_list_n (
265 ly_symbol2scm ("page-number"), scm_from_int (page_num),
266 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
267 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
269 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
270 return scm_to_double (height) - page_top_space_;
274 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
276 Break_position const &pos = breaks_[breakpoint];
278 if (pos.system_spec_index_ == VPOS)
280 if (system_specs_[pos.system_spec_index_].pscore_)
281 return pos.col_->get_property (str);
282 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
286 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
288 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
289 SCM page_module = scm_c_resolve_module ("scm page");
291 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
292 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
293 make_page = scm_variable_ref (make_page);
294 page_stencil = scm_variable_ref (page_stencil);
296 SCM book = book_->self_scm ();
297 int first_page_number
298 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
299 bool last_bookpart = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
301 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
302 if (label_page_table == SCM_UNDEFINED)
303 label_page_table = SCM_EOL;
305 for (vsize i = 0; i < lines_per_page.size (); i++)
307 SCM page_num = scm_from_int (i + first_page_number);
308 bool partbook_last_page = (i == lines_per_page.size () - 1);
309 SCM rag = scm_from_bool (ragged () || ( partbook_last_page && ragged_last ()));
310 SCM line_count = scm_from_int (lines_per_page[i]);
311 SCM lines = scm_list_head (systems, line_count);
312 SCM page = scm_apply_0 (make_page,
313 scm_list_n (book, lines, page_num, rag,
314 scm_from_bool (last_bookpart),
315 scm_from_bool (partbook_last_page),
318 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
320 SCM labels = SCM_EOL;
321 if (Grob * line = unsmob_grob (scm_car (l)))
323 System *system = dynamic_cast<System*> (line);
324 labels = system->get_property ("labels");
326 else if (Prob *prob = unsmob_prob (scm_car (l)))
327 labels = prob->get_property ("labels");
329 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
330 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
334 scm_apply_1 (page_stencil, page, SCM_EOL);
335 ret = scm_cons (page, ret);
336 systems = scm_list_tail (systems, line_count);
338 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
339 ret = scm_reverse (ret);
343 /* The page-turn-page-breaker needs to have a line-breaker between any two
344 columns with non-NULL page-turn-permission.
346 The optimal-breaker needs to have a line-breaker between any two columns
347 with page-break-permission = 'force.
349 By using a grob predicate, we can accommodate both of these uses.
352 Page_breaking::create_system_list ()
354 SCM specs = book_->get_system_specs ();
355 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
357 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
359 SCM system_count = ps->layout ()->c_variable ("system-count");
361 if (scm_is_number (system_count))
362 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
363 scm_vector_to_list (ps->get_paper_systems ()),
366 system_specs_.push_back (System_spec (ps));
370 Prob *pb = unsmob_prob (scm_car (s));
374 system_specs_.push_back (System_spec (pb));
380 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
382 SCM force_sym = ly_symbol2scm ("force");
384 chunks_.push_back (Break_position ());
385 breaks_.push_back (Break_position ());
387 for (vsize i = 0; i < system_specs_.size (); i++)
389 if (system_specs_[i].pscore_)
392 = system_specs_[i].pscore_->root_system ()->used_columns ();
393 vector<vsize> line_breaker_columns;
394 line_breaker_columns.push_back (0);
396 for (vsize j = 1; j < cols.size (); j++)
398 bool last = (j == cols.size () - 1);
399 bool break_point = is_break (cols[j]);
400 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
401 Break_position cur_pos = Break_position (i,
402 line_breaker_columns.size (),
406 if (break_point || (i == system_specs_.size () - 1 && last))
407 breaks_.push_back (cur_pos);
408 if (chunk_end || last)
409 chunks_.push_back (cur_pos);
411 if ((break_point || chunk_end) && !last)
412 line_breaker_columns.push_back (j);
414 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
418 /* TODO: we want some way of applying Break_p to a prob? */
419 if (i == system_specs_.size () - 1)
420 breaks_.push_back (Break_position (i));
422 chunks_.push_back (Break_position (i));
424 /* FIXME: shouldn't we push a Null_breaker or similar dummy
426 line_breaking_.push_back (Constrained_breaking (NULL));
431 vector<Break_position>
432 Page_breaking::chunk_list (vsize start_index, vsize end_index)
434 Break_position start = breaks_[start_index];
435 Break_position end = breaks_[end_index];
438 for (; i < chunks_.size () && chunks_[i] <= start; i++)
441 vector<Break_position> ret;
442 ret.push_back (start);
443 for (; i < chunks_.size () && chunks_[i] < end; i++)
444 ret.push_back (chunks_[i]);
450 Page_breaking::min_system_count (vsize start, vsize end)
452 vector<Break_position> chunks = chunk_list (start, end);
453 Line_division div = system_count_bounds (chunks, true);
456 for (vsize i = 0; i < div.size (); i++)
462 Page_breaking::max_system_count (vsize start, vsize end)
464 vector<Break_position> chunks = chunk_list (start, end);
465 Line_division div = system_count_bounds (chunks, false);
468 for (vsize i = 0; i < div.size (); i++)
473 Page_breaking::Line_division
474 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
477 assert (chunks.size () >= 2);
480 ret.resize (chunks.size () - 1, 1);
482 for (vsize i = 0; i + 1 < chunks.size (); i++)
484 vsize sys = next_system (chunks[i]);
485 if (system_specs_[sys].pscore_)
489 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
491 ? line_breaking_[sys].min_system_count (start, end)
492 : line_breaking_[sys].max_system_count (start, end);
500 Page_breaking::set_current_breakpoints (vsize start,
503 Line_division lower_bound,
504 Line_division upper_bound)
506 system_count_ = system_count;
507 current_chunks_ = chunk_list (start, end);
508 current_start_breakpoint_ = start;
509 current_end_breakpoint_ = end;
510 clear_line_details_cache ();
512 if (!lower_bound.size ())
513 lower_bound = system_count_bounds (current_chunks_, true);
514 if (!upper_bound.size ())
515 upper_bound = system_count_bounds (current_chunks_, false);
517 assert (lower_bound.size () == current_chunks_.size () - 1);
518 assert (upper_bound.size () == current_chunks_.size () - 1);
520 Line_division work_in_progress;
521 current_configurations_.clear ();
522 line_divisions_rec (system_count,
527 /* we only consider a constant number of configurations. Otherwise,
528 this becomes slow when there are many small scores. The constant
529 5 is somewhat arbitrary. */
530 if (current_configurations_.size () > 5)
532 vector<pair<Real,vsize> > dems_and_indices;
534 for (vsize i = 0; i < current_configurations_.size (); i++)
536 cache_line_details (i);
538 for (vsize j = 0; j < cached_line_details_.size (); j++)
539 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
540 + cached_line_details_[j].break_penalty_;
542 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
544 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
546 vector<Line_division> best_5_configurations;
547 for (vsize i = 0; i < 5; i++)
548 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
550 clear_line_details_cache ();
551 current_configurations_ = best_5_configurations;
556 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
558 current_chunks_ = chunk_list (start, end);
559 current_start_breakpoint_ = start;
560 current_end_breakpoint_ = end;
561 clear_line_details_cache ();
565 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
567 vsize sys = next_system (current_chunks_[i]);
568 if (system_specs_[sys].pscore_)
570 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
571 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
576 system_count_ += div.back ();
578 current_configurations_.clear ();
579 current_configurations_.push_back (div);
583 Page_breaking::current_configuration_count () const
585 return current_configurations_.size ();
589 Page_breaking::cache_line_details (vsize configuration_index)
591 if (cached_configuration_index_ != configuration_index)
593 cached_configuration_index_ = configuration_index;
594 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
595 if (!scm_is_number (padding_scm))
596 padding_scm = book_->paper_->c_variable ("between-system-padding");
597 Real padding = robust_scm2double (padding_scm, 0.0);
599 Line_division &div = current_configurations_[configuration_index];
600 uncompressed_line_details_.clear ();
601 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
603 vsize sys = next_system (current_chunks_[i]);
604 if (system_specs_[sys].pscore_)
608 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
610 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
611 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
615 assert (div[i] == 1);
616 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
617 uncompressed_line_details_.back ().padding_ =
618 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
622 cached_line_details_ = compress_lines (uncompressed_line_details_);
627 Page_breaking::clear_line_details_cache ()
629 cached_configuration_index_ = VPOS;
630 cached_line_details_.clear ();
631 uncompressed_line_details_.clear ();
635 Page_breaking::line_divisions_rec (vsize system_count,
636 Line_division const &min_sys,
637 Line_division const &max_sys,
638 Line_division *cur_division)
640 vsize my_index = cur_division->size ();
641 vsize others_min = 0;
642 vsize others_max = 0;
644 for (vsize i = my_index + 1; i < min_sys.size (); i++)
646 others_min += min_sys[i];
647 others_max += max_sys[i];
649 others_max = min (others_max, system_count);
650 vsize real_min = max (min_sys[my_index], system_count - others_max);
651 vsize real_max = min (max_sys[my_index], system_count - others_min);
653 if (real_min > real_max || real_min <= 0)
655 /* this should never happen within a recursive call. If it happens
656 at all, it means that we were called with an unsolvable problem
657 and we should return an empty result */
658 assert (my_index == 0);
662 for (vsize i = real_min; i <= real_max; i++)
664 cur_division->push_back (i);
665 if (my_index == min_sys.size () - 1)
666 current_configurations_.push_back (*cur_division);
668 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
669 cur_division->pop_back ();
674 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
677 Real cur_rod_height = 0;
678 Real cur_spring_height = 0;
679 Real cur_page_height = page_height (first_page_num, false);
682 cache_line_details (configuration);
683 for (vsize i = 0; i < cached_line_details_.size (); i++)
685 Real ext_len = cached_line_details_[i].extent_.length ();
686 Real next_rod_height = cur_rod_height + ext_len
687 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
688 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
689 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
691 line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
693 if ((next_height > cur_page_height && cur_rod_height > 0)
694 || too_many_lines (line_count)
696 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
698 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
699 cur_rod_height = ext_len;
700 cur_spring_height = cached_line_details_[i].space_;
701 cur_page_height = page_height (first_page_num + ret, false);
706 cur_rod_height = next_rod_height;
707 cur_spring_height = next_spring_height;
711 /* there are two potential problems with the last page (because we didn't know
712 it was the last page until after we managed to fit all the systems to it):
713 - we are ragged-last but the last page has a compressed spring
714 - the value returned by page_height (num, true) is smaller than the
715 value returned by page_height (num, false) and it causes the page not to
718 In either case, we just need to add one more page. This is because the last
719 line will always fit on the extra page and by adding one more page to the
720 end, the previous page is no longer the last page, so our previous
721 calculations that treated it as a non-last page were ok.
724 cur_page_height = page_height (first_page_num + ret - 1, true);
725 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
726 if (cur_height > cur_page_height
727 /* don't increase the page count if the last page had only one system */
728 && cur_rod_height > cached_line_details_.back ().extent_.length ())
731 assert (ret <= cached_line_details_.size ());
735 // If systems_per_page_ is positive, we don't really try to space on N pages;
736 // we just put the requested number of systems on each page and penalize
737 // if the result doesn't have N pages.
739 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
741 Page_spacing_result ret;
743 if (systems_per_page_ > 0)
745 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
746 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
750 cache_line_details (configuration);
751 bool valid_n = (n >= min_page_count (configuration, first_page_num)
752 && n <= cached_line_details_.size ());
755 programming_error ("number of pages is out of bounds");
757 if (n == 1 && valid_n)
758 ret = space_systems_on_1_page (cached_line_details_,
759 page_height (first_page_num, is_last ()),
760 ragged () || (is_last () && ragged_last ()));
761 else if (n == 2 && valid_n)
762 ret = space_systems_on_2_pages (configuration, first_page_num);
765 Page_spacer ps (cached_line_details_, first_page_num, this);
769 return finalize_spacing_result (configuration, ret);
773 Page_breaking::blank_page_penalty () const
778 penalty_sym = ly_symbol2scm ("blank-last-page-force");
779 else if (ends_score ())
780 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
782 penalty_sym = ly_symbol2scm ("blank-page-force");
784 Break_position const &pos = breaks_[current_end_breakpoint_];
785 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
786 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
788 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
791 // If systems_per_page_ is positive, we don't really try to space on N
792 // or N+1 pages; see the comment to space_systems_on_n_pages.
794 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
796 Page_spacing_result n_res;
797 Page_spacing_result m_res;
799 if (systems_per_page_ > 0)
801 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
802 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
806 cache_line_details (configuration);
807 vsize min_p_count = min_page_count (configuration, first_page_num);
808 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
811 programming_error ("both page counts are out of bounds");
813 if (n == 1 && valid_n)
815 bool rag = ragged () || (is_last () && ragged_last ());
816 Real height = page_height (first_page_num, is_last ());
818 if (1 >= min_p_count)
819 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
820 if (1 < cached_line_details_.size ())
821 m_res = space_systems_on_2_pages (configuration, first_page_num);
825 Page_spacer ps (cached_line_details_, first_page_num, this);
827 if (n >= min_p_count || !valid_n)
828 n_res = ps.solve (n);
829 if (n < cached_line_details_.size () || !valid_n)
830 m_res = ps.solve (n+1);
833 m_res = finalize_spacing_result (configuration, m_res);
834 n_res = finalize_spacing_result (configuration, n_res);
836 Real penalty = blank_page_penalty ();
837 n_res.demerits_ += penalty;
839 if (n_res.force_.size ())
840 n_res.force_.back () += penalty;
842 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
846 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
848 vsize min_p_count = min_page_count (configuration, first_page_num);
849 Real odd_pages_penalty = blank_page_penalty ();
851 cache_line_details (configuration);
852 Page_spacer ps (cached_line_details_, first_page_num, this);
853 Page_spacing_result best = ps.solve (min_p_count);
854 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
855 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
857 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
859 Page_spacing_result cur = ps.solve (i);
860 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
861 if (cur.demerits_ < best.demerits_)
865 return finalize_spacing_result (configuration, best);
869 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
870 vsize first_page_num)
872 Page_spacing_result res;
873 Page_spacing space (page_height (first_page_num, false), page_top_space_);
876 vsize page_first_line = 0;
878 cache_line_details (configuration);
879 while (line < cached_line_details_.size ())
883 space.resize (page_height (first_page_num + page, false));
885 int system_count_on_this_page = 0;
886 while (system_count_on_this_page < systems_per_page_
887 && line < cached_line_details_.size ())
889 Line_details const &cur_line = cached_line_details_[line];
890 space.append_system (cur_line);
891 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
894 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
898 res.systems_per_page_.push_back (line - page_first_line);
900 // Don't say that the force is infinite even if it is: if we were told to
901 // put a certain number of systems on a page then we will, even if it's bad.
902 res.force_.push_back (min (space.force_, BAD_SPACING_PENALTY));
903 res.penalty_ += cached_line_details_[line-1].page_penalty_;
904 page_first_line = line;
907 /* Recalculate forces for the last page because we know now that is
908 really the last page. */
909 space.resize (page_height (first_page_num + page, true));
910 res.force_.back () = min(space.force_, BAD_SPACING_PENALTY);
911 return finalize_spacing_result (configuration, res);
915 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
917 Page_spacing_result res;
919 vsize page_first_line = 0;
920 Page_spacing space (page_height (first_page_num, false), page_top_space_);
922 cache_line_details (configuration);
923 for (vsize line = 0; line < cached_line_details_.size (); line++)
925 Real prev_force = space.force_;
926 space.append_system (cached_line_details_[line]);
927 if ((line > page_first_line)
928 && (isinf (space.force_)
930 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
932 res.systems_per_page_.push_back (line - page_first_line);
933 res.force_.push_back (prev_force);
934 res.penalty_ += cached_line_details_[line-1].page_penalty_;
936 space.resize (page_height (first_page_num + page, false));
938 space.append_system (cached_line_details_[line]);
939 page_first_line = line;
942 if (line == cached_line_details_.size () - 1)
944 /* This is the last line */
945 /* When the last page height was computed, we did not know yet that it
946 * was the last one. If the systems put on it don't fit anymore, the last
947 * system is moved to a new page */
948 space.resize (page_height (first_page_num + page, true));
949 if ((line > page_first_line) && (isinf (space.force_)))
951 res.systems_per_page_.push_back (line - page_first_line);
952 res.force_.push_back (prev_force);
953 /* the last page containing the last line */
954 space.resize (page_height (first_page_num + page + 1, true));
956 space.append_system (cached_line_details_[line]);
957 res.systems_per_page_.push_back (1);
958 res.force_.push_back (space.force_);
959 res.penalty_ += cached_line_details_[line-1].page_penalty_;
960 res.penalty_ += cached_line_details_[line].page_penalty_;
964 res.systems_per_page_.push_back (line + 1 - page_first_line);
965 res.force_.push_back (space.force_);
966 res.penalty_ += cached_line_details_[line].page_penalty_;
970 return finalize_spacing_result (configuration, res);
973 /* Calculate demerits and fix res.systems_per_page_ so that
974 it refers to the original line numbers, not the ones given by compress_lines (). */
976 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
978 if (res.force_.empty ())
981 cache_line_details (configuration);
982 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
985 Real line_penalty = 0;
987 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
989 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
991 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
992 line_penalty += uncompressed_line_details_[i].break_penalty_;
995 for (vsize i = 0; i < res.force_.size (); i++)
997 Real f = res.force_[i];
998 if (isinf (f) && res.systems_per_page_[i] == 1)
999 f = BAD_SPACING_PENALTY;
1001 page_force += f * f;
1004 /* for a while we tried averaging page and line forces across pages instead
1005 of summing them, but it caused a problem: if there is a single page
1006 with a very bad page force (for example because of a forced page break),
1007 the page breaker will put in a _lot_ of pages so that the bad force
1008 becomes averaged out over many pages. */
1009 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
1014 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1015 are by far the most common cases, we have special functions for them.
1017 space_systems_on_1_page has a different calling convention than most of the
1018 space_systems functions. This is because space_systems_on_1_page is (unlike
1019 the other space_systems functions) sometimes called on subsets of a full
1022 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1024 Page_spacing space (page_height, page_top_space_);
1025 Page_spacing_result ret;
1027 for (vsize i = 0; i < lines.size (); i++)
1028 space.append_system (lines[i]);
1030 ret.systems_per_page_.push_back (lines.size ());
1031 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1032 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1034 /* don't do finalize_spacing_result () because we are only an internal function */
1039 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1041 Real page1_height = page_height (first_page_num, false);
1042 Real page2_height = page_height (first_page_num + 1, is_last ());
1043 bool ragged1 = ragged ();
1044 bool ragged2 = ragged () || (is_last () && ragged_last ());
1046 /* if there is a forced break, this reduces to 2 1-page problems */
1047 cache_line_details (configuration);
1048 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1049 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1051 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1052 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1053 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1054 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1056 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1057 p1.force_.push_back (p2.force_[0]);
1058 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1062 vector<Real> page1_force;
1063 vector<Real> page2_force;
1064 Page_spacing page1 (page1_height, page_top_space_);
1065 Page_spacing page2 (page2_height, page_top_space_);
1066 int page1_line_count = 0;
1067 int page2_line_count = 0;
1069 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1070 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1072 /* find the page 1 and page 2 forces for each page-breaking position */
1073 for (vsize i = 0; i < page1_force.size (); i++)
1075 page1.append_system (cached_line_details_[i]);
1076 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1077 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1078 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1080 page1_force[i] = + (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1083 page2_force[page2_force.size () - 1 - i] =
1084 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1086 page2_force[page2_force.size () - 1 - i] = page2.force_;
1089 /* find the position that minimises the sum of the page forces */
1090 vsize best_sys_count = 1;
1091 Real best_demerits = infinity_f;
1092 for (vsize i = 0; i < page1_force.size (); i++)
1094 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1095 Real uneven = 2 * (page1_force[i] - page2_force[i]);
1097 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1098 // constraints. That is, we penalize harshly when they don't happen
1099 // but we don't completely reject.
1100 Real dem = uneven * uneven + f
1101 + line_count_penalty (i+1) + line_count_penalty (page2_force.size () - i)
1102 + cached_line_details_[i+1].page_penalty_
1103 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1104 if (dem < best_demerits)
1106 best_demerits = dem;
1107 best_sys_count = i+1;
1111 Page_spacing_result ret;
1112 ret.systems_per_page_.push_back (best_sys_count);
1113 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1114 ret.force_.push_back (page1_force[best_sys_count-1]);
1115 ret.force_.push_back (page2_force[best_sys_count-1]);
1116 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1117 + cached_line_details_.back ().page_penalty_
1118 + cached_line_details_.back ().turn_penalty_;
1120 /* don't do finalize_spacing_result () because we are only an internal function */
1125 Page_breaking::all_lines_stretched (vsize configuration)
1127 cache_line_details (configuration);
1128 for (vsize i = 0; i < cached_line_details_.size (); i++)
1129 if (cached_line_details_[i].force_ < 0)
1135 Page_breaking::Line_division
1136 Page_breaking::current_configuration (vsize configuration_index) const
1138 return current_configurations_[configuration_index];
1142 Page_breaking::is_last () const
1144 return current_end_breakpoint_ == last_break_position ();
1148 Page_breaking::ends_score () const
1150 return breaks_[current_end_breakpoint_].score_ender_;
1154 Page_breaking::last_break_position () const
1156 return breaks_.size () - 1;