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       SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
 530       if (!scm_is_number (padding_scm))
 531         padding_scm = book_->paper_->c_variable ("between-system-padding");
 532       Real padding = robust_scm2double (padding_scm, 0.0);
 533
 534       Line_division &div = current_configurations_[configuration_index];
 535       uncompressed_line_details_.clear ();
 536       for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
 537         {
 538           vsize sys = next_system (current_chunks_[i]);
 539           if (system_specs_[sys].pscore_)
 540             {
 541               vsize start;
 542               vsize end;
 543               line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
 544
 545               vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
 546               uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
 547             }
 548           else
 549             {
 550               assert (div[i] == 1);
 551               uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
 552               uncompressed_line_details_.back ().padding_ = padding;
 553             }
 554         }
 555       cached_line_details_ = compress_lines (uncompressed_line_details_);
 556     }
 557 }
 558
 559 void
 560 Page_breaking::clear_line_details_cache ()
 561 {
 562   cached_configuration_index_ = VPOS;
 563   cached_line_details_.clear ();
 564   uncompressed_line_details_.clear ();
 565 }
 566
 567 void
 568 Page_breaking::line_divisions_rec (vsize system_count,
 569                                    Line_division const &min_sys,
 570                                    Line_division const &max_sys,
 571                                    Line_division *cur_division)
 572 {
 573   vsize my_index = cur_division->size ();
 574   vsize others_min = 0;
 575   vsize others_max = 0;
 576
 577   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 578     {
 579       others_min += min_sys[i];
 580       others_max += max_sys[i];
 581     }
 582   others_max = min (others_max, system_count);
 583   vsize real_min = max (min_sys[my_index], system_count - others_max);
 584   vsize real_max = min (max_sys[my_index], system_count - others_min);
 585
 586   if (real_min > real_max || real_min <= 0)
 587     {
 588       /* this should never happen within a recursive call. If it happens
 589          at all, it means that we were called with an unsolvable problem
 590          and we should return an empty result */
 591       assert (my_index == 0);
 592       return;
 593     }
 594
 595   for (vsize i = real_min; i <= real_max; i++)
 596     {
 597       cur_division->push_back (i);
 598       if (my_index == min_sys.size () - 1)
 599         current_configurations_.push_back (*cur_division);
 600       else
 601         line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
 602       cur_division->pop_back ();
 603     }
 604 }
 605
 606 vsize
 607 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
 608 {
 609   vsize ret = 1;
 610   Real cur_rod_height = 0;
 611   Real cur_spring_height = 0;
 612   Real cur_page_height = page_height (first_page_num, false);
 613
 614   cache_line_details (configuration);
 615   for (vsize i = 0; i < cached_line_details_.size (); i++)
 616     {
 617       Real ext_len = cached_line_details_[i].extent_.length ();
 618       Real next_rod_height = cur_rod_height + ext_len
 619         + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
 620       Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
 621       Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
 622
 623
 624       if ((next_height > cur_page_height && cur_rod_height > 0)
 625           || (i > 0
 626               && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
 627         {
 628           cur_rod_height = ext_len;
 629           cur_spring_height = line_space (cached_line_details_[i]);
 630           cur_page_height = page_height (first_page_num + ret, false);
 631           ret++;
 632         }
 633       else
 634         {
 635           cur_rod_height = next_rod_height;
 636           cur_spring_height = next_spring_height;
 637         }
 638     }
 639
 640   /* there are two potential problems with the last page (because we didn't know
 641      it was the last page until after we managed to fit all the systems to it):
 642      - we are ragged-last but the last page has a compressed spring
 643      - the value returned by page_height (num, true) is smaller than the
 644        value returned by page_height (num, false) and it causes the page not to
 645        fit.
 646
 647      In either case, we just need to add one more page. This is because the last
 648      line will always fit on the extra page and by adding one more page to the
 649      end, the previous page is no longer the last page, so our previous
 650      calculations that treated it as a non-last page were ok.
 651   */
 652
 653   cur_page_height = page_height (first_page_num + ret - 1, true);
 654   Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
 655   if (cur_height > cur_page_height
 656       /* don't increase the page count if the last page had only one system */
 657       && cur_rod_height > cached_line_details_.back ().extent_.length ())
 658     ret++;
 659
 660   assert (ret <= cached_line_details_.size ());
 661   return ret;
 662 }
 663
 664 Page_spacing_result
 665 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
 666 {
 667   Page_spacing_result ret;
 668   assert (n >= min_page_count (configuration, first_page_num));
 669
 670   cache_line_details (configuration);
 671   if (n > cached_line_details_.size ())
 672     return Page_spacing_result ();
 673   if (n == 1)
 674     ret = space_systems_on_1_page (cached_line_details_,
 675                                    page_height (first_page_num, is_last ()),
 676                                    ragged () || (is_last () && ragged_last ()));
 677   else if (n == 2)
 678     ret = space_systems_on_2_pages (configuration, first_page_num);
 679   else
 680     {
 681       Page_spacer ps (cached_line_details_, first_page_num, this);
 682       ret = ps.solve (n);
 683     }
 684
 685   return finalize_spacing_result (configuration, ret);
 686 }
 687
 688 Real
 689 Page_breaking::blank_page_penalty () const
 690 {
 691   SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
 692   return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
 693 }
 694
 695 Page_spacing_result
 696 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
 697 {
 698   Page_spacing_result n_res;
 699   Page_spacing_result m_res;
 700
 701   cache_line_details (configuration);
 702   vsize min_p_count = min_page_count (configuration, first_page_num);
 703
 704   if (n == 1)
 705     {
 706       bool rag = ragged () || (is_last () && ragged_last ());
 707       Real height = page_height (first_page_num, is_last ());
 708
 709       if (1 >= min_p_count)
 710         n_res = space_systems_on_1_page (cached_line_details_, height, rag);
 711       if (1 < cached_line_details_.size ())
 712         m_res = space_systems_on_2_pages (configuration, first_page_num);
 713     }
 714   else
 715     {
 716       Page_spacer ps (cached_line_details_, first_page_num, this);
 717
 718       if (n >= min_p_count)
 719         n_res = ps.solve (n);
 720       if (n < cached_line_details_.size ())
 721         m_res = ps.solve (n+1);
 722     }
 723
 724   m_res = finalize_spacing_result (configuration, m_res);
 725   n_res = finalize_spacing_result (configuration, n_res);
 726
 727   Real penalty = blank_page_penalty ();
 728   n_res.demerits_ += penalty;
 729
 730   if (n_res.force_.size ())
 731     n_res.force_.back () += penalty;
 732
 733   return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
 734 }
 735
 736 Page_spacing_result
 737 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
 738 {
 739   vsize min_p_count = min_page_count (configuration, first_page_num);
 740   Real odd_pages_penalty = blank_page_penalty ();
 741
 742   cache_line_details (configuration);
 743   Page_spacer ps (cached_line_details_, first_page_num, this);
 744   Page_spacing_result best = ps.solve (min_p_count);
 745   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
 746   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 747
 748   for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
 749     {
 750       Page_spacing_result cur = ps.solve (i);
 751       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 752       if (cur.demerits_ < best.demerits_)
 753         best = cur;
 754     }
 755
 756   return finalize_spacing_result (configuration, best);
 757 }
 758
 759 /* Calculate demerits and fix res.systems_per_page_ so that
 760    it refers to the original line numbers, not the ones given by compress_lines (). */
 761 Page_spacing_result
 762 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
 763 {
 764   if (res.force_.empty ())
 765     return res;
 766
 767   cache_line_details (configuration);
 768   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
 769
 770   Real line_force = 0;
 771   Real line_penalty = 0;
 772   Real page_force = 0;
 773   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
 774
 775   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
 776     {
 777       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
 778       line_penalty += uncompressed_line_details_[i].break_penalty_;
 779     }
 780
 781   for (vsize i = 0; i < res.force_.size (); i++)
 782     {
 783       Real f = res.force_[i];
 784       if (isinf (f) && res.systems_per_page_[i] == 1)
 785         f = 20000;
 786
 787       page_force += f * f;
 788     }
 789
 790   /* for a while we tried averaging page and line forces across pages instead
 791      of summing them, but it caused a problem: if there is a single page
 792      with a very bad page force (for example because of a forced page break),
 793      the page breaker will put in a _lot_ of pages so that the bad force
 794      becomes averaged out over many pages. */
 795   res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
 796   return res;
 797
 798 }
 799
 800 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
 801    are by far the most common cases, we have special functions for them.
 802
 803    space_systems_on_1_page has a different calling convention than most of the
 804    space_systems functions. This is because space_systems_on_1_page is (unlike
 805    the other space_systems functions) sometimes called on subsets of a full
 806    configuration. */
 807 Page_spacing_result
 808 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
 809 {
 810   Page_spacing space (page_height);
 811   Page_spacing_result ret;
 812
 813   for (vsize i = 0; i < lines.size (); i++)
 814     space.append_system (lines[i]);
 815
 816   ret.systems_per_page_.push_back (lines.size ());
 817   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
 818   ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 819
 820   /* don't do finalize_spacing_result () because we are only an internal function */
 821   return ret;
 822 }
 823
 824 Page_spacing_result
 825 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
 826 {
 827   Real page1_height = page_height (first_page_num, false);
 828   Real page2_height = page_height (first_page_num + 1, is_last ());
 829   bool ragged1 = ragged ();
 830   bool ragged2 = ragged () || (is_last () && ragged_last ());
 831
 832   /* if there is a forced break, this reduces to 2 1-page problems */
 833   cache_line_details (configuration);
 834   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
 835     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
 836       {
 837         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
 838         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
 839         Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
 840         Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
 841
 842         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
 843         p1.force_.push_back (p2.force_[0]);
 844         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
 845         return p1;
 846       }
 847
 848   vector<Real> page1_force;
 849   vector<Real> page2_force;
 850   Page_spacing page1 (page1_height);
 851   Page_spacing page2 (page2_height);
 852
 853   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
 854   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
 855
 856   /* find the page 1 and page 2 forces for each page-breaking position */
 857   for (vsize i = 0; i < page1_force.size (); i++)
 858     {
 859       page1.append_system (cached_line_details_[i]);
 860       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
 861       page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
 862
 863       if (ragged2)
 864         page2_force[page2_force.size () - 1 - i] =
 865           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
 866       else
 867         page2_force[page2_force.size () - 1 - i] = page2.force_;
 868     }
 869
 870   /* find the position that minimises the sum of the page forces */
 871   vsize best_sys_count = 1;
 872   Real best_demerits = infinity_f;
 873   for (vsize i = 0; i < page1_force.size (); i++)
 874     {
 875       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
 876       Real uneven = 2 * (page1_force[i] - page2_force[i]);
 877       Real dem = uneven * uneven + f
 878         + cached_line_details_[i+1].page_penalty_
 879         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
 880       if (dem < best_demerits)
 881         {
 882           best_demerits = dem;
 883           best_sys_count = i+1;
 884         }
 885     }
 886
 887   Page_spacing_result ret;
 888   ret.systems_per_page_.push_back (best_sys_count);
 889   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
 890   ret.force_.push_back (page1_force[best_sys_count-1]);
 891   ret.force_.push_back (page2_force[best_sys_count-1]);
 892   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
 893     + cached_line_details_.back ().page_penalty_
 894     + cached_line_details_.back ().turn_penalty_;
 895
 896   /* don't do finalize_spacing_result () because we are only an internal function */
 897   return ret;
 898 }
 899
 900 bool
 901 Page_breaking::all_lines_stretched (vsize configuration)
 902 {
 903   cache_line_details (configuration);
 904   for (vsize i = 0; i < cached_line_details_.size (); i++)
 905     if (cached_line_details_[i].force_ < 0)
 906       return false;
 907
 908   return true;
 909 }
 910
 911 Page_breaking::Line_division
 912 Page_breaking::current_configuration (vsize configuration_index) const
 913 {
 914   return current_configurations_[configuration_index];
 915 }
 916
 917 bool
 918 Page_breaking::is_last () const
 919 {
 920   return current_end_breakpoint_ == last_break_position ();
 921 }
 922
 923 vsize
 924 Page_breaking::last_break_position () const
 925 {
 926   return breaks_.size () - 1;
 927 }