lily/page-breaking.cc

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