lily/page-breaking.cc

   1 /*
   2   page-breaking.cc -- implement a superclass and utility
   3   functions shared by various page-breaking algorithms
   4
   5   source file of the GNU LilyPond music typesetter
   6
   7   (c) 2006--2007 Joe Neeman <joeneeman@gmail.com>
   8 */
   9
  10 #include "page-breaking.hh"
  11
  12 #include "international.hh"
  13 #include "item.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"
  19 #include "system.hh"
  20 #include "warn.hh"
  21
  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
  26    it. */
  27
  28 /* Turn a break index into the sys index that starts the next page */
  29 vsize
  30 Page_breaking::next_system (Break_position const &break_pos) const
  31 {
  32   vsize sys = break_pos.sys_;
  33
  34   if (sys == VPOS) /* beginning of the book */
  35     return 0;
  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 */
  39 }
  40
  41 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
  42 {
  43   book_ = pb;
  44   create_system_list ();
  45   find_chunks_and_breaks (is_break);
  46 }
  47
  48 Page_breaking::~Page_breaking ()
  49 {
  50 }
  51
  52 /* translate indices into breaks_ into start-end parameters for the line breaker */
  53 void
  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)
  59 {
  60   assert (all_[sys].pscore_);
  61   assert (next_system (start) <= sys && sys <= end.sys_);
  62
  63   if (start.sys_ == sys)
  64     *line_breaker_start = start.score_break_;
  65   else
  66     *line_breaker_start = 0;
  67
  68   if (end.sys_ == sys)
  69     *line_breaker_end = end.score_break_;
  70   else
  71     *line_breaker_end = VPOS;
  72 }
  73
  74 void
  75 Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div)
  76 {
  77   vector<Break_position> chunks = chunk_list (start_break, end_break);
  78   assert (chunks.size () == div.size () + 1);
  79
  80   for (vsize i = 0; i + 1 < chunks.size (); i++)
  81     {
  82       vsize sys = next_system (chunks[i]);
  83       if (all_[sys].pscore_)
  84         {
  85           vsize start;
  86           vsize end;
  87           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
  88
  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);
  91         }
  92     }
  93 }
  94
  95 SCM
  96 Page_breaking::systems ()
  97 {
  98   SCM ret = SCM_EOL;
  99   for (vsize sys = 0; sys < all_.size (); sys++)
 100     {
 101       if (all_[sys].pscore_)
 102         {
 103           SCM lines = all_[sys].pscore_->root_system ()->get_paper_systems ();
 104           ret = scm_cons (scm_vector_to_list (lines), ret);
 105         }
 106       else
 107         {
 108           Prob *pb = all_[sys].prob_;
 109           ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
 110           pb->unprotect ();
 111         }
 112     }
 113   return scm_append (scm_reverse (ret));
 114 }
 115
 116 vector<Line_details>
 117 Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
 118 {
 119   vector<Break_position> chunks = chunk_list (start_break, end_break);
 120   vector<Line_details> ret;
 121   assert (chunks.size () == div.size () + 1);
 122
 123   for (vsize i = 0; i + 1 < chunks.size (); i++)
 124     {
 125       vsize sys = next_system (chunks[i]);
 126       if (all_[sys].pscore_)
 127         {
 128           vsize start;
 129           vsize end;
 130           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 131
 132           vector<Line_details> details = line_breaking_[sys].get_details (start, end, div[i]);
 133           ret.insert (ret.end (), details.begin (), details.end ());
 134         }
 135       else
 136         {
 137           assert (div[i] == 1);
 138           ret.push_back (Line_details (all_[sys].prob_));
 139         }
 140     }
 141   return ret;
 142 }
 143
 144 Real
 145 Page_breaking::page_height (int page_num, bool last)
 146 {
 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");
 150
 151   calc_height = scm_variable_ref (calc_height);
 152   make_page = scm_variable_ref (make_page);
 153
 154   SCM page = scm_apply_0 (make_page, scm_list_n (
 155                   book_->self_scm (),
 156                   ly_symbol2scm ("page-number"), scm_from_int (page_num),
 157                   ly_symbol2scm ("is-last"), scm_from_bool (last),
 158                   SCM_UNDEFINED));
 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"));
 161 }
 162
 163 SCM
 164 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
 165 {
 166   Break_position const &pos = breaks_[breakpoint];
 167
 168   if (pos.sys_ == VPOS)
 169     return SCM_EOL;
 170   if (all_[pos.sys_].pscore_)
 171     return pos.col_->get_property (str);
 172   return all_[pos.sys_].prob_->get_property (str);
 173 }
 174
 175 SCM
 176 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
 177 {
 178   SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
 179   SCM page_module = scm_c_resolve_module ("scm page");
 180
 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);
 185
 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);
 190   SCM ret = SCM_EOL;
 191
 192   for (vsize i = 0; i < lines_per_page.size (); i++)
 193     {
 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));
 201
 202       scm_apply_1 (page_stencil, page, SCM_EOL);
 203       ret = scm_cons (page, ret);
 204       systems = scm_list_tail (systems, line_count);
 205     }
 206   ret = scm_reverse (ret);
 207   return ret;
 208 }
 209
 210 /* The page-turn-page-breaker needs to have a line-breaker between any two
 211    columns with non-NULL page-turn-permission.
 212
 213    The optimal-breaker needs to have a line-breaker between any two columns
 214    with page-break-permission = 'force.
 215
 216    By using a grob predicate, we can accommodate both of these uses.
 217 */
 218 void
 219 Page_breaking::create_system_list ()
 220 {
 221   SCM specs = book_->get_system_specs ();
 222   for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
 223     {
 224       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
 225         {
 226           SCM system_count = ps->layout ()->c_variable ("system-count");
 227
 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 ()),
 231                                         scm_cdr (s)));
 232           else
 233             all_.push_back (System_spec (ps));
 234         }
 235       else
 236         {
 237           Prob *pb = unsmob_prob (scm_car (s));
 238           assert (pb);
 239
 240           pb->protect ();
 241           all_.push_back (System_spec (pb));
 242         }
 243     }
 244 }
 245
 246 void
 247 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
 248 {
 249   SCM force_sym = ly_symbol2scm ("force");
 250
 251   chunks_.push_back (Break_position ());
 252   breaks_.push_back (Break_position ());
 253
 254   for (vsize i = 0; i < all_.size (); i++)
 255     {
 256       if (all_[i].pscore_)
 257         {
 258           vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
 259           vector<vsize> line_breaker_columns;
 260           line_breaker_columns.push_back (0);
 261
 262           for (vsize j = 1; j < cols.size (); j++)
 263             {
 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 (),
 269                                                        cols[j],
 270                                                        last);
 271
 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);
 276
 277               if ((break_point || chunk_end) && !last)
 278                 line_breaker_columns.push_back (j);
 279             }
 280           line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
 281         }
 282       else
 283         {
 284           /* TODO: we want some way of applying Break_p to a prob? */
 285           if (i == all_.size () - 1)
 286             breaks_.push_back (Break_position (i));
 287
 288           chunks_.push_back (Break_position (i));
 289           line_breaking_.push_back (Constrained_breaking (NULL));
 290         }
 291     }
 292 }
 293
 294 vector<Break_position>
 295 Page_breaking::chunk_list (vsize start_index, vsize end_index)
 296 {
 297   Break_position start = breaks_[start_index];
 298   Break_position end = breaks_[end_index];
 299
 300   vsize i;
 301   for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
 302     ;
 303
 304   vector<Break_position> ret;
 305   ret.push_back (start);
 306   for (; i < chunks_.size () && chunks_[i] < end; i++)
 307     ret.push_back (chunks_[i]);
 308   ret.push_back (end);
 309   return ret;
 310 }
 311
 312 vsize
 313 Page_breaking::min_system_count (vsize start, vsize end)
 314 {
 315   vector<Break_position> chunks = chunk_list (start, end);
 316   Line_division div = system_count_bounds (chunks, true);
 317   vsize ret = 0;
 318
 319   for (vsize i = 0; i < div.size (); i++)
 320     ret += div[i];
 321   return ret;
 322 }
 323
 324 vsize
 325 Page_breaking::max_system_count (vsize start, vsize end)
 326 {
 327   vector<Break_position> chunks = chunk_list (start, end);
 328   Line_division div = system_count_bounds (chunks, false);
 329   vsize ret = 0;
 330
 331   for (vsize i = 0; i < div.size (); i++)
 332     ret += div[i];
 333   return ret;
 334 }
 335
 336 Page_breaking::Line_division
 337 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
 338 {
 339   assert (chunks.size () >= 2);
 340
 341   Line_division ret;
 342   ret.resize (chunks.size () - 1, 1);
 343
 344   for (vsize i = 0; i + 1 < chunks.size (); i++)
 345     {
 346       vsize sys = next_system (chunks[i]);
 347       if (all_[sys].pscore_)
 348         {
 349           vsize start;
 350           vsize end;
 351           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 352           ret[i] = min
 353             ? line_breaking_[sys].get_min_systems (start, end)
 354             : line_breaking_[sys].get_max_systems (start, end);
 355         }
 356     }
 357
 358   return ret;
 359 }
 360
 361 vector<Page_breaking::Line_division>
 362 Page_breaking::line_divisions (vsize start,
 363                                vsize end,
 364                                vsize system_count,
 365                                Line_division lower_bound,
 366                                Line_division upper_bound)
 367 {
 368   vector<Break_position> chunks = chunk_list (start, end);
 369
 370   if (!lower_bound.size ())
 371     lower_bound = system_count_bounds (chunks, true);
 372   if (!upper_bound.size ())
 373     upper_bound = system_count_bounds (chunks, false);
 374
 375   assert (lower_bound.size () == chunks.size () - 1);
 376   assert (upper_bound.size () == chunks.size () - 1);
 377
 378   vector<Line_division> ret;
 379   Line_division work_in_progress;
 380
 381   line_divisions_rec (system_count,
 382                       lower_bound,
 383                       upper_bound,
 384                       &ret,
 385                       &work_in_progress);
 386   return ret;
 387 }
 388
 389 void
 390 Page_breaking::line_divisions_rec (vsize system_count,
 391                                    Line_division const &min_sys,
 392                                    Line_division const &max_sys,
 393                                    vector<Line_division > *result,
 394                                    Line_division *cur_division)
 395 {
 396   vsize my_index = cur_division->size ();
 397   vsize others_min = 0;
 398   vsize others_max = 0;
 399
 400   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 401     {
 402       others_min += min_sys[i];
 403       others_max += max_sys[i];
 404     }
 405   others_max = min (others_max, system_count);
 406   vsize real_min = max (min_sys[my_index], system_count - others_max);
 407   vsize real_max = min (max_sys[my_index], system_count - others_min);
 408
 409   if (real_min > real_max || real_min <= 0)
 410     {
 411       /* this should never happen within a recursive call. If it happens
 412          at all, it means that we were called with an unsolvable problem
 413          and we should return an empty result */
 414       assert (my_index == 0);
 415       return;
 416     }
 417
 418   for (vsize i = real_min; i <= real_max; i++)
 419     {
 420       cur_division->push_back (i);
 421       if (my_index == min_sys.size () - 1)
 422         result->push_back (*cur_division);
 423       else
 424         line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
 425       cur_division->pop_back ();
 426     }
 427 }