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_;
39 compressed.title_ = old.title_;
41 /* we don't need the force_ field for the vertical spacing,
42 so we use force_ = n to signal that the line was compressed,
43 reducing the number of lines by n (and force_ = 0 otherwise).
44 This makes uncompression much easier. */
45 compressed.force_ = old.force_ + 1;
46 ret.back () = compressed;
50 ret.push_back (orig[i]);
51 ret.back ().force_ = 0;
57 /* translate the number of systems-per-page into something meaningful for
58 the uncompressed lines.
61 uncompress_solution (vector<vsize> const &systems_per_page,
62 vector<Line_details> const &compressed)
67 for (vsize i = 0; i < systems_per_page.size (); i++)
69 int compressed_count = 0;
70 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
71 compressed_count += (int)compressed[j].force_;
73 ret.push_back (systems_per_page[i] + compressed_count);
74 start_sys += systems_per_page[i];
79 /* for Page_breaking, the start index (when we are dealing with the stuff
80 between a pair of breakpoints) refers to the break_ index of the end of
81 the previous page. So the system index of the start of the current page
82 could either be the same as the end of the previous page or one more than
85 /* Turn a break index into the sys index that starts the next page */
87 Page_breaking::next_system (Break_position const &break_pos) const
89 vsize sys = break_pos.system_spec_index_;
91 if (sys == VPOS) /* beginning of the book */
93 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
94 return sys; /* the score overflows the previous page */
95 return sys + 1; /* this page starts with a new System_spec */
98 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
102 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
103 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
104 page_top_space_ = robust_scm2double (pb->paper_->c_variable ("page-top-space"), 0);
105 create_system_list ();
106 find_chunks_and_breaks (is_break);
109 Page_breaking::~Page_breaking ()
114 Page_breaking::ragged () const
120 Page_breaking::ragged_last () const
126 Page_breaking::page_top_space () const
128 return page_top_space_;
132 Page_breaking::system_count () const
134 return system_count_;
137 /* translate indices into breaks_ into start-end parameters for the line breaker */
139 Page_breaking::line_breaker_args (vsize sys,
140 Break_position const &start,
141 Break_position const &end,
142 vsize *line_breaker_start,
143 vsize *line_breaker_end)
145 assert (system_specs_[sys].pscore_);
146 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
148 if (start.system_spec_index_ == sys)
149 *line_breaker_start = start.score_break_;
151 *line_breaker_start = 0;
153 if (end.system_spec_index_ == sys)
154 *line_breaker_end = end.score_break_;
156 *line_breaker_end = VPOS;
160 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
161 Line_division const &div)
163 vector<Break_position> chunks = chunk_list (start_break, end_break);
164 bool ignore_div = false;
165 if (chunks.size () != div.size () + 1)
167 programming_error ("did not find a valid page breaking configuration");
171 for (vsize i = 0; i + 1 < chunks.size (); i++)
173 vsize sys = next_system (chunks[i]);
174 if (system_specs_[sys].pscore_)
178 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
180 vector<Column_x_positions> pos = ignore_div
181 ? line_breaking_[sys].best_solution (start, end)
182 : line_breaking_[sys].solve (start, end, div[i]);
183 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
189 Page_breaking::systems ()
192 for (vsize sys = 0; sys < system_specs_.size (); sys++)
194 if (system_specs_[sys].pscore_)
196 system_specs_[sys].pscore_->root_system ()
197 ->do_break_substitution_and_fixup_refpoints ();
198 SCM lines = system_specs_[sys].pscore_->root_system ()
199 ->get_broken_system_grobs ();
200 ret = scm_cons (lines, ret);
204 Prob *pb = system_specs_[sys].prob_;
205 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
209 return scm_append (scm_reverse (ret));
213 Page_breaking::page_height (int page_num, bool last) const
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"), scm_from_bool (last),
227 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
228 return scm_to_double (height) - page_top_space_;
232 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
234 Break_position const &pos = breaks_[breakpoint];
236 if (pos.system_spec_index_ == VPOS)
238 if (system_specs_[pos.system_spec_index_].pscore_)
239 return pos.col_->get_property (str);
240 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
244 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
246 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
247 SCM page_module = scm_c_resolve_module ("scm page");
249 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
250 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
251 make_page = scm_variable_ref (make_page);
252 page_stencil = scm_variable_ref (page_stencil);
254 SCM book = book_->self_scm ();
255 int first_page_number
256 = robust_scm2int (book_->paper_->c_variable ("part-first-page-number"), 1);
257 bool last_part = ly_scm2bool (book_->paper_->c_variable ("part-is-last"));
259 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
260 if (label_page_table == SCM_UNDEFINED)
261 label_page_table = SCM_EOL;
263 for (vsize i = 0; i < lines_per_page.size (); i++)
265 SCM page_num = scm_from_int (i + first_page_number);
266 bool last_from_part = (i == lines_per_page.size () - 1);
267 SCM last_from_book = scm_from_bool (last_part && last_from_part);
268 SCM rag = scm_from_bool (ragged () || (last_from_part && 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,
273 rag, last_from_book, SCM_UNDEFINED));
276 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
278 SCM labels = SCM_EOL;
279 if (Grob * line = unsmob_grob (scm_car (l)))
281 System *system = dynamic_cast<System*> (line);
282 labels = system->get_property ("labels");
284 else if (Prob *prob = unsmob_prob (scm_car (l)))
285 labels = prob->get_property ("labels");
287 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
288 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
292 scm_apply_1 (page_stencil, page, SCM_EOL);
293 ret = scm_cons (page, ret);
294 systems = scm_list_tail (systems, line_count);
296 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
297 ret = scm_reverse (ret);
301 /* The page-turn-page-breaker needs to have a line-breaker between any two
302 columns with non-NULL page-turn-permission.
304 The optimal-breaker needs to have a line-breaker between any two columns
305 with page-break-permission = 'force.
307 By using a grob predicate, we can accommodate both of these uses.
310 Page_breaking::create_system_list ()
312 SCM specs = book_->get_system_specs ();
313 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
315 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
317 SCM system_count = ps->layout ()->c_variable ("system-count");
319 if (scm_is_number (system_count))
320 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
321 scm_vector_to_list (ps->get_paper_systems ()),
324 system_specs_.push_back (System_spec (ps));
328 Prob *pb = unsmob_prob (scm_car (s));
332 system_specs_.push_back (System_spec (pb));
338 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
340 SCM force_sym = ly_symbol2scm ("force");
342 chunks_.push_back (Break_position ());
343 breaks_.push_back (Break_position ());
345 for (vsize i = 0; i < system_specs_.size (); i++)
347 if (system_specs_[i].pscore_)
350 = system_specs_[i].pscore_->root_system ()->used_columns ();
351 vector<vsize> line_breaker_columns;
352 line_breaker_columns.push_back (0);
354 for (vsize j = 1; j < cols.size (); j++)
356 bool last = (j == cols.size () - 1);
357 bool break_point = is_break (cols[j]);
358 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
359 Break_position cur_pos = Break_position (i,
360 line_breaker_columns.size (),
364 if (break_point || (i == system_specs_.size () - 1 && last))
365 breaks_.push_back (cur_pos);
366 if (chunk_end || last)
367 chunks_.push_back (cur_pos);
369 if ((break_point || chunk_end) && !last)
370 line_breaker_columns.push_back (j);
372 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
376 /* TODO: we want some way of applying Break_p to a prob? */
377 if (i == system_specs_.size () - 1)
378 breaks_.push_back (Break_position (i));
380 chunks_.push_back (Break_position (i));
382 /* FIXME: shouldn't we push a Null_breaker or similar dummy
384 line_breaking_.push_back (Constrained_breaking (NULL));
389 vector<Break_position>
390 Page_breaking::chunk_list (vsize start_index, vsize end_index)
392 Break_position start = breaks_[start_index];
393 Break_position end = breaks_[end_index];
396 for (; i < chunks_.size () && chunks_[i] <= start; i++)
399 vector<Break_position> ret;
400 ret.push_back (start);
401 for (; i < chunks_.size () && chunks_[i] < end; i++)
402 ret.push_back (chunks_[i]);
408 Page_breaking::min_system_count (vsize start, vsize end)
410 vector<Break_position> chunks = chunk_list (start, end);
411 Line_division div = system_count_bounds (chunks, true);
414 for (vsize i = 0; i < div.size (); i++)
420 Page_breaking::max_system_count (vsize start, vsize end)
422 vector<Break_position> chunks = chunk_list (start, end);
423 Line_division div = system_count_bounds (chunks, false);
426 for (vsize i = 0; i < div.size (); i++)
431 Page_breaking::Line_division
432 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
435 assert (chunks.size () >= 2);
438 ret.resize (chunks.size () - 1, 1);
440 for (vsize i = 0; i + 1 < chunks.size (); i++)
442 vsize sys = next_system (chunks[i]);
443 if (system_specs_[sys].pscore_)
447 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
449 ? line_breaking_[sys].min_system_count (start, end)
450 : line_breaking_[sys].max_system_count (start, end);
458 Page_breaking::set_current_breakpoints (vsize start,
461 Line_division lower_bound,
462 Line_division upper_bound)
464 system_count_ = system_count;
465 current_chunks_ = chunk_list (start, end);
466 current_start_breakpoint_ = start;
467 current_end_breakpoint_ = end;
468 clear_line_details_cache ();
470 if (!lower_bound.size ())
471 lower_bound = system_count_bounds (current_chunks_, true);
472 if (!upper_bound.size ())
473 upper_bound = system_count_bounds (current_chunks_, false);
475 assert (lower_bound.size () == current_chunks_.size () - 1);
476 assert (upper_bound.size () == current_chunks_.size () - 1);
478 Line_division work_in_progress;
479 current_configurations_.clear ();
480 line_divisions_rec (system_count,
485 /* we only consider a constant number of configurations. Otherwise,
486 this becomes slow when there are many small scores. The constant
487 5 is somewhat arbitrary. */
488 if (current_configurations_.size () > 5)
490 vector<pair<Real,vsize> > dems_and_indices;
492 for (vsize i = 0; i < current_configurations_.size (); i++)
494 cache_line_details (i);
496 for (vsize j = 0; j < cached_line_details_.size (); j++)
497 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
498 + cached_line_details_[j].break_penalty_;
500 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
502 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
504 vector<Line_division> best_5_configurations;
505 for (vsize i = 0; i < 5; i++)
506 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
508 clear_line_details_cache ();
509 current_configurations_ = best_5_configurations;
514 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
516 current_chunks_ = chunk_list (start, end);
517 current_start_breakpoint_ = start;
518 current_end_breakpoint_ = end;
519 clear_line_details_cache ();
523 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
525 vsize sys = next_system (current_chunks_[i]);
526 if (system_specs_[sys].pscore_)
528 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
529 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
534 system_count_ += div.back ();
536 current_configurations_.clear ();
537 current_configurations_.push_back (div);
541 Page_breaking::current_configuration_count () const
543 return current_configurations_.size ();
547 Page_breaking::cache_line_details (vsize configuration_index)
549 if (cached_configuration_index_ != configuration_index)
551 cached_configuration_index_ = configuration_index;
552 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
553 if (!scm_is_number (padding_scm))
554 padding_scm = book_->paper_->c_variable ("between-system-padding");
555 Real padding = robust_scm2double (padding_scm, 0.0);
557 Line_division &div = current_configurations_[configuration_index];
558 uncompressed_line_details_.clear ();
559 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
561 vsize sys = next_system (current_chunks_[i]);
562 if (system_specs_[sys].pscore_)
566 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
568 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
569 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
573 assert (div[i] == 1);
574 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
575 uncompressed_line_details_.back ().padding_ =
576 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
580 cached_line_details_ = compress_lines (uncompressed_line_details_);
585 Page_breaking::clear_line_details_cache ()
587 cached_configuration_index_ = VPOS;
588 cached_line_details_.clear ();
589 uncompressed_line_details_.clear ();
593 Page_breaking::line_divisions_rec (vsize system_count,
594 Line_division const &min_sys,
595 Line_division const &max_sys,
596 Line_division *cur_division)
598 vsize my_index = cur_division->size ();
599 vsize others_min = 0;
600 vsize others_max = 0;
602 for (vsize i = my_index + 1; i < min_sys.size (); i++)
604 others_min += min_sys[i];
605 others_max += max_sys[i];
607 others_max = min (others_max, system_count);
608 vsize real_min = max (min_sys[my_index], system_count - others_max);
609 vsize real_max = min (max_sys[my_index], system_count - others_min);
611 if (real_min > real_max || real_min <= 0)
613 /* this should never happen within a recursive call. If it happens
614 at all, it means that we were called with an unsolvable problem
615 and we should return an empty result */
616 assert (my_index == 0);
620 for (vsize i = real_min; i <= real_max; i++)
622 cur_division->push_back (i);
623 if (my_index == min_sys.size () - 1)
624 current_configurations_.push_back (*cur_division);
626 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
627 cur_division->pop_back ();
632 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
635 Real cur_rod_height = 0;
636 Real cur_spring_height = 0;
637 Real cur_page_height = page_height (first_page_num, false);
639 cache_line_details (configuration);
640 for (vsize i = 0; i < cached_line_details_.size (); i++)
642 Real ext_len = cached_line_details_[i].extent_.length ();
643 Real next_rod_height = cur_rod_height + ext_len
644 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
645 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
646 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
649 if ((next_height > cur_page_height && cur_rod_height > 0)
651 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
653 cur_rod_height = ext_len;
654 cur_spring_height = cached_line_details_[i].space_;
655 cur_page_height = page_height (first_page_num + ret, false);
660 cur_rod_height = next_rod_height;
661 cur_spring_height = next_spring_height;
665 /* there are two potential problems with the last page (because we didn't know
666 it was the last page until after we managed to fit all the systems to it):
667 - we are ragged-last but the last page has a compressed spring
668 - the value returned by page_height (num, true) is smaller than the
669 value returned by page_height (num, false) and it causes the page not to
672 In either case, we just need to add one more page. This is because the last
673 line will always fit on the extra page and by adding one more page to the
674 end, the previous page is no longer the last page, so our previous
675 calculations that treated it as a non-last page were ok.
678 cur_page_height = page_height (first_page_num + ret - 1, true);
679 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
680 if (cur_height > cur_page_height
681 /* don't increase the page count if the last page had only one system */
682 && cur_rod_height > cached_line_details_.back ().extent_.length ())
685 assert (ret <= cached_line_details_.size ());
690 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
692 Page_spacing_result ret;
694 cache_line_details (configuration);
695 bool valid_n = (n >= min_page_count (configuration, first_page_num)
696 && n <= cached_line_details_.size ());
699 programming_error ("number of pages is out of bounds");
701 if (n == 1 && valid_n)
702 ret = space_systems_on_1_page (cached_line_details_,
703 page_height (first_page_num, is_last ()),
704 ragged () || (is_last () && ragged_last ()));
705 else if (n == 2 && valid_n)
706 ret = space_systems_on_2_pages (configuration, first_page_num);
709 Page_spacer ps (cached_line_details_, first_page_num, this);
713 return finalize_spacing_result (configuration, ret);
717 Page_breaking::blank_page_penalty () const
722 penalty_sym = ly_symbol2scm ("blank-last-page-force");
723 else if (ends_score ())
724 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
726 penalty_sym = ly_symbol2scm ("blank-page-force");
728 Break_position const &pos = breaks_[current_end_breakpoint_];
729 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
730 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
732 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
736 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
738 Page_spacing_result n_res;
739 Page_spacing_result m_res;
741 cache_line_details (configuration);
742 vsize min_p_count = min_page_count (configuration, first_page_num);
743 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
746 programming_error ("both page counts are out of bounds");
748 if (n == 1 && valid_n)
750 bool rag = ragged () || (is_last () && ragged_last ());
751 Real height = page_height (first_page_num, is_last ());
753 if (1 >= min_p_count)
754 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
755 if (1 < cached_line_details_.size ())
756 m_res = space_systems_on_2_pages (configuration, first_page_num);
760 Page_spacer ps (cached_line_details_, first_page_num, this);
762 if (n >= min_p_count || !valid_n)
763 n_res = ps.solve (n);
764 if (n < cached_line_details_.size () || !valid_n)
765 m_res = ps.solve (n+1);
768 m_res = finalize_spacing_result (configuration, m_res);
769 n_res = finalize_spacing_result (configuration, n_res);
771 Real penalty = blank_page_penalty ();
772 n_res.demerits_ += penalty;
774 if (n_res.force_.size ())
775 n_res.force_.back () += penalty;
777 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
781 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
783 vsize min_p_count = min_page_count (configuration, first_page_num);
784 Real odd_pages_penalty = blank_page_penalty ();
786 cache_line_details (configuration);
787 Page_spacer ps (cached_line_details_, first_page_num, this);
788 Page_spacing_result best = ps.solve (min_p_count);
789 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
790 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
792 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
794 Page_spacing_result cur = ps.solve (i);
795 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
796 if (cur.demerits_ < best.demerits_)
800 return finalize_spacing_result (configuration, best);
804 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
806 Page_spacing_result res;
808 vsize page_first_line = 0;
809 Page_spacing space (page_height (first_page_num, false), page_top_space_);
811 cache_line_details (configuration);
812 for (vsize line = 0; line < cached_line_details_.size (); line++)
814 Real prev_force = space.force_;
815 space.append_system (cached_line_details_[line]);
816 if ((line > page_first_line)
817 && (isinf (space.force_)
819 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
821 res.systems_per_page_.push_back (line - page_first_line);
822 res.force_.push_back (prev_force);
823 res.penalty_ += cached_line_details_[line-1].page_penalty_;
825 space.resize (page_height (first_page_num + page, false));
827 space.append_system (cached_line_details_[line]);
828 page_first_line = line;
831 if (line == cached_line_details_.size () - 1)
833 /* This is the last line */
834 /* When the last page height was computed, we did not know yet that it
835 * was the last one. If the systems put on it don't fit anymore, the last
836 * system is moved to a new page */
837 space.resize (page_height (first_page_num + page, true));
838 if ((line > page_first_line) && (isinf (space.force_)))
840 res.systems_per_page_.push_back (line - page_first_line);
841 res.force_.push_back (prev_force);
842 /* the last page containing the last line */
843 space.resize (page_height (first_page_num + page + 1, true));
845 space.append_system (cached_line_details_[line]);
846 res.systems_per_page_.push_back (1);
847 res.force_.push_back (space.force_);
848 res.penalty_ += cached_line_details_[line-1].page_penalty_;
849 res.penalty_ += cached_line_details_[line].page_penalty_;
853 res.systems_per_page_.push_back (line + 1 - page_first_line);
854 res.force_.push_back (space.force_);
855 res.penalty_ += cached_line_details_[line].page_penalty_;
859 return finalize_spacing_result (configuration, res);
862 /* Calculate demerits and fix res.systems_per_page_ so that
863 it refers to the original line numbers, not the ones given by compress_lines (). */
865 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
867 if (res.force_.empty ())
870 cache_line_details (configuration);
871 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
874 Real line_penalty = 0;
876 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
878 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
880 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
881 line_penalty += uncompressed_line_details_[i].break_penalty_;
884 for (vsize i = 0; i < res.force_.size (); i++)
886 Real f = res.force_[i];
887 if (isinf (f) && res.systems_per_page_[i] == 1)
893 /* for a while we tried averaging page and line forces across pages instead
894 of summing them, but it caused a problem: if there is a single page
895 with a very bad page force (for example because of a forced page break),
896 the page breaker will put in a _lot_ of pages so that the bad force
897 becomes averaged out over many pages. */
898 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
903 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
904 are by far the most common cases, we have special functions for them.
906 space_systems_on_1_page has a different calling convention than most of the
907 space_systems functions. This is because space_systems_on_1_page is (unlike
908 the other space_systems functions) sometimes called on subsets of a full
911 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
913 Page_spacing space (page_height, page_top_space_);
914 Page_spacing_result ret;
916 for (vsize i = 0; i < lines.size (); i++)
917 space.append_system (lines[i]);
919 ret.systems_per_page_.push_back (lines.size ());
920 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
921 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
923 /* don't do finalize_spacing_result () because we are only an internal function */
928 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
930 Real page1_height = page_height (first_page_num, false);
931 Real page2_height = page_height (first_page_num + 1, is_last ());
932 bool ragged1 = ragged ();
933 bool ragged2 = ragged () || (is_last () && ragged_last ());
935 /* if there is a forced break, this reduces to 2 1-page problems */
936 cache_line_details (configuration);
937 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
938 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
940 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
941 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
942 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
943 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
945 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
946 p1.force_.push_back (p2.force_[0]);
947 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
951 vector<Real> page1_force;
952 vector<Real> page2_force;
953 Page_spacing page1 (page1_height, page_top_space_);
954 Page_spacing page2 (page2_height, page_top_space_);
956 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
957 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
959 /* find the page 1 and page 2 forces for each page-breaking position */
960 for (vsize i = 0; i < page1_force.size (); i++)
962 page1.append_system (cached_line_details_[i]);
963 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
964 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
967 page2_force[page2_force.size () - 1 - i] =
968 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
970 page2_force[page2_force.size () - 1 - i] = page2.force_;
973 /* find the position that minimises the sum of the page forces */
974 vsize best_sys_count = 1;
975 Real best_demerits = infinity_f;
976 for (vsize i = 0; i < page1_force.size (); i++)
978 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
979 Real uneven = 2 * (page1_force[i] - page2_force[i]);
980 Real dem = uneven * uneven + f
981 + cached_line_details_[i+1].page_penalty_
982 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
983 if (dem < best_demerits)
986 best_sys_count = i+1;
990 Page_spacing_result ret;
991 ret.systems_per_page_.push_back (best_sys_count);
992 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
993 ret.force_.push_back (page1_force[best_sys_count-1]);
994 ret.force_.push_back (page2_force[best_sys_count-1]);
995 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
996 + cached_line_details_.back ().page_penalty_
997 + cached_line_details_.back ().turn_penalty_;
999 /* don't do finalize_spacing_result () because we are only an internal function */
1004 Page_breaking::all_lines_stretched (vsize configuration)
1006 cache_line_details (configuration);
1007 for (vsize i = 0; i < cached_line_details_.size (); i++)
1008 if (cached_line_details_[i].force_ < 0)
1014 Page_breaking::Line_division
1015 Page_breaking::current_configuration (vsize configuration_index) const
1017 return current_configurations_[configuration_index];
1021 Page_breaking::is_last () const
1023 return current_end_breakpoint_ == last_break_position ();
1027 Page_breaking::ends_score () const
1029 return breaks_[current_end_breakpoint_].score_ender_;
1033 Page_breaking::last_break_position () const
1035 return breaks_.size () - 1;