2 page-breaking.cc -- implement a superclass and utility
3 functions shared by various page-breaking algorithms
5 source file of the GNU LilyPond music typesetter
7 (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
10 #include "page-breaking.hh"
12 #include "international.hh"
14 #include "output-def.hh"
15 #include "page-spacing.hh"
16 #include "paper-book.hh"
17 #include "paper-score.hh"
18 #include "paper-system.hh"
22 /* for each forbidden page break, merge the systems around it into one
24 static vector<Line_details>
25 compress_lines (const vector<Line_details> &orig)
27 vector<Line_details> ret;
29 for (vsize i = 0; i < orig.size (); i++)
31 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
33 Line_details const &old = ret.back ();
34 Line_details compressed = orig[i];
35 compressed.extent_[DOWN] = old.extent_[DOWN];
36 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
37 compressed.space_ += old.space_;
38 compressed.inverse_hooke_ += old.inverse_hooke_;
40 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
41 compressed.compressed_nontitle_lines_count_ =
42 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
44 compressed.title_ = compressed.title_ && old.title_;
45 ret.back () = compressed;
49 ret.push_back (orig[i]);
50 ret.back ().force_ = 0;
56 /* translate the number of systems-per-page into something meaningful for
57 the uncompressed lines.
60 uncompress_solution (vector<vsize> const &systems_per_page,
61 vector<Line_details> const &compressed)
66 for (vsize i = 0; i < systems_per_page.size (); i++)
68 int compressed_count = 0;
69 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
70 compressed_count += compressed[j].compressed_lines_count_ - 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_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
105 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
106 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
108 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
110 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
111 min_systems_per_page_ = max_systems_per_page_ = 0;
113 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
115 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
116 min_systems_per_page_ = max_systems_per_page_ = 0;
119 create_system_list ();
120 find_chunks_and_breaks (is_break);
123 Page_breaking::~Page_breaking ()
128 Page_breaking::ragged () const
134 Page_breaking::ragged_last () const
140 Page_breaking::systems_per_page () const
142 return systems_per_page_;
146 Page_breaking::max_systems_per_page () const
148 return max_systems_per_page_;
152 Page_breaking::min_systems_per_page () const
154 return min_systems_per_page_;
158 Page_breaking::page_top_space () const
160 return page_top_space_;
164 Page_breaking::system_count () const
166 return system_count_;
170 Page_breaking::too_many_lines (int line_count) const
172 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
176 Page_breaking::too_few_lines (int line_count) const
178 return line_count < min_systems_per_page ();
182 Page_breaking::line_count_penalty (int line_count) const
184 if (too_many_lines (line_count))
185 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
186 if (too_few_lines (line_count))
187 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
193 Page_breaking::line_count_status (int line_count) const
195 if (too_many_lines (line_count))
196 return SYSTEM_COUNT_TOO_MANY;
197 if (too_few_lines (line_count))
198 return SYSTEM_COUNT_TOO_FEW;
200 return SYSTEM_COUNT_OK;
203 /* translate indices into breaks_ into start-end parameters for the line breaker */
205 Page_breaking::line_breaker_args (vsize sys,
206 Break_position const &start,
207 Break_position const &end,
208 vsize *line_breaker_start,
209 vsize *line_breaker_end)
211 assert (system_specs_[sys].pscore_);
212 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
214 if (start.system_spec_index_ == sys)
215 *line_breaker_start = start.score_break_;
217 *line_breaker_start = 0;
219 if (end.system_spec_index_ == sys)
220 *line_breaker_end = end.score_break_;
222 *line_breaker_end = VPOS;
226 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
227 Line_division const &div)
229 vector<Break_position> chunks = chunk_list (start_break, end_break);
230 bool ignore_div = false;
231 if (chunks.size () != div.size () + 1)
233 programming_error ("did not find a valid page breaking configuration");
237 for (vsize i = 0; i + 1 < chunks.size (); i++)
239 vsize sys = next_system (chunks[i]);
240 if (system_specs_[sys].pscore_)
244 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
246 vector<Column_x_positions> pos = ignore_div
247 ? line_breaking_[sys].best_solution (start, end)
248 : line_breaking_[sys].solve (start, end, div[i]);
249 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
255 Page_breaking::systems ()
258 for (vsize sys = 0; sys < system_specs_.size (); sys++)
260 if (system_specs_[sys].pscore_)
262 system_specs_[sys].pscore_->root_system ()
263 ->do_break_substitution_and_fixup_refpoints ();
264 SCM lines = system_specs_[sys].pscore_->root_system ()
265 ->get_broken_system_grobs ();
266 ret = scm_cons (lines, ret);
270 Prob *pb = system_specs_[sys].prob_;
271 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
275 return scm_append (scm_reverse (ret));
279 Page_breaking::page_height (int page_num, bool last) const
281 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
282 SCM mod = scm_c_resolve_module ("scm page");
283 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
284 SCM make_page = scm_c_module_lookup (mod, "make-page");
286 calc_height = scm_variable_ref (calc_height);
287 make_page = scm_variable_ref (make_page);
289 SCM page = scm_apply_0 (make_page, scm_list_n (
291 ly_symbol2scm ("page-number"), scm_from_int (page_num),
292 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
293 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
295 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
296 return scm_to_double (height) - page_top_space_;
300 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
302 Break_position const &pos = breaks_[breakpoint];
304 if (pos.system_spec_index_ == VPOS)
306 if (system_specs_[pos.system_spec_index_].pscore_)
307 return pos.col_->get_property (str);
308 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
312 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
314 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
315 SCM page_module = scm_c_resolve_module ("scm page");
317 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
318 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
319 make_page = scm_variable_ref (make_page);
320 page_stencil = scm_variable_ref (page_stencil);
322 SCM book = book_->self_scm ();
323 int first_page_number
324 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
325 bool last_bookpart = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
327 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
328 if (label_page_table == SCM_UNDEFINED)
329 label_page_table = SCM_EOL;
331 for (vsize i = 0; i < lines_per_page.size (); i++)
333 SCM page_num = scm_from_int (i + first_page_number);
334 bool partbook_last_page = (i == lines_per_page.size () - 1);
335 SCM rag = scm_from_bool (ragged () || ( partbook_last_page && ragged_last ()));
336 SCM line_count = scm_from_int (lines_per_page[i]);
337 SCM lines = scm_list_head (systems, line_count);
338 SCM page = scm_apply_0 (make_page,
339 scm_list_n (book, lines, page_num, rag,
340 scm_from_bool (last_bookpart),
341 scm_from_bool (partbook_last_page),
344 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
346 SCM labels = SCM_EOL;
347 if (Grob * line = unsmob_grob (scm_car (l)))
349 System *system = dynamic_cast<System*> (line);
350 labels = system->get_property ("labels");
352 else if (Prob *prob = unsmob_prob (scm_car (l)))
353 labels = prob->get_property ("labels");
355 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
356 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
360 scm_apply_1 (page_stencil, page, SCM_EOL);
361 ret = scm_cons (page, ret);
362 systems = scm_list_tail (systems, line_count);
364 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
365 ret = scm_reverse (ret);
369 /* The page-turn-page-breaker needs to have a line-breaker between any two
370 columns with non-NULL page-turn-permission.
372 The optimal-breaker needs to have a line-breaker between any two columns
373 with page-break-permission = 'force.
375 By using a grob predicate, we can accommodate both of these uses.
378 Page_breaking::create_system_list ()
380 SCM specs = book_->get_system_specs ();
381 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
383 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
385 SCM system_count = ps->layout ()->c_variable ("system-count");
387 if (scm_is_number (system_count))
388 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
389 scm_vector_to_list (ps->get_paper_systems ()),
392 system_specs_.push_back (System_spec (ps));
396 Prob *pb = unsmob_prob (scm_car (s));
400 system_specs_.push_back (System_spec (pb));
406 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
408 SCM force_sym = ly_symbol2scm ("force");
410 chunks_.push_back (Break_position ());
411 breaks_.push_back (Break_position ());
413 for (vsize i = 0; i < system_specs_.size (); i++)
415 if (system_specs_[i].pscore_)
418 = system_specs_[i].pscore_->root_system ()->used_columns ();
419 vector<vsize> line_breaker_columns;
420 line_breaker_columns.push_back (0);
422 for (vsize j = 1; j < cols.size (); j++)
424 bool last = (j == cols.size () - 1);
425 bool break_point = is_break (cols[j]);
426 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
427 Break_position cur_pos = Break_position (i,
428 line_breaker_columns.size (),
432 if (break_point || (i == system_specs_.size () - 1 && last))
433 breaks_.push_back (cur_pos);
434 if (chunk_end || last)
435 chunks_.push_back (cur_pos);
437 if ((break_point || chunk_end) && !last)
438 line_breaker_columns.push_back (j);
440 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
444 /* TODO: we want some way of applying Break_p to a prob? */
445 if (i == system_specs_.size () - 1)
446 breaks_.push_back (Break_position (i));
448 chunks_.push_back (Break_position (i));
450 /* FIXME: shouldn't we push a Null_breaker or similar dummy
452 line_breaking_.push_back (Constrained_breaking (NULL));
457 vector<Break_position>
458 Page_breaking::chunk_list (vsize start_index, vsize end_index)
460 Break_position start = breaks_[start_index];
461 Break_position end = breaks_[end_index];
464 for (; i < chunks_.size () && chunks_[i] <= start; i++)
467 vector<Break_position> ret;
468 ret.push_back (start);
469 for (; i < chunks_.size () && chunks_[i] < end; i++)
470 ret.push_back (chunks_[i]);
476 Page_breaking::min_system_count (vsize start, vsize end)
478 vector<Break_position> chunks = chunk_list (start, end);
479 Line_division div = system_count_bounds (chunks, true);
482 for (vsize i = 0; i < div.size (); i++)
488 Page_breaking::max_system_count (vsize start, vsize end)
490 vector<Break_position> chunks = chunk_list (start, end);
491 Line_division div = system_count_bounds (chunks, false);
494 for (vsize i = 0; i < div.size (); i++)
499 Page_breaking::Line_division
500 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
503 assert (chunks.size () >= 2);
506 ret.resize (chunks.size () - 1, 1);
508 for (vsize i = 0; i + 1 < chunks.size (); i++)
510 vsize sys = next_system (chunks[i]);
511 if (system_specs_[sys].pscore_)
515 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
517 ? line_breaking_[sys].min_system_count (start, end)
518 : line_breaking_[sys].max_system_count (start, end);
526 Page_breaking::set_current_breakpoints (vsize start,
529 Line_division lower_bound,
530 Line_division upper_bound)
532 system_count_ = system_count;
533 current_chunks_ = chunk_list (start, end);
534 current_start_breakpoint_ = start;
535 current_end_breakpoint_ = end;
536 clear_line_details_cache ();
538 if (!lower_bound.size ())
539 lower_bound = system_count_bounds (current_chunks_, true);
540 if (!upper_bound.size ())
541 upper_bound = system_count_bounds (current_chunks_, false);
543 assert (lower_bound.size () == current_chunks_.size () - 1);
544 assert (upper_bound.size () == current_chunks_.size () - 1);
546 Line_division work_in_progress;
547 current_configurations_.clear ();
548 line_divisions_rec (system_count,
553 /* we only consider a constant number of configurations. Otherwise,
554 this becomes slow when there are many small scores. The constant
555 5 is somewhat arbitrary. */
556 if (current_configurations_.size () > 5)
558 vector<pair<Real,vsize> > dems_and_indices;
560 for (vsize i = 0; i < current_configurations_.size (); i++)
562 cache_line_details (i);
564 for (vsize j = 0; j < cached_line_details_.size (); j++)
565 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
566 + cached_line_details_[j].break_penalty_;
568 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
570 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
572 vector<Line_division> best_5_configurations;
573 for (vsize i = 0; i < 5; i++)
574 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
576 clear_line_details_cache ();
577 current_configurations_ = best_5_configurations;
582 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
584 current_chunks_ = chunk_list (start, end);
585 current_start_breakpoint_ = start;
586 current_end_breakpoint_ = end;
587 clear_line_details_cache ();
591 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
593 vsize sys = next_system (current_chunks_[i]);
594 if (system_specs_[sys].pscore_)
596 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
597 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
602 system_count_ += div.back ();
604 current_configurations_.clear ();
605 current_configurations_.push_back (div);
609 Page_breaking::current_configuration_count () const
611 return current_configurations_.size ();
615 Page_breaking::cache_line_details (vsize configuration_index)
617 if (cached_configuration_index_ != configuration_index)
619 cached_configuration_index_ = configuration_index;
620 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
621 if (!scm_is_number (padding_scm))
622 padding_scm = book_->paper_->c_variable ("between-system-padding");
623 Real padding = robust_scm2double (padding_scm, 0.0);
625 Line_division &div = current_configurations_[configuration_index];
626 uncompressed_line_details_.clear ();
627 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
629 vsize sys = next_system (current_chunks_[i]);
630 if (system_specs_[sys].pscore_)
634 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
636 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
637 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
641 assert (div[i] == 1);
642 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
643 uncompressed_line_details_.back ().padding_ =
644 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
648 cached_line_details_ = compress_lines (uncompressed_line_details_);
653 Page_breaking::clear_line_details_cache ()
655 cached_configuration_index_ = VPOS;
656 cached_line_details_.clear ();
657 uncompressed_line_details_.clear ();
661 Page_breaking::line_divisions_rec (vsize system_count,
662 Line_division const &min_sys,
663 Line_division const &max_sys,
664 Line_division *cur_division)
666 vsize my_index = cur_division->size ();
667 vsize others_min = 0;
668 vsize others_max = 0;
670 for (vsize i = my_index + 1; i < min_sys.size (); i++)
672 others_min += min_sys[i];
673 others_max += max_sys[i];
675 others_max = min (others_max, system_count);
676 vsize real_min = max (min_sys[my_index], system_count - others_max);
677 vsize real_max = min (max_sys[my_index], system_count - others_min);
679 if (real_min > real_max || real_min <= 0)
681 /* this should never happen within a recursive call. If it happens
682 at all, it means that we were called with an unsolvable problem
683 and we should return an empty result */
684 assert (my_index == 0);
688 for (vsize i = real_min; i <= real_max; i++)
690 cur_division->push_back (i);
691 if (my_index == min_sys.size () - 1)
692 current_configurations_.push_back (*cur_division);
694 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
695 cur_division->pop_back ();
700 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
703 Real cur_rod_height = 0;
704 Real cur_spring_height = 0;
705 Real cur_page_height = page_height (first_page_num, false);
708 cache_line_details (configuration);
709 for (vsize i = 0; i < cached_line_details_.size (); i++)
711 Real ext_len = cached_line_details_[i].extent_.length ();
712 Real next_rod_height = cur_rod_height + ext_len
713 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
714 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
715 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
716 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
718 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
719 || too_many_lines (next_line_count)
721 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
723 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
724 cur_rod_height = ext_len;
725 cur_spring_height = cached_line_details_[i].space_;
726 cur_page_height = page_height (first_page_num + ret, false);
731 cur_rod_height = next_rod_height;
732 cur_spring_height = next_spring_height;
733 line_count = next_line_count;
737 /* there are two potential problems with the last page (because we didn't know
738 it was the last page until after we managed to fit all the systems to it):
739 - we are ragged-last but the last page has a compressed spring
740 - the value returned by page_height (num, true) is smaller than the
741 value returned by page_height (num, false) and it causes the page not to
744 In either case, we just need to add one more page. This is because the last
745 line will always fit on the extra page and by adding one more page to the
746 end, the previous page is no longer the last page, so our previous
747 calculations that treated it as a non-last page were ok.
750 cur_page_height = page_height (first_page_num + ret - 1, true);
751 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
752 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
753 && cur_height > cur_page_height
754 /* don't increase the page count if the last page had only one system */
755 && cur_rod_height > cached_line_details_.back ().extent_.length ())
758 assert (ret <= cached_line_details_.size ());
762 // If systems_per_page_ is positive, we don't really try to space on N pages;
763 // we just put the requested number of systems on each page and penalize
764 // if the result doesn't have N pages.
766 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
768 Page_spacing_result ret;
770 if (systems_per_page_ > 0)
772 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
773 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
777 cache_line_details (configuration);
778 bool valid_n = (n >= min_page_count (configuration, first_page_num)
779 && n <= cached_line_details_.size ());
782 programming_error ("number of pages is out of bounds");
784 if (n == 1 && valid_n)
785 ret = space_systems_on_1_page (cached_line_details_,
786 page_height (first_page_num, is_last ()),
787 ragged () || (is_last () && ragged_last ()));
788 else if (n == 2 && valid_n)
789 ret = space_systems_on_2_pages (configuration, first_page_num);
792 Page_spacer ps (cached_line_details_, first_page_num, this);
796 return finalize_spacing_result (configuration, ret);
800 Page_breaking::blank_page_penalty () const
805 penalty_sym = ly_symbol2scm ("blank-last-page-force");
806 else if (ends_score ())
807 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
809 penalty_sym = ly_symbol2scm ("blank-page-force");
811 Break_position const &pos = breaks_[current_end_breakpoint_];
812 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
813 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
815 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
818 // If systems_per_page_ is positive, we don't really try to space on N
819 // or N+1 pages; see the comment to space_systems_on_n_pages.
821 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
823 Page_spacing_result n_res;
824 Page_spacing_result m_res;
826 if (systems_per_page_ > 0)
828 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
829 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
833 cache_line_details (configuration);
834 vsize min_p_count = min_page_count (configuration, first_page_num);
835 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
838 programming_error ("both page counts are out of bounds");
840 if (n == 1 && valid_n)
842 bool rag = ragged () || (is_last () && ragged_last ());
843 Real height = page_height (first_page_num, is_last ());
845 if (1 >= min_p_count)
846 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
847 if (1 < cached_line_details_.size ())
848 m_res = space_systems_on_2_pages (configuration, first_page_num);
852 Page_spacer ps (cached_line_details_, first_page_num, this);
854 if (n >= min_p_count || !valid_n)
855 n_res = ps.solve (n);
856 if (n < cached_line_details_.size () || !valid_n)
857 m_res = ps.solve (n+1);
860 m_res = finalize_spacing_result (configuration, m_res);
861 n_res = finalize_spacing_result (configuration, n_res);
863 Real penalty = blank_page_penalty ();
864 n_res.demerits_ += penalty;
866 if (n_res.force_.size ())
867 n_res.force_.back () += penalty;
869 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
873 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
875 vsize min_p_count = min_page_count (configuration, first_page_num);
876 Real odd_pages_penalty = blank_page_penalty ();
878 cache_line_details (configuration);
879 Page_spacer ps (cached_line_details_, first_page_num, this);
880 Page_spacing_result best = ps.solve (min_p_count);
881 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
882 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
884 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
886 Page_spacing_result cur = ps.solve (i);
887 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
888 if (cur.demerits_ < best.demerits_)
892 return finalize_spacing_result (configuration, best);
896 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
897 vsize first_page_num)
899 Page_spacing_result res;
900 Page_spacing space (page_height (first_page_num, false), page_top_space_);
903 vsize page_first_line = 0;
905 cache_line_details (configuration);
906 while (line < cached_line_details_.size ())
910 space.resize (page_height (first_page_num + page, false));
912 int system_count_on_this_page = 0;
913 while (system_count_on_this_page < systems_per_page_
914 && line < cached_line_details_.size ())
916 Line_details const &cur_line = cached_line_details_[line];
917 space.append_system (cur_line);
918 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
921 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
925 res.systems_per_page_.push_back (line - page_first_line);
927 // Don't say that the force is infinite even if it is: if we were told to
928 // put a certain number of systems on a page then we will, even if it's bad.
929 res.force_.push_back (min (space.force_, BAD_SPACING_PENALTY));
930 res.penalty_ += cached_line_details_[line-1].page_penalty_;
931 page_first_line = line;
934 /* Recalculate forces for the last page because we know now that is
935 really the last page. */
936 space.resize (page_height (first_page_num + page, true));
937 res.force_.back () = min(space.force_, BAD_SPACING_PENALTY);
938 return finalize_spacing_result (configuration, res);
942 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
944 // TODO: add support for min/max-systems-per-page.
945 Page_spacing_result res;
947 vsize page_first_line = 0;
948 Page_spacing space (page_height (first_page_num, false), page_top_space_);
950 cache_line_details (configuration);
951 for (vsize line = 0; line < cached_line_details_.size (); line++)
953 Real prev_force = space.force_;
954 space.append_system (cached_line_details_[line]);
955 if ((line > page_first_line)
956 && (isinf (space.force_)
958 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
960 res.systems_per_page_.push_back (line - page_first_line);
961 res.force_.push_back (prev_force);
962 res.penalty_ += cached_line_details_[line-1].page_penalty_;
964 space.resize (page_height (first_page_num + page, false));
966 space.append_system (cached_line_details_[line]);
967 page_first_line = line;
970 if (line == cached_line_details_.size () - 1)
972 /* This is the last line */
973 /* When the last page height was computed, we did not know yet that it
974 * was the last one. If the systems put on it don't fit anymore, the last
975 * system is moved to a new page */
976 space.resize (page_height (first_page_num + page, true));
977 if ((line > page_first_line) && (isinf (space.force_)))
979 res.systems_per_page_.push_back (line - page_first_line);
980 res.force_.push_back (prev_force);
981 /* the last page containing the last line */
982 space.resize (page_height (first_page_num + page + 1, true));
984 space.append_system (cached_line_details_[line]);
985 res.systems_per_page_.push_back (1);
986 res.force_.push_back (space.force_);
987 res.penalty_ += cached_line_details_[line-1].page_penalty_;
988 res.penalty_ += cached_line_details_[line].page_penalty_;
992 res.systems_per_page_.push_back (line + 1 - page_first_line);
993 res.force_.push_back (space.force_);
994 res.penalty_ += cached_line_details_[line].page_penalty_;
998 return finalize_spacing_result (configuration, res);
1001 /* Calculate demerits and fix res.systems_per_page_ so that
1002 it refers to the original line numbers, not the ones given by compress_lines (). */
1004 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1006 if (res.force_.empty ())
1009 cache_line_details (configuration);
1010 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1012 Real line_force = 0;
1013 Real line_penalty = 0;
1014 Real page_demerits = res.penalty_;
1015 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1017 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1019 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1020 line_penalty += uncompressed_line_details_[i].break_penalty_;
1023 for (vsize i = 0; i < res.force_.size (); i++)
1025 Real f = res.force_[i];
1027 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1030 /* for a while we tried averaging page and line forces across pages instead
1031 of summing them, but it caused a problem: if there is a single page
1032 with a very bad page force (for example because of a forced page break),
1033 the page breaker will put in a _lot_ of pages so that the bad force
1034 becomes averaged out over many pages. */
1035 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1040 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1041 are by far the most common cases, we have special functions for them.
1043 space_systems_on_1_page has a different calling convention than most of the
1044 space_systems functions. This is because space_systems_on_1_page is (unlike
1045 the other space_systems functions) sometimes called on subsets of a full
1048 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1050 Page_spacing space (page_height, page_top_space_);
1051 Page_spacing_result ret;
1054 for (vsize i = 0; i < lines.size (); i++)
1056 space.append_system (lines[i]);
1057 line_count += lines[i].compressed_nontitle_lines_count_;
1060 ret.systems_per_page_.push_back (lines.size ());
1061 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1062 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1063 ret.system_count_status_ |= line_count_status (line_count);
1065 /* don't do finalize_spacing_result () because we are only an internal function */
1070 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1072 Real page1_height = page_height (first_page_num, false);
1073 Real page2_height = page_height (first_page_num + 1, is_last ());
1074 bool ragged1 = ragged ();
1075 bool ragged2 = ragged () || (is_last () && ragged_last ());
1077 /* if there is a forced break, this reduces to 2 1-page problems */
1078 cache_line_details (configuration);
1079 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1080 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1082 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1083 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1084 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1085 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1087 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1088 p1.force_.push_back (p2.force_[0]);
1089 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1093 vector<Real> page1_force;
1094 vector<Real> page2_force;
1096 // page1_penalty and page2_penalty store the penalties based
1097 // on min-systems-per-page and max-systems-per-page.
1098 vector<Real> page1_penalty;
1099 vector<Real> page2_penalty;
1101 // page1_status and page2_status keep track of whether the min-systems-per-page
1102 // and max-systems-per-page constraints are satisfied.
1103 vector<int> page1_status;
1104 vector<int> page2_status;
1106 Page_spacing page1 (page1_height, page_top_space_);
1107 Page_spacing page2 (page2_height, page_top_space_);
1108 int page1_line_count = 0;
1109 int page2_line_count = 0;
1111 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1112 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1113 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1114 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1115 page1_status.resize (cached_line_details_.size () - 1, 0);
1116 page2_status.resize (cached_line_details_.size () - 1, 0);
1118 /* find the page 1 and page 2 forces for each page-breaking position */
1119 for (vsize i = 0; i < page1_force.size (); i++)
1121 page1.append_system (cached_line_details_[i]);
1122 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1123 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1124 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1126 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1127 page1_penalty[i] = line_count_penalty (page1_line_count);
1128 page1_status[i] = line_count_status (page1_line_count);
1131 page2_force[page2_force.size () - 1 - i] =
1132 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1134 page2_force[page2_force.size () - 1 - i] = page2.force_;
1135 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1136 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1139 /* find the position that minimises the sum of the page forces */
1140 vsize best_sys_count = 1;
1141 Real best_demerits = infinity_f;
1142 for (vsize i = 0; i < page1_force.size (); i++)
1144 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1146 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1147 // constraints. That is, we penalize harshly when they don't happen
1148 // but we don't completely reject.
1150 + page1_penalty[i] + page2_penalty[i]
1151 + cached_line_details_[i+1].page_penalty_
1152 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1153 if (dem < best_demerits)
1155 best_demerits = dem;
1156 best_sys_count = i+1;
1160 Page_spacing_result ret;
1161 ret.systems_per_page_.push_back (best_sys_count);
1162 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1163 ret.force_.push_back (page1_force[best_sys_count-1]);
1164 ret.force_.push_back (page2_force[best_sys_count-1]);
1165 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1166 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1167 + cached_line_details_.back ().page_penalty_
1168 + cached_line_details_.back ().turn_penalty_
1169 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1171 /* don't do finalize_spacing_result () because we are only an internal function */
1176 Page_breaking::all_lines_stretched (vsize configuration)
1178 cache_line_details (configuration);
1179 for (vsize i = 0; i < cached_line_details_.size (); i++)
1180 if (cached_line_details_[i].force_ < 0)
1186 Page_breaking::Line_division
1187 Page_breaking::current_configuration (vsize configuration_index) const
1189 return current_configurations_[configuration_index];
1193 Page_breaking::is_last () const
1195 return current_end_breakpoint_ == last_break_position ();
1199 Page_breaking::ends_score () const
1201 return breaks_[current_end_breakpoint_].score_ender_;
1205 Page_breaking::last_break_position () const
1207 return breaks_.size () - 1;