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 each forbidden page break, merge the systems around it into one
  23    system. */
  24 static vector<Line_details>
  25 compress_lines (const vector<Line_details> &orig)
  26 {
  27   vector<Line_details> ret;
  28
  29   for (vsize i = 0; i < orig.size (); i++)
  30     {
  31       if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
  32         {
  33           Line_details const &old = ret.back ();
  34           Line_details compressed = orig[i];
  35           compressed.extent_[DOWN] = old.extent_[DOWN];
  36           compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
  37           compressed.space_ += old.space_;
  38           compressed.inverse_hooke_ += old.inverse_hooke_;
  39           compressed.title_ = old.title_;
  40
  41           /* we don't need the force_ field for the vertical spacing,
  42              so we use force_ = n to signal that the line was compressed,
  43              reducing the number of lines by n (and force_ = 0 otherwise).
  44              This makes uncompression much easier. */
  45           compressed.force_ = old.force_ + 1;
  46           ret.back () = compressed;
  47         }
  48       else
  49         {
  50           ret.push_back (orig[i]);
  51           ret.back ().force_ = 0;
  52         }
  53     }
  54   return ret;
  55 }
  56
  57 /* translate the number of systems-per-page into something meaningful for
  58    the uncompressed lines.
  59 */
  60 static vector<vsize>
  61 uncompress_solution (vector<vsize> const &systems_per_page,
  62                      vector<Line_details> const &compressed)
  63 {
  64   vector<vsize> ret;
  65   vsize start_sys = 0;
  66
  67   for (vsize i = 0; i < systems_per_page.size (); i++)
  68     {
  69       int compressed_count = 0;
  70       for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
  71         compressed_count += (int)compressed[j].force_;
  72
  73       ret.push_back (systems_per_page[i] + compressed_count);
  74       start_sys += systems_per_page[i];
  75     }
  76   return ret;
  77 }
  78
  79 /* for Page_breaking, the start index (when we are dealing with the stuff
  80    between a pair of breakpoints) refers to the break_ index of the end of
  81    the previous page. So the system index of the start of the current page
  82    could either be the same as the end of the previous page or one more than
  83    it. */
  84
  85 /* Turn a break index into the sys index that starts the next page */
  86 vsize
  87 Page_breaking::next_system (Break_position const &break_pos) const
  88 {
  89   vsize sys = break_pos.system_spec_index_;
  90
  91   if (sys == VPOS) /* beginning of the book */
  92     return 0;
  93   if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
  94     return sys; /* the score overflows the previous page */
  95   return sys + 1; /* this page starts with a new System_spec */
  96 }
  97
  98 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
  99 {
 100   book_ = pb;
 101   system_count_ = 0;
 102   ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
 103   ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
 104   page_top_space_ = robust_scm2double (pb->paper_->c_variable ("page-top-space"), 0);
 105   create_system_list ();
 106   find_chunks_and_breaks (is_break);
 107 }
 108
 109 Page_breaking::~Page_breaking ()
 110 {
 111 }
 112
 113 bool
 114 Page_breaking::ragged () const
 115 {
 116   return ragged_;
 117 }
 118
 119 bool
 120 Page_breaking::ragged_last () const
 121 {
 122   return ragged_last_;
 123 }
 124
 125 Real
 126 Page_breaking::page_top_space () const
 127 {
 128   return page_top_space_;
 129 }
 130
 131 vsize
 132 Page_breaking::system_count () const
 133 {
 134   return system_count_;
 135 }
 136
 137 /* translate indices into breaks_ into start-end parameters for the line breaker */
 138 void
 139 Page_breaking::line_breaker_args (vsize sys,
 140                                   Break_position const &start,
 141                                   Break_position const &end,
 142                                   vsize *line_breaker_start,
 143                                   vsize *line_breaker_end)
 144 {
 145   assert (system_specs_[sys].pscore_);
 146   assert (next_system (start) <= sys && sys <= end.system_spec_index_);
 147
 148   if (start.system_spec_index_ == sys)
 149     *line_breaker_start = start.score_break_;
 150   else
 151     *line_breaker_start = 0;
 152
 153   if (end.system_spec_index_ == sys)
 154     *line_breaker_end = end.score_break_;
 155   else
 156     *line_breaker_end = VPOS;
 157 }
 158
 159 void
 160 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
 161                                   Line_division const &div)
 162 {
 163   vector<Break_position> chunks = chunk_list (start_break, end_break);
 164   bool ignore_div = false;
 165   if (chunks.size () != div.size () + 1)
 166     {
 167       programming_error ("did not find a valid page breaking configuration");
 168       ignore_div = true;
 169     }
 170
 171   for (vsize i = 0; i + 1 < chunks.size (); i++)
 172     {
 173       vsize sys = next_system (chunks[i]);
 174       if (system_specs_[sys].pscore_)
 175         {
 176           vsize start;
 177           vsize end;
 178           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 179
 180           vector<Column_x_positions> pos = ignore_div
 181             ? line_breaking_[sys].best_solution (start, end)
 182             : line_breaking_[sys].solve (start, end, div[i]);
 183           system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
 184         }
 185     }
 186 }
 187
 188 SCM
 189 Page_breaking::systems ()
 190 {
 191   SCM ret = SCM_EOL;
 192   for (vsize sys = 0; sys < system_specs_.size (); sys++)
 193     {
 194       if (system_specs_[sys].pscore_)
 195         {
 196           system_specs_[sys].pscore_->root_system ()
 197             ->do_break_substitution_and_fixup_refpoints ();
 198           SCM lines = system_specs_[sys].pscore_->root_system ()
 199             ->get_broken_system_grobs ();
 200           ret = scm_cons (lines, ret);
 201         }
 202       else
 203         {
 204           Prob *pb = system_specs_[sys].prob_;
 205           ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
 206           pb->unprotect ();
 207         }
 208     }
 209   return scm_append (scm_reverse (ret));
 210 }
 211
 212 Real
 213 Page_breaking::page_height (int page_num, bool last) const
 214 {
 215   bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
 216   SCM mod = scm_c_resolve_module ("scm page");
 217   SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
 218   SCM make_page = scm_c_module_lookup (mod, "make-page");
 219
 220   calc_height = scm_variable_ref (calc_height);
 221   make_page = scm_variable_ref (make_page);
 222
 223   SCM page = scm_apply_0 (make_page, scm_list_n (
 224                   book_->self_scm (),
 225                   ly_symbol2scm ("page-number"), scm_from_int (page_num),
 226                   ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
 227                   ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
 228                   SCM_UNDEFINED));
 229   SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
 230   return scm_to_double (height) - page_top_space_;
 231 }
 232
 233 SCM
 234 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
 235 {
 236   Break_position const &pos = breaks_[breakpoint];
 237
 238   if (pos.system_spec_index_ == VPOS)
 239     return SCM_EOL;
 240   if (system_specs_[pos.system_spec_index_].pscore_)
 241     return pos.col_->get_property (str);
 242   return system_specs_[pos.system_spec_index_].prob_->get_property (str);
 243 }
 244
 245 SCM
 246 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
 247 {
 248   SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
 249   SCM page_module = scm_c_resolve_module ("scm page");
 250
 251   SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
 252   SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
 253   make_page = scm_variable_ref (make_page);
 254   page_stencil = scm_variable_ref (page_stencil);
 255
 256   SCM book = book_->self_scm ();
 257   int first_page_number
 258     = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
 259   bool last_bookpart = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
 260   SCM ret = SCM_EOL;
 261   SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
 262   if (label_page_table == SCM_UNDEFINED)
 263     label_page_table = SCM_EOL;
 264
 265   for (vsize i = 0; i < lines_per_page.size (); i++)
 266     {
 267       SCM page_num = scm_from_int (i + first_page_number);
 268       bool partbook_last_page = (i == lines_per_page.size () - 1);
 269       SCM rag = scm_from_bool (ragged () || ( partbook_last_page && ragged_last ()));
 270       SCM line_count = scm_from_int (lines_per_page[i]);
 271       SCM lines = scm_list_head (systems, line_count);
 272       SCM page = scm_apply_0 (make_page,
 273                               scm_list_n (book, lines, page_num, rag,
 274                                           scm_from_bool (last_bookpart),
 275                                           scm_from_bool (partbook_last_page),
 276                                           SCM_UNDEFINED));
 277       /* collect labels */
 278       for (SCM l = lines ; scm_is_pair (l)  ; l = scm_cdr (l))
 279         {
 280           SCM labels = SCM_EOL;
 281           if (Grob * line = unsmob_grob (scm_car (l)))
 282             {
 283               System *system = dynamic_cast<System*> (line);
 284               labels = system->get_property ("labels");
 285             }
 286           else if (Prob *prob = unsmob_prob (scm_car (l)))
 287             labels = prob->get_property ("labels");
 288
 289           for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
 290             label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
 291                                          label_page_table);
 292         }
 293
 294       scm_apply_1 (page_stencil, page, SCM_EOL);
 295       ret = scm_cons (page, ret);
 296       systems = scm_list_tail (systems, line_count);
 297     }
 298   book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
 299   ret = scm_reverse (ret);
 300   return ret;
 301 }
 302
 303 /* The page-turn-page-breaker needs to have a line-breaker between any two
 304    columns with non-NULL page-turn-permission.
 305
 306    The optimal-breaker needs to have a line-breaker between any two columns
 307    with page-break-permission = 'force.
 308
 309    By using a grob predicate, we can accommodate both of these uses.
 310 */
 311 void
 312 Page_breaking::create_system_list ()
 313 {
 314   SCM specs = book_->get_system_specs ();
 315   for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
 316     {
 317       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
 318         {
 319           SCM system_count = ps->layout ()->c_variable ("system-count");
 320
 321           if (scm_is_number (system_count))
 322             s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
 323                                         scm_vector_to_list (ps->get_paper_systems ()),
 324                                         scm_cdr (s)));
 325           else
 326             system_specs_.push_back (System_spec (ps));
 327         }
 328       else
 329         {
 330           Prob *pb = unsmob_prob (scm_car (s));
 331           assert (pb);
 332
 333           pb->protect ();
 334           system_specs_.push_back (System_spec (pb));
 335         }
 336     }
 337 }
 338
 339 void
 340 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
 341 {
 342   SCM force_sym = ly_symbol2scm ("force");
 343
 344   chunks_.push_back (Break_position ());
 345   breaks_.push_back (Break_position ());
 346
 347   for (vsize i = 0; i < system_specs_.size (); i++)
 348     {
 349       if (system_specs_[i].pscore_)
 350         {
 351           vector<Grob*> cols
 352             = system_specs_[i].pscore_->root_system ()->used_columns ();
 353           vector<vsize> line_breaker_columns;
 354           line_breaker_columns.push_back (0);
 355
 356           for (vsize j = 1; j < cols.size (); j++)
 357             {
 358               bool last = (j == cols.size () - 1);
 359               bool break_point = is_break (cols[j]);
 360               bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
 361               Break_position cur_pos = Break_position (i,
 362                                                        line_breaker_columns.size (),
 363                                                        cols[j],
 364                                                        last);
 365
 366               if (break_point || (i == system_specs_.size () - 1 && last))
 367                 breaks_.push_back (cur_pos);
 368               if (chunk_end || last)
 369                 chunks_.push_back (cur_pos);
 370
 371               if ((break_point || chunk_end) && !last)
 372                 line_breaker_columns.push_back (j);
 373             }
 374           line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
 375         }
 376       else
 377         {
 378           /* TODO: we want some way of applying Break_p to a prob? */
 379           if (i == system_specs_.size () - 1)
 380             breaks_.push_back (Break_position (i));
 381
 382           chunks_.push_back (Break_position (i));
 383
 384           /* FIXME: shouldn't we push a Null_breaker or similar dummy
 385              class? --hwn */
 386           line_breaking_.push_back (Constrained_breaking (NULL));
 387         }
 388     }
 389 }
 390
 391 vector<Break_position>
 392 Page_breaking::chunk_list (vsize start_index, vsize end_index)
 393 {
 394   Break_position start = breaks_[start_index];
 395   Break_position end = breaks_[end_index];
 396
 397   vsize i = 0;
 398   for (; i < chunks_.size () && chunks_[i] <= start; i++)
 399     ;
 400
 401   vector<Break_position> ret;
 402   ret.push_back (start);
 403   for (; i < chunks_.size () && chunks_[i] < end; i++)
 404     ret.push_back (chunks_[i]);
 405   ret.push_back (end);
 406   return ret;
 407 }
 408
 409 vsize
 410 Page_breaking::min_system_count (vsize start, vsize end)
 411 {
 412   vector<Break_position> chunks = chunk_list (start, end);
 413   Line_division div = system_count_bounds (chunks, true);
 414   vsize ret = 0;
 415
 416   for (vsize i = 0; i < div.size (); i++)
 417     ret += div[i];
 418   return ret;
 419 }
 420
 421 vsize
 422 Page_breaking::max_system_count (vsize start, vsize end)
 423 {
 424   vector<Break_position> chunks = chunk_list (start, end);
 425   Line_division div = system_count_bounds (chunks, false);
 426   vsize ret = 0;
 427
 428   for (vsize i = 0; i < div.size (); i++)
 429     ret += div[i];
 430   return ret;
 431 }
 432
 433 Page_breaking::Line_division
 434 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
 435                                     bool min)
 436 {
 437   assert (chunks.size () >= 2);
 438
 439   Line_division ret;
 440   ret.resize (chunks.size () - 1, 1);
 441
 442   for (vsize i = 0; i + 1 < chunks.size (); i++)
 443     {
 444       vsize sys = next_system (chunks[i]);
 445       if (system_specs_[sys].pscore_)
 446         {
 447           vsize start;
 448           vsize end;
 449           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 450           ret[i] = min
 451             ? line_breaking_[sys].min_system_count (start, end)
 452             : line_breaking_[sys].max_system_count (start, end);
 453         }
 454     }
 455
 456   return ret;
 457 }
 458
 459 void
 460 Page_breaking::set_current_breakpoints (vsize start,
 461                                         vsize end,
 462                                         vsize system_count,
 463                                         Line_division lower_bound,
 464                                         Line_division upper_bound)
 465 {
 466   system_count_ = system_count;
 467   current_chunks_ = chunk_list (start, end);
 468   current_start_breakpoint_ = start;
 469   current_end_breakpoint_ = end;
 470   clear_line_details_cache ();
 471
 472   if (!lower_bound.size ())
 473     lower_bound = system_count_bounds (current_chunks_, true);
 474   if (!upper_bound.size ())
 475     upper_bound = system_count_bounds (current_chunks_, false);
 476
 477   assert (lower_bound.size () == current_chunks_.size () - 1);
 478   assert (upper_bound.size () == current_chunks_.size () - 1);
 479
 480   Line_division work_in_progress;
 481   current_configurations_.clear ();
 482   line_divisions_rec (system_count,
 483                       lower_bound,
 484                       upper_bound,
 485                       &work_in_progress);
 486
 487   /* we only consider a constant number of configurations. Otherwise,
 488      this becomes slow when there are many small scores. The constant
 489      5 is somewhat arbitrary. */
 490   if (current_configurations_.size () > 5)
 491     {
 492       vector<pair<Real,vsize> > dems_and_indices;
 493
 494       for (vsize i = 0; i < current_configurations_.size (); i++)
 495         {
 496           cache_line_details (i);
 497           Real dem = 0;
 498           for (vsize j = 0; j < cached_line_details_.size (); j++)
 499             dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
 500               + cached_line_details_[j].break_penalty_;
 501
 502           dems_and_indices.push_back (pair<Real,vsize> (dem, i));
 503         }
 504       vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
 505
 506       vector<Line_division> best_5_configurations;
 507       for (vsize i = 0; i < 5; i++)
 508         best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
 509
 510       clear_line_details_cache ();
 511       current_configurations_ = best_5_configurations;
 512     }
 513 }
 514
 515 void
 516 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
 517 {
 518   current_chunks_ = chunk_list (start, end);
 519   current_start_breakpoint_ = start;
 520   current_end_breakpoint_ = end;
 521   clear_line_details_cache ();
 522   system_count_ = 0;
 523
 524   Line_division div;
 525   for (vsize i = 0; i+1 < current_chunks_.size (); i++)
 526     {
 527       vsize sys = next_system (current_chunks_[i]);
 528       if (system_specs_[sys].pscore_)
 529         {
 530           line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
 531           div.push_back (line_breaking_[sys].best_solution (start, end).size ());
 532         }
 533       else
 534         div.push_back (1);
 535
 536       system_count_ += div.back ();
 537     }
 538   current_configurations_.clear ();
 539   current_configurations_.push_back (div);
 540 }
 541
 542 vsize
 543 Page_breaking::current_configuration_count () const
 544 {
 545   return current_configurations_.size ();
 546 }
 547
 548 void
 549 Page_breaking::cache_line_details (vsize configuration_index)
 550 {
 551   if (cached_configuration_index_ != configuration_index)
 552     {
 553       cached_configuration_index_ = configuration_index;
 554       SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
 555       if (!scm_is_number (padding_scm))
 556         padding_scm = book_->paper_->c_variable ("between-system-padding");
 557       Real padding = robust_scm2double (padding_scm, 0.0);
 558
 559       Line_division &div = current_configurations_[configuration_index];
 560       uncompressed_line_details_.clear ();
 561       for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
 562         {
 563           vsize sys = next_system (current_chunks_[i]);
 564           if (system_specs_[sys].pscore_)
 565             {
 566               vsize start;
 567               vsize end;
 568               line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
 569
 570               vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
 571               uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
 572             }
 573           else
 574             {
 575               assert (div[i] == 1);
 576               uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
 577               uncompressed_line_details_.back ().padding_ =
 578                 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
 579                                    padding);
 580             }
 581         }
 582       cached_line_details_ = compress_lines (uncompressed_line_details_);
 583     }
 584 }
 585
 586 void
 587 Page_breaking::clear_line_details_cache ()
 588 {
 589   cached_configuration_index_ = VPOS;
 590   cached_line_details_.clear ();
 591   uncompressed_line_details_.clear ();
 592 }
 593
 594 void
 595 Page_breaking::line_divisions_rec (vsize system_count,
 596                                    Line_division const &min_sys,
 597                                    Line_division const &max_sys,
 598                                    Line_division *cur_division)
 599 {
 600   vsize my_index = cur_division->size ();
 601   vsize others_min = 0;
 602   vsize others_max = 0;
 603
 604   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 605     {
 606       others_min += min_sys[i];
 607       others_max += max_sys[i];
 608     }
 609   others_max = min (others_max, system_count);
 610   vsize real_min = max (min_sys[my_index], system_count - others_max);
 611   vsize real_max = min (max_sys[my_index], system_count - others_min);
 612
 613   if (real_min > real_max || real_min <= 0)
 614     {
 615       /* this should never happen within a recursive call. If it happens
 616          at all, it means that we were called with an unsolvable problem
 617          and we should return an empty result */
 618       assert (my_index == 0);
 619       return;
 620     }
 621
 622   for (vsize i = real_min; i <= real_max; i++)
 623     {
 624       cur_division->push_back (i);
 625       if (my_index == min_sys.size () - 1)
 626         current_configurations_.push_back (*cur_division);
 627       else
 628         line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
 629       cur_division->pop_back ();
 630     }
 631 }
 632
 633 vsize
 634 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
 635 {
 636   vsize ret = 1;
 637   Real cur_rod_height = 0;
 638   Real cur_spring_height = 0;
 639   Real cur_page_height = page_height (first_page_num, false);
 640
 641   cache_line_details (configuration);
 642   for (vsize i = 0; i < cached_line_details_.size (); i++)
 643     {
 644       Real ext_len = cached_line_details_[i].extent_.length ();
 645       Real next_rod_height = cur_rod_height + ext_len
 646         + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
 647       Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
 648       Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
 649
 650
 651       if ((next_height > cur_page_height && cur_rod_height > 0)
 652           || (i > 0
 653               && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
 654         {
 655           cur_rod_height = ext_len;
 656           cur_spring_height = cached_line_details_[i].space_;
 657           cur_page_height = page_height (first_page_num + ret, false);
 658           ret++;
 659         }
 660       else
 661         {
 662           cur_rod_height = next_rod_height;
 663           cur_spring_height = next_spring_height;
 664         }
 665     }
 666
 667   /* there are two potential problems with the last page (because we didn't know
 668      it was the last page until after we managed to fit all the systems to it):
 669      - we are ragged-last but the last page has a compressed spring
 670      - the value returned by page_height (num, true) is smaller than the
 671        value returned by page_height (num, false) and it causes the page not to
 672        fit.
 673
 674      In either case, we just need to add one more page. This is because the last
 675      line will always fit on the extra page and by adding one more page to the
 676      end, the previous page is no longer the last page, so our previous
 677      calculations that treated it as a non-last page were ok.
 678   */
 679
 680   cur_page_height = page_height (first_page_num + ret - 1, true);
 681   Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
 682   if (cur_height > cur_page_height
 683       /* don't increase the page count if the last page had only one system */
 684       && cur_rod_height > cached_line_details_.back ().extent_.length ())
 685     ret++;
 686
 687   assert (ret <= cached_line_details_.size ());
 688   return ret;
 689 }
 690
 691 Page_spacing_result
 692 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
 693 {
 694   Page_spacing_result ret;
 695
 696   cache_line_details (configuration);
 697   bool valid_n = (n >= min_page_count (configuration, first_page_num)
 698                   && n <= cached_line_details_.size ());
 699
 700   if (!valid_n)
 701     programming_error ("number of pages is out of bounds");
 702
 703   if (n == 1 && valid_n)
 704     ret = space_systems_on_1_page (cached_line_details_,
 705                                    page_height (first_page_num, is_last ()),
 706                                    ragged () || (is_last () && ragged_last ()));
 707   else if (n == 2 && valid_n)
 708     ret = space_systems_on_2_pages (configuration, first_page_num);
 709   else
 710     {
 711       Page_spacer ps (cached_line_details_, first_page_num, this);
 712       ret = ps.solve (n);
 713     }
 714
 715   return finalize_spacing_result (configuration, ret);
 716 }
 717
 718 Real
 719 Page_breaking::blank_page_penalty () const
 720 {
 721   SCM penalty_sym;
 722
 723   if (is_last ())
 724     penalty_sym = ly_symbol2scm ("blank-last-page-force");
 725   else if (ends_score ())
 726     penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
 727   else
 728     penalty_sym = ly_symbol2scm ("blank-page-force");
 729
 730   Break_position const &pos = breaks_[current_end_breakpoint_];
 731   if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
 732     return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
 733
 734   return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
 735 }
 736
 737 Page_spacing_result
 738 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
 739 {
 740   Page_spacing_result n_res;
 741   Page_spacing_result m_res;
 742
 743   cache_line_details (configuration);
 744   vsize min_p_count = min_page_count (configuration, first_page_num);
 745   bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
 746
 747   if (!valid_n)
 748     programming_error ("both page counts are out of bounds");
 749
 750   if (n == 1 && valid_n)
 751     {
 752       bool rag = ragged () || (is_last () && ragged_last ());
 753       Real height = page_height (first_page_num, is_last ());
 754
 755       if (1 >= min_p_count)
 756         n_res = space_systems_on_1_page (cached_line_details_, height, rag);
 757       if (1 < cached_line_details_.size ())
 758         m_res = space_systems_on_2_pages (configuration, first_page_num);
 759     }
 760   else
 761     {
 762       Page_spacer ps (cached_line_details_, first_page_num, this);
 763
 764       if (n >= min_p_count || !valid_n)
 765         n_res = ps.solve (n);
 766       if (n < cached_line_details_.size () || !valid_n)
 767         m_res = ps.solve (n+1);
 768     }
 769
 770   m_res = finalize_spacing_result (configuration, m_res);
 771   n_res = finalize_spacing_result (configuration, n_res);
 772
 773   Real penalty = blank_page_penalty ();
 774   n_res.demerits_ += penalty;
 775
 776   if (n_res.force_.size ())
 777     n_res.force_.back () += penalty;
 778
 779   return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
 780 }
 781
 782 Page_spacing_result
 783 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
 784 {
 785   vsize min_p_count = min_page_count (configuration, first_page_num);
 786   Real odd_pages_penalty = blank_page_penalty ();
 787
 788   cache_line_details (configuration);
 789   Page_spacer ps (cached_line_details_, first_page_num, this);
 790   Page_spacing_result best = ps.solve (min_p_count);
 791   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
 792   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 793
 794   for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
 795     {
 796       Page_spacing_result cur = ps.solve (i);
 797       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 798       if (cur.demerits_ < best.demerits_)
 799         best = cur;
 800     }
 801
 802   return finalize_spacing_result (configuration, best);
 803 }
 804
 805 Page_spacing_result
 806 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
 807 {
 808   Page_spacing_result res;
 809   vsize page = 0;
 810   vsize page_first_line = 0;
 811   Page_spacing space (page_height (first_page_num, false), page_top_space_);
 812
 813   cache_line_details (configuration);
 814   for (vsize line = 0; line < cached_line_details_.size (); line++)
 815     {
 816       Real prev_force = space.force_;
 817       space.append_system (cached_line_details_[line]);
 818       if ((line > page_first_line)
 819           && (isinf (space.force_)
 820               || ((line > 0)
 821                   && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
 822         {
 823           res.systems_per_page_.push_back (line - page_first_line);
 824           res.force_.push_back (prev_force);
 825           res.penalty_ += cached_line_details_[line-1].page_penalty_;
 826           page++;
 827           space.resize (page_height (first_page_num + page, false));
 828           space.clear ();
 829           space.append_system (cached_line_details_[line]);
 830           page_first_line = line;
 831         }
 832
 833       if (line == cached_line_details_.size () - 1)
 834         {
 835           /* This is the last line */
 836           /* When the last page height was computed, we did not know yet that it
 837            * was the last one. If the systems put on it don't fit anymore, the last
 838            * system is moved to a new page */
 839           space.resize (page_height (first_page_num + page, true));
 840           if ((line > page_first_line) && (isinf (space.force_)))
 841             {
 842               res.systems_per_page_.push_back (line - page_first_line);
 843               res.force_.push_back (prev_force);
 844               /* the last page containing the last line */
 845               space.resize (page_height (first_page_num + page + 1, true));
 846               space.clear ();
 847               space.append_system (cached_line_details_[line]);
 848               res.systems_per_page_.push_back (1);
 849               res.force_.push_back (space.force_);
 850               res.penalty_ += cached_line_details_[line-1].page_penalty_;
 851               res.penalty_ += cached_line_details_[line].page_penalty_;
 852             }
 853           else
 854             {
 855               res.systems_per_page_.push_back (line + 1 - page_first_line);
 856               res.force_.push_back (space.force_);
 857               res.penalty_ += cached_line_details_[line].page_penalty_;
 858             }
 859         }
 860     }
 861   return finalize_spacing_result (configuration, res);
 862 }
 863
 864 /* Calculate demerits and fix res.systems_per_page_ so that
 865    it refers to the original line numbers, not the ones given by compress_lines (). */
 866 Page_spacing_result
 867 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
 868 {
 869   if (res.force_.empty ())
 870     return res;
 871
 872   cache_line_details (configuration);
 873   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
 874
 875   Real line_force = 0;
 876   Real line_penalty = 0;
 877   Real page_force = 0;
 878   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
 879
 880   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
 881     {
 882       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
 883       line_penalty += uncompressed_line_details_[i].break_penalty_;
 884     }
 885
 886   for (vsize i = 0; i < res.force_.size (); i++)
 887     {
 888       Real f = res.force_[i];
 889       if (isinf (f) && res.systems_per_page_[i] == 1)
 890         f = 20000;
 891
 892       page_force += f * f;
 893     }
 894
 895   /* for a while we tried averaging page and line forces across pages instead
 896      of summing them, but it caused a problem: if there is a single page
 897      with a very bad page force (for example because of a forced page break),
 898      the page breaker will put in a _lot_ of pages so that the bad force
 899      becomes averaged out over many pages. */
 900   res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
 901   return res;
 902
 903 }
 904
 905 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
 906    are by far the most common cases, we have special functions for them.
 907
 908    space_systems_on_1_page has a different calling convention than most of the
 909    space_systems functions. This is because space_systems_on_1_page is (unlike
 910    the other space_systems functions) sometimes called on subsets of a full
 911    configuration. */
 912 Page_spacing_result
 913 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
 914 {
 915   Page_spacing space (page_height, page_top_space_);
 916   Page_spacing_result ret;
 917
 918   for (vsize i = 0; i < lines.size (); i++)
 919     space.append_system (lines[i]);
 920
 921   ret.systems_per_page_.push_back (lines.size ());
 922   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
 923   ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 924
 925   /* don't do finalize_spacing_result () because we are only an internal function */
 926   return ret;
 927 }
 928
 929 Page_spacing_result
 930 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
 931 {
 932   Real page1_height = page_height (first_page_num, false);
 933   Real page2_height = page_height (first_page_num + 1, is_last ());
 934   bool ragged1 = ragged ();
 935   bool ragged2 = ragged () || (is_last () && ragged_last ());
 936
 937   /* if there is a forced break, this reduces to 2 1-page problems */
 938   cache_line_details (configuration);
 939   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
 940     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
 941       {
 942         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
 943         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
 944         Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
 945         Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
 946
 947         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
 948         p1.force_.push_back (p2.force_[0]);
 949         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
 950         return p1;
 951       }
 952
 953   vector<Real> page1_force;
 954   vector<Real> page2_force;
 955   Page_spacing page1 (page1_height, page_top_space_);
 956   Page_spacing page2 (page2_height, page_top_space_);
 957
 958   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
 959   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
 960
 961   /* find the page 1 and page 2 forces for each page-breaking position */
 962   for (vsize i = 0; i < page1_force.size (); i++)
 963     {
 964       page1.append_system (cached_line_details_[i]);
 965       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
 966       page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
 967
 968       if (ragged2)
 969         page2_force[page2_force.size () - 1 - i] =
 970           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
 971       else
 972         page2_force[page2_force.size () - 1 - i] = page2.force_;
 973     }
 974
 975   /* find the position that minimises the sum of the page forces */
 976   vsize best_sys_count = 1;
 977   Real best_demerits = infinity_f;
 978   for (vsize i = 0; i < page1_force.size (); i++)
 979     {
 980       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
 981       Real uneven = 2 * (page1_force[i] - page2_force[i]);
 982       Real dem = uneven * uneven + f
 983         + cached_line_details_[i+1].page_penalty_
 984         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
 985       if (dem < best_demerits)
 986         {
 987           best_demerits = dem;
 988           best_sys_count = i+1;
 989         }
 990     }
 991
 992   Page_spacing_result ret;
 993   ret.systems_per_page_.push_back (best_sys_count);
 994   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
 995   ret.force_.push_back (page1_force[best_sys_count-1]);
 996   ret.force_.push_back (page2_force[best_sys_count-1]);
 997   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
 998     + cached_line_details_.back ().page_penalty_
 999     + cached_line_details_.back ().turn_penalty_;
1000
1001   /* don't do finalize_spacing_result () because we are only an internal function */
1002   return ret;
1003 }
1004
1005 bool
1006 Page_breaking::all_lines_stretched (vsize configuration)
1007 {
1008   cache_line_details (configuration);
1009   for (vsize i = 0; i < cached_line_details_.size (); i++)
1010     if (cached_line_details_[i].force_ < 0)
1011       return false;
1012
1013   return true;
1014 }
1015
1016 Page_breaking::Line_division
1017 Page_breaking::current_configuration (vsize configuration_index) const
1018 {
1019   return current_configurations_[configuration_index];
1020 }
1021
1022 bool
1023 Page_breaking::is_last () const
1024 {
1025   return current_end_breakpoint_ == last_break_position ();
1026 }
1027
1028 bool
1029 Page_breaking::ends_score () const
1030 {
1031   return breaks_[current_end_breakpoint_].score_ender_;
1032 }
1033
1034 vsize
1035 Page_breaking::last_break_position () const
1036 {
1037   return breaks_.size () - 1;
1038 }