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   cache_line_details (configuration);
 683   vsize min_p_count = min_page_count (configuration, first_page_num);
 684
 685   if (n == 1)
 686     {
 687       bool rag = ragged () || (is_last () && ragged_last ());
 688       Real height = page_height (first_page_num, is_last ());
 689
 690       if (1 >= min_p_count)
 691         n_res = space_systems_on_1_page (cached_line_details_, height, rag);
 692       if (1 < cached_line_details_.size ())
 693         m_res = space_systems_on_2_pages (configuration, first_page_num);
 694     }
 695   else
 696     {
 697       Page_spacer ps (cached_line_details_, first_page_num, this);
 698
 699       if (n >= min_p_count)
 700         n_res = ps.solve (n);
 701       if (n < cached_line_details_.size ())
 702         m_res = ps.solve (n+1);
 703     }
 704
 705   m_res = finalize_spacing_result (configuration, m_res);
 706   n_res = finalize_spacing_result (configuration, n_res);
 707
 708   Real penalty = blank_page_penalty ();
 709   n_res.demerits_ += penalty;
 710   n_res.force_.back () += penalty;
 711
 712   return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
 713 }
 714
 715 Page_spacing_result
 716 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
 717 {
 718   vsize min_p_count = min_page_count (configuration, first_page_num);
 719   Real odd_pages_penalty = blank_page_penalty ();
 720
 721   cache_line_details (configuration);
 722   Page_spacer ps (cached_line_details_, first_page_num, this);
 723   Page_spacing_result best = ps.solve (min_p_count);
 724   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
 725   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 726
 727   for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
 728     {
 729       Page_spacing_result cur = ps.solve (i);
 730       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 731       if (cur.demerits_ < best.demerits_)
 732         best = cur;
 733     }
 734
 735   return finalize_spacing_result (configuration, best);
 736 }
 737
 738 /* Calculate demerits and fix res.systems_per_page_ so that
 739    it refers to the original line numbers, not the ones given by compress_lines (). */
 740 Page_spacing_result
 741 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
 742 {
 743   cache_line_details (configuration);
 744   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
 745
 746   Real line_force = 0;
 747   Real line_penalty = 0;
 748   Real page_force = 0;
 749   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
 750
 751   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
 752     {
 753       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
 754       line_penalty += uncompressed_line_details_[i].break_penalty_;
 755     }
 756
 757   for (vsize i = 0; i < res.force_.size (); i++)
 758     {
 759       Real f = res.force_[i];
 760       if (isinf (f) && res.systems_per_page_[i] == 1)
 761         f = 20000;
 762
 763       page_force += f * f;
 764     }
 765
 766   /* for a while we tried averaging page and line forces across pages instead
 767      of summing them, but it caused a problem: if there is a single page
 768      with a very bad page force (for example because of a forced page break),
 769      the page breaker will put in a _lot_ of pages so that the bad force
 770      becomes averaged out over many pages. */
 771   res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
 772   return res;
 773
 774 }
 775
 776 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
 777    are by far the most common cases, we have special functions for them.
 778
 779    space_systems_on_1_page has a different calling convention than most of the
 780    space_systems functions. This is because space_systems_on_1_page is (unlike
 781    the other space_systems functions) sometimes called on subsets of a full
 782    configuration. */
 783 Page_spacing_result
 784 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
 785 {
 786   Page_spacing space (page_height);
 787   Page_spacing_result ret;
 788
 789   for (vsize i = 0; i < lines.size (); i++)
 790     space.append_system (lines[i]);
 791
 792   ret.systems_per_page_.push_back (lines.size ());
 793   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
 794   ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
 795
 796   /* don't do finalize_spacing_result () because we are only an internal function */
 797   return ret;
 798 }
 799
 800 Page_spacing_result
 801 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
 802 {
 803   Real page1_height = page_height (first_page_num, false);
 804   Real page2_height = page_height (first_page_num + 1, is_last ());
 805   bool ragged1 = ragged ();
 806   bool ragged2 = ragged () || (is_last () && ragged_last ());
 807
 808   /* if there is a forced break, this reduces to 2 1-page problems */
 809   cache_line_details (configuration);
 810   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
 811     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
 812       {
 813         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
 814         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
 815         Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
 816         Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
 817
 818         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
 819         p1.force_.push_back (p2.force_[0]);
 820         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
 821         return p1;
 822       }
 823
 824   vector<Real> page1_force;
 825   vector<Real> page2_force;
 826   Page_spacing page1 (page1_height);
 827   Page_spacing page2 (page2_height);
 828
 829   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
 830   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
 831
 832   /* find the page 1 and page 2 forces for each page-breaking position */
 833   for (vsize i = 0; i < page1_force.size (); i++)
 834     {
 835       page1.append_system (cached_line_details_[i]);
 836       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
 837       page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
 838
 839       if (ragged2)
 840         page2_force[page2_force.size () - 1 - i] =
 841           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
 842       else
 843         page2_force[page2_force.size () - 1 - i] = page2.force_;
 844     }
 845
 846   /* find the position that minimises the sum of the page forces */
 847   vsize best_sys_count = 1;
 848   Real best_demerits = infinity_f;
 849   for (vsize i = 0; i < page1_force.size (); i++)
 850     {
 851       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
 852       Real uneven = 2 * (page1_force[i] - page2_force[i]);
 853       Real dem = uneven * uneven + f
 854         + cached_line_details_[i+1].page_penalty_
 855         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
 856       if (dem < best_demerits)
 857         {
 858           best_demerits = dem;
 859           best_sys_count = i+1;
 860         }
 861     }
 862
 863   Page_spacing_result ret;
 864   ret.systems_per_page_.push_back (best_sys_count);
 865   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
 866   ret.force_.push_back (page1_force[best_sys_count-1]);
 867   ret.force_.push_back (page2_force[best_sys_count-1]);
 868   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
 869     + cached_line_details_.back ().page_penalty_
 870     + cached_line_details_.back ().turn_penalty_;
 871
 872   /* don't do finalize_spacing_result () because we are only an internal function */
 873   return ret;
 874 }
 875
 876 bool
 877 Page_breaking::all_lines_stretched (vsize configuration)
 878 {
 879   cache_line_details (configuration);
 880   for (vsize i = 0; i < cached_line_details_.size (); i++)
 881     if (cached_line_details_[i].force_ < 0)
 882       return false;
 883
 884   return true;
 885 }
 886
 887 Page_breaking::Line_division
 888 Page_breaking::current_configuration (vsize configuration_index) const
 889 {
 890   return current_configurations_[configuration_index];
 891 }
 892
 893 bool
 894 Page_breaking::is_last () const
 895 {
 896   return current_end_breakpoint_ == last_break_position ();
 897 }
 898
 899 vsize
 900 Page_breaking::last_break_position () const
 901 {
 902   return breaks_.size () - 1;
 903 }