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