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--2009 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           compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
  41           compressed.compressed_nontitle_lines_count_ =
  42             old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
  43
  44           compressed.title_ = compressed.title_ && old.title_;
  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 += compressed[j].compressed_lines_count_ - 1;
  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   system_count_ = 0;
 101   ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
 102   ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
 103   page_top_space_ = robust_scm2double (pb->paper_->c_variable ("page-top-space"), 0);
 104   systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0);
 105   max_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0);
 106   min_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0);
 107
 108   create_system_list ();
 109   find_chunks_and_breaks (is_break);
 110 }
 111
 112 Page_breaking::~Page_breaking ()
 113 {
 114 }
 115
 116 bool
 117 Page_breaking::ragged () const
 118 {
 119   return ragged_;
 120 }
 121
 122 bool
 123 Page_breaking::ragged_last () const
 124 {
 125   return ragged_last_;
 126 }
 127
 128 int
 129 Page_breaking::systems_per_page () const
 130 {
 131   return systems_per_page_;
 132 }
 133
 134 int
 135 Page_breaking::max_systems_per_page () const
 136 {
 137   return max_systems_per_page_;
 138 }
 139
 140 int
 141 Page_breaking::min_systems_per_page () const
 142 {
 143   return min_systems_per_page_;
 144 }
 145
 146 Real
 147 Page_breaking::page_top_space () const
 148 {
 149   return page_top_space_;
 150 }
 151
 152 vsize
 153 Page_breaking::system_count () const
 154 {
 155   return system_count_;
 156 }
 157
 158 bool
 159 Page_breaking::too_many_lines (int line_count) const
 160 {
 161   return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
 162 }
 163
 164 bool
 165 Page_breaking::too_few_lines (int line_count) const
 166 {
 167   return line_count < min_systems_per_page ();
 168 }
 169
 170 Real
 171 Page_breaking::line_count_penalty (int line_count) const
 172 {
 173   // TODO: also check min_systems_per_page (once we support it in Page_spacer)
 174   return too_many_lines (line_count) ? BAD_SPACING_PENALTY : 0;
 175 }
 176
 177 /* translate indices into breaks_ into start-end parameters for the line breaker */
 178 void
 179 Page_breaking::line_breaker_args (vsize sys,
 180                                   Break_position const &start,
 181                                   Break_position const &end,
 182                                   vsize *line_breaker_start,
 183                                   vsize *line_breaker_end)
 184 {
 185   assert (system_specs_[sys].pscore_);
 186   assert (next_system (start) <= sys && sys <= end.system_spec_index_);
 187
 188   if (start.system_spec_index_ == sys)
 189     *line_breaker_start = start.score_break_;
 190   else
 191     *line_breaker_start = 0;
 192
 193   if (end.system_spec_index_ == sys)
 194     *line_breaker_end = end.score_break_;
 195   else
 196     *line_breaker_end = VPOS;
 197 }
 198
 199 void
 200 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
 201                                   Line_division const &div)
 202 {
 203   vector<Break_position> chunks = chunk_list (start_break, end_break);
 204   bool ignore_div = false;
 205   if (chunks.size () != div.size () + 1)
 206     {
 207       programming_error ("did not find a valid page breaking configuration");
 208       ignore_div = true;
 209     }
 210
 211   for (vsize i = 0; i + 1 < chunks.size (); i++)
 212     {
 213       vsize sys = next_system (chunks[i]);
 214       if (system_specs_[sys].pscore_)
 215         {
 216           vsize start;
 217           vsize end;
 218           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 219
 220           vector<Column_x_positions> pos = ignore_div
 221             ? line_breaking_[sys].best_solution (start, end)
 222             : line_breaking_[sys].solve (start, end, div[i]);
 223           system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
 224         }
 225     }
 226 }
 227
 228 SCM
 229 Page_breaking::systems ()
 230 {
 231   SCM ret = SCM_EOL;
 232   for (vsize sys = 0; sys < system_specs_.size (); sys++)
 233     {
 234       if (system_specs_[sys].pscore_)
 235         {
 236           system_specs_[sys].pscore_->root_system ()
 237             ->do_break_substitution_and_fixup_refpoints ();
 238           SCM lines = system_specs_[sys].pscore_->root_system ()
 239             ->get_broken_system_grobs ();
 240           ret = scm_cons (lines, ret);
 241         }
 242       else
 243         {
 244           Prob *pb = system_specs_[sys].prob_;
 245           ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
 246           pb->unprotect ();
 247         }
 248     }
 249   return scm_append (scm_reverse (ret));
 250 }
 251
 252 Real
 253 Page_breaking::page_height (int page_num, bool last) const
 254 {
 255   bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
 256   SCM mod = scm_c_resolve_module ("scm page");
 257   SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
 258   SCM make_page = scm_c_module_lookup (mod, "make-page");
 259
 260   calc_height = scm_variable_ref (calc_height);
 261   make_page = scm_variable_ref (make_page);
 262
 263   SCM page = scm_apply_0 (make_page, scm_list_n (
 264                   book_->self_scm (),
 265                   ly_symbol2scm ("page-number"), scm_from_int (page_num),
 266                   ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
 267                   ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
 268                   SCM_UNDEFINED));
 269   SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
 270   return scm_to_double (height) - page_top_space_;
 271 }
 272
 273 SCM
 274 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
 275 {
 276   Break_position const &pos = breaks_[breakpoint];
 277
 278   if (pos.system_spec_index_ == VPOS)
 279     return SCM_EOL;
 280   if (system_specs_[pos.system_spec_index_].pscore_)
 281     return pos.col_->get_property (str);
 282   return system_specs_[pos.system_spec_index_].prob_->get_property (str);
 283 }
 284
 285 SCM
 286 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
 287 {
 288   SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
 289   SCM page_module = scm_c_resolve_module ("scm page");
 290
 291   SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
 292   SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
 293   make_page = scm_variable_ref (make_page);
 294   page_stencil = scm_variable_ref (page_stencil);
 295
 296   SCM book = book_->self_scm ();
 297   int first_page_number
 298     = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
 299   bool last_bookpart = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
 300   SCM ret = SCM_EOL;
 301   SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
 302   if (label_page_table == SCM_UNDEFINED)
 303     label_page_table = SCM_EOL;
 304
 305   for (vsize i = 0; i < lines_per_page.size (); i++)
 306     {
 307       SCM page_num = scm_from_int (i + first_page_number);
 308       bool partbook_last_page = (i == lines_per_page.size () - 1);
 309       SCM rag = scm_from_bool (ragged () || ( partbook_last_page && ragged_last ()));
 310       SCM line_count = scm_from_int (lines_per_page[i]);
 311       SCM lines = scm_list_head (systems, line_count);
 312       SCM page = scm_apply_0 (make_page,
 313                               scm_list_n (book, lines, page_num, rag,
 314                                           scm_from_bool (last_bookpart),
 315                                           scm_from_bool (partbook_last_page),
 316                                           SCM_UNDEFINED));
 317       /* collect labels */
 318       for (SCM l = lines ; scm_is_pair (l)  ; l = scm_cdr (l))
 319         {
 320           SCM labels = SCM_EOL;
 321           if (Grob * line = unsmob_grob (scm_car (l)))
 322             {
 323               System *system = dynamic_cast<System*> (line);
 324               labels = system->get_property ("labels");
 325             }
 326           else if (Prob *prob = unsmob_prob (scm_car (l)))
 327             labels = prob->get_property ("labels");
 328
 329           for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
 330             label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
 331                                          label_page_table);
 332         }
 333
 334       scm_apply_1 (page_stencil, page, SCM_EOL);
 335       ret = scm_cons (page, ret);
 336       systems = scm_list_tail (systems, line_count);
 337     }
 338   book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
 339   ret = scm_reverse (ret);
 340   return ret;
 341 }
 342
 343 /* The page-turn-page-breaker needs to have a line-breaker between any two
 344    columns with non-NULL page-turn-permission.
 345
 346    The optimal-breaker needs to have a line-breaker between any two columns
 347    with page-break-permission = 'force.
 348
 349    By using a grob predicate, we can accommodate both of these uses.
 350 */
 351 void
 352 Page_breaking::create_system_list ()
 353 {
 354   SCM specs = book_->get_system_specs ();
 355   for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
 356     {
 357       if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
 358         {
 359           SCM system_count = ps->layout ()->c_variable ("system-count");
 360
 361           if (scm_is_number (system_count))
 362             s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
 363                                         scm_vector_to_list (ps->get_paper_systems ()),
 364                                         scm_cdr (s)));
 365           else
 366             system_specs_.push_back (System_spec (ps));
 367         }
 368       else
 369         {
 370           Prob *pb = unsmob_prob (scm_car (s));
 371           assert (pb);
 372
 373           pb->protect ();
 374           system_specs_.push_back (System_spec (pb));
 375         }
 376     }
 377 }
 378
 379 void
 380 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
 381 {
 382   SCM force_sym = ly_symbol2scm ("force");
 383
 384   chunks_.push_back (Break_position ());
 385   breaks_.push_back (Break_position ());
 386
 387   for (vsize i = 0; i < system_specs_.size (); i++)
 388     {
 389       if (system_specs_[i].pscore_)
 390         {
 391           vector<Grob*> cols
 392             = system_specs_[i].pscore_->root_system ()->used_columns ();
 393           vector<vsize> line_breaker_columns;
 394           line_breaker_columns.push_back (0);
 395
 396           for (vsize j = 1; j < cols.size (); j++)
 397             {
 398               bool last = (j == cols.size () - 1);
 399               bool break_point = is_break (cols[j]);
 400               bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
 401               Break_position cur_pos = Break_position (i,
 402                                                        line_breaker_columns.size (),
 403                                                        cols[j],
 404                                                        last);
 405
 406               if (break_point || (i == system_specs_.size () - 1 && last))
 407                 breaks_.push_back (cur_pos);
 408               if (chunk_end || last)
 409                 chunks_.push_back (cur_pos);
 410
 411               if ((break_point || chunk_end) && !last)
 412                 line_breaker_columns.push_back (j);
 413             }
 414           line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
 415         }
 416       else
 417         {
 418           /* TODO: we want some way of applying Break_p to a prob? */
 419           if (i == system_specs_.size () - 1)
 420             breaks_.push_back (Break_position (i));
 421
 422           chunks_.push_back (Break_position (i));
 423
 424           /* FIXME: shouldn't we push a Null_breaker or similar dummy
 425              class? --hwn */
 426           line_breaking_.push_back (Constrained_breaking (NULL));
 427         }
 428     }
 429 }
 430
 431 vector<Break_position>
 432 Page_breaking::chunk_list (vsize start_index, vsize end_index)
 433 {
 434   Break_position start = breaks_[start_index];
 435   Break_position end = breaks_[end_index];
 436
 437   vsize i = 0;
 438   for (; i < chunks_.size () && chunks_[i] <= start; i++)
 439     ;
 440
 441   vector<Break_position> ret;
 442   ret.push_back (start);
 443   for (; i < chunks_.size () && chunks_[i] < end; i++)
 444     ret.push_back (chunks_[i]);
 445   ret.push_back (end);
 446   return ret;
 447 }
 448
 449 vsize
 450 Page_breaking::min_system_count (vsize start, vsize end)
 451 {
 452   vector<Break_position> chunks = chunk_list (start, end);
 453   Line_division div = system_count_bounds (chunks, true);
 454   vsize ret = 0;
 455
 456   for (vsize i = 0; i < div.size (); i++)
 457     ret += div[i];
 458   return ret;
 459 }
 460
 461 vsize
 462 Page_breaking::max_system_count (vsize start, vsize end)
 463 {
 464   vector<Break_position> chunks = chunk_list (start, end);
 465   Line_division div = system_count_bounds (chunks, false);
 466   vsize ret = 0;
 467
 468   for (vsize i = 0; i < div.size (); i++)
 469     ret += div[i];
 470   return ret;
 471 }
 472
 473 Page_breaking::Line_division
 474 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
 475                                     bool min)
 476 {
 477   assert (chunks.size () >= 2);
 478
 479   Line_division ret;
 480   ret.resize (chunks.size () - 1, 1);
 481
 482   for (vsize i = 0; i + 1 < chunks.size (); i++)
 483     {
 484       vsize sys = next_system (chunks[i]);
 485       if (system_specs_[sys].pscore_)
 486         {
 487           vsize start;
 488           vsize end;
 489           line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
 490           ret[i] = min
 491             ? line_breaking_[sys].min_system_count (start, end)
 492             : line_breaking_[sys].max_system_count (start, end);
 493         }
 494     }
 495
 496   return ret;
 497 }
 498
 499 void
 500 Page_breaking::set_current_breakpoints (vsize start,
 501                                         vsize end,
 502                                         vsize system_count,
 503                                         Line_division lower_bound,
 504                                         Line_division upper_bound)
 505 {
 506   system_count_ = system_count;
 507   current_chunks_ = chunk_list (start, end);
 508   current_start_breakpoint_ = start;
 509   current_end_breakpoint_ = end;
 510   clear_line_details_cache ();
 511
 512   if (!lower_bound.size ())
 513     lower_bound = system_count_bounds (current_chunks_, true);
 514   if (!upper_bound.size ())
 515     upper_bound = system_count_bounds (current_chunks_, false);
 516
 517   assert (lower_bound.size () == current_chunks_.size () - 1);
 518   assert (upper_bound.size () == current_chunks_.size () - 1);
 519
 520   Line_division work_in_progress;
 521   current_configurations_.clear ();
 522   line_divisions_rec (system_count,
 523                       lower_bound,
 524                       upper_bound,
 525                       &work_in_progress);
 526
 527   /* we only consider a constant number of configurations. Otherwise,
 528      this becomes slow when there are many small scores. The constant
 529      5 is somewhat arbitrary. */
 530   if (current_configurations_.size () > 5)
 531     {
 532       vector<pair<Real,vsize> > dems_and_indices;
 533
 534       for (vsize i = 0; i < current_configurations_.size (); i++)
 535         {
 536           cache_line_details (i);
 537           Real dem = 0;
 538           for (vsize j = 0; j < cached_line_details_.size (); j++)
 539             dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
 540               + cached_line_details_[j].break_penalty_;
 541
 542           dems_and_indices.push_back (pair<Real,vsize> (dem, i));
 543         }
 544       vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
 545
 546       vector<Line_division> best_5_configurations;
 547       for (vsize i = 0; i < 5; i++)
 548         best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
 549
 550       clear_line_details_cache ();
 551       current_configurations_ = best_5_configurations;
 552     }
 553 }
 554
 555 void
 556 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
 557 {
 558   current_chunks_ = chunk_list (start, end);
 559   current_start_breakpoint_ = start;
 560   current_end_breakpoint_ = end;
 561   clear_line_details_cache ();
 562   system_count_ = 0;
 563
 564   Line_division div;
 565   for (vsize i = 0; i+1 < current_chunks_.size (); i++)
 566     {
 567       vsize sys = next_system (current_chunks_[i]);
 568       if (system_specs_[sys].pscore_)
 569         {
 570           line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
 571           div.push_back (line_breaking_[sys].best_solution (start, end).size ());
 572         }
 573       else
 574         div.push_back (1);
 575
 576       system_count_ += div.back ();
 577     }
 578   current_configurations_.clear ();
 579   current_configurations_.push_back (div);
 580 }
 581
 582 vsize
 583 Page_breaking::current_configuration_count () const
 584 {
 585   return current_configurations_.size ();
 586 }
 587
 588 void
 589 Page_breaking::cache_line_details (vsize configuration_index)
 590 {
 591   if (cached_configuration_index_ != configuration_index)
 592     {
 593       cached_configuration_index_ = configuration_index;
 594       SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
 595       if (!scm_is_number (padding_scm))
 596         padding_scm = book_->paper_->c_variable ("between-system-padding");
 597       Real padding = robust_scm2double (padding_scm, 0.0);
 598
 599       Line_division &div = current_configurations_[configuration_index];
 600       uncompressed_line_details_.clear ();
 601       for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
 602         {
 603           vsize sys = next_system (current_chunks_[i]);
 604           if (system_specs_[sys].pscore_)
 605             {
 606               vsize start;
 607               vsize end;
 608               line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
 609
 610               vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
 611               uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
 612             }
 613           else
 614             {
 615               assert (div[i] == 1);
 616               uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
 617               uncompressed_line_details_.back ().padding_ =
 618                 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
 619                                    padding);
 620             }
 621         }
 622       cached_line_details_ = compress_lines (uncompressed_line_details_);
 623     }
 624 }
 625
 626 void
 627 Page_breaking::clear_line_details_cache ()
 628 {
 629   cached_configuration_index_ = VPOS;
 630   cached_line_details_.clear ();
 631   uncompressed_line_details_.clear ();
 632 }
 633
 634 void
 635 Page_breaking::line_divisions_rec (vsize system_count,
 636                                    Line_division const &min_sys,
 637                                    Line_division const &max_sys,
 638                                    Line_division *cur_division)
 639 {
 640   vsize my_index = cur_division->size ();
 641   vsize others_min = 0;
 642   vsize others_max = 0;
 643
 644   for (vsize i = my_index + 1; i < min_sys.size (); i++)
 645     {
 646       others_min += min_sys[i];
 647       others_max += max_sys[i];
 648     }
 649   others_max = min (others_max, system_count);
 650   vsize real_min = max (min_sys[my_index], system_count - others_max);
 651   vsize real_max = min (max_sys[my_index], system_count - others_min);
 652
 653   if (real_min > real_max || real_min <= 0)
 654     {
 655       /* this should never happen within a recursive call. If it happens
 656          at all, it means that we were called with an unsolvable problem
 657          and we should return an empty result */
 658       assert (my_index == 0);
 659       return;
 660     }
 661
 662   for (vsize i = real_min; i <= real_max; i++)
 663     {
 664       cur_division->push_back (i);
 665       if (my_index == min_sys.size () - 1)
 666         current_configurations_.push_back (*cur_division);
 667       else
 668         line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
 669       cur_division->pop_back ();
 670     }
 671 }
 672
 673 vsize
 674 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
 675 {
 676   vsize ret = 1;
 677   Real cur_rod_height = 0;
 678   Real cur_spring_height = 0;
 679   Real cur_page_height = page_height (first_page_num, false);
 680   int line_count = 0;
 681
 682   cache_line_details (configuration);
 683   for (vsize i = 0; i < cached_line_details_.size (); i++)
 684     {
 685       Real ext_len = cached_line_details_[i].extent_.length ();
 686       Real next_rod_height = cur_rod_height + ext_len
 687         + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
 688       Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
 689       Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
 690
 691       line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
 692
 693       if ((next_height > cur_page_height && cur_rod_height > 0)
 694           || too_many_lines (line_count)
 695           || (i > 0
 696               && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
 697         {
 698           line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
 699           cur_rod_height = ext_len;
 700           cur_spring_height = cached_line_details_[i].space_;
 701           cur_page_height = page_height (first_page_num + ret, false);
 702           ret++;
 703         }
 704       else
 705         {
 706           cur_rod_height = next_rod_height;
 707           cur_spring_height = next_spring_height;
 708         }
 709     }
 710
 711   /* there are two potential problems with the last page (because we didn't know
 712      it was the last page until after we managed to fit all the systems to it):
 713      - we are ragged-last but the last page has a compressed spring
 714      - the value returned by page_height (num, true) is smaller than the
 715        value returned by page_height (num, false) and it causes the page not to
 716        fit.
 717
 718      In either case, we just need to add one more page. This is because the last
 719      line will always fit on the extra page and by adding one more page to the
 720      end, the previous page is no longer the last page, so our previous
 721      calculations that treated it as a non-last page were ok.
 722   */
 723
 724   cur_page_height = page_height (first_page_num + ret - 1, true);
 725   Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
 726   if (cur_height > cur_page_height
 727       /* don't increase the page count if the last page had only one system */
 728       && cur_rod_height > cached_line_details_.back ().extent_.length ())
 729     ret++;
 730
 731   assert (ret <= cached_line_details_.size ());
 732   return ret;
 733 }
 734
 735 // If systems_per_page_ is positive, we don't really try to space on N pages;
 736 // we just put the requested number of systems on each page and penalize
 737 // if the result doesn't have N pages.
 738 Page_spacing_result
 739 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
 740 {
 741   Page_spacing_result ret;
 742
 743   if (systems_per_page_ > 0)
 744     {
 745       Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
 746       ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
 747       return ret;
 748     }
 749
 750   cache_line_details (configuration);
 751   bool valid_n = (n >= min_page_count (configuration, first_page_num)
 752                   && n <= cached_line_details_.size ());
 753
 754   if (!valid_n)
 755     programming_error ("number of pages is out of bounds");
 756
 757   if (n == 1 && valid_n)
 758     ret = space_systems_on_1_page (cached_line_details_,
 759                                    page_height (first_page_num, is_last ()),
 760                                    ragged () || (is_last () && ragged_last ()));
 761   else if (n == 2 && valid_n)
 762     ret = space_systems_on_2_pages (configuration, first_page_num);
 763   else
 764     {
 765       Page_spacer ps (cached_line_details_, first_page_num, this);
 766       ret = ps.solve (n);
 767     }
 768
 769   return finalize_spacing_result (configuration, ret);
 770 }
 771
 772 Real
 773 Page_breaking::blank_page_penalty () const
 774 {
 775   SCM penalty_sym;
 776
 777   if (is_last ())
 778     penalty_sym = ly_symbol2scm ("blank-last-page-force");
 779   else if (ends_score ())
 780     penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
 781   else
 782     penalty_sym = ly_symbol2scm ("blank-page-force");
 783
 784   Break_position const &pos = breaks_[current_end_breakpoint_];
 785   if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
 786     return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
 787
 788   return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
 789 }
 790
 791 // If systems_per_page_ is positive, we don't really try to space on N
 792 // or N+1 pages; see the comment to space_systems_on_n_pages.
 793 Page_spacing_result
 794 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
 795 {
 796   Page_spacing_result n_res;
 797   Page_spacing_result m_res;
 798
 799   if (systems_per_page_ > 0)
 800     {
 801       Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
 802       ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
 803       return ret;
 804     }
 805
 806   cache_line_details (configuration);
 807   vsize min_p_count = min_page_count (configuration, first_page_num);
 808   bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
 809
 810   if (!valid_n)
 811     programming_error ("both page counts are out of bounds");
 812
 813   if (n == 1 && valid_n)
 814     {
 815       bool rag = ragged () || (is_last () && ragged_last ());
 816       Real height = page_height (first_page_num, is_last ());
 817
 818       if (1 >= min_p_count)
 819         n_res = space_systems_on_1_page (cached_line_details_, height, rag);
 820       if (1 < cached_line_details_.size ())
 821         m_res = space_systems_on_2_pages (configuration, first_page_num);
 822     }
 823   else
 824     {
 825       Page_spacer ps (cached_line_details_, first_page_num, this);
 826
 827       if (n >= min_p_count || !valid_n)
 828         n_res = ps.solve (n);
 829       if (n < cached_line_details_.size () || !valid_n)
 830         m_res = ps.solve (n+1);
 831     }
 832
 833   m_res = finalize_spacing_result (configuration, m_res);
 834   n_res = finalize_spacing_result (configuration, n_res);
 835
 836   Real penalty = blank_page_penalty ();
 837   n_res.demerits_ += penalty;
 838
 839   if (n_res.force_.size ())
 840     n_res.force_.back () += penalty;
 841
 842   return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
 843 }
 844
 845 Page_spacing_result
 846 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
 847 {
 848   vsize min_p_count = min_page_count (configuration, first_page_num);
 849   Real odd_pages_penalty = blank_page_penalty ();
 850
 851   cache_line_details (configuration);
 852   Page_spacer ps (cached_line_details_, first_page_num, this);
 853   Page_spacing_result best = ps.solve (min_p_count);
 854   best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
 855   best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
 856
 857   for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
 858     {
 859       Page_spacing_result cur = ps.solve (i);
 860       cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
 861       if (cur.demerits_ < best.demerits_)
 862         best = cur;
 863     }
 864
 865   return finalize_spacing_result (configuration, best);
 866 }
 867
 868 Page_spacing_result
 869 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
 870                                                          vsize first_page_num)
 871 {
 872   Page_spacing_result res;
 873   Page_spacing space (page_height (first_page_num, false), page_top_space_);
 874   vsize line = 0;
 875   vsize page = 0;
 876   vsize page_first_line = 0;
 877
 878   cache_line_details (configuration);
 879   while (line < cached_line_details_.size ())
 880     {
 881       page++;
 882       space.clear ();
 883       space.resize (page_height (first_page_num + page, false));
 884
 885       int system_count_on_this_page = 0;
 886       while (system_count_on_this_page < systems_per_page_
 887              && line < cached_line_details_.size ())
 888         {
 889           Line_details const &cur_line = cached_line_details_[line];
 890           space.append_system (cur_line);
 891           system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
 892           line++;
 893
 894           if (cur_line.page_permission_ == ly_symbol2scm ("force"))
 895             break;
 896         }
 897
 898       res.systems_per_page_.push_back (line - page_first_line);
 899
 900       // Don't say that the force is infinite even if it is: if we were told to
 901       // put a certain number of systems on a page then we will, even if it's bad.
 902       res.force_.push_back (min (space.force_, BAD_SPACING_PENALTY));
 903       res.penalty_ += cached_line_details_[line-1].page_penalty_;
 904       page_first_line = line;
 905     }
 906
 907   /* Recalculate forces for the last page because we know now that is
 908      really the last page. */
 909   space.resize (page_height (first_page_num + page, true));
 910   res.force_.back () = min(space.force_, BAD_SPACING_PENALTY);
 911   return finalize_spacing_result (configuration, res);
 912 }
 913
 914 Page_spacing_result
 915 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
 916 {
 917   Page_spacing_result res;
 918   vsize page = 0;
 919   vsize page_first_line = 0;
 920   Page_spacing space (page_height (first_page_num, false), page_top_space_);
 921
 922   cache_line_details (configuration);
 923   for (vsize line = 0; line < cached_line_details_.size (); line++)
 924     {
 925       Real prev_force = space.force_;
 926       space.append_system (cached_line_details_[line]);
 927       if ((line > page_first_line)
 928           && (isinf (space.force_)
 929               || ((line > 0)
 930                   && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
 931         {
 932           res.systems_per_page_.push_back (line - page_first_line);
 933           res.force_.push_back (prev_force);
 934           res.penalty_ += cached_line_details_[line-1].page_penalty_;
 935           page++;
 936           space.resize (page_height (first_page_num + page, false));
 937           space.clear ();
 938           space.append_system (cached_line_details_[line]);
 939           page_first_line = line;
 940         }
 941
 942       if (line == cached_line_details_.size () - 1)
 943         {
 944           /* This is the last line */
 945           /* When the last page height was computed, we did not know yet that it
 946            * was the last one. If the systems put on it don't fit anymore, the last
 947            * system is moved to a new page */
 948           space.resize (page_height (first_page_num + page, true));
 949           if ((line > page_first_line) && (isinf (space.force_)))
 950             {
 951               res.systems_per_page_.push_back (line - page_first_line);
 952               res.force_.push_back (prev_force);
 953               /* the last page containing the last line */
 954               space.resize (page_height (first_page_num + page + 1, true));
 955               space.clear ();
 956               space.append_system (cached_line_details_[line]);
 957               res.systems_per_page_.push_back (1);
 958               res.force_.push_back (space.force_);
 959               res.penalty_ += cached_line_details_[line-1].page_penalty_;
 960               res.penalty_ += cached_line_details_[line].page_penalty_;
 961             }
 962           else
 963             {
 964               res.systems_per_page_.push_back (line + 1 - page_first_line);
 965               res.force_.push_back (space.force_);
 966               res.penalty_ += cached_line_details_[line].page_penalty_;
 967             }
 968         }
 969     }
 970   return finalize_spacing_result (configuration, res);
 971 }
 972
 973 /* Calculate demerits and fix res.systems_per_page_ so that
 974    it refers to the original line numbers, not the ones given by compress_lines (). */
 975 Page_spacing_result
 976 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
 977 {
 978   if (res.force_.empty ())
 979     return res;
 980
 981   cache_line_details (configuration);
 982   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
 983
 984   Real line_force = 0;
 985   Real line_penalty = 0;
 986   Real page_force = 0;
 987   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
 988
 989   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
 990     {
 991       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
 992       line_penalty += uncompressed_line_details_[i].break_penalty_;
 993     }
 994
 995   for (vsize i = 0; i < res.force_.size (); i++)
 996     {
 997       Real f = res.force_[i];
 998       if (isinf (f) && res.systems_per_page_[i] == 1)
 999         f = BAD_SPACING_PENALTY;
1000
1001       page_force += f * f;
1002     }
1003
1004   /* for a while we tried averaging page and line forces across pages instead
1005      of summing them, but it caused a problem: if there is a single page
1006      with a very bad page force (for example because of a forced page break),
1007      the page breaker will put in a _lot_ of pages so that the bad force
1008      becomes averaged out over many pages. */
1009   res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
1010   return res;
1011
1012 }
1013
1014 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1015    are by far the most common cases, we have special functions for them.
1016
1017    space_systems_on_1_page has a different calling convention than most of the
1018    space_systems functions. This is because space_systems_on_1_page is (unlike
1019    the other space_systems functions) sometimes called on subsets of a full
1020    configuration. */
1021 Page_spacing_result
1022 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1023 {
1024   Page_spacing space (page_height, page_top_space_);
1025   Page_spacing_result ret;
1026
1027   for (vsize i = 0; i < lines.size (); i++)
1028     space.append_system (lines[i]);
1029
1030   ret.systems_per_page_.push_back (lines.size ());
1031   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1032   ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1033
1034   /* don't do finalize_spacing_result () because we are only an internal function */
1035   return ret;
1036 }
1037
1038 Page_spacing_result
1039 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1040 {
1041   Real page1_height = page_height (first_page_num, false);
1042   Real page2_height = page_height (first_page_num + 1, is_last ());
1043   bool ragged1 = ragged ();
1044   bool ragged2 = ragged () || (is_last () && ragged_last ());
1045
1046   /* if there is a forced break, this reduces to 2 1-page problems */
1047   cache_line_details (configuration);
1048   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1049     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1050       {
1051         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1052         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1053         Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1054         Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1055
1056         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1057         p1.force_.push_back (p2.force_[0]);
1058         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1059         return p1;
1060       }
1061
1062   vector<Real> page1_force;
1063   vector<Real> page2_force;
1064   Page_spacing page1 (page1_height, page_top_space_);
1065   Page_spacing page2 (page2_height, page_top_space_);
1066   int page1_line_count = 0;
1067   int page2_line_count = 0;
1068
1069   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1070   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1071
1072   /* find the page 1 and page 2 forces for each page-breaking position */
1073   for (vsize i = 0; i < page1_force.size (); i++)
1074     {
1075       page1.append_system (cached_line_details_[i]);
1076       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1077       page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1078       page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1079
1080       // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1081       // constraints. That is, we penalize harshly when they don't happen
1082       // but we don't completely reject.
1083       page1_force[i] = line_count_penalty (page1_line_count)
1084         + (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1085
1086       if (ragged2)
1087         page2_force[page2_force.size () - 1 - i] =
1088           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1089       else
1090         page2_force[page2_force.size () - 1 - i] = page2.force_;
1091
1092       page2_force[page2_force.size () - 1 - i] += line_count_penalty (page2_line_count);
1093     }
1094
1095   /* find the position that minimises the sum of the page forces */
1096   vsize best_sys_count = 1;
1097   Real best_demerits = infinity_f;
1098   for (vsize i = 0; i < page1_force.size (); i++)
1099     {
1100       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1101       Real uneven = 2 * (page1_force[i] - page2_force[i]);
1102       Real dem = uneven * uneven + f
1103         + cached_line_details_[i+1].page_penalty_
1104         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1105       if (dem < best_demerits)
1106         {
1107           best_demerits = dem;
1108           best_sys_count = i+1;
1109         }
1110     }
1111
1112   Page_spacing_result ret;
1113   ret.systems_per_page_.push_back (best_sys_count);
1114   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1115   ret.force_.push_back (page1_force[best_sys_count-1]);
1116   ret.force_.push_back (page2_force[best_sys_count-1]);
1117   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1118     + cached_line_details_.back ().page_penalty_
1119     + cached_line_details_.back ().turn_penalty_;
1120
1121   /* don't do finalize_spacing_result () because we are only an internal function */
1122   return ret;
1123 }
1124
1125 bool
1126 Page_breaking::all_lines_stretched (vsize configuration)
1127 {
1128   cache_line_details (configuration);
1129   for (vsize i = 0; i < cached_line_details_.size (); i++)
1130     if (cached_line_details_[i].force_ < 0)
1131       return false;
1132
1133   return true;
1134 }
1135
1136 Page_breaking::Line_division
1137 Page_breaking::current_configuration (vsize configuration_index) const
1138 {
1139   return current_configurations_[configuration_index];
1140 }
1141
1142 bool
1143 Page_breaking::is_last () const
1144 {
1145   return current_end_breakpoint_ == last_break_position ();
1146 }
1147
1148 bool
1149 Page_breaking::ends_score () const
1150 {
1151   return breaks_[current_end_breakpoint_].score_ender_;
1152 }
1153
1154 vsize
1155 Page_breaking::last_break_position () const
1156 {
1157   return breaks_.size () - 1;
1158 }