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