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 Page_breaking, the start index (when we are dealing with the stuff
23 between a pair of breakpoints) refers to the break_ index of the end of
24 the previous page. So the system index of the start of the current page
25 could either be the same as the end of the previous page or one more than
28 /* Turn a break index into the sys index that starts the next page */
30 Page_breaking::next_system (Break_position const &break_pos) const
32 vsize sys = break_pos.sys_;
34 if (sys == VPOS) /* beginning of the book */
36 if (all_[sys].pscore_ && !break_pos.score_ender_)
37 return sys; /* the score overflows the previous page */
38 return sys + 1; /* this page starts with a new sys */
41 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
44 create_system_list ();
45 find_chunks_and_breaks (is_break);
48 Page_breaking::~Page_breaking ()
52 /* translate indices into breaks_ into start-end parameters for the line breaker */
54 Page_breaking::line_breaker_args (vsize sys,
55 Break_position const &start,
56 Break_position const &end,
57 vsize *line_breaker_start,
58 vsize *line_breaker_end)
60 assert (all_[sys].pscore_);
61 assert (next_system (start) <= sys && sys <= end.sys_);
63 if (start.sys_ == sys)
64 *line_breaker_start = start.score_break_;
66 *line_breaker_start = 0;
69 *line_breaker_end = end.score_break_;
71 *line_breaker_end = VPOS;
75 Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div)
77 vector<Break_position> chunks = chunk_list (start_break, end_break);
78 bool ignore_div = false;
79 if (chunks.size () != div.size () + 1)
81 programming_error ("did not find a valid page breaking configuration");
86 for (vsize i = 0; i + 1 < chunks.size (); i++)
88 vsize sys = next_system (chunks[i]);
89 if (all_[sys].pscore_)
93 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
95 vector<Column_x_positions> pos = ignore_div
96 ? line_breaking_[sys].get_best_solution (start, end)
97 : line_breaking_[sys].get_solution (start, end, div[i]);
98 all_[sys].pscore_->root_system ()->break_into_pieces (pos);
104 Page_breaking::systems ()
107 for (vsize sys = 0; sys < all_.size (); sys++)
109 if (all_[sys].pscore_)
111 SCM lines = all_[sys].pscore_->root_system ()->get_paper_systems ();
112 ret = scm_cons (scm_vector_to_list (lines), ret);
116 Prob *pb = all_[sys].prob_;
117 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
121 return scm_append (scm_reverse (ret));
125 Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
127 vector<Break_position> chunks = chunk_list (start_break, end_break);
128 vector<Line_details> ret;
129 assert (chunks.size () == div.size () + 1);
131 for (vsize i = 0; i + 1 < chunks.size (); i++)
133 vsize sys = next_system (chunks[i]);
134 if (all_[sys].pscore_)
138 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
140 vector<Line_details> details = line_breaking_[sys].get_details (start, end, div[i]);
141 ret.insert (ret.end (), details.begin (), details.end ());
145 assert (div[i] == 1);
146 ret.push_back (Line_details (all_[sys].prob_));
153 Page_breaking::page_height (int page_num, bool last)
155 SCM mod = scm_c_resolve_module ("scm page");
156 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
157 SCM make_page = scm_c_module_lookup (mod, "make-page");
159 calc_height = scm_variable_ref (calc_height);
160 make_page = scm_variable_ref (make_page);
162 SCM page = scm_apply_0 (make_page, scm_list_n (
164 ly_symbol2scm ("page-number"), scm_from_int (page_num),
165 ly_symbol2scm ("is-last"), scm_from_bool (last),
167 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
168 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
172 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
174 Break_position const &pos = breaks_[breakpoint];
176 if (pos.sys_ == VPOS)
178 if (all_[pos.sys_].pscore_)
179 return pos.col_->get_property (str);
180 return all_[pos.sys_].prob_->get_property (str);
184 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
186 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
187 SCM page_module = scm_c_resolve_module ("scm page");
189 SCM make_page = scm_c_module_lookup (layout_module, "make-page-from-systems");
190 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
191 make_page = scm_variable_ref (make_page);
192 page_stencil = scm_variable_ref (page_stencil);
194 SCM book = book_->self_scm ();
195 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
196 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
197 int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
200 for (vsize i = 0; i < lines_per_page.size (); i++)
202 SCM page_num = scm_from_int (i + first_page_number);
203 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
204 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
205 SCM line_count = scm_from_int (lines_per_page[i]);
206 SCM lines = scm_list_head (systems, line_count);
207 SCM page = scm_apply_0 (make_page,
208 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
210 scm_apply_1 (page_stencil, page, SCM_EOL);
211 ret = scm_cons (page, ret);
212 systems = scm_list_tail (systems, line_count);
214 ret = scm_reverse (ret);
218 /* The page-turn-page-breaker needs to have a line-breaker between any two
219 columns with non-NULL page-turn-permission.
221 The optimal-breaker needs to have a line-breaker between any two columns
222 with page-break-permission = 'force.
224 By using a grob predicate, we can accommodate both of these uses.
227 Page_breaking::create_system_list ()
229 SCM specs = book_->get_system_specs ();
230 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
232 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
234 SCM system_count = ps->layout ()->c_variable ("system-count");
236 if (scm_is_number (system_count))
237 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
238 scm_vector_to_list (ps->get_paper_systems ()),
241 all_.push_back (System_spec (ps));
245 Prob *pb = unsmob_prob (scm_car (s));
249 all_.push_back (System_spec (pb));
255 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
257 SCM force_sym = ly_symbol2scm ("force");
259 chunks_.push_back (Break_position ());
260 breaks_.push_back (Break_position ());
262 for (vsize i = 0; i < all_.size (); i++)
266 vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
267 vector<vsize> line_breaker_columns;
268 line_breaker_columns.push_back (0);
270 for (vsize j = 1; j < cols.size (); j++)
272 bool last = j == cols.size () - 1;
273 bool break_point = is_break (cols[j]);
274 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
275 Break_position cur_pos = Break_position (i,
276 line_breaker_columns.size (),
280 if (break_point || (i == all_.size () - 1 && last))
281 breaks_.push_back (cur_pos);
282 if (chunk_end || last)
283 chunks_.push_back (cur_pos);
285 if ((break_point || chunk_end) && !last)
286 line_breaker_columns.push_back (j);
288 line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
292 /* TODO: we want some way of applying Break_p to a prob? */
293 if (i == all_.size () - 1)
294 breaks_.push_back (Break_position (i));
296 chunks_.push_back (Break_position (i));
297 line_breaking_.push_back (Constrained_breaking (NULL));
302 vector<Break_position>
303 Page_breaking::chunk_list (vsize start_index, vsize end_index)
305 Break_position start = breaks_[start_index];
306 Break_position end = breaks_[end_index];
309 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
312 vector<Break_position> ret;
313 ret.push_back (start);
314 for (; i < chunks_.size () && chunks_[i] < end; i++)
315 ret.push_back (chunks_[i]);
321 Page_breaking::min_system_count (vsize start, vsize end)
323 vector<Break_position> chunks = chunk_list (start, end);
324 Line_division div = system_count_bounds (chunks, true);
327 for (vsize i = 0; i < div.size (); i++)
333 Page_breaking::max_system_count (vsize start, vsize end)
335 vector<Break_position> chunks = chunk_list (start, end);
336 Line_division div = system_count_bounds (chunks, false);
339 for (vsize i = 0; i < div.size (); i++)
344 Page_breaking::Line_division
345 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
347 assert (chunks.size () >= 2);
350 ret.resize (chunks.size () - 1, 1);
352 for (vsize i = 0; i + 1 < chunks.size (); i++)
354 vsize sys = next_system (chunks[i]);
355 if (all_[sys].pscore_)
359 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
361 ? line_breaking_[sys].get_min_systems (start, end)
362 : line_breaking_[sys].get_max_systems (start, end);
369 vector<Page_breaking::Line_division>
370 Page_breaking::line_divisions (vsize start,
373 Line_division lower_bound,
374 Line_division upper_bound)
376 vector<Break_position> chunks = chunk_list (start, end);
378 if (!lower_bound.size ())
379 lower_bound = system_count_bounds (chunks, true);
380 if (!upper_bound.size ())
381 upper_bound = system_count_bounds (chunks, false);
383 assert (lower_bound.size () == chunks.size () - 1);
384 assert (upper_bound.size () == chunks.size () - 1);
386 vector<Line_division> ret;
387 Line_division work_in_progress;
389 line_divisions_rec (system_count,
398 Page_breaking::line_divisions_rec (vsize system_count,
399 Line_division const &min_sys,
400 Line_division const &max_sys,
401 vector<Line_division > *result,
402 Line_division *cur_division)
404 vsize my_index = cur_division->size ();
405 vsize others_min = 0;
406 vsize others_max = 0;
408 for (vsize i = my_index + 1; i < min_sys.size (); i++)
410 others_min += min_sys[i];
411 others_max += max_sys[i];
413 others_max = min (others_max, system_count);
414 vsize real_min = max (min_sys[my_index], system_count - others_max);
415 vsize real_max = min (max_sys[my_index], system_count - others_min);
417 if (real_min > real_max || real_min <= 0)
419 /* this should never happen within a recursive call. If it happens
420 at all, it means that we were called with an unsolvable problem
421 and we should return an empty result */
422 assert (my_index == 0);
426 for (vsize i = real_min; i <= real_max; i++)
428 cur_division->push_back (i);
429 if (my_index == min_sys.size () - 1)
430 result->push_back (*cur_division);
432 line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
433 cur_division->pop_back ();