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