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