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