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