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_;
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 create_system_list ();
105 find_chunks_and_breaks (is_break);
108 Page_breaking::~Page_breaking ()
113 Page_breaking::ragged () const
119 Page_breaking::ragged_last () const
125 Page_breaking::page_top_space () const
127 return page_top_space_;
131 Page_breaking::system_count () const
133 return system_count_;
136 /* translate indices into breaks_ into start-end parameters for the line breaker */
138 Page_breaking::line_breaker_args (vsize sys,
139 Break_position const &start,
140 Break_position const &end,
141 vsize *line_breaker_start,
142 vsize *line_breaker_end)
144 assert (system_specs_[sys].pscore_);
145 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
147 if (start.system_spec_index_ == sys)
148 *line_breaker_start = start.score_break_;
150 *line_breaker_start = 0;
152 if (end.system_spec_index_ == sys)
153 *line_breaker_end = end.score_break_;
155 *line_breaker_end = VPOS;
159 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
160 Line_division const &div)
162 vector<Break_position> chunks = chunk_list (start_break, end_break);
163 bool ignore_div = false;
164 if (chunks.size () != div.size () + 1)
166 programming_error ("did not find a valid page breaking configuration");
170 for (vsize i = 0; i + 1 < chunks.size (); i++)
172 vsize sys = next_system (chunks[i]);
173 if (system_specs_[sys].pscore_)
177 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
179 vector<Column_x_positions> pos = ignore_div
180 ? line_breaking_[sys].best_solution (start, end)
181 : line_breaking_[sys].solve (start, end, div[i]);
182 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
188 Page_breaking::systems ()
191 for (vsize sys = 0; sys < system_specs_.size (); sys++)
193 if (system_specs_[sys].pscore_)
195 system_specs_[sys].pscore_->root_system ()
196 ->do_break_substitution_and_fixup_refpoints ();
197 SCM lines = system_specs_[sys].pscore_->root_system ()
198 ->get_broken_system_grobs ();
199 ret = scm_cons (lines, ret);
203 Prob *pb = system_specs_[sys].prob_;
204 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
208 return scm_append (scm_reverse (ret));
212 Page_breaking::page_height (int page_num, bool last) const
214 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
215 SCM mod = scm_c_resolve_module ("scm page");
216 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
217 SCM make_page = scm_c_module_lookup (mod, "make-page");
219 calc_height = scm_variable_ref (calc_height);
220 make_page = scm_variable_ref (make_page);
222 SCM page = scm_apply_0 (make_page, scm_list_n (
224 ly_symbol2scm ("page-number"), scm_from_int (page_num),
225 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
226 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
228 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
229 return scm_to_double (height) - page_top_space_;
233 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
235 Break_position const &pos = breaks_[breakpoint];
237 if (pos.system_spec_index_ == VPOS)
239 if (system_specs_[pos.system_spec_index_].pscore_)
240 return pos.col_->get_property (str);
241 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
245 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
247 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
248 SCM page_module = scm_c_resolve_module ("scm page");
250 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
251 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
252 make_page = scm_variable_ref (make_page);
253 page_stencil = scm_variable_ref (page_stencil);
255 SCM book = book_->self_scm ();
256 int first_page_number
257 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
258 bool last_bookpart = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
260 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
261 if (label_page_table == SCM_UNDEFINED)
262 label_page_table = SCM_EOL;
264 for (vsize i = 0; i < lines_per_page.size (); i++)
266 SCM page_num = scm_from_int (i + first_page_number);
267 bool partbook_last_page = (i == lines_per_page.size () - 1);
268 SCM rag = scm_from_bool (ragged () || ( partbook_last_page && ragged_last ()));
269 SCM line_count = scm_from_int (lines_per_page[i]);
270 SCM lines = scm_list_head (systems, line_count);
271 SCM page = scm_apply_0 (make_page,
272 scm_list_n (book, lines, page_num, rag,
273 scm_from_bool (last_bookpart),
274 scm_from_bool (partbook_last_page),
277 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
279 SCM labels = SCM_EOL;
280 if (Grob * line = unsmob_grob (scm_car (l)))
282 System *system = dynamic_cast<System*> (line);
283 labels = system->get_property ("labels");
285 else if (Prob *prob = unsmob_prob (scm_car (l)))
286 labels = prob->get_property ("labels");
288 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
289 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
293 scm_apply_1 (page_stencil, page, SCM_EOL);
294 ret = scm_cons (page, ret);
295 systems = scm_list_tail (systems, line_count);
297 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
298 ret = scm_reverse (ret);
302 /* The page-turn-page-breaker needs to have a line-breaker between any two
303 columns with non-NULL page-turn-permission.
305 The optimal-breaker needs to have a line-breaker between any two columns
306 with page-break-permission = 'force.
308 By using a grob predicate, we can accommodate both of these uses.
311 Page_breaking::create_system_list ()
313 SCM specs = book_->get_system_specs ();
314 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
316 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
318 SCM system_count = ps->layout ()->c_variable ("system-count");
320 if (scm_is_number (system_count))
321 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
322 scm_vector_to_list (ps->get_paper_systems ()),
325 system_specs_.push_back (System_spec (ps));
329 Prob *pb = unsmob_prob (scm_car (s));
333 system_specs_.push_back (System_spec (pb));
339 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
341 SCM force_sym = ly_symbol2scm ("force");
343 chunks_.push_back (Break_position ());
344 breaks_.push_back (Break_position ());
346 for (vsize i = 0; i < system_specs_.size (); i++)
348 if (system_specs_[i].pscore_)
351 = system_specs_[i].pscore_->root_system ()->used_columns ();
352 vector<vsize> line_breaker_columns;
353 line_breaker_columns.push_back (0);
355 for (vsize j = 1; j < cols.size (); j++)
357 bool last = (j == cols.size () - 1);
358 bool break_point = is_break (cols[j]);
359 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
360 Break_position cur_pos = Break_position (i,
361 line_breaker_columns.size (),
365 if (break_point || (i == system_specs_.size () - 1 && last))
366 breaks_.push_back (cur_pos);
367 if (chunk_end || last)
368 chunks_.push_back (cur_pos);
370 if ((break_point || chunk_end) && !last)
371 line_breaker_columns.push_back (j);
373 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
377 /* TODO: we want some way of applying Break_p to a prob? */
378 if (i == system_specs_.size () - 1)
379 breaks_.push_back (Break_position (i));
381 chunks_.push_back (Break_position (i));
383 /* FIXME: shouldn't we push a Null_breaker or similar dummy
385 line_breaking_.push_back (Constrained_breaking (NULL));
390 vector<Break_position>
391 Page_breaking::chunk_list (vsize start_index, vsize end_index)
393 Break_position start = breaks_[start_index];
394 Break_position end = breaks_[end_index];
397 for (; i < chunks_.size () && chunks_[i] <= start; i++)
400 vector<Break_position> ret;
401 ret.push_back (start);
402 for (; i < chunks_.size () && chunks_[i] < end; i++)
403 ret.push_back (chunks_[i]);
409 Page_breaking::min_system_count (vsize start, vsize end)
411 vector<Break_position> chunks = chunk_list (start, end);
412 Line_division div = system_count_bounds (chunks, true);
415 for (vsize i = 0; i < div.size (); i++)
421 Page_breaking::max_system_count (vsize start, vsize end)
423 vector<Break_position> chunks = chunk_list (start, end);
424 Line_division div = system_count_bounds (chunks, false);
427 for (vsize i = 0; i < div.size (); i++)
432 Page_breaking::Line_division
433 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
436 assert (chunks.size () >= 2);
439 ret.resize (chunks.size () - 1, 1);
441 for (vsize i = 0; i + 1 < chunks.size (); i++)
443 vsize sys = next_system (chunks[i]);
444 if (system_specs_[sys].pscore_)
448 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
450 ? line_breaking_[sys].min_system_count (start, end)
451 : line_breaking_[sys].max_system_count (start, end);
459 Page_breaking::set_current_breakpoints (vsize start,
462 Line_division lower_bound,
463 Line_division upper_bound)
465 system_count_ = system_count;
466 current_chunks_ = chunk_list (start, end);
467 current_start_breakpoint_ = start;
468 current_end_breakpoint_ = end;
469 clear_line_details_cache ();
471 if (!lower_bound.size ())
472 lower_bound = system_count_bounds (current_chunks_, true);
473 if (!upper_bound.size ())
474 upper_bound = system_count_bounds (current_chunks_, false);
476 assert (lower_bound.size () == current_chunks_.size () - 1);
477 assert (upper_bound.size () == current_chunks_.size () - 1);
479 Line_division work_in_progress;
480 current_configurations_.clear ();
481 line_divisions_rec (system_count,
486 /* we only consider a constant number of configurations. Otherwise,
487 this becomes slow when there are many small scores. The constant
488 5 is somewhat arbitrary. */
489 if (current_configurations_.size () > 5)
491 vector<pair<Real,vsize> > dems_and_indices;
493 for (vsize i = 0; i < current_configurations_.size (); i++)
495 cache_line_details (i);
497 for (vsize j = 0; j < cached_line_details_.size (); j++)
498 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
499 + cached_line_details_[j].break_penalty_;
501 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
503 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
505 vector<Line_division> best_5_configurations;
506 for (vsize i = 0; i < 5; i++)
507 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
509 clear_line_details_cache ();
510 current_configurations_ = best_5_configurations;
515 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
517 current_chunks_ = chunk_list (start, end);
518 current_start_breakpoint_ = start;
519 current_end_breakpoint_ = end;
520 clear_line_details_cache ();
524 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
526 vsize sys = next_system (current_chunks_[i]);
527 if (system_specs_[sys].pscore_)
529 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
530 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
535 system_count_ += div.back ();
537 current_configurations_.clear ();
538 current_configurations_.push_back (div);
542 Page_breaking::current_configuration_count () const
544 return current_configurations_.size ();
548 Page_breaking::cache_line_details (vsize configuration_index)
550 if (cached_configuration_index_ != configuration_index)
552 cached_configuration_index_ = configuration_index;
553 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
554 if (!scm_is_number (padding_scm))
555 padding_scm = book_->paper_->c_variable ("between-system-padding");
556 Real padding = robust_scm2double (padding_scm, 0.0);
558 Line_division &div = current_configurations_[configuration_index];
559 uncompressed_line_details_.clear ();
560 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
562 vsize sys = next_system (current_chunks_[i]);
563 if (system_specs_[sys].pscore_)
567 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
569 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
570 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
574 assert (div[i] == 1);
575 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
576 uncompressed_line_details_.back ().padding_ =
577 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
581 cached_line_details_ = compress_lines (uncompressed_line_details_);
586 Page_breaking::clear_line_details_cache ()
588 cached_configuration_index_ = VPOS;
589 cached_line_details_.clear ();
590 uncompressed_line_details_.clear ();
594 Page_breaking::line_divisions_rec (vsize system_count,
595 Line_division const &min_sys,
596 Line_division const &max_sys,
597 Line_division *cur_division)
599 vsize my_index = cur_division->size ();
600 vsize others_min = 0;
601 vsize others_max = 0;
603 for (vsize i = my_index + 1; i < min_sys.size (); i++)
605 others_min += min_sys[i];
606 others_max += max_sys[i];
608 others_max = min (others_max, system_count);
609 vsize real_min = max (min_sys[my_index], system_count - others_max);
610 vsize real_max = min (max_sys[my_index], system_count - others_min);
612 if (real_min > real_max || real_min <= 0)
614 /* this should never happen within a recursive call. If it happens
615 at all, it means that we were called with an unsolvable problem
616 and we should return an empty result */
617 assert (my_index == 0);
621 for (vsize i = real_min; i <= real_max; i++)
623 cur_division->push_back (i);
624 if (my_index == min_sys.size () - 1)
625 current_configurations_.push_back (*cur_division);
627 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
628 cur_division->pop_back ();
633 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
636 Real cur_rod_height = 0;
637 Real cur_spring_height = 0;
638 Real cur_page_height = page_height (first_page_num, false);
640 cache_line_details (configuration);
641 for (vsize i = 0; i < cached_line_details_.size (); i++)
643 Real ext_len = cached_line_details_[i].extent_.length ();
644 Real next_rod_height = cur_rod_height + ext_len
645 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
646 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
647 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
650 if ((next_height > cur_page_height && cur_rod_height > 0)
652 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
654 cur_rod_height = ext_len;
655 cur_spring_height = cached_line_details_[i].space_;
656 cur_page_height = page_height (first_page_num + ret, false);
661 cur_rod_height = next_rod_height;
662 cur_spring_height = next_spring_height;
666 /* there are two potential problems with the last page (because we didn't know
667 it was the last page until after we managed to fit all the systems to it):
668 - we are ragged-last but the last page has a compressed spring
669 - the value returned by page_height (num, true) is smaller than the
670 value returned by page_height (num, false) and it causes the page not to
673 In either case, we just need to add one more page. This is because the last
674 line will always fit on the extra page and by adding one more page to the
675 end, the previous page is no longer the last page, so our previous
676 calculations that treated it as a non-last page were ok.
679 cur_page_height = page_height (first_page_num + ret - 1, true);
680 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
681 if (cur_height > cur_page_height
682 /* don't increase the page count if the last page had only one system */
683 && cur_rod_height > cached_line_details_.back ().extent_.length ())
686 assert (ret <= cached_line_details_.size ());
691 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
693 Page_spacing_result ret;
695 cache_line_details (configuration);
696 bool valid_n = (n >= min_page_count (configuration, first_page_num)
697 && n <= cached_line_details_.size ());
700 programming_error ("number of pages is out of bounds");
702 if (n == 1 && valid_n)
703 ret = space_systems_on_1_page (cached_line_details_,
704 page_height (first_page_num, is_last ()),
705 ragged () || (is_last () && ragged_last ()));
706 else if (n == 2 && valid_n)
707 ret = space_systems_on_2_pages (configuration, first_page_num);
710 Page_spacer ps (cached_line_details_, first_page_num, this);
714 return finalize_spacing_result (configuration, ret);
718 Page_breaking::blank_page_penalty () const
723 penalty_sym = ly_symbol2scm ("blank-last-page-force");
724 else if (ends_score ())
725 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
727 penalty_sym = ly_symbol2scm ("blank-page-force");
729 Break_position const &pos = breaks_[current_end_breakpoint_];
730 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
731 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
733 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
737 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
739 Page_spacing_result n_res;
740 Page_spacing_result m_res;
742 cache_line_details (configuration);
743 vsize min_p_count = min_page_count (configuration, first_page_num);
744 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
747 programming_error ("both page counts are out of bounds");
749 if (n == 1 && valid_n)
751 bool rag = ragged () || (is_last () && ragged_last ());
752 Real height = page_height (first_page_num, is_last ());
754 if (1 >= min_p_count)
755 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
756 if (1 < cached_line_details_.size ())
757 m_res = space_systems_on_2_pages (configuration, first_page_num);
761 Page_spacer ps (cached_line_details_, first_page_num, this);
763 if (n >= min_p_count || !valid_n)
764 n_res = ps.solve (n);
765 if (n < cached_line_details_.size () || !valid_n)
766 m_res = ps.solve (n+1);
769 m_res = finalize_spacing_result (configuration, m_res);
770 n_res = finalize_spacing_result (configuration, n_res);
772 Real penalty = blank_page_penalty ();
773 n_res.demerits_ += penalty;
775 if (n_res.force_.size ())
776 n_res.force_.back () += penalty;
778 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
782 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
784 vsize min_p_count = min_page_count (configuration, first_page_num);
785 Real odd_pages_penalty = blank_page_penalty ();
787 cache_line_details (configuration);
788 Page_spacer ps (cached_line_details_, first_page_num, this);
789 Page_spacing_result best = ps.solve (min_p_count);
790 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
791 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
793 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
795 Page_spacing_result cur = ps.solve (i);
796 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
797 if (cur.demerits_ < best.demerits_)
801 return finalize_spacing_result (configuration, best);
805 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
806 int systems_per_page,
807 vsize first_page_num)
809 Page_spacing_result res;
810 Page_spacing space (page_height (first_page_num, false), page_top_space_);
813 vsize page_first_line = 0;
815 cache_line_details (configuration);
816 while (line < cached_line_details_.size ())
820 space.resize (page_height (first_page_num + page, false));
822 int system_count_on_this_page = 0;
823 while (system_count_on_this_page < systems_per_page
824 && line < cached_line_details_.size ())
826 space.append_system (cached_line_details_[line]);
827 system_count_on_this_page += cached_line_details_[line].compressed_nontitle_lines_count_;
831 res.systems_per_page_.push_back (line - page_first_line);
832 res.force_.push_back (space.force_);
833 res.penalty_ += cached_line_details_[line-1].page_penalty_;
834 page_first_line = line;
837 /* Recalculate forces for the last page because we know now that is
838 was really the last page. */
839 space.resize (page_height (first_page_num + page, true));
840 res.force_.back () = space.force_;
841 return finalize_spacing_result (configuration, res);
845 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
847 Page_spacing_result res;
849 vsize page_first_line = 0;
850 Page_spacing space (page_height (first_page_num, false), page_top_space_);
852 cache_line_details (configuration);
853 for (vsize line = 0; line < cached_line_details_.size (); line++)
855 Real prev_force = space.force_;
856 space.append_system (cached_line_details_[line]);
857 if ((line > page_first_line)
858 && (isinf (space.force_)
860 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
862 res.systems_per_page_.push_back (line - page_first_line);
863 res.force_.push_back (prev_force);
864 res.penalty_ += cached_line_details_[line-1].page_penalty_;
866 space.resize (page_height (first_page_num + page, false));
868 space.append_system (cached_line_details_[line]);
869 page_first_line = line;
872 if (line == cached_line_details_.size () - 1)
874 /* This is the last line */
875 /* When the last page height was computed, we did not know yet that it
876 * was the last one. If the systems put on it don't fit anymore, the last
877 * system is moved to a new page */
878 space.resize (page_height (first_page_num + page, true));
879 if ((line > page_first_line) && (isinf (space.force_)))
881 res.systems_per_page_.push_back (line - page_first_line);
882 res.force_.push_back (prev_force);
883 /* the last page containing the last line */
884 space.resize (page_height (first_page_num + page + 1, true));
886 space.append_system (cached_line_details_[line]);
887 res.systems_per_page_.push_back (1);
888 res.force_.push_back (space.force_);
889 res.penalty_ += cached_line_details_[line-1].page_penalty_;
890 res.penalty_ += cached_line_details_[line].page_penalty_;
894 res.systems_per_page_.push_back (line + 1 - page_first_line);
895 res.force_.push_back (space.force_);
896 res.penalty_ += cached_line_details_[line].page_penalty_;
900 return finalize_spacing_result (configuration, res);
903 /* Calculate demerits and fix res.systems_per_page_ so that
904 it refers to the original line numbers, not the ones given by compress_lines (). */
906 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
908 if (res.force_.empty ())
911 cache_line_details (configuration);
912 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
915 Real line_penalty = 0;
917 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
919 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
921 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
922 line_penalty += uncompressed_line_details_[i].break_penalty_;
925 for (vsize i = 0; i < res.force_.size (); i++)
927 Real f = res.force_[i];
928 if (isinf (f) && res.systems_per_page_[i] == 1)
934 /* for a while we tried averaging page and line forces across pages instead
935 of summing them, but it caused a problem: if there is a single page
936 with a very bad page force (for example because of a forced page break),
937 the page breaker will put in a _lot_ of pages so that the bad force
938 becomes averaged out over many pages. */
939 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
944 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
945 are by far the most common cases, we have special functions for them.
947 space_systems_on_1_page has a different calling convention than most of the
948 space_systems functions. This is because space_systems_on_1_page is (unlike
949 the other space_systems functions) sometimes called on subsets of a full
952 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
954 Page_spacing space (page_height, page_top_space_);
955 Page_spacing_result ret;
957 for (vsize i = 0; i < lines.size (); i++)
958 space.append_system (lines[i]);
960 ret.systems_per_page_.push_back (lines.size ());
961 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
962 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
964 /* don't do finalize_spacing_result () because we are only an internal function */
969 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
971 Real page1_height = page_height (first_page_num, false);
972 Real page2_height = page_height (first_page_num + 1, is_last ());
973 bool ragged1 = ragged ();
974 bool ragged2 = ragged () || (is_last () && ragged_last ());
976 /* if there is a forced break, this reduces to 2 1-page problems */
977 cache_line_details (configuration);
978 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
979 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
981 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
982 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
983 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
984 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
986 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
987 p1.force_.push_back (p2.force_[0]);
988 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
992 vector<Real> page1_force;
993 vector<Real> page2_force;
994 Page_spacing page1 (page1_height, page_top_space_);
995 Page_spacing page2 (page2_height, page_top_space_);
997 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
998 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1000 /* find the page 1 and page 2 forces for each page-breaking position */
1001 for (vsize i = 0; i < page1_force.size (); i++)
1003 page1.append_system (cached_line_details_[i]);
1004 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1005 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1008 page2_force[page2_force.size () - 1 - i] =
1009 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1011 page2_force[page2_force.size () - 1 - i] = page2.force_;
1014 /* find the position that minimises the sum of the page forces */
1015 vsize best_sys_count = 1;
1016 Real best_demerits = infinity_f;
1017 for (vsize i = 0; i < page1_force.size (); i++)
1019 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1020 Real uneven = 2 * (page1_force[i] - page2_force[i]);
1021 Real dem = uneven * uneven + f
1022 + cached_line_details_[i+1].page_penalty_
1023 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1024 if (dem < best_demerits)
1026 best_demerits = dem;
1027 best_sys_count = i+1;
1031 Page_spacing_result ret;
1032 ret.systems_per_page_.push_back (best_sys_count);
1033 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1034 ret.force_.push_back (page1_force[best_sys_count-1]);
1035 ret.force_.push_back (page2_force[best_sys_count-1]);
1036 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1037 + cached_line_details_.back ().page_penalty_
1038 + cached_line_details_.back ().turn_penalty_;
1040 /* don't do finalize_spacing_result () because we are only an internal function */
1045 Page_breaking::all_lines_stretched (vsize configuration)
1047 cache_line_details (configuration);
1048 for (vsize i = 0; i < cached_line_details_.size (); i++)
1049 if (cached_line_details_[i].force_ < 0)
1055 Page_breaking::Line_division
1056 Page_breaking::current_configuration (vsize configuration_index) const
1058 return current_configurations_[configuration_index];
1062 Page_breaking::is_last () const
1064 return current_end_breakpoint_ == last_break_position ();
1068 Page_breaking::ends_score () const
1070 return breaks_[current_end_breakpoint_].score_ender_;
1074 Page_breaking::last_break_position () const
1076 return breaks_.size () - 1;