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 ("first-page-number"), 1);
258 SCM label_page_table = SCM_EOL;
260 for (vsize i = 0; i < lines_per_page.size (); i++)
262 SCM page_num = scm_from_int (i + first_page_number);
263 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
264 SCM rag = scm_from_bool (ragged () || (to_boolean (last)
266 SCM line_count = scm_from_int (lines_per_page[i]);
267 SCM lines = scm_list_head (systems, line_count);
268 SCM page = scm_apply_0 (make_page,
269 scm_list_n (book, lines, page_num,
270 rag, last, SCM_UNDEFINED));
273 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
275 SCM labels = SCM_EOL;
276 if (Grob * line = unsmob_grob (scm_car (l)))
278 System *system = dynamic_cast<System*> (line);
279 labels = system->get_property ("labels");
281 else if (Prob *prob = unsmob_prob (scm_car (l)))
282 labels = prob->get_property ("labels");
284 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
285 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
289 scm_apply_1 (page_stencil, page, SCM_EOL);
290 ret = scm_cons (page, ret);
291 systems = scm_list_tail (systems, line_count);
293 book_->paper_->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
294 ret = scm_reverse (ret);
298 /* The page-turn-page-breaker needs to have a line-breaker between any two
299 columns with non-NULL page-turn-permission.
301 The optimal-breaker needs to have a line-breaker between any two columns
302 with page-break-permission = 'force.
304 By using a grob predicate, we can accommodate both of these uses.
307 Page_breaking::create_system_list ()
309 SCM specs = book_->get_system_specs ();
310 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
312 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
314 SCM system_count = ps->layout ()->c_variable ("system-count");
316 if (scm_is_number (system_count))
317 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
318 scm_vector_to_list (ps->get_paper_systems ()),
321 system_specs_.push_back (System_spec (ps));
325 Prob *pb = unsmob_prob (scm_car (s));
329 system_specs_.push_back (System_spec (pb));
335 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
337 SCM force_sym = ly_symbol2scm ("force");
339 chunks_.push_back (Break_position ());
340 breaks_.push_back (Break_position ());
342 for (vsize i = 0; i < system_specs_.size (); i++)
344 if (system_specs_[i].pscore_)
347 = system_specs_[i].pscore_->root_system ()->used_columns ();
348 vector<vsize> line_breaker_columns;
349 line_breaker_columns.push_back (0);
351 for (vsize j = 1; j < cols.size (); j++)
353 bool last = (j == cols.size () - 1);
354 bool break_point = is_break (cols[j]);
355 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
356 Break_position cur_pos = Break_position (i,
357 line_breaker_columns.size (),
361 if (break_point || (i == system_specs_.size () - 1 && last))
362 breaks_.push_back (cur_pos);
363 if (chunk_end || last)
364 chunks_.push_back (cur_pos);
366 if ((break_point || chunk_end) && !last)
367 line_breaker_columns.push_back (j);
369 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
373 /* TODO: we want some way of applying Break_p to a prob? */
374 if (i == system_specs_.size () - 1)
375 breaks_.push_back (Break_position (i));
377 chunks_.push_back (Break_position (i));
379 /* FIXME: shouldn't we push a Null_breaker or similar dummy
381 line_breaking_.push_back (Constrained_breaking (NULL));
386 vector<Break_position>
387 Page_breaking::chunk_list (vsize start_index, vsize end_index)
389 Break_position start = breaks_[start_index];
390 Break_position end = breaks_[end_index];
393 for (; i < chunks_.size () && chunks_[i] <= start; i++)
396 vector<Break_position> ret;
397 ret.push_back (start);
398 for (; i < chunks_.size () && chunks_[i] < end; i++)
399 ret.push_back (chunks_[i]);
405 Page_breaking::min_system_count (vsize start, vsize end)
407 vector<Break_position> chunks = chunk_list (start, end);
408 Line_division div = system_count_bounds (chunks, true);
411 for (vsize i = 0; i < div.size (); i++)
417 Page_breaking::max_system_count (vsize start, vsize end)
419 vector<Break_position> chunks = chunk_list (start, end);
420 Line_division div = system_count_bounds (chunks, false);
423 for (vsize i = 0; i < div.size (); i++)
428 Page_breaking::Line_division
429 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
432 assert (chunks.size () >= 2);
435 ret.resize (chunks.size () - 1, 1);
437 for (vsize i = 0; i + 1 < chunks.size (); i++)
439 vsize sys = next_system (chunks[i]);
440 if (system_specs_[sys].pscore_)
444 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
446 ? line_breaking_[sys].min_system_count (start, end)
447 : line_breaking_[sys].max_system_count (start, end);
455 Page_breaking::set_current_breakpoints (vsize start,
458 Line_division lower_bound,
459 Line_division upper_bound)
461 system_count_ = system_count;
462 current_chunks_ = chunk_list (start, end);
463 current_start_breakpoint_ = start;
464 current_end_breakpoint_ = end;
465 clear_line_details_cache ();
467 if (!lower_bound.size ())
468 lower_bound = system_count_bounds (current_chunks_, true);
469 if (!upper_bound.size ())
470 upper_bound = system_count_bounds (current_chunks_, false);
472 assert (lower_bound.size () == current_chunks_.size () - 1);
473 assert (upper_bound.size () == current_chunks_.size () - 1);
475 Line_division work_in_progress;
476 current_configurations_.clear ();
477 line_divisions_rec (system_count,
482 /* we only consider a constant number of configurations. Otherwise,
483 this becomes slow when there are many small scores. The constant
484 5 is somewhat arbitrary. */
485 if (current_configurations_.size () > 5)
487 vector<pair<Real,vsize> > dems_and_indices;
489 for (vsize i = 0; i < current_configurations_.size (); i++)
491 cache_line_details (i);
493 for (vsize j = 0; j < cached_line_details_.size (); j++)
494 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
495 + cached_line_details_[j].break_penalty_;
497 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
499 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
501 vector<Line_division> best_5_configurations;
502 for (vsize i = 0; i < 5; i++)
503 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
505 clear_line_details_cache ();
506 current_configurations_ = best_5_configurations;
511 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
513 current_chunks_ = chunk_list (start, end);
514 current_start_breakpoint_ = start;
515 current_end_breakpoint_ = end;
516 clear_line_details_cache ();
520 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
522 vsize sys = next_system (current_chunks_[i]);
523 if (system_specs_[sys].pscore_)
525 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
526 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
531 system_count_ += div.back ();
533 current_configurations_.clear ();
534 current_configurations_.push_back (div);
538 Page_breaking::current_configuration_count () const
540 return current_configurations_.size ();
544 Page_breaking::cache_line_details (vsize configuration_index)
546 if (cached_configuration_index_ != configuration_index)
548 cached_configuration_index_ = configuration_index;
549 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
550 if (!scm_is_number (padding_scm))
551 padding_scm = book_->paper_->c_variable ("between-system-padding");
552 Real padding = robust_scm2double (padding_scm, 0.0);
554 Line_division &div = current_configurations_[configuration_index];
555 uncompressed_line_details_.clear ();
556 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
558 vsize sys = next_system (current_chunks_[i]);
559 if (system_specs_[sys].pscore_)
563 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
565 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
566 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
570 assert (div[i] == 1);
571 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
572 uncompressed_line_details_.back ().padding_ =
573 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
577 cached_line_details_ = compress_lines (uncompressed_line_details_);
582 Page_breaking::clear_line_details_cache ()
584 cached_configuration_index_ = VPOS;
585 cached_line_details_.clear ();
586 uncompressed_line_details_.clear ();
590 Page_breaking::line_divisions_rec (vsize system_count,
591 Line_division const &min_sys,
592 Line_division const &max_sys,
593 Line_division *cur_division)
595 vsize my_index = cur_division->size ();
596 vsize others_min = 0;
597 vsize others_max = 0;
599 for (vsize i = my_index + 1; i < min_sys.size (); i++)
601 others_min += min_sys[i];
602 others_max += max_sys[i];
604 others_max = min (others_max, system_count);
605 vsize real_min = max (min_sys[my_index], system_count - others_max);
606 vsize real_max = min (max_sys[my_index], system_count - others_min);
608 if (real_min > real_max || real_min <= 0)
610 /* this should never happen within a recursive call. If it happens
611 at all, it means that we were called with an unsolvable problem
612 and we should return an empty result */
613 assert (my_index == 0);
617 for (vsize i = real_min; i <= real_max; i++)
619 cur_division->push_back (i);
620 if (my_index == min_sys.size () - 1)
621 current_configurations_.push_back (*cur_division);
623 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
624 cur_division->pop_back ();
629 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
632 Real cur_rod_height = 0;
633 Real cur_spring_height = 0;
634 Real cur_page_height = page_height (first_page_num, false);
636 cache_line_details (configuration);
637 for (vsize i = 0; i < cached_line_details_.size (); i++)
639 Real ext_len = cached_line_details_[i].extent_.length ();
640 Real next_rod_height = cur_rod_height + ext_len
641 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
642 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
643 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
646 if ((next_height > cur_page_height && cur_rod_height > 0)
648 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
650 cur_rod_height = ext_len;
651 cur_spring_height = cached_line_details_[i].space_;
652 cur_page_height = page_height (first_page_num + ret, false);
657 cur_rod_height = next_rod_height;
658 cur_spring_height = next_spring_height;
662 /* there are two potential problems with the last page (because we didn't know
663 it was the last page until after we managed to fit all the systems to it):
664 - we are ragged-last but the last page has a compressed spring
665 - the value returned by page_height (num, true) is smaller than the
666 value returned by page_height (num, false) and it causes the page not to
669 In either case, we just need to add one more page. This is because the last
670 line will always fit on the extra page and by adding one more page to the
671 end, the previous page is no longer the last page, so our previous
672 calculations that treated it as a non-last page were ok.
675 cur_page_height = page_height (first_page_num + ret - 1, true);
676 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
677 if (cur_height > cur_page_height
678 /* don't increase the page count if the last page had only one system */
679 && cur_rod_height > cached_line_details_.back ().extent_.length ())
682 assert (ret <= cached_line_details_.size ());
687 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
689 Page_spacing_result ret;
691 cache_line_details (configuration);
692 bool valid_n = (n >= min_page_count (configuration, first_page_num)
693 && n <= cached_line_details_.size ());
696 programming_error ("number of pages is out of bounds");
698 if (n == 1 && valid_n)
699 ret = space_systems_on_1_page (cached_line_details_,
700 page_height (first_page_num, is_last ()),
701 ragged () || (is_last () && ragged_last ()));
702 else if (n == 2 && valid_n)
703 ret = space_systems_on_2_pages (configuration, first_page_num);
706 Page_spacer ps (cached_line_details_, first_page_num, this);
710 return finalize_spacing_result (configuration, ret);
714 Page_breaking::blank_page_penalty () const
716 SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
717 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
721 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
723 Page_spacing_result n_res;
724 Page_spacing_result m_res;
726 cache_line_details (configuration);
727 vsize min_p_count = min_page_count (configuration, first_page_num);
728 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
731 programming_error ("both page counts are out of bounds");
733 if (n == 1 && valid_n)
735 bool rag = ragged () || (is_last () && ragged_last ());
736 Real height = page_height (first_page_num, is_last ());
738 if (1 >= min_p_count)
739 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
740 if (1 < cached_line_details_.size ())
741 m_res = space_systems_on_2_pages (configuration, first_page_num);
745 Page_spacer ps (cached_line_details_, first_page_num, this);
747 if (n >= min_p_count || !valid_n)
748 n_res = ps.solve (n);
749 if (n < cached_line_details_.size () || !valid_n)
750 m_res = ps.solve (n+1);
753 m_res = finalize_spacing_result (configuration, m_res);
754 n_res = finalize_spacing_result (configuration, n_res);
756 Real penalty = blank_page_penalty ();
757 n_res.demerits_ += penalty;
759 if (n_res.force_.size ())
760 n_res.force_.back () += penalty;
762 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
766 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
768 vsize min_p_count = min_page_count (configuration, first_page_num);
769 Real odd_pages_penalty = blank_page_penalty ();
771 cache_line_details (configuration);
772 Page_spacer ps (cached_line_details_, first_page_num, this);
773 Page_spacing_result best = ps.solve (min_p_count);
774 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
775 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
777 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
779 Page_spacing_result cur = ps.solve (i);
780 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
781 if (cur.demerits_ < best.demerits_)
785 return finalize_spacing_result (configuration, best);
789 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
791 Page_spacing_result res;
793 vsize page_first_line = 0;
794 Page_spacing space (page_height (first_page_num, false), page_top_space_);
796 cache_line_details (configuration);
797 for (vsize line = 0; line < cached_line_details_.size (); line++)
799 Real prev_force = space.force_;
800 space.append_system (cached_line_details_[line]);
801 if ((line > page_first_line)
802 && (isinf (space.force_)
804 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
806 res.systems_per_page_.push_back (line - page_first_line);
807 res.force_.push_back (prev_force);
808 res.penalty_ += cached_line_details_[line-1].page_penalty_;
810 space.resize (page_height (first_page_num + page, false));
812 space.append_system (cached_line_details_[line]);
813 page_first_line = line;
816 if (line == cached_line_details_.size () - 1)
818 /* This is the last line */
819 /* When the last page height was computed, we did not know yet that it
820 * was the last one. If the systems put on it don't fit anymore, the last
821 * system is moved to a new page */
822 space.resize (page_height (first_page_num + page, true));
823 if ((line > page_first_line) && (isinf (space.force_)))
825 res.systems_per_page_.push_back (line - page_first_line);
826 res.force_.push_back (prev_force);
827 /* the last page containing the last line */
828 space.resize (page_height (first_page_num + page + 1, true));
830 space.append_system (cached_line_details_[line]);
831 res.systems_per_page_.push_back (1);
832 res.force_.push_back (space.force_);
833 res.penalty_ += cached_line_details_[line-1].page_penalty_;
834 res.penalty_ += cached_line_details_[line].page_penalty_;
838 res.systems_per_page_.push_back (line + 1 - page_first_line);
839 res.force_.push_back (space.force_);
840 res.penalty_ += cached_line_details_[line].page_penalty_;
844 return finalize_spacing_result (configuration, res);
847 /* Calculate demerits and fix res.systems_per_page_ so that
848 it refers to the original line numbers, not the ones given by compress_lines (). */
850 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
852 if (res.force_.empty ())
855 cache_line_details (configuration);
856 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
859 Real line_penalty = 0;
861 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
863 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
865 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
866 line_penalty += uncompressed_line_details_[i].break_penalty_;
869 for (vsize i = 0; i < res.force_.size (); i++)
871 Real f = res.force_[i];
872 if (isinf (f) && res.systems_per_page_[i] == 1)
878 /* for a while we tried averaging page and line forces across pages instead
879 of summing them, but it caused a problem: if there is a single page
880 with a very bad page force (for example because of a forced page break),
881 the page breaker will put in a _lot_ of pages so that the bad force
882 becomes averaged out over many pages. */
883 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
888 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
889 are by far the most common cases, we have special functions for them.
891 space_systems_on_1_page has a different calling convention than most of the
892 space_systems functions. This is because space_systems_on_1_page is (unlike
893 the other space_systems functions) sometimes called on subsets of a full
896 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
898 Page_spacing space (page_height, page_top_space_);
899 Page_spacing_result ret;
901 for (vsize i = 0; i < lines.size (); i++)
902 space.append_system (lines[i]);
904 ret.systems_per_page_.push_back (lines.size ());
905 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
906 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
908 /* don't do finalize_spacing_result () because we are only an internal function */
913 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
915 Real page1_height = page_height (first_page_num, false);
916 Real page2_height = page_height (first_page_num + 1, is_last ());
917 bool ragged1 = ragged ();
918 bool ragged2 = ragged () || (is_last () && ragged_last ());
920 /* if there is a forced break, this reduces to 2 1-page problems */
921 cache_line_details (configuration);
922 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
923 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
925 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
926 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
927 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
928 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
930 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
931 p1.force_.push_back (p2.force_[0]);
932 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
936 vector<Real> page1_force;
937 vector<Real> page2_force;
938 Page_spacing page1 (page1_height, page_top_space_);
939 Page_spacing page2 (page2_height, page_top_space_);
941 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
942 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
944 /* find the page 1 and page 2 forces for each page-breaking position */
945 for (vsize i = 0; i < page1_force.size (); i++)
947 page1.append_system (cached_line_details_[i]);
948 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
949 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
952 page2_force[page2_force.size () - 1 - i] =
953 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
955 page2_force[page2_force.size () - 1 - i] = page2.force_;
958 /* find the position that minimises the sum of the page forces */
959 vsize best_sys_count = 1;
960 Real best_demerits = infinity_f;
961 for (vsize i = 0; i < page1_force.size (); i++)
963 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
964 Real uneven = 2 * (page1_force[i] - page2_force[i]);
965 Real dem = uneven * uneven + f
966 + cached_line_details_[i+1].page_penalty_
967 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
968 if (dem < best_demerits)
971 best_sys_count = i+1;
975 Page_spacing_result ret;
976 ret.systems_per_page_.push_back (best_sys_count);
977 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
978 ret.force_.push_back (page1_force[best_sys_count-1]);
979 ret.force_.push_back (page2_force[best_sys_count-1]);
980 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
981 + cached_line_details_.back ().page_penalty_
982 + cached_line_details_.back ().turn_penalty_;
984 /* don't do finalize_spacing_result () because we are only an internal function */
989 Page_breaking::all_lines_stretched (vsize configuration)
991 cache_line_details (configuration);
992 for (vsize i = 0; i < cached_line_details_.size (); i++)
993 if (cached_line_details_[i].force_ < 0)
999 Page_breaking::Line_division
1000 Page_breaking::current_configuration (vsize configuration_index) const
1002 return current_configurations_[configuration_index];
1006 Page_breaking::is_last () const
1008 return current_end_breakpoint_ == last_break_position ();
1012 Page_breaking::last_break_position () const
1014 return breaks_.size () - 1;