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   assert (n >= min_page_count (configuration, first_page_num));
 691
 692   cache_line_details (configuration);
 693
 694   if (n == 1 && n <= cached_line_details_.size ())
 695     ret = space_systems_on_1_page (cached_line_details_,
 696                                    page_height (first_page_num, is_last ()),
 697                                    ragged () || (is_last () && ragged_last ()));
 698   else if (n == 2 && n <= cached_line_details_.size ())
 699     ret = space_systems_on_2_pages (configuration, first_page_num);
 700   else
 701     {
 702       Page_spacer ps (cached_line_details_, first_page_num, this);
 703       ret = ps.solve (n);
 704     }
 705
 706   return finalize_spacing_result (configuration, ret);
 707 }
 708
 709 Real
 710 Page_breaking::blank_page_penalty () const
 711 {
 712   SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
 713   return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
 714 }
 715
 716 Page_spacing_result
 717 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
 718 {
 719   Page_spacing_result n_res;
 720   Page_spacing_result m_res;
 721
 722   cache_line_details (configuration);
 723   vsize min_p_count = min_page_count (configuration, first_page_num);
 724
 725   if (n == 1)
 726     {
 727       bool rag = ragged () || (is_last () && ragged_last ());
 728       Real height = page_height (first_page_num, is_last ());
 729
 730       if (1 >= min_p_count)
 731         n_res = space_systems_on_1_page (cached_line_details_, height, rag);
 732       if (1 < cached_line_details_.size ())
 733         m_res = space_systems_on_2_pages (configuration, first_page_num);
 734     }
 735   else
 736     {
 737       Page_spacer ps (cached_line_details_, first_page_num, this);
 738
 739       if (n >= min_p_count)
 740         n_res = ps.solve (n);
 741       if (n < cached_line_details_.size ())
 742         m_res = ps.solve (n+1);
 743     }
 744
 745   m_res = finalize_spacing_result (configuration, m_res);
 746   n_res = finalize_spacing_result (configuration, n_res);
 747
 748   Real penalty = blank_page_penalty ();
 749   n_res.demerits_ += penalty;
 750
 751   if (n_res.force_.size ())
 752     n_res.force_.back () += penalty;
 753
 754   return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
 755 }
 756
 757 Page_spacing_result
 758 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
 759 {
 760   vsize min_p_count = min_page_count (configuration, first_page_num);
 761   Real odd_pages_penalty = blank_page_penalty ();
 762
 763   cache_line_details (configuration);
 764   Page_spacer ps (cached_line_details_, first_page_num, this);
 765   Page_spacing_result best = ps.solve (min_p_count);
 766   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
 767   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 768
 769   for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
 770     {
 771       Page_spacing_result cur = ps.solve (i);
 772       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 773       if (cur.demerits_ < best.demerits_)
 774         best = cur;
 775     }
 776
 777   return finalize_spacing_result (configuration, best);
 778 }
 779
 780 Page_spacing_result
 781 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
 782 {
 783   Page_spacing_result res;
 784   vsize page = 0;
 785   vsize page_first_line = 0;
 786   Page_spacing space (page_height (first_page_num, false), page_top_space_);
 787
 788   cache_line_details (configuration);
 789   for (vsize line = 0; line < cached_line_details_.size (); line++)
 790     {
 791       Real prev_force = space.force_;
 792       space.append_system (cached_line_details_[line]);
 793       if ((line > page_first_line)
 794           && (isinf (space.force_)
 795               || ((line > 0)
 796                   && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
 797         {
 798           res.systems_per_page_.push_back (line - page_first_line);
 799           res.force_.push_back (prev_force);
 800           res.penalty_ += cached_line_details_[line-1].page_penalty_;
 801           page++;
 802           space.resize (page_height (first_page_num + page, false));
 803           space.clear ();
 804           space.append_system (cached_line_details_[line]);
 805           page_first_line = line;
 806         }
 807
 808       if (line == cached_line_details_.size () - 1)
 809         {
 810           /* This is the last line */
 811           /* When the last page height was computed, we did not know yet that it
 812            * was the last one. If the systems put on it don't fit anymore, the last
 813            * system is moved to a new page */
 814           space.resize (page_height (first_page_num + page, true));
 815           if ((line > page_first_line) && (isinf (space.force_)))
 816             {
 817               res.systems_per_page_.push_back (line - page_first_line);
 818               res.force_.push_back (prev_force);
 819               /* the last page containing the last line */
 820               space.resize (page_height (first_page_num + page + 1, true));
 821               space.clear ();
 822               space.append_system (cached_line_details_[line]);
 823               res.systems_per_page_.push_back (1);
 824               res.force_.push_back (space.force_);
 825               res.penalty_ += cached_line_details_[line-1].page_penalty_;
 826               res.penalty_ += cached_line_details_[line].page_penalty_;
 827             }
 828           else
 829             {
 830               res.systems_per_page_.push_back (line + 1 - page_first_line);
 831               res.force_.push_back (space.force_);
 832               res.penalty_ += cached_line_details_[line].page_penalty_;
 833             }
 834         }
 835     }
 836   return finalize_spacing_result (configuration, res);
 837 }
 838
 839 /* Calculate demerits and fix res.systems_per_page_ so that
 840    it refers to the original line numbers, not the ones given by compress_lines (). */
 841 Page_spacing_result
 842 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
 843 {
 844   if (res.force_.empty ())
 845     return res;
 846
 847   cache_line_details (configuration);
 848   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
 849
 850   Real line_force = 0;
 851   Real line_penalty = 0;
 852   Real page_force = 0;
 853   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
 854
 855   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
 856     {
 857       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
 858       line_penalty += uncompressed_line_details_[i].break_penalty_;
 859     }
 860
 861   for (vsize i = 0; i < res.force_.size (); i++)
 862     {
 863       Real f = res.force_[i];
 864       if (isinf (f) && res.systems_per_page_[i] == 1)
 865         f = 20000;
 866
 867       page_force += f * f;
 868     }
 869
 870   /* for a while we tried averaging page and line forces across pages instead
 871      of summing them, but it caused a problem: if there is a single page
 872      with a very bad page force (for example because of a forced page break),
 873      the page breaker will put in a _lot_ of pages so that the bad force
 874      becomes averaged out over many pages. */
 875   res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
 876   return res;
 877
 878 }
 879
 880 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
 881    are by far the most common cases, we have special functions for them.
 882
 883    space_systems_on_1_page has a different calling convention than most of the
 884    space_systems functions. This is because space_systems_on_1_page is (unlike
 885    the other space_systems functions) sometimes called on subsets of a full
 886    configuration. */
 887 Page_spacing_result
 888 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
 889 {
 890   Page_spacing space (page_height, page_top_space_);
 891   Page_spacing_result ret;
 892
 893   for (vsize i = 0; i < lines.size (); i++)
 894     space.append_system (lines[i]);
 895
 896   ret.systems_per_page_.push_back (lines.size ());
 897   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
 898   ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 899
 900   /* don't do finalize_spacing_result () because we are only an internal function */
 901   return ret;
 902 }
 903
 904 Page_spacing_result
 905 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
 906 {
 907   Real page1_height = page_height (first_page_num, false);
 908   Real page2_height = page_height (first_page_num + 1, is_last ());
 909   bool ragged1 = ragged ();
 910   bool ragged2 = ragged () || (is_last () && ragged_last ());
 911
 912   /* if there is a forced break, this reduces to 2 1-page problems */
 913   cache_line_details (configuration);
 914   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
 915     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
 916       {
 917         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
 918         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
 919         Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
 920         Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
 921
 922         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
 923         p1.force_.push_back (p2.force_[0]);
 924         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
 925         return p1;
 926       }
 927
 928   vector<Real> page1_force;
 929   vector<Real> page2_force;
 930   Page_spacing page1 (page1_height, page_top_space_);
 931   Page_spacing page2 (page2_height, page_top_space_);
 932
 933   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
 934   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
 935
 936   /* find the page 1 and page 2 forces for each page-breaking position */
 937   for (vsize i = 0; i < page1_force.size (); i++)
 938     {
 939       page1.append_system (cached_line_details_[i]);
 940       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
 941       page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
 942
 943       if (ragged2)
 944         page2_force[page2_force.size () - 1 - i] =
 945           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
 946       else
 947         page2_force[page2_force.size () - 1 - i] = page2.force_;
 948     }
 949
 950   /* find the position that minimises the sum of the page forces */
 951   vsize best_sys_count = 1;
 952   Real best_demerits = infinity_f;
 953   for (vsize i = 0; i < page1_force.size (); i++)
 954     {
 955       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
 956       Real uneven = 2 * (page1_force[i] - page2_force[i]);
 957       Real dem = uneven * uneven + f
 958         + cached_line_details_[i+1].page_penalty_
 959         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
 960       if (dem < best_demerits)
 961         {
 962           best_demerits = dem;
 963           best_sys_count = i+1;
 964         }
 965     }
 966
 967   Page_spacing_result ret;
 968   ret.systems_per_page_.push_back (best_sys_count);
 969   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
 970   ret.force_.push_back (page1_force[best_sys_count-1]);
 971   ret.force_.push_back (page2_force[best_sys_count-1]);
 972   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
 973     + cached_line_details_.back ().page_penalty_
 974     + cached_line_details_.back ().turn_penalty_;
 975
 976   /* don't do finalize_spacing_result () because we are only an internal function */
 977   return ret;
 978 }
 979
 980 bool
 981 Page_breaking::all_lines_stretched (vsize configuration)
 982 {
 983   cache_line_details (configuration);
 984   for (vsize i = 0; i < cached_line_details_.size (); i++)
 985     if (cached_line_details_[i].force_ < 0)
 986       return false;
 987
 988   return true;
 989 }
 990
 991 Page_breaking::Line_division
 992 Page_breaking::current_configuration (vsize configuration_index) const
 993 {
 994   return current_configurations_[configuration_index];
 995 }
 996
 997 bool
 998 Page_breaking::is_last () const
 999 {
1000   return current_end_breakpoint_ == last_break_position ();
1001 }
1002
1003 vsize
1004 Page_breaking::last_break_position () const
1005 {
1006   return breaks_.size () - 1;
1007 }