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
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 /* we don't need the force_ field for the vertical spacing,
41 so we use force_ = n to signal that the line was compressed,
42 reducing the number of lines by n (and force_ = 0 otherwise).
43 This makes uncompression much easier. */
44 compressed.force_ = old.force_ + 1;
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 += (int)compressed[j].force_;
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)
100 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
101 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
102 create_system_list ();
103 find_chunks_and_breaks (is_break);
106 Page_breaking::~Page_breaking ()
111 Page_breaking::ragged () const
117 Page_breaking::ragged_last () const
122 /* translate indices into breaks_ into start-end parameters for the line breaker */
124 Page_breaking::line_breaker_args (vsize sys,
125 Break_position const &start,
126 Break_position const &end,
127 vsize *line_breaker_start,
128 vsize *line_breaker_end)
130 assert (system_specs_[sys].pscore_);
131 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
133 if (start.system_spec_index_ == sys)
134 *line_breaker_start = start.score_break_;
136 *line_breaker_start = 0;
138 if (end.system_spec_index_ == sys)
139 *line_breaker_end = end.score_break_;
141 *line_breaker_end = VPOS;
145 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
146 Line_division const &div)
148 vector<Break_position> chunks = chunk_list (start_break, end_break);
149 bool ignore_div = false;
150 if (chunks.size () != div.size () + 1)
152 programming_error ("did not find a valid page breaking configuration");
156 for (vsize i = 0; i + 1 < chunks.size (); i++)
158 vsize sys = next_system (chunks[i]);
159 if (system_specs_[sys].pscore_)
163 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
165 vector<Column_x_positions> pos = ignore_div
166 ? line_breaking_[sys].best_solution (start, end)
167 : line_breaking_[sys].solve (start, end, div[i]);
168 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
174 Page_breaking::systems ()
177 for (vsize sys = 0; sys < system_specs_.size (); sys++)
179 if (system_specs_[sys].pscore_)
181 system_specs_[sys].pscore_->root_system ()
182 ->do_break_substitution_and_fixup_refpoints ();
183 SCM lines = system_specs_[sys].pscore_->root_system ()
184 ->get_broken_system_grobs ();
185 ret = scm_cons (lines, ret);
189 Prob *pb = system_specs_[sys].prob_;
190 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
194 return scm_append (scm_reverse (ret));
198 Page_breaking::page_height (int page_num, bool last) const
200 SCM mod = scm_c_resolve_module ("scm page");
201 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
202 SCM make_page = scm_c_module_lookup (mod, "make-page");
204 calc_height = scm_variable_ref (calc_height);
205 make_page = scm_variable_ref (make_page);
207 SCM page = scm_apply_0 (make_page, scm_list_n (
209 ly_symbol2scm ("page-number"), scm_from_int (page_num),
210 ly_symbol2scm ("is-last"), scm_from_bool (last),
212 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
213 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
217 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
219 Break_position const &pos = breaks_[breakpoint];
221 if (pos.system_spec_index_ == VPOS)
223 if (system_specs_[pos.system_spec_index_].pscore_)
224 return pos.col_->get_property (str);
225 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
229 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
231 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
232 SCM page_module = scm_c_resolve_module ("scm page");
234 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
235 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
236 make_page = scm_variable_ref (make_page);
237 page_stencil = scm_variable_ref (page_stencil);
239 SCM book = book_->self_scm ();
240 int first_page_number
241 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
243 SCM label_page_table = SCM_EOL;
245 for (vsize i = 0; i < lines_per_page.size (); i++)
247 SCM page_num = scm_from_int (i + first_page_number);
248 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
249 SCM rag = scm_from_bool (ragged () || (to_boolean (last)
251 SCM line_count = scm_from_int (lines_per_page[i]);
252 SCM lines = scm_list_head (systems, line_count);
253 SCM page = scm_apply_0 (make_page,
254 scm_list_n (book, lines, page_num,
255 rag, last, SCM_UNDEFINED));
258 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
260 SCM labels = SCM_EOL;
261 if (Grob * line = unsmob_grob (scm_car (l)))
263 System *system = dynamic_cast<System*> (line);
264 labels = system->get_property ("labels");
266 else if (Prob *prob = unsmob_prob (scm_car (l)))
267 labels = prob->get_property ("labels");
269 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
270 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
274 scm_apply_1 (page_stencil, page, SCM_EOL);
275 ret = scm_cons (page, ret);
276 systems = scm_list_tail (systems, line_count);
278 book_->paper_->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
279 ret = scm_reverse (ret);
283 /* The page-turn-page-breaker needs to have a line-breaker between any two
284 columns with non-NULL page-turn-permission.
286 The optimal-breaker needs to have a line-breaker between any two columns
287 with page-break-permission = 'force.
289 By using a grob predicate, we can accommodate both of these uses.
292 Page_breaking::create_system_list ()
294 SCM specs = book_->get_system_specs ();
295 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
297 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
299 SCM system_count = ps->layout ()->c_variable ("system-count");
301 if (scm_is_number (system_count))
302 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
303 scm_vector_to_list (ps->get_paper_systems ()),
306 system_specs_.push_back (System_spec (ps));
310 Prob *pb = unsmob_prob (scm_car (s));
314 system_specs_.push_back (System_spec (pb));
320 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
322 SCM force_sym = ly_symbol2scm ("force");
324 chunks_.push_back (Break_position ());
325 breaks_.push_back (Break_position ());
327 for (vsize i = 0; i < system_specs_.size (); i++)
329 if (system_specs_[i].pscore_)
332 = system_specs_[i].pscore_->root_system ()->used_columns ();
333 vector<vsize> line_breaker_columns;
334 line_breaker_columns.push_back (0);
336 for (vsize j = 1; j < cols.size (); j++)
338 bool last = (j == cols.size () - 1);
339 bool break_point = is_break (cols[j]);
340 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
341 Break_position cur_pos = Break_position (i,
342 line_breaker_columns.size (),
346 if (break_point || (i == system_specs_.size () - 1 && last))
347 breaks_.push_back (cur_pos);
348 if (chunk_end || last)
349 chunks_.push_back (cur_pos);
351 if ((break_point || chunk_end) && !last)
352 line_breaker_columns.push_back (j);
354 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
358 /* TODO: we want some way of applying Break_p to a prob? */
359 if (i == system_specs_.size () - 1)
360 breaks_.push_back (Break_position (i));
362 chunks_.push_back (Break_position (i));
364 /* FIXME: shouldn't we push a Null_breaker or similar dummy
366 line_breaking_.push_back (Constrained_breaking (NULL));
371 vector<Break_position>
372 Page_breaking::chunk_list (vsize start_index, vsize end_index)
374 Break_position start = breaks_[start_index];
375 Break_position end = breaks_[end_index];
378 for (; i < chunks_.size () && chunks_[i] <= start; i++)
381 vector<Break_position> ret;
382 ret.push_back (start);
383 for (; i < chunks_.size () && chunks_[i] < end; i++)
384 ret.push_back (chunks_[i]);
390 Page_breaking::min_system_count (vsize start, vsize end)
392 vector<Break_position> chunks = chunk_list (start, end);
393 Line_division div = system_count_bounds (chunks, true);
396 for (vsize i = 0; i < div.size (); i++)
402 Page_breaking::max_system_count (vsize start, vsize end)
404 vector<Break_position> chunks = chunk_list (start, end);
405 Line_division div = system_count_bounds (chunks, false);
408 for (vsize i = 0; i < div.size (); i++)
413 Page_breaking::Line_division
414 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
417 assert (chunks.size () >= 2);
420 ret.resize (chunks.size () - 1, 1);
422 for (vsize i = 0; i + 1 < chunks.size (); i++)
424 vsize sys = next_system (chunks[i]);
425 if (system_specs_[sys].pscore_)
429 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
431 ? line_breaking_[sys].min_system_count (start, end)
432 : line_breaking_[sys].max_system_count (start, end);
440 Page_breaking::set_current_breakpoints (vsize start,
443 Line_division lower_bound,
444 Line_division upper_bound)
446 current_chunks_ = chunk_list (start, end);
447 current_start_breakpoint_ = start;
448 current_end_breakpoint_ = end;
449 clear_line_details_cache ();
451 if (!lower_bound.size ())
452 lower_bound = system_count_bounds (current_chunks_, true);
453 if (!upper_bound.size ())
454 upper_bound = system_count_bounds (current_chunks_, false);
456 assert (lower_bound.size () == current_chunks_.size () - 1);
457 assert (upper_bound.size () == current_chunks_.size () - 1);
459 Line_division work_in_progress;
460 current_configurations_.clear ();
461 line_divisions_rec (system_count,
466 /* we only consider a constant number of configurations. Otherwise,
467 this becomes slow when there are many small scores. The constant
468 5 is somewhat arbitrary. */
469 if (current_configurations_.size () > 5)
471 vector<pair<Real,vsize> > dems_and_indices;
473 for (vsize i = 0; i < current_configurations_.size (); i++)
475 cache_line_details (i);
477 for (vsize j = 0; j < cached_line_details_.size (); j++)
478 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
479 + cached_line_details_[j].break_penalty_;
481 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
483 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
485 vector<Line_division> best_5_configurations;
486 for (vsize i = 0; i < 5; i++)
487 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
489 clear_line_details_cache ();
490 current_configurations_ = best_5_configurations;
495 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
497 current_chunks_ = chunk_list (start, end);
498 current_start_breakpoint_ = start;
499 current_end_breakpoint_ = end;
500 clear_line_details_cache ();
503 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
505 vsize sys = next_system (current_chunks_[i]);
506 if (system_specs_[sys].pscore_)
508 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
509 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
514 current_configurations_.clear ();
515 current_configurations_.push_back (div);
519 Page_breaking::current_configuration_count () const
521 return current_configurations_.size ();
525 Page_breaking::cache_line_details (vsize configuration_index)
527 if (cached_configuration_index_ != configuration_index)
529 cached_configuration_index_ = configuration_index;
530 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
531 if (!scm_is_number (padding_scm))
532 padding_scm = book_->paper_->c_variable ("between-system-padding");
533 Real padding = robust_scm2double (padding_scm, 0.0);
535 Line_division &div = current_configurations_[configuration_index];
536 uncompressed_line_details_.clear ();
537 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
539 vsize sys = next_system (current_chunks_[i]);
540 if (system_specs_[sys].pscore_)
544 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
546 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
547 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
551 assert (div[i] == 1);
552 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
553 uncompressed_line_details_.back ().padding_ =
554 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
558 cached_line_details_ = compress_lines (uncompressed_line_details_);
563 Page_breaking::clear_line_details_cache ()
565 cached_configuration_index_ = VPOS;
566 cached_line_details_.clear ();
567 uncompressed_line_details_.clear ();
571 Page_breaking::line_divisions_rec (vsize system_count,
572 Line_division const &min_sys,
573 Line_division const &max_sys,
574 Line_division *cur_division)
576 vsize my_index = cur_division->size ();
577 vsize others_min = 0;
578 vsize others_max = 0;
580 for (vsize i = my_index + 1; i < min_sys.size (); i++)
582 others_min += min_sys[i];
583 others_max += max_sys[i];
585 others_max = min (others_max, system_count);
586 vsize real_min = max (min_sys[my_index], system_count - others_max);
587 vsize real_max = min (max_sys[my_index], system_count - others_min);
589 if (real_min > real_max || real_min <= 0)
591 /* this should never happen within a recursive call. If it happens
592 at all, it means that we were called with an unsolvable problem
593 and we should return an empty result */
594 assert (my_index == 0);
598 for (vsize i = real_min; i <= real_max; i++)
600 cur_division->push_back (i);
601 if (my_index == min_sys.size () - 1)
602 current_configurations_.push_back (*cur_division);
604 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
605 cur_division->pop_back ();
610 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
613 Real cur_rod_height = 0;
614 Real cur_spring_height = 0;
615 Real cur_page_height = page_height (first_page_num, false);
617 cache_line_details (configuration);
618 for (vsize i = 0; i < cached_line_details_.size (); i++)
620 Real ext_len = cached_line_details_[i].extent_.length ();
621 Real next_rod_height = cur_rod_height + ext_len
622 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
623 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
624 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
627 if ((next_height > cur_page_height && cur_rod_height > 0)
629 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
631 cur_rod_height = ext_len;
632 cur_spring_height = cached_line_details_[i].space_;
633 cur_page_height = page_height (first_page_num + ret, false);
638 cur_rod_height = next_rod_height;
639 cur_spring_height = next_spring_height;
643 /* there are two potential problems with the last page (because we didn't know
644 it was the last page until after we managed to fit all the systems to it):
645 - we are ragged-last but the last page has a compressed spring
646 - the value returned by page_height (num, true) is smaller than the
647 value returned by page_height (num, false) and it causes the page not to
650 In either case, we just need to add one more page. This is because the last
651 line will always fit on the extra page and by adding one more page to the
652 end, the previous page is no longer the last page, so our previous
653 calculations that treated it as a non-last page were ok.
656 cur_page_height = page_height (first_page_num + ret - 1, true);
657 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
658 if (cur_height > cur_page_height
659 /* don't increase the page count if the last page had only one system */
660 && cur_rod_height > cached_line_details_.back ().extent_.length ())
663 assert (ret <= cached_line_details_.size ());
668 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
670 Page_spacing_result ret;
671 assert (n >= min_page_count (configuration, first_page_num));
673 cache_line_details (configuration);
674 if (n > cached_line_details_.size ())
675 return Page_spacing_result ();
677 ret = space_systems_on_1_page (cached_line_details_,
678 page_height (first_page_num, is_last ()),
679 ragged () || (is_last () && ragged_last ()));
681 ret = space_systems_on_2_pages (configuration, first_page_num);
684 Page_spacer ps (cached_line_details_, first_page_num, this);
688 return finalize_spacing_result (configuration, ret);
692 Page_breaking::blank_page_penalty () const
694 SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
695 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
699 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
701 Page_spacing_result n_res;
702 Page_spacing_result m_res;
704 cache_line_details (configuration);
705 vsize min_p_count = min_page_count (configuration, first_page_num);
709 bool rag = ragged () || (is_last () && ragged_last ());
710 Real height = page_height (first_page_num, is_last ());
712 if (1 >= min_p_count)
713 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
714 if (1 < cached_line_details_.size ())
715 m_res = space_systems_on_2_pages (configuration, first_page_num);
719 Page_spacer ps (cached_line_details_, first_page_num, this);
721 if (n >= min_p_count)
722 n_res = ps.solve (n);
723 if (n < cached_line_details_.size ())
724 m_res = ps.solve (n+1);
727 m_res = finalize_spacing_result (configuration, m_res);
728 n_res = finalize_spacing_result (configuration, n_res);
730 Real penalty = blank_page_penalty ();
731 n_res.demerits_ += penalty;
733 if (n_res.force_.size ())
734 n_res.force_.back () += penalty;
736 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
740 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
742 vsize min_p_count = min_page_count (configuration, first_page_num);
743 Real odd_pages_penalty = blank_page_penalty ();
745 cache_line_details (configuration);
746 Page_spacer ps (cached_line_details_, first_page_num, this);
747 Page_spacing_result best = ps.solve (min_p_count);
748 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
749 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
751 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
753 Page_spacing_result cur = ps.solve (i);
754 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
755 if (cur.demerits_ < best.demerits_)
759 return finalize_spacing_result (configuration, best);
763 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
765 Page_spacing_result res;
767 vsize page_first_line = 0;
768 Page_spacing space (page_height (first_page_num, false));
770 cache_line_details (configuration);
771 for (vsize line = 0; line < cached_line_details_.size (); line++)
773 Real prev_force = space.force_;
774 space.append_system (cached_line_details_[line]);
775 if ((line > page_first_line)
776 && (isinf (space.force_)
778 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
780 res.systems_per_page_.push_back (line - page_first_line);
781 res.force_.push_back (prev_force);
782 res.penalty_ += cached_line_details_[line-1].page_penalty_;
784 space.resize (page_height (first_page_num + page, false));
786 space.append_system (cached_line_details_[line]);
787 page_first_line = line;
790 if (line == cached_line_details_.size () - 1)
792 /* This is the last line */
793 /* When the last page height was computed, we did not know yet that it
794 * was the last one. If the systems put on it don't fit anymore, the last
795 * system is moved to a new page */
796 space.resize (page_height (first_page_num + page, true));
797 if ((line > page_first_line) && (isinf (space.force_)))
799 res.systems_per_page_.push_back (line - page_first_line);
800 res.force_.push_back (prev_force);
801 /* the last page containing the last line */
802 space.resize (page_height (first_page_num + page + 1, true));
804 space.append_system (cached_line_details_[line]);
805 res.systems_per_page_.push_back (1);
806 res.force_.push_back (space.force_);
807 res.penalty_ += cached_line_details_[line-1].page_penalty_;
808 res.penalty_ += cached_line_details_[line].page_penalty_;
812 res.systems_per_page_.push_back (line + 1 - page_first_line);
813 res.force_.push_back (space.force_);
814 res.penalty_ += cached_line_details_[line].page_penalty_;
818 return finalize_spacing_result (configuration, res);
821 /* Calculate demerits and fix res.systems_per_page_ so that
822 it refers to the original line numbers, not the ones given by compress_lines (). */
824 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
826 if (res.force_.empty ())
829 cache_line_details (configuration);
830 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
833 Real line_penalty = 0;
835 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
837 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
839 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
840 line_penalty += uncompressed_line_details_[i].break_penalty_;
843 for (vsize i = 0; i < res.force_.size (); i++)
845 Real f = res.force_[i];
846 if (isinf (f) && res.systems_per_page_[i] == 1)
852 /* for a while we tried averaging page and line forces across pages instead
853 of summing them, but it caused a problem: if there is a single page
854 with a very bad page force (for example because of a forced page break),
855 the page breaker will put in a _lot_ of pages so that the bad force
856 becomes averaged out over many pages. */
857 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
862 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
863 are by far the most common cases, we have special functions for them.
865 space_systems_on_1_page has a different calling convention than most of the
866 space_systems functions. This is because space_systems_on_1_page is (unlike
867 the other space_systems functions) sometimes called on subsets of a full
870 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
872 Page_spacing space (page_height);
873 Page_spacing_result ret;
875 for (vsize i = 0; i < lines.size (); i++)
876 space.append_system (lines[i]);
878 ret.systems_per_page_.push_back (lines.size ());
879 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
880 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
882 /* don't do finalize_spacing_result () because we are only an internal function */
887 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
889 Real page1_height = page_height (first_page_num, false);
890 Real page2_height = page_height (first_page_num + 1, is_last ());
891 bool ragged1 = ragged ();
892 bool ragged2 = ragged () || (is_last () && ragged_last ());
894 /* if there is a forced break, this reduces to 2 1-page problems */
895 cache_line_details (configuration);
896 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
897 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
899 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
900 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
901 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
902 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
904 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
905 p1.force_.push_back (p2.force_[0]);
906 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
910 vector<Real> page1_force;
911 vector<Real> page2_force;
912 Page_spacing page1 (page1_height);
913 Page_spacing page2 (page2_height);
915 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
916 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
918 /* find the page 1 and page 2 forces for each page-breaking position */
919 for (vsize i = 0; i < page1_force.size (); i++)
921 page1.append_system (cached_line_details_[i]);
922 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
923 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
926 page2_force[page2_force.size () - 1 - i] =
927 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
929 page2_force[page2_force.size () - 1 - i] = page2.force_;
932 /* find the position that minimises the sum of the page forces */
933 vsize best_sys_count = 1;
934 Real best_demerits = infinity_f;
935 for (vsize i = 0; i < page1_force.size (); i++)
937 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
938 Real uneven = 2 * (page1_force[i] - page2_force[i]);
939 Real dem = uneven * uneven + f
940 + cached_line_details_[i+1].page_penalty_
941 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
942 if (dem < best_demerits)
945 best_sys_count = i+1;
949 Page_spacing_result ret;
950 ret.systems_per_page_.push_back (best_sys_count);
951 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
952 ret.force_.push_back (page1_force[best_sys_count-1]);
953 ret.force_.push_back (page2_force[best_sys_count-1]);
954 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
955 + cached_line_details_.back ().page_penalty_
956 + cached_line_details_.back ().turn_penalty_;
958 /* don't do finalize_spacing_result () because we are only an internal function */
963 Page_breaking::all_lines_stretched (vsize configuration)
965 cache_line_details (configuration);
966 for (vsize i = 0; i < cached_line_details_.size (); i++)
967 if (cached_line_details_[i].force_ < 0)
973 Page_breaking::Line_division
974 Page_breaking::current_configuration (vsize configuration_index) const
976 return current_configurations_[configuration_index];
980 Page_breaking::is_last () const
982 return current_end_breakpoint_ == last_break_position ();
986 Page_breaking::last_break_position () const
988 return breaks_.size () - 1;