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     }
  84
  85   for (vsize i = 0; i + 1 < chunks.size (); i++)
  86     {
  87       vsize sys = next_system (chunks[i]);
  88       if (all_[sys].pscore_)
  89         {
  90           vsize start;
  91           vsize end;
  92           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
  93
  94           vector<Column_x_positions> pos = ignore_div
  95             ? line_breaking_[sys].best_solution (start, end)
  96             : line_breaking_[sys].solve (start, end, div[i]);
  97           all_[sys].pscore_->root_system ()->break_into_pieces (pos);
  98         }
  99     }
 100 }
 101
 102 SCM
 103 Page_breaking::systems ()
 104 {
 105   SCM ret = SCM_EOL;
 106   for (vsize sys = 0; sys < all_.size (); sys++)
 107     {
 108       if (all_[sys].pscore_)
 109         {
 110           all_[sys].pscore_->root_system ()->do_break_substitution_and_fixup_refpoints ();
 111           SCM lines = all_[sys].pscore_->root_system ()->get_broken_system_grobs ();
 112           ret = scm_cons (lines, ret);
 113         }
 114       else
 115         {
 116           Prob *pb = all_[sys].prob_;
 117           ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
 118           pb->unprotect ();
 119         }
 120     }
 121   return scm_append (scm_reverse (ret));
 122 }
 123
 124 vector<Line_details>
 125 Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
 126 {
 127   vector<Break_position> chunks = chunk_list (start_break, end_break);
 128   vector<Line_details> ret;
 129   assert (chunks.size () == div.size () + 1);
 130
 131   SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
 132   if (!scm_is_number (padding_scm))
 133     padding_scm = book_->paper_->c_variable ("between-system-padding");
 134   Real padding = robust_scm2double (padding_scm, 0.0);
 135
 136   for (vsize i = 0; i + 1 < chunks.size (); i++)
 137     {
 138       vsize sys = next_system (chunks[i]);
 139       if (all_[sys].pscore_)
 140         {
 141           vsize start;
 142           vsize end;
 143           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 144
 145           vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
 146           ret.insert (ret.end (), details.begin (), details.end ());
 147         }
 148       else
 149         {
 150           assert (div[i] == 1);
 151           ret.push_back (Line_details (all_[sys].prob_));
 152           ret.back ().padding_ = padding;
 153         }
 154     }
 155   return ret;
 156 }
 157
 158 Real
 159 Page_breaking::page_height (int page_num, bool last)
 160 {
 161   SCM mod = scm_c_resolve_module ("scm page");
 162   SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
 163   SCM make_page = scm_c_module_lookup (mod, "make-page");
 164
 165   calc_height = scm_variable_ref (calc_height);
 166   make_page = scm_variable_ref (make_page);
 167
 168   SCM page = scm_apply_0 (make_page, scm_list_n (
 169                   book_->self_scm (),
 170                   ly_symbol2scm ("page-number"), scm_from_int (page_num),
 171                   ly_symbol2scm ("is-last"), scm_from_bool (last),
 172                   SCM_UNDEFINED));
 173   SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
 174   return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
 175 }
 176
 177 SCM
 178 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
 179 {
 180   Break_position const &pos = breaks_[breakpoint];
 181
 182   if (pos.sys_ == VPOS)
 183     return SCM_EOL;
 184   if (all_[pos.sys_].pscore_)
 185     return pos.col_->get_property (str);
 186   return all_[pos.sys_].prob_->get_property (str);
 187 }
 188
 189 SCM
 190 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
 191 {
 192   SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
 193   SCM page_module = scm_c_resolve_module ("scm page");
 194
 195   SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
 196   SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
 197   make_page = scm_variable_ref (make_page);
 198   page_stencil = scm_variable_ref (page_stencil);
 199
 200   SCM book = book_->self_scm ();
 201   bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
 202   bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
 203   int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
 204   SCM ret = SCM_EOL;
 205
 206   for (vsize i = 0; i < lines_per_page.size (); i++)
 207     {
 208       SCM page_num = scm_from_int (i + first_page_number);
 209       SCM last = scm_from_bool (i == lines_per_page.size () - 1);
 210       SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
 211       SCM line_count = scm_from_int (lines_per_page[i]);
 212       SCM lines = scm_list_head (systems, line_count);
 213       SCM page = scm_apply_0 (make_page,
 214                               scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
 215
 216       scm_apply_1 (page_stencil, page, SCM_EOL);
 217       ret = scm_cons (page, ret);
 218       systems = scm_list_tail (systems, line_count);
 219     }
 220   ret = scm_reverse (ret);
 221   return ret;
 222 }
 223
 224 /* The page-turn-page-breaker needs to have a line-breaker between any two
 225    columns with non-NULL page-turn-permission.
 226
 227    The optimal-breaker needs to have a line-breaker between any two columns
 228    with page-break-permission = 'force.
 229
 230    By using a grob predicate, we can accommodate both of these uses.
 231 */
 232 void
 233 Page_breaking::create_system_list ()
 234 {
 235   SCM specs = book_->get_system_specs ();
 236   for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
 237     {
 238       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
 239         {
 240           SCM system_count = ps->layout ()->c_variable ("system-count");
 241
 242           if (scm_is_number (system_count))
 243             s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
 244                                         scm_vector_to_list (ps->get_paper_systems ()),
 245                                         scm_cdr (s)));
 246           else
 247             all_.push_back (System_spec (ps));
 248         }
 249       else
 250         {
 251           Prob *pb = unsmob_prob (scm_car (s));
 252           assert (pb);
 253
 254           pb->protect ();
 255           all_.push_back (System_spec (pb));
 256         }
 257     }
 258 }
 259
 260 void
 261 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
 262 {
 263   SCM force_sym = ly_symbol2scm ("force");
 264
 265   chunks_.push_back (Break_position ());
 266   breaks_.push_back (Break_position ());
 267
 268   for (vsize i = 0; i < all_.size (); i++)
 269     {
 270       if (all_[i].pscore_)
 271         {
 272           vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
 273           vector<vsize> line_breaker_columns;
 274           line_breaker_columns.push_back (0);
 275
 276           for (vsize j = 1; j < cols.size (); j++)
 277             {
 278               bool last = j == cols.size () - 1;
 279               bool break_point = is_break (cols[j]);
 280               bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
 281               Break_position cur_pos = Break_position (i,
 282                                                        line_breaker_columns.size (),
 283                                                        cols[j],
 284                                                        last);
 285
 286               if (break_point || (i == all_.size () - 1 && last))
 287                 breaks_.push_back (cur_pos);
 288               if (chunk_end || last)
 289                 chunks_.push_back (cur_pos);
 290
 291               if ((break_point || chunk_end) && !last)
 292                 line_breaker_columns.push_back (j);
 293             }
 294           line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
 295         }
 296       else
 297         {
 298           /* TODO: we want some way of applying Break_p to a prob? */
 299           if (i == all_.size () - 1)
 300             breaks_.push_back (Break_position (i));
 301
 302           chunks_.push_back (Break_position (i));
 303           line_breaking_.push_back (Constrained_breaking (NULL));
 304         }
 305     }
 306 }
 307
 308 vector<Break_position>
 309 Page_breaking::chunk_list (vsize start_index, vsize end_index)
 310 {
 311   Break_position start = breaks_[start_index];
 312   Break_position end = breaks_[end_index];
 313
 314   vsize i;
 315   for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
 316     ;
 317
 318   vector<Break_position> ret;
 319   ret.push_back (start);
 320   for (; i < chunks_.size () && chunks_[i] < end; i++)
 321     ret.push_back (chunks_[i]);
 322   ret.push_back (end);
 323   return ret;
 324 }
 325
 326 vsize
 327 Page_breaking::min_system_count (vsize start, vsize end)
 328 {
 329   vector<Break_position> chunks = chunk_list (start, end);
 330   Line_division div = system_count_bounds (chunks, true);
 331   vsize ret = 0;
 332
 333   for (vsize i = 0; i < div.size (); i++)
 334     ret += div[i];
 335   return ret;
 336 }
 337
 338 vsize
 339 Page_breaking::max_system_count (vsize start, vsize end)
 340 {
 341   vector<Break_position> chunks = chunk_list (start, end);
 342   Line_division div = system_count_bounds (chunks, false);
 343   vsize ret = 0;
 344
 345   for (vsize i = 0; i < div.size (); i++)
 346     ret += div[i];
 347   return ret;
 348 }
 349
 350 Page_breaking::Line_division
 351 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
 352 {
 353   assert (chunks.size () >= 2);
 354
 355   Line_division ret;
 356   ret.resize (chunks.size () - 1, 1);
 357
 358   for (vsize i = 0; i + 1 < chunks.size (); i++)
 359     {
 360       vsize sys = next_system (chunks[i]);
 361       if (all_[sys].pscore_)
 362         {
 363           vsize start;
 364           vsize end;
 365           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 366           ret[i] = min
 367             ? line_breaking_[sys].min_system_count (start, end)
 368             : line_breaking_[sys].max_system_count (start, end);
 369         }
 370     }
 371
 372   return ret;
 373 }
 374
 375 vector<Page_breaking::Line_division>
 376 Page_breaking::line_divisions (vsize start,
 377                                vsize end,
 378                                vsize system_count,
 379                                Line_division lower_bound,
 380                                Line_division upper_bound)
 381 {
 382   vector<Break_position> chunks = chunk_list (start, end);
 383
 384   if (!lower_bound.size ())
 385     lower_bound = system_count_bounds (chunks, true);
 386   if (!upper_bound.size ())
 387     upper_bound = system_count_bounds (chunks, false);
 388
 389   assert (lower_bound.size () == chunks.size () - 1);
 390   assert (upper_bound.size () == chunks.size () - 1);
 391
 392   vector<Line_division> ret;
 393   Line_division work_in_progress;
 394
 395   line_divisions_rec (system_count,
 396                       lower_bound,
 397                       upper_bound,
 398                       &ret,
 399                       &work_in_progress);
 400   return ret;
 401 }
 402
 403 void
 404 Page_breaking::line_divisions_rec (vsize system_count,
 405                                    Line_division const &min_sys,
 406                                    Line_division const &max_sys,
 407                                    vector<Line_division > *result,
 408                                    Line_division *cur_division)
 409 {
 410   vsize my_index = cur_division->size ();
 411   vsize others_min = 0;
 412   vsize others_max = 0;
 413
 414   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 415     {
 416       others_min += min_sys[i];
 417       others_max += max_sys[i];
 418     }
 419   others_max = min (others_max, system_count);
 420   vsize real_min = max (min_sys[my_index], system_count - others_max);
 421   vsize real_max = min (max_sys[my_index], system_count - others_min);
 422
 423   if (real_min > real_max || real_min <= 0)
 424     {
 425       /* this should never happen within a recursive call. If it happens
 426          at all, it means that we were called with an unsolvable problem
 427          and we should return an empty result */
 428       assert (my_index == 0);
 429       return;
 430     }
 431
 432   for (vsize i = real_min; i <= real_max; i++)
 433     {
 434       cur_division->push_back (i);
 435       if (my_index == min_sys.size () - 1)
 436         result->push_back (*cur_division);
 437       else
 438         line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
 439       cur_division->pop_back ();
 440     }
 441 }