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 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
41 compressed.compressed_nontitle_lines_count_ =
42 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
44 compressed.title_ = compressed.title_ && old.title_;
45 ret.back () = compressed;
49 ret.push_back (orig[i]);
50 ret.back ().force_ = 0;
56 /* translate the number of systems-per-page into something meaningful for
57 the uncompressed lines.
60 uncompress_solution (vector<vsize> const &systems_per_page,
61 vector<Line_details> const &compressed)
66 for (vsize i = 0; i < systems_per_page.size (); i++)
68 int compressed_count = 0;
69 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
70 compressed_count += compressed[j].compressed_lines_count_ - 1;
72 ret.push_back (systems_per_page[i] + compressed_count);
73 start_sys += systems_per_page[i];
78 /* for Page_breaking, the start index (when we are dealing with the stuff
79 between a pair of breakpoints) refers to the break_ index of the end of
80 the previous page. So the system index of the start of the current page
81 could either be the same as the end of the previous page or one more than
84 /* Turn a break index into the sys index that starts the next page */
86 Page_breaking::next_system (Break_position const &break_pos) const
88 vsize sys = break_pos.system_spec_index_;
90 if (sys == VPOS) /* beginning of the book */
92 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
93 return sys; /* the score overflows the previous page */
94 return sys + 1; /* this page starts with a new System_spec */
97 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
101 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
102 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
103 page_top_space_ = robust_scm2double (pb->paper_->c_variable ("page-top-space"), 0);
104 systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0);
105 max_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0);
107 create_system_list ();
108 find_chunks_and_breaks (is_break);
111 Page_breaking::~Page_breaking ()
116 Page_breaking::ragged () const
122 Page_breaking::ragged_last () const
128 Page_breaking::systems_per_page () const
130 return systems_per_page_;
134 Page_breaking::max_systems_per_page () const
136 return max_systems_per_page_;
140 Page_breaking::page_top_space () const
142 return page_top_space_;
146 Page_breaking::system_count () const
148 return system_count_;
151 /* translate indices into breaks_ into start-end parameters for the line breaker */
153 Page_breaking::line_breaker_args (vsize sys,
154 Break_position const &start,
155 Break_position const &end,
156 vsize *line_breaker_start,
157 vsize *line_breaker_end)
159 assert (system_specs_[sys].pscore_);
160 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
162 if (start.system_spec_index_ == sys)
163 *line_breaker_start = start.score_break_;
165 *line_breaker_start = 0;
167 if (end.system_spec_index_ == sys)
168 *line_breaker_end = end.score_break_;
170 *line_breaker_end = VPOS;
174 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
175 Line_division const &div)
177 vector<Break_position> chunks = chunk_list (start_break, end_break);
178 bool ignore_div = false;
179 if (chunks.size () != div.size () + 1)
181 programming_error ("did not find a valid page breaking configuration");
185 for (vsize i = 0; i + 1 < chunks.size (); i++)
187 vsize sys = next_system (chunks[i]);
188 if (system_specs_[sys].pscore_)
192 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
194 vector<Column_x_positions> pos = ignore_div
195 ? line_breaking_[sys].best_solution (start, end)
196 : line_breaking_[sys].solve (start, end, div[i]);
197 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
203 Page_breaking::systems ()
206 for (vsize sys = 0; sys < system_specs_.size (); sys++)
208 if (system_specs_[sys].pscore_)
210 system_specs_[sys].pscore_->root_system ()
211 ->do_break_substitution_and_fixup_refpoints ();
212 SCM lines = system_specs_[sys].pscore_->root_system ()
213 ->get_broken_system_grobs ();
214 ret = scm_cons (lines, ret);
218 Prob *pb = system_specs_[sys].prob_;
219 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
223 return scm_append (scm_reverse (ret));
227 Page_breaking::page_height (int page_num, bool last) const
229 SCM mod = scm_c_resolve_module ("scm page");
230 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
231 SCM make_page = scm_c_module_lookup (mod, "make-page");
233 calc_height = scm_variable_ref (calc_height);
234 make_page = scm_variable_ref (make_page);
236 SCM page = scm_apply_0 (make_page, scm_list_n (
238 ly_symbol2scm ("page-number"), scm_from_int (page_num),
239 ly_symbol2scm ("is-last"), scm_from_bool (last),
241 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
242 return scm_to_double (height) - page_top_space_;
246 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
248 Break_position const &pos = breaks_[breakpoint];
250 if (pos.system_spec_index_ == VPOS)
252 if (system_specs_[pos.system_spec_index_].pscore_)
253 return pos.col_->get_property (str);
254 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
258 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
260 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
261 SCM page_module = scm_c_resolve_module ("scm page");
263 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
264 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
265 make_page = scm_variable_ref (make_page);
266 page_stencil = scm_variable_ref (page_stencil);
268 SCM book = book_->self_scm ();
269 int first_page_number
270 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
272 SCM label_page_table = SCM_EOL;
274 for (vsize i = 0; i < lines_per_page.size (); i++)
276 SCM page_num = scm_from_int (i + first_page_number);
277 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
278 SCM rag = scm_from_bool (ragged () || (to_boolean (last)
280 SCM line_count = scm_from_int (lines_per_page[i]);
281 SCM lines = scm_list_head (systems, line_count);
282 SCM page = scm_apply_0 (make_page,
283 scm_list_n (book, lines, page_num,
284 rag, last, SCM_UNDEFINED));
287 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
289 SCM labels = SCM_EOL;
290 if (Grob * line = unsmob_grob (scm_car (l)))
292 System *system = dynamic_cast<System*> (line);
293 labels = system->get_property ("labels");
295 else if (Prob *prob = unsmob_prob (scm_car (l)))
296 labels = prob->get_property ("labels");
298 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
299 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
303 scm_apply_1 (page_stencil, page, SCM_EOL);
304 ret = scm_cons (page, ret);
305 systems = scm_list_tail (systems, line_count);
307 book_->paper_->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
308 ret = scm_reverse (ret);
312 /* The page-turn-page-breaker needs to have a line-breaker between any two
313 columns with non-NULL page-turn-permission.
315 The optimal-breaker needs to have a line-breaker between any two columns
316 with page-break-permission = 'force.
318 By using a grob predicate, we can accommodate both of these uses.
321 Page_breaking::create_system_list ()
323 SCM specs = book_->get_system_specs ();
324 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
326 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
328 SCM system_count = ps->layout ()->c_variable ("system-count");
330 if (scm_is_number (system_count))
331 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
332 scm_vector_to_list (ps->get_paper_systems ()),
335 system_specs_.push_back (System_spec (ps));
339 Prob *pb = unsmob_prob (scm_car (s));
343 system_specs_.push_back (System_spec (pb));
349 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
351 SCM force_sym = ly_symbol2scm ("force");
353 chunks_.push_back (Break_position ());
354 breaks_.push_back (Break_position ());
356 for (vsize i = 0; i < system_specs_.size (); i++)
358 if (system_specs_[i].pscore_)
361 = system_specs_[i].pscore_->root_system ()->used_columns ();
362 vector<vsize> line_breaker_columns;
363 line_breaker_columns.push_back (0);
365 for (vsize j = 1; j < cols.size (); j++)
367 bool last = (j == cols.size () - 1);
368 bool break_point = is_break (cols[j]);
369 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
370 Break_position cur_pos = Break_position (i,
371 line_breaker_columns.size (),
375 if (break_point || (i == system_specs_.size () - 1 && last))
376 breaks_.push_back (cur_pos);
377 if (chunk_end || last)
378 chunks_.push_back (cur_pos);
380 if ((break_point || chunk_end) && !last)
381 line_breaker_columns.push_back (j);
383 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
387 /* TODO: we want some way of applying Break_p to a prob? */
388 if (i == system_specs_.size () - 1)
389 breaks_.push_back (Break_position (i));
391 chunks_.push_back (Break_position (i));
393 /* FIXME: shouldn't we push a Null_breaker or similar dummy
395 line_breaking_.push_back (Constrained_breaking (NULL));
400 vector<Break_position>
401 Page_breaking::chunk_list (vsize start_index, vsize end_index)
403 Break_position start = breaks_[start_index];
404 Break_position end = breaks_[end_index];
407 for (; i < chunks_.size () && chunks_[i] <= start; i++)
410 vector<Break_position> ret;
411 ret.push_back (start);
412 for (; i < chunks_.size () && chunks_[i] < end; i++)
413 ret.push_back (chunks_[i]);
419 Page_breaking::min_system_count (vsize start, vsize end)
421 vector<Break_position> chunks = chunk_list (start, end);
422 Line_division div = system_count_bounds (chunks, true);
425 for (vsize i = 0; i < div.size (); i++)
431 Page_breaking::max_system_count (vsize start, vsize end)
433 vector<Break_position> chunks = chunk_list (start, end);
434 Line_division div = system_count_bounds (chunks, false);
437 for (vsize i = 0; i < div.size (); i++)
442 Page_breaking::Line_division
443 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
446 assert (chunks.size () >= 2);
449 ret.resize (chunks.size () - 1, 1);
451 for (vsize i = 0; i + 1 < chunks.size (); i++)
453 vsize sys = next_system (chunks[i]);
454 if (system_specs_[sys].pscore_)
458 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
460 ? line_breaking_[sys].min_system_count (start, end)
461 : line_breaking_[sys].max_system_count (start, end);
469 Page_breaking::set_current_breakpoints (vsize start,
472 Line_division lower_bound,
473 Line_division upper_bound)
475 system_count_ = system_count;
476 current_chunks_ = chunk_list (start, end);
477 current_start_breakpoint_ = start;
478 current_end_breakpoint_ = end;
479 clear_line_details_cache ();
481 if (!lower_bound.size ())
482 lower_bound = system_count_bounds (current_chunks_, true);
483 if (!upper_bound.size ())
484 upper_bound = system_count_bounds (current_chunks_, false);
486 assert (lower_bound.size () == current_chunks_.size () - 1);
487 assert (upper_bound.size () == current_chunks_.size () - 1);
489 Line_division work_in_progress;
490 current_configurations_.clear ();
491 line_divisions_rec (system_count,
496 /* we only consider a constant number of configurations. Otherwise,
497 this becomes slow when there are many small scores. The constant
498 5 is somewhat arbitrary. */
499 if (current_configurations_.size () > 5)
501 vector<pair<Real,vsize> > dems_and_indices;
503 for (vsize i = 0; i < current_configurations_.size (); i++)
505 cache_line_details (i);
507 for (vsize j = 0; j < cached_line_details_.size (); j++)
508 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
509 + cached_line_details_[j].break_penalty_;
511 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
513 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
515 vector<Line_division> best_5_configurations;
516 for (vsize i = 0; i < 5; i++)
517 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
519 clear_line_details_cache ();
520 current_configurations_ = best_5_configurations;
525 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
527 current_chunks_ = chunk_list (start, end);
528 current_start_breakpoint_ = start;
529 current_end_breakpoint_ = end;
530 clear_line_details_cache ();
534 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
536 vsize sys = next_system (current_chunks_[i]);
537 if (system_specs_[sys].pscore_)
539 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
540 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
545 system_count_ += div.back ();
547 current_configurations_.clear ();
548 current_configurations_.push_back (div);
552 Page_breaking::current_configuration_count () const
554 return current_configurations_.size ();
558 Page_breaking::cache_line_details (vsize configuration_index)
560 if (cached_configuration_index_ != configuration_index)
562 cached_configuration_index_ = configuration_index;
563 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
564 if (!scm_is_number (padding_scm))
565 padding_scm = book_->paper_->c_variable ("between-system-padding");
566 Real padding = robust_scm2double (padding_scm, 0.0);
568 Line_division &div = current_configurations_[configuration_index];
569 uncompressed_line_details_.clear ();
570 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
572 vsize sys = next_system (current_chunks_[i]);
573 if (system_specs_[sys].pscore_)
577 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
579 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
580 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
584 assert (div[i] == 1);
585 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
586 uncompressed_line_details_.back ().padding_ =
587 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
591 cached_line_details_ = compress_lines (uncompressed_line_details_);
596 Page_breaking::clear_line_details_cache ()
598 cached_configuration_index_ = VPOS;
599 cached_line_details_.clear ();
600 uncompressed_line_details_.clear ();
604 Page_breaking::line_divisions_rec (vsize system_count,
605 Line_division const &min_sys,
606 Line_division const &max_sys,
607 Line_division *cur_division)
609 vsize my_index = cur_division->size ();
610 vsize others_min = 0;
611 vsize others_max = 0;
613 for (vsize i = my_index + 1; i < min_sys.size (); i++)
615 others_min += min_sys[i];
616 others_max += max_sys[i];
618 others_max = min (others_max, system_count);
619 vsize real_min = max (min_sys[my_index], system_count - others_max);
620 vsize real_max = min (max_sys[my_index], system_count - others_min);
622 if (real_min > real_max || real_min <= 0)
624 /* this should never happen within a recursive call. If it happens
625 at all, it means that we were called with an unsolvable problem
626 and we should return an empty result */
627 assert (my_index == 0);
631 for (vsize i = real_min; i <= real_max; i++)
633 cur_division->push_back (i);
634 if (my_index == min_sys.size () - 1)
635 current_configurations_.push_back (*cur_division);
637 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
638 cur_division->pop_back ();
643 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
646 Real cur_rod_height = 0;
647 Real cur_spring_height = 0;
648 Real cur_page_height = page_height (first_page_num, false);
650 cache_line_details (configuration);
651 for (vsize i = 0; i < cached_line_details_.size (); i++)
653 Real ext_len = cached_line_details_[i].extent_.length ();
654 Real next_rod_height = cur_rod_height + ext_len
655 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
656 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
657 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
660 if ((next_height > cur_page_height && cur_rod_height > 0)
662 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
664 cur_rod_height = ext_len;
665 cur_spring_height = cached_line_details_[i].space_;
666 cur_page_height = page_height (first_page_num + ret, false);
671 cur_rod_height = next_rod_height;
672 cur_spring_height = next_spring_height;
676 /* there are two potential problems with the last page (because we didn't know
677 it was the last page until after we managed to fit all the systems to it):
678 - we are ragged-last but the last page has a compressed spring
679 - the value returned by page_height (num, true) is smaller than the
680 value returned by page_height (num, false) and it causes the page not to
683 In either case, we just need to add one more page. This is because the last
684 line will always fit on the extra page and by adding one more page to the
685 end, the previous page is no longer the last page, so our previous
686 calculations that treated it as a non-last page were ok.
689 cur_page_height = page_height (first_page_num + ret - 1, true);
690 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
691 if (cur_height > cur_page_height
692 /* don't increase the page count if the last page had only one system */
693 && cur_rod_height > cached_line_details_.back ().extent_.length ())
696 assert (ret <= cached_line_details_.size ());
700 // If systems_per_page_ is positive, we don't really try to space on N pages;
701 // we just put the requested number of systems on each page and penalize
702 // if the result doesn't have N pages.
704 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
706 Page_spacing_result ret;
708 if (systems_per_page_ > 0)
710 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
711 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
715 cache_line_details (configuration);
716 bool valid_n = (n >= min_page_count (configuration, first_page_num)
717 && n <= cached_line_details_.size ());
720 programming_error ("number of pages is out of bounds");
722 if (n == 1 && valid_n)
723 ret = space_systems_on_1_page (cached_line_details_,
724 page_height (first_page_num, is_last ()),
725 ragged () || (is_last () && ragged_last ()));
726 else if (n == 2 && valid_n)
727 ret = space_systems_on_2_pages (configuration, first_page_num);
730 Page_spacer ps (cached_line_details_, first_page_num, this);
734 return finalize_spacing_result (configuration, ret);
738 Page_breaking::blank_page_penalty () const
743 penalty_sym = ly_symbol2scm ("blank-last-page-force");
744 else if (ends_score ())
745 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
747 penalty_sym = ly_symbol2scm ("blank-page-force");
749 Break_position const &pos = breaks_[current_end_breakpoint_];
750 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
751 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
753 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
756 // If systems_per_page_ is positive, we don't really try to space on N
757 // or N+1 pages; see the comment to space_systems_on_n_pages.
759 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
761 Page_spacing_result n_res;
762 Page_spacing_result m_res;
764 if (systems_per_page_ > 0)
766 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
767 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
771 cache_line_details (configuration);
772 vsize min_p_count = min_page_count (configuration, first_page_num);
773 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
776 programming_error ("both page counts are out of bounds");
778 if (n == 1 && valid_n)
780 bool rag = ragged () || (is_last () && ragged_last ());
781 Real height = page_height (first_page_num, is_last ());
783 if (1 >= min_p_count)
784 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
785 if (1 < cached_line_details_.size ())
786 m_res = space_systems_on_2_pages (configuration, first_page_num);
790 Page_spacer ps (cached_line_details_, first_page_num, this);
792 if (n >= min_p_count || !valid_n)
793 n_res = ps.solve (n);
794 if (n < cached_line_details_.size () || !valid_n)
795 m_res = ps.solve (n+1);
798 m_res = finalize_spacing_result (configuration, m_res);
799 n_res = finalize_spacing_result (configuration, n_res);
801 Real penalty = blank_page_penalty ();
802 n_res.demerits_ += penalty;
804 if (n_res.force_.size ())
805 n_res.force_.back () += penalty;
807 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
811 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
813 vsize min_p_count = min_page_count (configuration, first_page_num);
814 Real odd_pages_penalty = blank_page_penalty ();
816 cache_line_details (configuration);
817 Page_spacer ps (cached_line_details_, first_page_num, this);
818 Page_spacing_result best = ps.solve (min_p_count);
819 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
820 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
822 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
824 Page_spacing_result cur = ps.solve (i);
825 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
826 if (cur.demerits_ < best.demerits_)
830 return finalize_spacing_result (configuration, best);
834 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
835 vsize first_page_num)
837 Page_spacing_result res;
838 Page_spacing space (page_height (first_page_num, false), page_top_space_);
841 vsize page_first_line = 0;
843 cache_line_details (configuration);
844 while (line < cached_line_details_.size ())
848 space.resize (page_height (first_page_num + page, false));
850 int system_count_on_this_page = 0;
851 while (system_count_on_this_page < systems_per_page_
852 && line < cached_line_details_.size ())
854 Line_details const &cur_line = cached_line_details_[line];
855 space.append_system (cur_line);
856 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
859 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
863 res.systems_per_page_.push_back (line - page_first_line);
864 res.force_.push_back (space.force_);
865 res.penalty_ += cached_line_details_[line-1].page_penalty_;
866 page_first_line = line;
869 /* Recalculate forces for the last page because we know now that is
870 was really the last page. */
871 space.resize (page_height (first_page_num + page, true));
872 res.force_.back () = space.force_;
873 return finalize_spacing_result (configuration, res);
877 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
879 Page_spacing_result res;
881 vsize page_first_line = 0;
882 Page_spacing space (page_height (first_page_num, false), page_top_space_);
884 cache_line_details (configuration);
885 for (vsize line = 0; line < cached_line_details_.size (); line++)
887 Real prev_force = space.force_;
888 space.append_system (cached_line_details_[line]);
889 if ((line > page_first_line)
890 && (isinf (space.force_)
892 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
894 res.systems_per_page_.push_back (line - page_first_line);
895 res.force_.push_back (prev_force);
896 res.penalty_ += cached_line_details_[line-1].page_penalty_;
898 space.resize (page_height (first_page_num + page, false));
900 space.append_system (cached_line_details_[line]);
901 page_first_line = line;
904 if (line == cached_line_details_.size () - 1)
906 /* This is the last line */
907 /* When the last page height was computed, we did not know yet that it
908 * was the last one. If the systems put on it don't fit anymore, the last
909 * system is moved to a new page */
910 space.resize (page_height (first_page_num + page, true));
911 if ((line > page_first_line) && (isinf (space.force_)))
913 res.systems_per_page_.push_back (line - page_first_line);
914 res.force_.push_back (prev_force);
915 /* the last page containing the last line */
916 space.resize (page_height (first_page_num + page + 1, true));
918 space.append_system (cached_line_details_[line]);
919 res.systems_per_page_.push_back (1);
920 res.force_.push_back (space.force_);
921 res.penalty_ += cached_line_details_[line-1].page_penalty_;
922 res.penalty_ += cached_line_details_[line].page_penalty_;
926 res.systems_per_page_.push_back (line + 1 - page_first_line);
927 res.force_.push_back (space.force_);
928 res.penalty_ += cached_line_details_[line].page_penalty_;
932 return finalize_spacing_result (configuration, res);
935 /* Calculate demerits and fix res.systems_per_page_ so that
936 it refers to the original line numbers, not the ones given by compress_lines (). */
938 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
940 if (res.force_.empty ())
943 cache_line_details (configuration);
944 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
947 Real line_penalty = 0;
949 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
951 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
953 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
954 line_penalty += uncompressed_line_details_[i].break_penalty_;
957 for (vsize i = 0; i < res.force_.size (); i++)
959 Real f = res.force_[i];
960 if (isinf (f) && res.systems_per_page_[i] == 1)
966 /* for a while we tried averaging page and line forces across pages instead
967 of summing them, but it caused a problem: if there is a single page
968 with a very bad page force (for example because of a forced page break),
969 the page breaker will put in a _lot_ of pages so that the bad force
970 becomes averaged out over many pages. */
971 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
976 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
977 are by far the most common cases, we have special functions for them.
979 space_systems_on_1_page has a different calling convention than most of the
980 space_systems functions. This is because space_systems_on_1_page is (unlike
981 the other space_systems functions) sometimes called on subsets of a full
984 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
986 Page_spacing space (page_height, page_top_space_);
987 Page_spacing_result ret;
989 for (vsize i = 0; i < lines.size (); i++)
990 space.append_system (lines[i]);
992 ret.systems_per_page_.push_back (lines.size ());
993 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
994 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
996 /* don't do finalize_spacing_result () because we are only an internal function */
1001 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1003 Real page1_height = page_height (first_page_num, false);
1004 Real page2_height = page_height (first_page_num + 1, is_last ());
1005 bool ragged1 = ragged ();
1006 bool ragged2 = ragged () || (is_last () && ragged_last ());
1008 /* if there is a forced break, this reduces to 2 1-page problems */
1009 cache_line_details (configuration);
1010 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1011 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1013 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1014 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1015 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1016 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1018 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1019 p1.force_.push_back (p2.force_[0]);
1020 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1024 vector<Real> page1_force;
1025 vector<Real> page2_force;
1026 Page_spacing page1 (page1_height, page_top_space_);
1027 Page_spacing page2 (page2_height, page_top_space_);
1029 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1030 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1032 /* find the page 1 and page 2 forces for each page-breaking position */
1033 for (vsize i = 0; i < page1_force.size (); i++)
1035 page1.append_system (cached_line_details_[i]);
1036 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1037 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1040 page2_force[page2_force.size () - 1 - i] =
1041 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1043 page2_force[page2_force.size () - 1 - i] = page2.force_;
1046 /* find the position that minimises the sum of the page forces */
1047 vsize best_sys_count = 1;
1048 Real best_demerits = infinity_f;
1049 for (vsize i = 0; i < page1_force.size (); i++)
1051 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1052 Real uneven = 2 * (page1_force[i] - page2_force[i]);
1053 Real dem = uneven * uneven + f
1054 + cached_line_details_[i+1].page_penalty_
1055 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1056 if (dem < best_demerits)
1058 best_demerits = dem;
1059 best_sys_count = i+1;
1063 Page_spacing_result ret;
1064 ret.systems_per_page_.push_back (best_sys_count);
1065 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1066 ret.force_.push_back (page1_force[best_sys_count-1]);
1067 ret.force_.push_back (page2_force[best_sys_count-1]);
1068 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1069 + cached_line_details_.back ().page_penalty_
1070 + cached_line_details_.back ().turn_penalty_;
1072 /* don't do finalize_spacing_result () because we are only an internal function */
1077 Page_breaking::all_lines_stretched (vsize configuration)
1079 cache_line_details (configuration);
1080 for (vsize i = 0; i < cached_line_details_.size (); i++)
1081 if (cached_line_details_[i].force_ < 0)
1087 Page_breaking::Line_division
1088 Page_breaking::current_configuration (vsize configuration_index) const
1090 return current_configurations_[configuration_index];
1094 Page_breaking::is_last () const
1096 return current_end_breakpoint_ == last_break_position ();
1100 Page_breaking::ends_score () const
1102 return breaks_[current_end_breakpoint_].score_ender_;
1106 Page_breaking::last_break_position () const
1108 return breaks_.size () - 1;