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   SCM label_page_table = SCM_EOL;
 239
 240   for (vsize i = 0; i < lines_per_page.size (); i++)
 241     {
 242       SCM page_num = scm_from_int (i + first_page_number);
 243       SCM last = scm_from_bool (i == lines_per_page.size () - 1);
 244       SCM rag = scm_from_bool (ragged () || (to_boolean (last) && ragged_last ()));
 245       SCM line_count = scm_from_int (lines_per_page[i]);
 246       SCM lines = scm_list_head (systems, line_count);
 247       SCM page = scm_apply_0 (make_page,
 248                               scm_list_n (book, lines, page_num, rag, last, SCM_UNDEFINED));
 249
 250       /* collect labels */
 251       for (SCM l = lines ; scm_is_pair (l)  ; l = scm_cdr (l))
 252         {
 253           SCM labels = SCM_EOL;
 254           if (Grob * line = unsmob_grob (scm_car (l)))
 255             {
 256               System *system = dynamic_cast<System*> (line);
 257               labels = system->get_property ("labels");
 258             }
 259           else if (Prob *prob = unsmob_prob (scm_car (l)))
 260             labels = prob->get_property ("labels");
 261
 262           for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
 263             label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
 264                                          label_page_table);
 265         }
 266
 267       scm_apply_1 (page_stencil, page, SCM_EOL);
 268       ret = scm_cons (page, ret);
 269       systems = scm_list_tail (systems, line_count);
 270     }
 271   book_->paper_->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
 272   ret = scm_reverse (ret);
 273   return ret;
 274 }
 275
 276 /* The page-turn-page-breaker needs to have a line-breaker between any two
 277    columns with non-NULL page-turn-permission.
 278
 279    The optimal-breaker needs to have a line-breaker between any two columns
 280    with page-break-permission = 'force.
 281
 282    By using a grob predicate, we can accommodate both of these uses.
 283 */
 284 void
 285 Page_breaking::create_system_list ()
 286 {
 287   SCM specs = book_->get_system_specs ();
 288   for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
 289     {
 290       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
 291         {
 292           SCM system_count = ps->layout ()->c_variable ("system-count");
 293
 294           if (scm_is_number (system_count))
 295             s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
 296                                         scm_vector_to_list (ps->get_paper_systems ()),
 297                                         scm_cdr (s)));
 298           else
 299             all_.push_back (System_spec (ps));
 300         }
 301       else
 302         {
 303           Prob *pb = unsmob_prob (scm_car (s));
 304           assert (pb);
 305
 306           pb->protect ();
 307           all_.push_back (System_spec (pb));
 308         }
 309     }
 310 }
 311
 312 void
 313 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
 314 {
 315   SCM force_sym = ly_symbol2scm ("force");
 316
 317   chunks_.push_back (Break_position ());
 318   breaks_.push_back (Break_position ());
 319
 320   for (vsize i = 0; i < all_.size (); i++)
 321     {
 322       if (all_[i].pscore_)
 323         {
 324           vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
 325           vector<vsize> line_breaker_columns;
 326           line_breaker_columns.push_back (0);
 327
 328           for (vsize j = 1; j < cols.size (); j++)
 329             {
 330               bool last = j == cols.size () - 1;
 331               bool break_point = is_break (cols[j]);
 332               bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
 333               Break_position cur_pos = Break_position (i,
 334                                                        line_breaker_columns.size (),
 335                                                        cols[j],
 336                                                        last);
 337
 338               if (break_point || (i == all_.size () - 1 && last))
 339                 breaks_.push_back (cur_pos);
 340               if (chunk_end || last)
 341                 chunks_.push_back (cur_pos);
 342
 343               if ((break_point || chunk_end) && !last)
 344                 line_breaker_columns.push_back (j);
 345             }
 346           line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
 347         }
 348       else
 349         {
 350           /* TODO: we want some way of applying Break_p to a prob? */
 351           if (i == all_.size () - 1)
 352             breaks_.push_back (Break_position (i));
 353
 354           chunks_.push_back (Break_position (i));
 355           line_breaking_.push_back (Constrained_breaking (NULL));
 356         }
 357     }
 358 }
 359
 360 vector<Break_position>
 361 Page_breaking::chunk_list (vsize start_index, vsize end_index)
 362 {
 363   Break_position start = breaks_[start_index];
 364   Break_position end = breaks_[end_index];
 365
 366   vsize i;
 367   for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
 368     ;
 369
 370   vector<Break_position> ret;
 371   ret.push_back (start);
 372   for (; i < chunks_.size () && chunks_[i] < end; i++)
 373     ret.push_back (chunks_[i]);
 374   ret.push_back (end);
 375   return ret;
 376 }
 377
 378 vsize
 379 Page_breaking::min_system_count (vsize start, vsize end)
 380 {
 381   vector<Break_position> chunks = chunk_list (start, end);
 382   Line_division div = system_count_bounds (chunks, true);
 383   vsize ret = 0;
 384
 385   for (vsize i = 0; i < div.size (); i++)
 386     ret += div[i];
 387   return ret;
 388 }
 389
 390 vsize
 391 Page_breaking::max_system_count (vsize start, vsize end)
 392 {
 393   vector<Break_position> chunks = chunk_list (start, end);
 394   Line_division div = system_count_bounds (chunks, false);
 395   vsize ret = 0;
 396
 397   for (vsize i = 0; i < div.size (); i++)
 398     ret += div[i];
 399   return ret;
 400 }
 401
 402 Page_breaking::Line_division
 403 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
 404 {
 405   assert (chunks.size () >= 2);
 406
 407   Line_division ret;
 408   ret.resize (chunks.size () - 1, 1);
 409
 410   for (vsize i = 0; i + 1 < chunks.size (); i++)
 411     {
 412       vsize sys = next_system (chunks[i]);
 413       if (all_[sys].pscore_)
 414         {
 415           vsize start;
 416           vsize end;
 417           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 418           ret[i] = min
 419             ? line_breaking_[sys].min_system_count (start, end)
 420             : line_breaking_[sys].max_system_count (start, end);
 421         }
 422     }
 423
 424   return ret;
 425 }
 426
 427 void
 428 Page_breaking::set_current_breakpoints (vsize start,
 429                                         vsize end,
 430                                         vsize system_count,
 431                                         Line_division lower_bound,
 432                                         Line_division upper_bound)
 433 {
 434   current_chunks_ = chunk_list (start, end);
 435   current_start_breakpoint_ = start;
 436   current_end_breakpoint_ = end;
 437   clear_line_details_cache ();
 438
 439   if (!lower_bound.size ())
 440     lower_bound = system_count_bounds (current_chunks_, true);
 441   if (!upper_bound.size ())
 442     upper_bound = system_count_bounds (current_chunks_, false);
 443
 444   assert (lower_bound.size () == current_chunks_.size () - 1);
 445   assert (upper_bound.size () == current_chunks_.size () - 1);
 446
 447   Line_division work_in_progress;
 448   current_configurations_.clear ();
 449   line_divisions_rec (system_count,
 450                       lower_bound,
 451                       upper_bound,
 452                       &work_in_progress);
 453
 454   /* we only consider a constant number of configurations. Otherwise,
 455      this becomes slow when there are many small scores. The constant
 456      5 is somewhat arbitrary. */
 457   if (current_configurations_.size () > 5)
 458     {
 459       vector<pair<Real,vsize> > dems_and_indices;
 460
 461       for (vsize i = 0; i < current_configurations_.size (); i++)
 462         {
 463           cache_line_details (i);
 464           Real dem = 0;
 465           for (vsize j = 0; j < cached_line_details_.size (); j++)
 466             dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
 467               + cached_line_details_[j].break_penalty_;
 468
 469           dems_and_indices.push_back (pair<Real,vsize> (dem, i));
 470         }
 471       vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
 472
 473       vector<Line_division> best_5_configurations;
 474       for (vsize i = 0; i < 5; i++)
 475         best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
 476
 477       clear_line_details_cache ();
 478       current_configurations_ = best_5_configurations;
 479     }
 480 }
 481
 482 void
 483 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
 484 {
 485   current_chunks_ = chunk_list (start, end);
 486   current_start_breakpoint_ = start;
 487   current_end_breakpoint_ = end;
 488   clear_line_details_cache ();
 489
 490   Line_division div;
 491   for (vsize i = 0; i+1 < current_chunks_.size (); i++)
 492     {
 493       vsize sys = next_system (current_chunks_[i]);
 494       if (all_[sys].pscore_)
 495         {
 496           line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
 497           div.push_back (line_breaking_[sys].best_solution (start, end).size ());
 498         }
 499       else
 500         div.push_back (1);
 501     }
 502   current_configurations_.clear ();
 503   current_configurations_.push_back (div);
 504 }
 505
 506 vsize
 507 Page_breaking::current_configuration_count () const
 508 {
 509   return current_configurations_.size ();
 510 }
 511
 512 void
 513 Page_breaking::cache_line_details (vsize configuration_index)
 514 {
 515   if (cached_configuration_index_ != configuration_index)
 516     {
 517       SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
 518       if (!scm_is_number (padding_scm))
 519         padding_scm = book_->paper_->c_variable ("between-system-padding");
 520       Real padding = robust_scm2double (padding_scm, 0.0);
 521
 522       Line_division &div = current_configurations_[configuration_index];
 523       uncompressed_line_details_.clear ();
 524       for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
 525         {
 526           vsize sys = next_system (current_chunks_[i]);
 527           if (all_[sys].pscore_)
 528             {
 529               vsize start;
 530               vsize end;
 531               line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
 532
 533               vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
 534               uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
 535             }
 536           else
 537             {
 538               assert (div[i] == 1);
 539               uncompressed_line_details_.push_back (Line_details (all_[sys].prob_));
 540               uncompressed_line_details_.back ().padding_ = padding;
 541             }
 542         }
 543       cached_line_details_ = compress_lines (uncompressed_line_details_);
 544     }
 545 }
 546
 547 void
 548 Page_breaking::clear_line_details_cache ()
 549 {
 550   cached_configuration_index_ = VPOS;
 551   cached_line_details_.clear ();
 552   uncompressed_line_details_.clear ();
 553 }
 554
 555 void
 556 Page_breaking::line_divisions_rec (vsize system_count,
 557                                    Line_division const &min_sys,
 558                                    Line_division const &max_sys,
 559                                    Line_division *cur_division)
 560 {
 561   vsize my_index = cur_division->size ();
 562   vsize others_min = 0;
 563   vsize others_max = 0;
 564
 565   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 566     {
 567       others_min += min_sys[i];
 568       others_max += max_sys[i];
 569     }
 570   others_max = min (others_max, system_count);
 571   vsize real_min = max (min_sys[my_index], system_count - others_max);
 572   vsize real_max = min (max_sys[my_index], system_count - others_min);
 573
 574   if (real_min > real_max || real_min <= 0)
 575     {
 576       /* this should never happen within a recursive call. If it happens
 577          at all, it means that we were called with an unsolvable problem
 578          and we should return an empty result */
 579       assert (my_index == 0);
 580       return;
 581     }
 582
 583   for (vsize i = real_min; i <= real_max; i++)
 584     {
 585       cur_division->push_back (i);
 586       if (my_index == min_sys.size () - 1)
 587         current_configurations_.push_back (*cur_division);
 588       else
 589         line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
 590       cur_division->pop_back ();
 591     }
 592 }
 593
 594 vsize
 595 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
 596 {
 597   vsize ret = 1;
 598   Real cur_rod_height = 0;
 599   Real cur_spring_height = 0;
 600   Real cur_page_height = page_height (first_page_num, false);
 601
 602   cache_line_details (configuration);
 603   for (vsize i = 0; i < cached_line_details_.size (); i++)
 604     {
 605       Real ext_len = cached_line_details_[i].extent_.length ();
 606       Real next_rod_height = cur_rod_height + ext_len
 607         + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
 608       Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
 609       Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
 610
 611
 612       if ((next_height > cur_page_height && cur_rod_height > 0)
 613           || (i > 0
 614               && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
 615         {
 616           cur_rod_height = ext_len;
 617           cur_spring_height = line_space (cached_line_details_[i]);
 618           cur_page_height = page_height (first_page_num + ret, false);
 619           ret++;
 620         }
 621       else
 622         {
 623           cur_rod_height = next_rod_height;
 624           cur_spring_height = next_spring_height;
 625         }
 626     }
 627
 628   /* there are two potential problems with the last page (because we didn't know
 629      it was the last page until after we managed to fit all the systems to it):
 630      - we are ragged-last but the last page has a compressed spring
 631      - the value returned by page_height (num, true) is smaller than the
 632        value returned by page_height (num, false) and it causes the page not to
 633        fit.
 634
 635      In either case, we just need to add one more page. This is because the last
 636      line will always fit on the extra page and by adding one more page to the
 637      end, the previous page is no longer the last page, so our previous
 638      calculations that treated it as a non-last page were ok.
 639   */
 640
 641   cur_page_height = page_height (first_page_num + ret - 1, true);
 642   Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
 643   if (cur_height > cur_page_height
 644       /* don't increase the page count if the last page had only one system */
 645       && cur_rod_height > cached_line_details_.back ().extent_.length ())
 646     ret++;
 647
 648   assert (ret <= cached_line_details_.size ());
 649   return ret;
 650 }
 651
 652 Spacing_result
 653 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
 654 {
 655   Spacing_result ret;
 656   assert (n >= min_page_count (configuration, first_page_num));
 657
 658   cache_line_details (configuration);
 659   if (n > cached_line_details_.size ())
 660     return Spacing_result ();
 661   if (n == 1)
 662     ret = space_systems_on_1_page (cached_line_details_,
 663                                    page_height (first_page_num, last ()),
 664                                    ragged () || (last () && ragged_last ()));
 665   else if (n == 2)
 666     ret = space_systems_on_2_pages (configuration, first_page_num);
 667   else
 668     {
 669       Page_spacer ps (cached_line_details_, first_page_num, this);
 670       ret = ps.solve (n);
 671     }
 672
 673   return finalize_spacing_result (configuration, ret);
 674 }
 675
 676 Real
 677 Page_breaking::blank_page_penalty () const
 678 {
 679   SCM penalty_sym = last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
 680   return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
 681 }
 682
 683 Spacing_result
 684 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
 685 {
 686   Spacing_result n_res;
 687   Spacing_result m_res;
 688
 689   if (n <= 2)
 690     {
 691       n_res = space_systems_on_n_pages (configuration, n, first_page_num);
 692       m_res = space_systems_on_n_pages (configuration, n+1, first_page_num);
 693     }
 694   else
 695     {
 696       cache_line_details (configuration);
 697
 698       vsize min_p_count = min_page_count (configuration, first_page_num);
 699       Page_spacer ps (cached_line_details_, first_page_num, this);
 700       if (n >= min_p_count)
 701         n_res = ps.solve (n);
 702       if (n < cached_line_details_.size ())
 703         m_res = ps.solve (n+1);
 704     }
 705
 706   Real penalty = blank_page_penalty ();
 707   n_res.demerits_ += penalty;
 708   n_res.force_.back () += penalty;
 709
 710   if (m_res.demerits_ < n_res.demerits_)
 711     return m_res;
 712   return n_res;
 713 }
 714
 715 Spacing_result
 716 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
 717 {
 718   vsize min_p_count = min_page_count (configuration, first_page_num);
 719   Real odd_pages_penalty = blank_page_penalty ();
 720
 721   cache_line_details (configuration);
 722   Page_spacer ps (cached_line_details_, first_page_num, this);
 723   Spacing_result best = ps.solve (min_p_count);
 724   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
 725   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 726
 727   for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
 728     {
 729       Spacing_result cur = ps.solve (i);
 730       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 731       if (cur.demerits_ < best.demerits_)
 732         best = cur;
 733     }
 734
 735   return finalize_spacing_result (configuration, best);
 736 }
 737
 738 /* Calculate demerits and fix res.systems_per_page_ so that
 739    it refers to the original line numbers, not the ones given by compress_lines (). */
 740 Spacing_result
 741 Page_breaking::finalize_spacing_result (vsize configuration, Spacing_result res)
 742 {
 743   cache_line_details (configuration);
 744   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
 745
 746   Real line_force = 0;
 747   Real line_penalty = 0;
 748   Real page_force = 0;
 749   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
 750
 751   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
 752     {
 753       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
 754       line_penalty += uncompressed_line_details_[i].break_penalty_;
 755     }
 756
 757   for (vsize i = 0; i < res.force_.size (); i++)
 758     {
 759       Real f = res.force_[i];
 760       if (isinf (f) && res.systems_per_page_[i] == 1)
 761         f = 20000;
 762
 763       page_force += f * f;
 764     }
 765
 766   /* for a while we tried averaging page and line forces across pages instead
 767      of summing them, but it caused a problem: if there is a single page
 768      with a very bad page force (for example because of a forced page break),
 769      the page breaker will put in a _lot_ of pages so that the bad force
 770      becomes averaged out over many pages. */
 771   res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
 772   return res;
 773
 774 }
 775
 776 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
 777    are by far the most common cases, we have special functions for them.
 778
 779    space_systems_on_1_page has a different calling convention than most of the
 780    space_systems functions. This is because space_systems_on_1_page is (unlike
 781    the other space_systems functions) sometimes called on subsets of a full
 782    configuration. */
 783 Spacing_result
 784 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
 785 {
 786   Page_spacing space (page_height);
 787   Spacing_result ret;
 788
 789   for (vsize i = 0; i < lines.size (); i++)
 790     space.append_system (lines[i]);
 791
 792   ret.systems_per_page_.push_back (lines.size ());
 793   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
 794   ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 795
 796   /* don't do finalize_spacing_result () because we are only an internal function */
 797   return ret;
 798 }
 799
 800 Spacing_result
 801 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
 802 {
 803   Real page1_height = page_height (first_page_num, false);
 804   Real page2_height = page_height (first_page_num+1, last ());
 805   bool ragged1 = ragged ();
 806   bool ragged2 = ragged () || (last () && ragged_last ());
 807
 808   /* if there is a forced break, this reduces to 2 1-page problems */
 809   cache_line_details (configuration);
 810   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
 811     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
 812       {
 813         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
 814         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
 815         Spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
 816         Spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
 817
 818         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
 819         p1.force_.push_back (p2.force_[0]);
 820         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
 821         return p1;
 822       }
 823
 824   vector<Real> page1_force;
 825   vector<Real> page2_force;
 826   Page_spacing page1 (page1_height);
 827   Page_spacing page2 (page2_height);
 828
 829   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
 830   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
 831
 832   /* find the page 1 and page 2 forces for each page-breaking position */
 833   for (vsize i = 0; i < page1_force.size (); i++)
 834     {
 835       page1.append_system (cached_line_details_[i]);
 836       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
 837       page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
 838
 839       if (ragged2)
 840         page2_force[page2_force.size () - 1 - i] =
 841           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
 842       else
 843         page2_force[page2_force.size () - 1 - i] = page2.force_;
 844     }
 845
 846   /* find the position that minimises the sum of the page forces */
 847   vsize best_sys_count = 1;
 848   Real best_demerits = infinity_f;
 849   for (vsize i = 0; i < page1_force.size (); i++)
 850     {
 851       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
 852       Real uneven = 2 * (page1_force[i] - page2_force[i]);
 853       Real dem = uneven * uneven + f
 854         + cached_line_details_[i+1].page_penalty_
 855         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
 856       if (dem < best_demerits)
 857         {
 858           best_demerits = dem;
 859           best_sys_count = i+1;
 860         }
 861     }
 862
 863   Spacing_result ret;
 864   ret.systems_per_page_.push_back (best_sys_count);
 865   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
 866   ret.force_.push_back (page1_force[best_sys_count-1]);
 867   ret.force_.push_back (page2_force[best_sys_count-1]);
 868   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
 869     + cached_line_details_.back ().page_penalty_
 870     + cached_line_details_.back ().turn_penalty_;
 871
 872   /* don't do finalize_spacing_result () because we are only an internal function */
 873   return ret;
 874 }
 875
 876 bool
 877 Page_breaking::all_lines_stretched (vsize configuration)
 878 {
 879   cache_line_details (configuration);
 880   for (vsize i = 0; i < cached_line_details_.size (); i++)
 881     if (cached_line_details_[i].force_ < 0)
 882       return false;
 883
 884   return true;
 885 }
 886
 887 Page_breaking::Line_division
 888 Page_breaking::current_configuration (vsize configuration_index) const
 889 {
 890   return current_configurations_[configuration_index];
 891 }
 892
 893 bool Page_breaking::last () const
 894 {
 895   return current_end_breakpoint_ == breaks_.size () - 1;
 896 }