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