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