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