2 page-breaking.cc -- implement a superclass and utility
3 functions for use by various page-breaking algorithms
5 source file of the GNU LilyPond music typesetter
7 (c) 2006 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 System_spec::System_spec (Paper_score *ps, int break_count)
26 score_break_count_ = break_count;
29 System_spec::System_spec (Prob *pb)
33 score_break_count_ = 0;
36 System_spec::System_spec ()
40 score_break_count_ = 0;
43 /* for Page_breaking, the start index (when we are dealing with the stuff
44 between a pair of breakpoints) refers to the break_ index of the end of
45 the previous page. So the system index of the start of the current page
46 could either be the same as the end of the previous page or one more than
49 /* Turn a break index into the sys index that starts the next page */
50 vsize Page_breaking::next_system (vsize start) const
52 vsize sys = breaks_[start].sys_;
54 if (sys == VPOS) /* beginning of the piece */
56 if (all_[sys].pscore_ && all_[sys].score_break_count_ > breaks_[start].score_break_)
57 return sys; /* the score overflows the previous page */
58 return sys + 1; /* this page starts with a new sys */
61 Page_breaking::Page_breaking (Paper_book *pb, bool allow_intra_score_breaks)
64 create_system_list (allow_intra_score_breaks);
67 Page_breaking::~Page_breaking ()
71 /* translate indices into breaks_ into start-end parameters for the line breaker */
73 Page_breaking::line_breaker_args (vsize i, vsize *start, vsize *end)
75 assert (all_[i].pscore_);
76 assert (next_system (*start) <= i && i <= breaks_[*end].sys_);
81 if (breaks_[*start].sys_ == i)
82 start_col = breaks_[*start].score_break_;
83 if (breaks_[*end].sys_ == i)
84 end_col = breaks_[*end].score_break_;
86 assert (end_col && (end_col == VPOS || end_col <= all_[breaks_[*end].sys_].score_break_count_));
91 vector<Column_x_positions>
92 Page_breaking::get_line_breaks (vsize i, vsize sys_count, vsize start, vsize end)
94 assert (all_[i].pscore_);
95 line_breaker_args (i, &start, &end);
96 return line_breaking_[i].get_solution (start, end, sys_count);
100 Page_breaking::get_line_details (vsize start_break, vsize end_break, vector<vsize> const &div)
102 vector<Line_details> ret;
104 for (vsize i = next_system (start_break); i <= breaks_[end_break].sys_; i++)
108 vsize div_index = i - next_system (start_break);
109 vsize start = start_break;
110 vsize end = end_break;
112 line_breaker_args (i, &start, &end);
113 vector<Line_details> l = line_breaking_[i].get_details (start, end, div[div_index]);
114 ret.insert (ret.end (), l.begin (), l.end ());
117 ret.push_back (Line_details (all_[i].prob_));
123 Page_breaking::get_min_systems (vsize i, vsize start, vsize end)
125 line_breaker_args (i, &start, &end);
126 return line_breaking_[i].get_min_systems (start, end);
130 Page_breaking::get_max_systems (vsize i, vsize start, vsize end)
132 line_breaker_args (i, &start, &end);
133 return line_breaking_[i].get_max_systems (start, end);
137 Page_breaking::page_height (int page_num, bool last)
139 SCM mod = scm_c_resolve_module ("scm page");
140 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
141 SCM make_page = scm_c_module_lookup (mod, "make-page");
143 calc_height = scm_variable_ref (calc_height);
144 make_page = scm_variable_ref (make_page);
146 SCM page = scm_apply_0 (make_page, scm_list_n (
148 ly_symbol2scm ("page-number"), scm_from_int (page_num),
149 ly_symbol2scm ("is-last"), scm_from_bool (last),
151 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
152 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
156 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
158 SCM module = scm_c_resolve_module ("scm layout-page-layout");
159 SCM make_page = scm_c_module_lookup (module, "make-page-from-systems");
160 make_page = scm_variable_ref (make_page);
161 SCM book = book_->self_scm ();
162 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
163 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
166 for (vsize i = 0; i < lines_per_page.size (); i++)
168 SCM page_num = scm_from_int (i + 1);
169 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
170 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
171 SCM line_count = scm_from_int (lines_per_page[i]);
172 SCM lines = scm_list_head (systems, line_count);
173 SCM page = scm_apply_0 (make_page,
174 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
176 ret = scm_cons (page, ret);
177 systems = scm_list_tail (systems, line_count);
179 return scm_reverse (ret);
182 /* if allow_intra_score_breaks is false, that doesn't necessarily mean that there will
183 be no page turns in the middle of a score, only that we don't give special
184 consideration to any internal part of a score.
186 Corollary: if allow_intra_score_breaks is false, any \pageTurn or \noPageTurn commands
187 in the middle of a score will be ignored.
190 Page_breaking::create_system_list (bool allow_intra_score_breaks)
192 breaks_.push_back (Break_position ());
194 SCM specs = book_->get_system_specs ();
195 for (SCM s = specs; s != SCM_EOL; s = scm_cdr (s))
197 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
199 /* add a breakpoint at the end of the last score, if necessary */
200 if (all_.size () && all_.back ().pscore_)
201 breaks_.push_back (Break_position (all_.size () - 1,
202 all_.back ().score_break_count_));
204 vector<vsize> score_brk;
205 if (allow_intra_score_breaks)
206 score_brk = find_page_break_indices (ps);
208 all_.push_back (System_spec (ps, score_brk.size () + 1));
210 for (vsize i = 0; i < score_brk.size(); i++)
211 breaks_.push_back (Break_position (all_.size () - 1, i + 1));
213 /* include a line breaker at the start of the score */
214 score_brk.insert (score_brk.begin (), 0);
215 line_breaking_.push_back (Constrained_breaking (score_brk));
216 line_breaking_.back ().set_pscore (ps);
220 Prob *pb = unsmob_prob (scm_car (s));
224 // ignore penalties (from break-before) in favour of using \pageBreak at the
226 if (all_.size () && all_.back ().pscore_)
227 breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_));
228 all_.push_back (System_spec (pb));
229 line_breaking_.push_back (Constrained_breaking ());
233 /* add the ending breakpoint */
234 if (all_.back ().pscore_)
235 breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_));
237 breaks_.push_back (Break_position (all_.size () - 1));
241 Page_breaking::find_page_break_indices (Paper_score *pscore)
243 vector<Grob*> all = pscore->root_system ()->columns ();
246 /* we don't include breaks at the beginning and end */
247 for (vsize i = 0; i < all.size () - 1; i++)
248 if (scm_is_symbol (all[i]->get_property ("page-turn-permission")))
255 Page_breaking::calc_system_count_bounds (vsize start, vsize end,
259 for (vsize i = next_system (start); i <= breaks_[end].sys_; i++)
263 min->push_back (get_min_systems (i, start, end));
264 max->push_back (get_max_systems (i, start, end));
274 /* calculate all possible ways of dividing system_count between the System_specs */
276 Page_breaking::divide_systems (vsize system_count,
277 vector<vsize> const &min_sys,
278 vector<vsize> const &max_sys,
279 vector<vector<vsize> > *result,
280 vector<vsize> *cur_division)
282 vsize my_index = cur_division->size ();
283 vsize others_min = 0;
284 vsize others_max = 0;
286 for (vsize i = my_index + 1; i < min_sys.size (); i++)
288 others_min += min_sys[i];
289 others_max += max_sys[i];
291 others_max = min (others_max, system_count);
292 vsize real_min = max (min_sys[my_index], system_count - others_max);
293 vsize real_max = min (max_sys[my_index], system_count - others_min);
295 if (real_min > real_max || real_min <= 0)
297 /* this should never happen within a recursive call. If it happens
298 at all, it means that we were called with an unsolvable problem
299 and we should return an empty result */
300 assert (my_index == 0);
304 for (vsize i = real_min; i <= real_max; i++)
306 cur_division->push_back (i);
307 if (my_index == min_sys.size () - 1)
308 result->push_back (*cur_division);
310 divide_systems (system_count - i, min_sys, max_sys, result, cur_division);
311 cur_division->pop_back ();