lily/page-breaking.cc

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