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 module = scm_c_resolve_module ("scm layout-page-layout");
179 SCM make_page = scm_c_module_lookup (module, "make-page-from-systems");
180 make_page = scm_variable_ref (make_page);
181 SCM book = book_->self_scm ();
182 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
183 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
186 for (vsize i = 0; i < lines_per_page.size (); i++)
188 SCM page_num = scm_from_int (i + 1);
189 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
190 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
191 SCM line_count = scm_from_int (lines_per_page[i]);
192 SCM lines = scm_list_head (systems, line_count);
193 SCM page = scm_apply_0 (make_page,
194 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
196 ret = scm_cons (page, ret);
197 systems = scm_list_tail (systems, line_count);
199 return scm_reverse (ret);
202 /* The page-turn-page-breaker needs to have a line-breaker between any two
203 columns with non-NULL page-turn-permission.
205 The optimal-breaker needs to have a line-breaker between any two columns
206 with page-break-permission = 'force.
208 By using a grob predicate, we can accommodate both of these uses.
211 Page_breaking::create_system_list ()
213 SCM specs = book_->get_system_specs ();
214 for (SCM s = specs; s != SCM_EOL; s = scm_cdr (s))
216 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
217 all_.push_back (System_spec (ps));
220 Prob *pb = unsmob_prob (scm_car (s));
224 all_.push_back (System_spec (pb));
230 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
232 SCM force_sym = ly_symbol2scm ("force");
234 chunks_.push_back (Break_position ());
235 breaks_.push_back (Break_position ());
237 for (vsize i = 0; i < all_.size (); i++)
241 vector<Grob*> cols = all_[i].pscore_->root_system ()->columns ();
242 vector<vsize> line_breaker_columns;
243 line_breaker_columns.push_back (0);
245 for (vsize j = 0; j < cols.size (); j++)
247 bool last = j == cols.size () - 1;
248 bool break_point = is_break (cols[j]);
249 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
250 Break_position cur_pos = Break_position (i,
251 line_breaker_columns.size (),
255 if (break_point || (i == all_.size () - 1 && last))
256 breaks_.push_back (cur_pos);
257 if (chunk_end || last)
258 chunks_.push_back (cur_pos);
260 if ((break_point || chunk_end) && !last)
261 line_breaker_columns.push_back (j);
263 line_breaking_.push_back (Constrained_breaking (line_breaker_columns));
264 line_breaking_.back ().set_pscore (all_[i].pscore_);
268 /* TODO: we want some way of applying Break_p to a prob? */
269 if (i == all_.size () - 1)
270 breaks_.push_back (Break_position (i));
272 chunks_.push_back (Break_position (i));
273 line_breaking_.push_back (Constrained_breaking ());
278 vector<Break_position>
279 Page_breaking::chunk_list (vsize start_index, vsize end_index)
281 Break_position start = breaks_[start_index];
282 Break_position end = breaks_[end_index];
285 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
288 vector<Break_position> ret;
289 ret.push_back (start);
290 for (; i < chunks_.size () && chunks_[i] < end; i++)
291 ret.push_back (chunks_[i]);
297 Page_breaking::min_system_count (vsize start, vsize end)
299 vector<Break_position> chunks = chunk_list (start, end);
300 Line_division div = system_count_bounds (chunks, true);
303 for (vsize i = 0; i < div.size (); i++)
309 Page_breaking::max_system_count (vsize start, vsize end)
311 vector<Break_position> chunks = chunk_list (start, end);
312 Line_division div = system_count_bounds (chunks, false);
315 for (vsize i = 0; i < div.size (); i++)
320 Page_breaking::Line_division
321 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
323 assert (chunks.size () >= 2);
326 ret.resize (chunks.size () - 1, 1);
328 for (vsize i = 0; i < chunks.size () - 1; i++)
330 vsize sys = next_system (chunks[i]);
331 if (all_[sys].pscore_)
335 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
337 ? line_breaking_[sys].get_min_systems (start, end)
338 : line_breaking_[sys].get_max_systems (start, end);
345 vector<Page_breaking::Line_division>
346 Page_breaking::line_divisions (vsize start,
349 Line_division lower_bound,
350 Line_division upper_bound)
352 vector<Break_position> chunks = chunk_list (start, end);
354 if (!lower_bound.size ())
355 lower_bound = system_count_bounds (chunks, true);
356 if (!upper_bound.size ())
357 upper_bound = system_count_bounds (chunks, false);
359 assert (lower_bound.size () == chunks.size () - 1);
360 assert (upper_bound.size () == chunks.size () - 1);
362 vector<Line_division> ret;
363 Line_division work_in_progress;
365 line_divisions_rec (system_count,
374 Page_breaking::line_divisions_rec (vsize system_count,
375 Line_division const &min_sys,
376 Line_division const &max_sys,
377 vector<Line_division > *result,
378 Line_division *cur_division)
380 vsize my_index = cur_division->size ();
381 vsize others_min = 0;
382 vsize others_max = 0;
384 for (vsize i = my_index + 1; i < min_sys.size (); i++)
386 others_min += min_sys[i];
387 others_max += max_sys[i];
389 others_max = min (others_max, system_count);
390 vsize real_min = max (min_sys[my_index], system_count - others_max);
391 vsize real_max = min (max_sys[my_index], system_count - others_min);
393 if (real_min > real_max || real_min <= 0)
395 /* this should never happen within a recursive call. If it happens
396 at all, it means that we were called with an unsolvable problem
397 and we should return an empty result */
398 assert (my_index == 0);
402 for (vsize i = real_min; i <= real_max; i++)
404 cur_division->push_back (i);
405 if (my_index == min_sys.size () - 1)
406 result->push_back (*cur_division);
408 line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
409 cur_division->pop_back ();