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
 865       // Don't say that the force is infinite even if it is: if we were told to
 866       // put a certain number of systems on a page then we will, even if it's bad.
 867       res.force_.push_back (min (space.force_, BAD_SPACING_PENALTY));
 868       res.penalty_ += cached_line_details_[line-1].page_penalty_;
 869       page_first_line = line;
 870     }
 871
 872   /* Recalculate forces for the last page because we know now that is
 873      really the last page. */
 874   space.resize (page_height (first_page_num + page, true));
 875   res.force_.back () = min(space.force_, BAD_SPACING_PENALTY);
 876   return finalize_spacing_result (configuration, res);
 877 }
 878
 879 Page_spacing_result
 880 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
 881 {
 882   Page_spacing_result res;
 883   vsize page = 0;
 884   vsize page_first_line = 0;
 885   Page_spacing space (page_height (first_page_num, false), page_top_space_);
 886
 887   cache_line_details (configuration);
 888   for (vsize line = 0; line < cached_line_details_.size (); line++)
 889     {
 890       Real prev_force = space.force_;
 891       space.append_system (cached_line_details_[line]);
 892       if ((line > page_first_line)
 893           && (isinf (space.force_)
 894               || ((line > 0)
 895                   && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
 896         {
 897           res.systems_per_page_.push_back (line - page_first_line);
 898           res.force_.push_back (prev_force);
 899           res.penalty_ += cached_line_details_[line-1].page_penalty_;
 900           page++;
 901           space.resize (page_height (first_page_num + page, false));
 902           space.clear ();
 903           space.append_system (cached_line_details_[line]);
 904           page_first_line = line;
 905         }
 906
 907       if (line == cached_line_details_.size () - 1)
 908         {
 909           /* This is the last line */
 910           /* When the last page height was computed, we did not know yet that it
 911            * was the last one. If the systems put on it don't fit anymore, the last
 912            * system is moved to a new page */
 913           space.resize (page_height (first_page_num + page, true));
 914           if ((line > page_first_line) && (isinf (space.force_)))
 915             {
 916               res.systems_per_page_.push_back (line - page_first_line);
 917               res.force_.push_back (prev_force);
 918               /* the last page containing the last line */
 919               space.resize (page_height (first_page_num + page + 1, true));
 920               space.clear ();
 921               space.append_system (cached_line_details_[line]);
 922               res.systems_per_page_.push_back (1);
 923               res.force_.push_back (space.force_);
 924               res.penalty_ += cached_line_details_[line-1].page_penalty_;
 925               res.penalty_ += cached_line_details_[line].page_penalty_;
 926             }
 927           else
 928             {
 929               res.systems_per_page_.push_back (line + 1 - page_first_line);
 930               res.force_.push_back (space.force_);
 931               res.penalty_ += cached_line_details_[line].page_penalty_;
 932             }
 933         }
 934     }
 935   return finalize_spacing_result (configuration, res);
 936 }
 937
 938 /* Calculate demerits and fix res.systems_per_page_ so that
 939    it refers to the original line numbers, not the ones given by compress_lines (). */
 940 Page_spacing_result
 941 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
 942 {
 943   if (res.force_.empty ())
 944     return res;
 945
 946   cache_line_details (configuration);
 947   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
 948
 949   Real line_force = 0;
 950   Real line_penalty = 0;
 951   Real page_force = 0;
 952   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
 953
 954   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
 955     {
 956       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
 957       line_penalty += uncompressed_line_details_[i].break_penalty_;
 958     }
 959
 960   for (vsize i = 0; i < res.force_.size (); i++)
 961     {
 962       Real f = res.force_[i];
 963       if (isinf (f) && res.systems_per_page_[i] == 1)
 964         f = BAD_SPACING_PENALTY;
 965
 966       page_force += f * f;
 967     }
 968
 969   /* for a while we tried averaging page and line forces across pages instead
 970      of summing them, but it caused a problem: if there is a single page
 971      with a very bad page force (for example because of a forced page break),
 972      the page breaker will put in a _lot_ of pages so that the bad force
 973      becomes averaged out over many pages. */
 974   res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
 975   return res;
 976
 977 }
 978
 979 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
 980    are by far the most common cases, we have special functions for them.
 981
 982    space_systems_on_1_page has a different calling convention than most of the
 983    space_systems functions. This is because space_systems_on_1_page is (unlike
 984    the other space_systems functions) sometimes called on subsets of a full
 985    configuration. */
 986 Page_spacing_result
 987 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
 988 {
 989   Page_spacing space (page_height, page_top_space_);
 990   Page_spacing_result ret;
 991
 992   for (vsize i = 0; i < lines.size (); i++)
 993     space.append_system (lines[i]);
 994
 995   ret.systems_per_page_.push_back (lines.size ());
 996   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
 997   ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 998
 999   /* don't do finalize_spacing_result () because we are only an internal function */
1000   return ret;
1001 }
1002
1003 Page_spacing_result
1004 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1005 {
1006   Real page1_height = page_height (first_page_num, false);
1007   Real page2_height = page_height (first_page_num + 1, is_last ());
1008   bool ragged1 = ragged ();
1009   bool ragged2 = ragged () || (is_last () && ragged_last ());
1010
1011   /* if there is a forced break, this reduces to 2 1-page problems */
1012   cache_line_details (configuration);
1013   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1014     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1015       {
1016         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1017         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1018         Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1019         Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1020
1021         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1022         p1.force_.push_back (p2.force_[0]);
1023         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1024         return p1;
1025       }
1026
1027   vector<Real> page1_force;
1028   vector<Real> page2_force;
1029   Page_spacing page1 (page1_height, page_top_space_);
1030   Page_spacing page2 (page2_height, page_top_space_);
1031
1032   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1033   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1034
1035   /* find the page 1 and page 2 forces for each page-breaking position */
1036   for (vsize i = 0; i < page1_force.size (); i++)
1037     {
1038       page1.append_system (cached_line_details_[i]);
1039       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1040       page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1041
1042       if (ragged2)
1043         page2_force[page2_force.size () - 1 - i] =
1044           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1045       else
1046         page2_force[page2_force.size () - 1 - i] = page2.force_;
1047     }
1048
1049   /* find the position that minimises the sum of the page forces */
1050   vsize best_sys_count = 1;
1051   Real best_demerits = infinity_f;
1052   for (vsize i = 0; i < page1_force.size (); i++)
1053     {
1054       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1055       Real uneven = 2 * (page1_force[i] - page2_force[i]);
1056       Real dem = uneven * uneven + f
1057         + cached_line_details_[i+1].page_penalty_
1058         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1059       if (dem < best_demerits)
1060         {
1061           best_demerits = dem;
1062           best_sys_count = i+1;
1063         }
1064     }
1065
1066   Page_spacing_result ret;
1067   ret.systems_per_page_.push_back (best_sys_count);
1068   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1069   ret.force_.push_back (page1_force[best_sys_count-1]);
1070   ret.force_.push_back (page2_force[best_sys_count-1]);
1071   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1072     + cached_line_details_.back ().page_penalty_
1073     + cached_line_details_.back ().turn_penalty_;
1074
1075   /* don't do finalize_spacing_result () because we are only an internal function */
1076   return ret;
1077 }
1078
1079 bool
1080 Page_breaking::all_lines_stretched (vsize configuration)
1081 {
1082   cache_line_details (configuration);
1083   for (vsize i = 0; i < cached_line_details_.size (); i++)
1084     if (cached_line_details_[i].force_ < 0)
1085       return false;
1086
1087   return true;
1088 }
1089
1090 Page_breaking::Line_division
1091 Page_breaking::current_configuration (vsize configuration_index) const
1092 {
1093   return current_configurations_[configuration_index];
1094 }
1095
1096 bool
1097 Page_breaking::is_last () const
1098 {
1099   return current_end_breakpoint_ == last_break_position ();
1100 }
1101
1102 bool
1103 Page_breaking::ends_score () const
1104 {
1105   return breaks_[current_end_breakpoint_].score_ender_;
1106 }
1107
1108 vsize
1109 Page_breaking::last_break_position () const
1110 {
1111   return breaks_.size () - 1;
1112 }