lily/page-breaking.cc

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