lily/page-breaking.cc

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