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