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