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