lily/page-breaking.cc

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