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