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