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   bool ignore_div = false;
  79   if (chunks.size () != div.size () + 1)
  80     {
  81       programming_error ("did not find a valid page breaking configuration");
  82       ignore_div = true;
  83       assert (0);
  84     }
  85
  86   for (vsize i = 0; i + 1 < chunks.size (); i++)
  87     {
  88       vsize sys = next_system (chunks[i]);
  89       if (all_[sys].pscore_)
  90         {
  91           vsize start;
  92           vsize end;
  93           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
  94
  95           vector<Column_x_positions> pos = ignore_div
  96             ? line_breaking_[sys].best_solution (start, end)
  97             : line_breaking_[sys].solve (start, end, div[i]);
  98           all_[sys].pscore_->root_system ()->break_into_pieces (pos);
  99         }
 100     }
 101 }
 102
 103 SCM
 104 Page_breaking::systems ()
 105 {
 106   SCM ret = SCM_EOL;
 107   for (vsize sys = 0; sys < all_.size (); sys++)
 108     {
 109       if (all_[sys].pscore_)
 110         {
 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);
 114         }
 115       else
 116         {
 117           Prob *pb = all_[sys].prob_;
 118           ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
 119           pb->unprotect ();
 120         }
 121     }
 122   return scm_append (scm_reverse (ret));
 123 }
 124
 125 vector<Line_details>
 126 Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
 127 {
 128   vector<Break_position> chunks = chunk_list (start_break, end_break);
 129   vector<Line_details> ret;
 130   assert (chunks.size () == div.size () + 1);
 131
 132   for (vsize i = 0; i + 1 < chunks.size (); i++)
 133     {
 134       vsize sys = next_system (chunks[i]);
 135       if (all_[sys].pscore_)
 136         {
 137           vsize start;
 138           vsize end;
 139           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 140
 141           vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
 142           ret.insert (ret.end (), details.begin (), details.end ());
 143         }
 144       else
 145         {
 146           assert (div[i] == 1);
 147           ret.push_back (Line_details (all_[sys].prob_));
 148         }
 149     }
 150   return ret;
 151 }
 152
 153 Real
 154 Page_breaking::page_height (int page_num, bool last)
 155 {
 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");
 159
 160   calc_height = scm_variable_ref (calc_height);
 161   make_page = scm_variable_ref (make_page);
 162
 163   SCM page = scm_apply_0 (make_page, scm_list_n (
 164                   book_->self_scm (),
 165                   ly_symbol2scm ("page-number"), scm_from_int (page_num),
 166                   ly_symbol2scm ("is-last"), scm_from_bool (last),
 167                   SCM_UNDEFINED));
 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"));
 170 }
 171
 172 SCM
 173 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
 174 {
 175   Break_position const &pos = breaks_[breakpoint];
 176
 177   if (pos.sys_ == VPOS)
 178     return SCM_EOL;
 179   if (all_[pos.sys_].pscore_)
 180     return pos.col_->get_property (str);
 181   return all_[pos.sys_].prob_->get_property (str);
 182 }
 183
 184 SCM
 185 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
 186 {
 187   SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
 188   SCM page_module = scm_c_resolve_module ("scm page");
 189
 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);
 194
 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);
 199   SCM ret = SCM_EOL;
 200
 201   for (vsize i = 0; i < lines_per_page.size (); i++)
 202     {
 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));
 210
 211       scm_apply_1 (page_stencil, page, SCM_EOL);
 212       ret = scm_cons (page, ret);
 213       systems = scm_list_tail (systems, line_count);
 214     }
 215   ret = scm_reverse (ret);
 216   return ret;
 217 }
 218
 219 /* The page-turn-page-breaker needs to have a line-breaker between any two
 220    columns with non-NULL page-turn-permission.
 221
 222    The optimal-breaker needs to have a line-breaker between any two columns
 223    with page-break-permission = 'force.
 224
 225    By using a grob predicate, we can accommodate both of these uses.
 226 */
 227 void
 228 Page_breaking::create_system_list ()
 229 {
 230   SCM specs = book_->get_system_specs ();
 231   for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
 232     {
 233       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
 234         {
 235           SCM system_count = ps->layout ()->c_variable ("system-count");
 236
 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 ()),
 240                                         scm_cdr (s)));
 241           else
 242             all_.push_back (System_spec (ps));
 243         }
 244       else
 245         {
 246           Prob *pb = unsmob_prob (scm_car (s));
 247           assert (pb);
 248
 249           pb->protect ();
 250           all_.push_back (System_spec (pb));
 251         }
 252     }
 253 }
 254
 255 void
 256 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
 257 {
 258   SCM force_sym = ly_symbol2scm ("force");
 259
 260   chunks_.push_back (Break_position ());
 261   breaks_.push_back (Break_position ());
 262
 263   for (vsize i = 0; i < all_.size (); i++)
 264     {
 265       if (all_[i].pscore_)
 266         {
 267           vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
 268           vector<vsize> line_breaker_columns;
 269           line_breaker_columns.push_back (0);
 270
 271           for (vsize j = 1; j < cols.size (); j++)
 272             {
 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 (),
 278                                                        cols[j],
 279                                                        last);
 280
 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);
 285
 286               if ((break_point || chunk_end) && !last)
 287                 line_breaker_columns.push_back (j);
 288             }
 289           line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
 290         }
 291       else
 292         {
 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));
 296
 297           chunks_.push_back (Break_position (i));
 298           line_breaking_.push_back (Constrained_breaking (NULL));
 299         }
 300     }
 301 }
 302
 303 vector<Break_position>
 304 Page_breaking::chunk_list (vsize start_index, vsize end_index)
 305 {
 306   Break_position start = breaks_[start_index];
 307   Break_position end = breaks_[end_index];
 308
 309   vsize i;
 310   for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
 311     ;
 312
 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]);
 317   ret.push_back (end);
 318   return ret;
 319 }
 320
 321 vsize
 322 Page_breaking::min_system_count (vsize start, vsize end)
 323 {
 324   vector<Break_position> chunks = chunk_list (start, end);
 325   Line_division div = system_count_bounds (chunks, true);
 326   vsize ret = 0;
 327
 328   for (vsize i = 0; i < div.size (); i++)
 329     ret += div[i];
 330   return ret;
 331 }
 332
 333 vsize
 334 Page_breaking::max_system_count (vsize start, vsize end)
 335 {
 336   vector<Break_position> chunks = chunk_list (start, end);
 337   Line_division div = system_count_bounds (chunks, false);
 338   vsize ret = 0;
 339
 340   for (vsize i = 0; i < div.size (); i++)
 341     ret += div[i];
 342   return ret;
 343 }
 344
 345 Page_breaking::Line_division
 346 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
 347 {
 348   assert (chunks.size () >= 2);
 349
 350   Line_division ret;
 351   ret.resize (chunks.size () - 1, 1);
 352
 353   for (vsize i = 0; i + 1 < chunks.size (); i++)
 354     {
 355       vsize sys = next_system (chunks[i]);
 356       if (all_[sys].pscore_)
 357         {
 358           vsize start;
 359           vsize end;
 360           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 361           ret[i] = min
 362             ? line_breaking_[sys].min_system_count (start, end)
 363             : line_breaking_[sys].max_system_count (start, end);
 364         }
 365     }
 366
 367   return ret;
 368 }
 369
 370 vector<Page_breaking::Line_division>
 371 Page_breaking::line_divisions (vsize start,
 372                                vsize end,
 373                                vsize system_count,
 374                                Line_division lower_bound,
 375                                Line_division upper_bound)
 376 {
 377   vector<Break_position> chunks = chunk_list (start, end);
 378
 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);
 383
 384   assert (lower_bound.size () == chunks.size () - 1);
 385   assert (upper_bound.size () == chunks.size () - 1);
 386
 387   vector<Line_division> ret;
 388   Line_division work_in_progress;
 389
 390   line_divisions_rec (system_count,
 391                       lower_bound,
 392                       upper_bound,
 393                       &ret,
 394                       &work_in_progress);
 395   return ret;
 396 }
 397
 398 void
 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)
 404 {
 405   vsize my_index = cur_division->size ();
 406   vsize others_min = 0;
 407   vsize others_max = 0;
 408
 409   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 410     {
 411       others_min += min_sys[i];
 412       others_max += max_sys[i];
 413     }
 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);
 417
 418   if (real_min > real_max || real_min <= 0)
 419     {
 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);
 424       return;
 425     }
 426
 427   for (vsize i = real_min; i <= real_max; i++)
 428     {
 429       cur_division->push_back (i);
 430       if (my_index == min_sys.size () - 1)
 431         result->push_back (*cur_division);
 432       else
 433         line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
 434       cur_division->pop_back ();
 435     }
 436 }