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