lily/page-breaking.cc

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