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