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 all_[sys].pscore_->root_system ()->do_break_substitution_and_fixup_refpoints ();
112 SCM lines = all_[sys].pscore_->root_system ()->get_broken_system_grobs ();
113 ret = scm_cons (lines, ret);
117 Prob *pb = all_[sys].prob_;
118 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
122 return scm_append (scm_reverse (ret));
126 Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
128 vector<Break_position> chunks = chunk_list (start_break, end_break);
129 vector<Line_details> ret;
130 assert (chunks.size () == div.size () + 1);
132 for (vsize i = 0; i + 1 < chunks.size (); i++)
134 vsize sys = next_system (chunks[i]);
135 if (all_[sys].pscore_)
139 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
141 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
142 ret.insert (ret.end (), details.begin (), details.end ());
146 assert (div[i] == 1);
147 ret.push_back (Line_details (all_[sys].prob_));
154 Page_breaking::page_height (int page_num, bool last)
156 SCM mod = scm_c_resolve_module ("scm page");
157 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
158 SCM make_page = scm_c_module_lookup (mod, "make-page");
160 calc_height = scm_variable_ref (calc_height);
161 make_page = scm_variable_ref (make_page);
163 SCM page = scm_apply_0 (make_page, scm_list_n (
165 ly_symbol2scm ("page-number"), scm_from_int (page_num),
166 ly_symbol2scm ("is-last"), scm_from_bool (last),
168 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
169 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
173 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
175 Break_position const &pos = breaks_[breakpoint];
177 if (pos.sys_ == VPOS)
179 if (all_[pos.sys_].pscore_)
180 return pos.col_->get_property (str);
181 return all_[pos.sys_].prob_->get_property (str);
185 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
187 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
188 SCM page_module = scm_c_resolve_module ("scm page");
190 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
191 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
192 make_page = scm_variable_ref (make_page);
193 page_stencil = scm_variable_ref (page_stencil);
195 SCM book = book_->self_scm ();
196 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
197 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
198 int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
201 for (vsize i = 0; i < lines_per_page.size (); i++)
203 SCM page_num = scm_from_int (i + first_page_number);
204 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
205 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
206 SCM line_count = scm_from_int (lines_per_page[i]);
207 SCM lines = scm_list_head (systems, line_count);
208 SCM page = scm_apply_0 (make_page,
209 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
211 scm_apply_1 (page_stencil, page, SCM_EOL);
212 ret = scm_cons (page, ret);
213 systems = scm_list_tail (systems, line_count);
215 ret = scm_reverse (ret);
219 /* The page-turn-page-breaker needs to have a line-breaker between any two
220 columns with non-NULL page-turn-permission.
222 The optimal-breaker needs to have a line-breaker between any two columns
223 with page-break-permission = 'force.
225 By using a grob predicate, we can accommodate both of these uses.
228 Page_breaking::create_system_list ()
230 SCM specs = book_->get_system_specs ();
231 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
233 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
235 SCM system_count = ps->layout ()->c_variable ("system-count");
237 if (scm_is_number (system_count))
238 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
239 scm_vector_to_list (ps->get_paper_systems ()),
242 all_.push_back (System_spec (ps));
246 Prob *pb = unsmob_prob (scm_car (s));
250 all_.push_back (System_spec (pb));
256 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
258 SCM force_sym = ly_symbol2scm ("force");
260 chunks_.push_back (Break_position ());
261 breaks_.push_back (Break_position ());
263 for (vsize i = 0; i < all_.size (); i++)
267 vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
268 vector<vsize> line_breaker_columns;
269 line_breaker_columns.push_back (0);
271 for (vsize j = 1; j < cols.size (); j++)
273 bool last = j == cols.size () - 1;
274 bool break_point = is_break (cols[j]);
275 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
276 Break_position cur_pos = Break_position (i,
277 line_breaker_columns.size (),
281 if (break_point || (i == all_.size () - 1 && last))
282 breaks_.push_back (cur_pos);
283 if (chunk_end || last)
284 chunks_.push_back (cur_pos);
286 if ((break_point || chunk_end) && !last)
287 line_breaker_columns.push_back (j);
289 line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
293 /* TODO: we want some way of applying Break_p to a prob? */
294 if (i == all_.size () - 1)
295 breaks_.push_back (Break_position (i));
297 chunks_.push_back (Break_position (i));
298 line_breaking_.push_back (Constrained_breaking (NULL));
303 vector<Break_position>
304 Page_breaking::chunk_list (vsize start_index, vsize end_index)
306 Break_position start = breaks_[start_index];
307 Break_position end = breaks_[end_index];
310 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
313 vector<Break_position> ret;
314 ret.push_back (start);
315 for (; i < chunks_.size () && chunks_[i] < end; i++)
316 ret.push_back (chunks_[i]);
322 Page_breaking::min_system_count (vsize start, vsize end)
324 vector<Break_position> chunks = chunk_list (start, end);
325 Line_division div = system_count_bounds (chunks, true);
328 for (vsize i = 0; i < div.size (); i++)
334 Page_breaking::max_system_count (vsize start, vsize end)
336 vector<Break_position> chunks = chunk_list (start, end);
337 Line_division div = system_count_bounds (chunks, false);
340 for (vsize i = 0; i < div.size (); i++)
345 Page_breaking::Line_division
346 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
348 assert (chunks.size () >= 2);
351 ret.resize (chunks.size () - 1, 1);
353 for (vsize i = 0; i + 1 < chunks.size (); i++)
355 vsize sys = next_system (chunks[i]);
356 if (all_[sys].pscore_)
360 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
362 ? line_breaking_[sys].min_system_count (start, end)
363 : line_breaking_[sys].max_system_count (start, end);
370 vector<Page_breaking::Line_division>
371 Page_breaking::line_divisions (vsize start,
374 Line_division lower_bound,
375 Line_division upper_bound)
377 vector<Break_position> chunks = chunk_list (start, end);
379 if (!lower_bound.size ())
380 lower_bound = system_count_bounds (chunks, true);
381 if (!upper_bound.size ())
382 upper_bound = system_count_bounds (chunks, false);
384 assert (lower_bound.size () == chunks.size () - 1);
385 assert (upper_bound.size () == chunks.size () - 1);
387 vector<Line_division> ret;
388 Line_division work_in_progress;
390 line_divisions_rec (system_count,
399 Page_breaking::line_divisions_rec (vsize system_count,
400 Line_division const &min_sys,
401 Line_division const &max_sys,
402 vector<Line_division > *result,
403 Line_division *cur_division)
405 vsize my_index = cur_division->size ();
406 vsize others_min = 0;
407 vsize others_max = 0;
409 for (vsize i = my_index + 1; i < min_sys.size (); i++)
411 others_min += min_sys[i];
412 others_max += max_sys[i];
414 others_max = min (others_max, system_count);
415 vsize real_min = max (min_sys[my_index], system_count - others_max);
416 vsize real_max = min (max_sys[my_index], system_count - others_min);
418 if (real_min > real_max || real_min <= 0)
420 /* this should never happen within a recursive call. If it happens
421 at all, it means that we were called with an unsolvable problem
422 and we should return an empty result */
423 assert (my_index == 0);
427 for (vsize i = real_min; i <= real_max; i++)
429 cur_division->push_back (i);
430 if (my_index == min_sys.size () - 1)
431 result->push_back (*cur_division);
433 line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
434 cur_division->pop_back ();