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 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 < chunks.size () - 1; 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 < chunks.size () - 1; 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 dump_module = scm_c_resolve_module ("scm layout-page-dump");
 180   SCM page_module = scm_c_resolve_module ("scm page");
 181
 182   SCM make_page = scm_c_module_lookup (layout_module, "make-page-from-systems");
 183   SCM write_page_breaks = scm_c_module_lookup (dump_module, "write-page-breaks");
 184   SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
 185   make_page = scm_variable_ref (make_page);
 186   write_page_breaks = scm_variable_ref (write_page_breaks);
 187   page_stencil = scm_variable_ref (page_stencil);
 188
 189   SCM book = book_->self_scm ();
 190   bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
 191   bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
 192   SCM ret = SCM_EOL;
 193
 194   for (vsize i = 0; i < lines_per_page.size (); i++)
 195     {
 196       SCM page_num = scm_from_int (i + 1);
 197       SCM last = scm_from_bool (i == lines_per_page.size () - 1);
 198       SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
 199       SCM line_count = scm_from_int (lines_per_page[i]);
 200       SCM lines = scm_list_head (systems, line_count);
 201       SCM page = scm_apply_0 (make_page,
 202                               scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
 203
 204       scm_apply_1 (page_stencil, page, SCM_EOL);
 205       ret = scm_cons (page, ret);
 206       systems = scm_list_tail (systems, line_count);
 207     }
 208   ret = scm_reverse (ret);
 209
 210   if (to_boolean (book_->paper_->c_variable ("write-page-layout")))
 211     scm_apply_1 (write_page_breaks, ret, SCM_EOL);
 212   return ret;
 213 }
 214
 215 /* The page-turn-page-breaker needs to have a line-breaker between any two
 216    columns with non-NULL page-turn-permission.
 217
 218    The optimal-breaker needs to have a line-breaker between any two columns
 219    with page-break-permission = 'force.
 220
 221    By using a grob predicate, we can accommodate both of these uses.
 222 */
 223 void
 224 Page_breaking::create_system_list ()
 225 {
 226   SCM specs = book_->get_system_specs ();
 227   for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
 228     {
 229       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
 230         {
 231           SCM system_count = ps->layout ()->c_variable ("system-count");
 232
 233           if (scm_is_number (system_count))
 234             s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
 235                                         scm_vector_to_list (ps->get_paper_systems ()),
 236                                         scm_cdr (s)));
 237           else
 238             all_.push_back (System_spec (ps));
 239         }
 240       else
 241         {
 242           Prob *pb = unsmob_prob (scm_car (s));
 243           assert (pb);
 244
 245           pb->protect ();
 246           all_.push_back (System_spec (pb));
 247         }
 248     }
 249 }
 250
 251 void
 252 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
 253 {
 254   SCM force_sym = ly_symbol2scm ("force");
 255
 256   chunks_.push_back (Break_position ());
 257   breaks_.push_back (Break_position ());
 258
 259   for (vsize i = 0; i < all_.size (); i++)
 260     {
 261       if (all_[i].pscore_)
 262         {
 263           vector<Grob*> cols = all_[i].pscore_->root_system ()->columns ();
 264           vector<vsize> line_breaker_columns;
 265           line_breaker_columns.push_back (0);
 266
 267           for (vsize j = 1; j < cols.size (); j++)
 268             {
 269               bool last = j == cols.size () - 1;
 270               bool break_point = is_break (cols[j]);
 271               bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
 272               Break_position cur_pos = Break_position (i,
 273                                                        line_breaker_columns.size (),
 274                                                        cols[j],
 275                                                        last);
 276
 277               if (break_point || (i == all_.size () - 1 && last))
 278                 breaks_.push_back (cur_pos);
 279               if (chunk_end || last)
 280                 chunks_.push_back (cur_pos);
 281
 282               if ((break_point || chunk_end) && !last)
 283                 line_breaker_columns.push_back (j);
 284             }
 285           line_breaking_.push_back (Constrained_breaking (line_breaker_columns));
 286           line_breaking_.back ().set_pscore (all_[i].pscore_);
 287         }
 288       else
 289         {
 290           /* TODO: we want some way of applying Break_p to a prob? */
 291           if (i == all_.size () - 1)
 292             breaks_.push_back (Break_position (i));
 293
 294           chunks_.push_back (Break_position (i));
 295           line_breaking_.push_back (Constrained_breaking ());
 296         }
 297     }
 298 }
 299
 300 vector<Break_position>
 301 Page_breaking::chunk_list (vsize start_index, vsize end_index)
 302 {
 303   Break_position start = breaks_[start_index];
 304   Break_position end = breaks_[end_index];
 305
 306   vsize i;
 307   for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
 308     ;
 309
 310   vector<Break_position> ret;
 311   ret.push_back (start);
 312   for (; i < chunks_.size () && chunks_[i] < end; i++)
 313     ret.push_back (chunks_[i]);
 314   ret.push_back (end);
 315   return ret;
 316 }
 317
 318 vsize
 319 Page_breaking::min_system_count (vsize start, vsize end)
 320 {
 321   vector<Break_position> chunks = chunk_list (start, end);
 322   Line_division div = system_count_bounds (chunks, true);
 323   vsize ret = 0;
 324
 325   for (vsize i = 0; i < div.size (); i++)
 326     ret += div[i];
 327   return ret;
 328 }
 329
 330 vsize
 331 Page_breaking::max_system_count (vsize start, vsize end)
 332 {
 333   vector<Break_position> chunks = chunk_list (start, end);
 334   Line_division div = system_count_bounds (chunks, false);
 335   vsize ret = 0;
 336
 337   for (vsize i = 0; i < div.size (); i++)
 338     ret += div[i];
 339   return ret;
 340 }
 341
 342 Page_breaking::Line_division
 343 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
 344 {
 345   assert (chunks.size () >= 2);
 346
 347   Line_division ret;
 348   ret.resize (chunks.size () - 1, 1);
 349
 350   for (vsize i = 0; i < chunks.size () - 1; i++)
 351     {
 352       vsize sys = next_system (chunks[i]);
 353       if (all_[sys].pscore_)
 354         {
 355           vsize start;
 356           vsize end;
 357           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 358           ret[i] = min
 359             ? line_breaking_[sys].get_min_systems (start, end)
 360             : line_breaking_[sys].get_max_systems (start, end);
 361         }
 362     }
 363
 364   return ret;
 365 }
 366
 367 vector<Page_breaking::Line_division>
 368 Page_breaking::line_divisions (vsize start,
 369                                vsize end,
 370                                vsize system_count,
 371                                Line_division lower_bound,
 372                                Line_division upper_bound)
 373 {
 374   vector<Break_position> chunks = chunk_list (start, end);
 375
 376   if (!lower_bound.size ())
 377     lower_bound = system_count_bounds (chunks, true);
 378   if (!upper_bound.size ())
 379     upper_bound = system_count_bounds (chunks, false);
 380
 381   assert (lower_bound.size () == chunks.size () - 1);
 382   assert (upper_bound.size () == chunks.size () - 1);
 383
 384   vector<Line_division> ret;
 385   Line_division work_in_progress;
 386
 387   line_divisions_rec (system_count,
 388                       lower_bound,
 389                       upper_bound,
 390                       &ret,
 391                       &work_in_progress);
 392   return ret;
 393 }
 394
 395 void
 396 Page_breaking::line_divisions_rec (vsize system_count,
 397                                    Line_division const &min_sys,
 398                                    Line_division const &max_sys,
 399                                    vector<Line_division > *result,
 400                                    Line_division *cur_division)
 401 {
 402   vsize my_index = cur_division->size ();
 403   vsize others_min = 0;
 404   vsize others_max = 0;
 405
 406   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 407     {
 408       others_min += min_sys[i];
 409       others_max += max_sys[i];
 410     }
 411   others_max = min (others_max, system_count);
 412   vsize real_min = max (min_sys[my_index], system_count - others_max);
 413   vsize real_max = min (max_sys[my_index], system_count - others_min);
 414
 415   if (real_min > real_max || real_min <= 0)
 416     {
 417       /* this should never happen within a recursive call. If it happens
 418          at all, it means that we were called with an unsolvable problem
 419          and we should return an empty result */
 420       assert (my_index == 0);
 421       return;
 422     }
 423
 424   for (vsize i = real_min; i <= real_max; i++)
 425     {
 426       cur_division->push_back (i);
 427       if (my_index == min_sys.size () - 1)
 428         result->push_back (*cur_division);
 429       else
 430         line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
 431       cur_division->pop_back ();
 432     }
 433 }