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