lily/page-breaking.cc

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