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