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 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 assert (chunks.size () == div.size () + 1);
80 for (vsize i = 0; i < chunks.size () - 1; i++)
82 vsize sys = next_system (chunks[i]);
83 if (all_[sys].pscore_)
87 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
89 vector<Column_x_positions> pos = line_breaking_[sys].get_solution (start, end, div[i]);
90 all_[sys].pscore_->root_system ()->break_into_pieces (pos);
96 Page_breaking::systems ()
99 for (vsize sys = 0; sys < all_.size (); sys++)
101 if (all_[sys].pscore_)
103 SCM lines = all_[sys].pscore_->root_system ()->get_paper_systems ();
104 ret = scm_cons (scm_vector_to_list (lines), ret);
108 Prob *pb = all_[sys].prob_;
109 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
113 return scm_append (scm_reverse (ret));
117 Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
119 vector<Break_position> chunks = chunk_list (start_break, end_break);
120 vector<Line_details> ret;
121 assert (chunks.size () == div.size () + 1);
123 for (vsize i = 0; i < chunks.size () - 1; i++)
125 vsize sys = next_system (chunks[i]);
126 if (all_[sys].pscore_)
130 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
132 vector<Line_details> details = line_breaking_[sys].get_details (start, end, div[i]);
133 ret.insert (ret.end (), details.begin (), details.end ());
137 assert (div[i] == 1);
138 ret.push_back (Line_details (all_[sys].prob_));
145 Page_breaking::page_height (int page_num, bool last)
147 SCM mod = scm_c_resolve_module ("scm page");
148 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
149 SCM make_page = scm_c_module_lookup (mod, "make-page");
151 calc_height = scm_variable_ref (calc_height);
152 make_page = scm_variable_ref (make_page);
154 SCM page = scm_apply_0 (make_page, scm_list_n (
156 ly_symbol2scm ("page-number"), scm_from_int (page_num),
157 ly_symbol2scm ("is-last"), scm_from_bool (last),
159 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
160 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
164 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
166 Break_position const &pos = breaks_[breakpoint];
168 if (pos.sys_ == VPOS)
170 if (all_[pos.sys_].pscore_)
171 return pos.col_->get_property (str);
172 return all_[pos.sys_].prob_->get_property (str);
176 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
178 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
179 SCM page_module = scm_c_resolve_module ("scm page");
181 SCM make_page = scm_c_module_lookup (layout_module, "make-page-from-systems");
182 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
183 make_page = scm_variable_ref (make_page);
184 page_stencil = scm_variable_ref (page_stencil);
186 SCM book = book_->self_scm ();
187 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
188 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
189 int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
192 for (vsize i = 0; i < lines_per_page.size (); i++)
194 SCM page_num = scm_from_int (i + first_page_number);
195 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
196 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
197 SCM line_count = scm_from_int (lines_per_page[i]);
198 SCM lines = scm_list_head (systems, line_count);
199 SCM page = scm_apply_0 (make_page,
200 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
202 scm_apply_1 (page_stencil, page, SCM_EOL);
203 ret = scm_cons (page, ret);
204 systems = scm_list_tail (systems, line_count);
206 ret = scm_reverse (ret);
210 /* The page-turn-page-breaker needs to have a line-breaker between any two
211 columns with non-NULL page-turn-permission.
213 The optimal-breaker needs to have a line-breaker between any two columns
214 with page-break-permission = 'force.
216 By using a grob predicate, we can accommodate both of these uses.
219 Page_breaking::create_system_list ()
221 SCM specs = book_->get_system_specs ();
222 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
224 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
226 SCM system_count = ps->layout ()->c_variable ("system-count");
228 if (scm_is_number (system_count))
229 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
230 scm_vector_to_list (ps->get_paper_systems ()),
233 all_.push_back (System_spec (ps));
237 Prob *pb = unsmob_prob (scm_car (s));
241 all_.push_back (System_spec (pb));
247 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
249 SCM force_sym = ly_symbol2scm ("force");
251 chunks_.push_back (Break_position ());
252 breaks_.push_back (Break_position ());
254 for (vsize i = 0; i < all_.size (); i++)
258 vector<Grob*> cols = all_[i].pscore_->root_system ()->columns ();
259 vector<vsize> line_breaker_columns;
260 line_breaker_columns.push_back (0);
262 for (vsize j = 1; j < cols.size (); j++)
264 bool last = j == cols.size () - 1;
265 bool break_point = is_break (cols[j]);
266 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
267 Break_position cur_pos = Break_position (i,
268 line_breaker_columns.size (),
272 if (break_point || (i == all_.size () - 1 && last))
273 breaks_.push_back (cur_pos);
274 if (chunk_end || last)
275 chunks_.push_back (cur_pos);
277 if ((break_point || chunk_end) && !last)
278 line_breaker_columns.push_back (j);
280 line_breaking_.push_back (Constrained_breaking (line_breaker_columns));
281 line_breaking_.back ().set_pscore (all_[i].pscore_);
285 /* TODO: we want some way of applying Break_p to a prob? */
286 if (i == all_.size () - 1)
287 breaks_.push_back (Break_position (i));
289 chunks_.push_back (Break_position (i));
290 line_breaking_.push_back (Constrained_breaking ());
295 vector<Break_position>
296 Page_breaking::chunk_list (vsize start_index, vsize end_index)
298 Break_position start = breaks_[start_index];
299 Break_position end = breaks_[end_index];
302 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
305 vector<Break_position> ret;
306 ret.push_back (start);
307 for (; i < chunks_.size () && chunks_[i] < end; i++)
308 ret.push_back (chunks_[i]);
314 Page_breaking::min_system_count (vsize start, vsize end)
316 vector<Break_position> chunks = chunk_list (start, end);
317 Line_division div = system_count_bounds (chunks, true);
320 for (vsize i = 0; i < div.size (); i++)
326 Page_breaking::max_system_count (vsize start, vsize end)
328 vector<Break_position> chunks = chunk_list (start, end);
329 Line_division div = system_count_bounds (chunks, false);
332 for (vsize i = 0; i < div.size (); i++)
337 Page_breaking::Line_division
338 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
340 assert (chunks.size () >= 2);
343 ret.resize (chunks.size () - 1, 1);
345 for (vsize i = 0; i < chunks.size () - 1; i++)
347 vsize sys = next_system (chunks[i]);
348 if (all_[sys].pscore_)
352 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
354 ? line_breaking_[sys].get_min_systems (start, end)
355 : line_breaking_[sys].get_max_systems (start, end);
362 vector<Page_breaking::Line_division>
363 Page_breaking::line_divisions (vsize start,
366 Line_division lower_bound,
367 Line_division upper_bound)
369 vector<Break_position> chunks = chunk_list (start, end);
371 if (!lower_bound.size ())
372 lower_bound = system_count_bounds (chunks, true);
373 if (!upper_bound.size ())
374 upper_bound = system_count_bounds (chunks, false);
376 assert (lower_bound.size () == chunks.size () - 1);
377 assert (upper_bound.size () == chunks.size () - 1);
379 vector<Line_division> ret;
380 Line_division work_in_progress;
382 line_divisions_rec (system_count,
391 Page_breaking::line_divisions_rec (vsize system_count,
392 Line_division const &min_sys,
393 Line_division const &max_sys,
394 vector<Line_division > *result,
395 Line_division *cur_division)
397 vsize my_index = cur_division->size ();
398 vsize others_min = 0;
399 vsize others_max = 0;
401 for (vsize i = my_index + 1; i < min_sys.size (); i++)
403 others_min += min_sys[i];
404 others_max += max_sys[i];
406 others_max = min (others_max, system_count);
407 vsize real_min = max (min_sys[my_index], system_count - others_max);
408 vsize real_max = min (max_sys[my_index], system_count - others_min);
410 if (real_min > real_max || real_min <= 0)
412 /* this should never happen within a recursive call. If it happens
413 at all, it means that we were called with an unsolvable problem
414 and we should return an empty result */
415 assert (my_index == 0);
419 for (vsize i = real_min; i <= real_max; i++)
421 cur_division->push_back (i);
422 if (my_index == min_sys.size () - 1)
423 result->push_back (*cur_division);
425 line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
426 cur_division->pop_back ();