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       res.force_.push_back (space.force_);
 928       res.penalty_ += cached_line_details_[line-1].page_penalty_;
 929       if (system_count_on_this_page != systems_per_page_)
 930         {
 931           res.penalty_ += TERRIBLE_SPACING_PENALTY;
 932           res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
 933             ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
 934         }
 935
 936       page_first_line = line;
 937     }
 938
 939   /* Recalculate forces for the last page because we know now that is
 940      really the last page. */
 941   space.resize (page_height (first_page_num + page, true));
 942   res.force_.back () = space.force_;
 943   return finalize_spacing_result (configuration, res);
 944 }
 945
 946 Page_spacing_result
 947 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
 948 {
 949   // TODO: add support for min/max-systems-per-page.
 950   Page_spacing_result res;
 951   vsize page = 0;
 952   vsize page_first_line = 0;
 953   Page_spacing space (page_height (first_page_num, false), page_top_space_);
 954
 955   cache_line_details (configuration);
 956   for (vsize line = 0; line < cached_line_details_.size (); line++)
 957     {
 958       Real prev_force = space.force_;
 959       space.append_system (cached_line_details_[line]);
 960       if ((line > page_first_line)
 961           && (isinf (space.force_)
 962               || ((line > 0)
 963                   && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
 964         {
 965           res.systems_per_page_.push_back (line - page_first_line);
 966           res.force_.push_back (prev_force);
 967           res.penalty_ += cached_line_details_[line-1].page_penalty_;
 968           page++;
 969           space.resize (page_height (first_page_num + page, false));
 970           space.clear ();
 971           space.append_system (cached_line_details_[line]);
 972           page_first_line = line;
 973         }
 974
 975       if (line == cached_line_details_.size () - 1)
 976         {
 977           /* This is the last line */
 978           /* When the last page height was computed, we did not know yet that it
 979            * was the last one. If the systems put on it don't fit anymore, the last
 980            * system is moved to a new page */
 981           space.resize (page_height (first_page_num + page, true));
 982           if ((line > page_first_line) && (isinf (space.force_)))
 983             {
 984               res.systems_per_page_.push_back (line - page_first_line);
 985               res.force_.push_back (prev_force);
 986               /* the last page containing the last line */
 987               space.resize (page_height (first_page_num + page + 1, true));
 988               space.clear ();
 989               space.append_system (cached_line_details_[line]);
 990               res.systems_per_page_.push_back (1);
 991               res.force_.push_back (space.force_);
 992               res.penalty_ += cached_line_details_[line-1].page_penalty_;
 993               res.penalty_ += cached_line_details_[line].page_penalty_;
 994             }
 995           else
 996             {
 997               res.systems_per_page_.push_back (line + 1 - page_first_line);
 998               res.force_.push_back (space.force_);
 999               res.penalty_ += cached_line_details_[line].page_penalty_;
1000             }
1001         }
1002     }
1003   return finalize_spacing_result (configuration, res);
1004 }
1005
1006 /* Calculate demerits and fix res.systems_per_page_ so that
1007    it refers to the original line numbers, not the ones given by compress_lines (). */
1008 Page_spacing_result
1009 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1010 {
1011   if (res.force_.empty ())
1012     return res;
1013
1014   cache_line_details (configuration);
1015   res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1016
1017   Real line_force = 0;
1018   Real line_penalty = 0;
1019   Real page_demerits = res.penalty_;
1020   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1021
1022   for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1023     {
1024       line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1025       line_penalty += uncompressed_line_details_[i].break_penalty_;
1026     }
1027
1028   for (vsize i = 0; i < res.force_.size (); i++)
1029     {
1030       Real f = res.force_[i];
1031
1032       page_demerits += min(f*f, BAD_SPACING_PENALTY);
1033     }
1034
1035   /* for a while we tried averaging page and line forces across pages instead
1036      of summing them, but it caused a problem: if there is a single page
1037      with a very bad page force (for example because of a forced page break),
1038      the page breaker will put in a _lot_ of pages so that the bad force
1039      becomes averaged out over many pages. */
1040   res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1041   return res;
1042
1043 }
1044
1045 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1046    are by far the most common cases, we have special functions for them.
1047
1048    space_systems_on_1_page has a different calling convention than most of the
1049    space_systems functions. This is because space_systems_on_1_page is (unlike
1050    the other space_systems functions) sometimes called on subsets of a full
1051    configuration. */
1052 Page_spacing_result
1053 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1054 {
1055   Page_spacing space (page_height, page_top_space_);
1056   Page_spacing_result ret;
1057   int line_count = 0;
1058
1059   for (vsize i = 0; i < lines.size (); i++)
1060     {
1061       space.append_system (lines[i]);
1062       line_count += lines[i].compressed_nontitle_lines_count_;
1063     }
1064
1065   ret.systems_per_page_.push_back (lines.size ());
1066   ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1067   ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1068   ret.system_count_status_ |= line_count_status (line_count);
1069
1070   /* don't do finalize_spacing_result () because we are only an internal function */
1071   return ret;
1072 }
1073
1074 Page_spacing_result
1075 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1076 {
1077   Real page1_height = page_height (first_page_num, false);
1078   Real page2_height = page_height (first_page_num + 1, is_last ());
1079   bool ragged1 = ragged ();
1080   bool ragged2 = ragged () || (is_last () && ragged_last ());
1081
1082   /* if there is a forced break, this reduces to 2 1-page problems */
1083   cache_line_details (configuration);
1084   for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1085     if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1086       {
1087         vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1088         vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1089         Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1090         Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1091
1092         p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1093         p1.force_.push_back (p2.force_[0]);
1094         p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1095         return p1;
1096       }
1097
1098   vector<Real> page1_force;
1099   vector<Real> page2_force;
1100
1101   // page1_penalty and page2_penalty store the penalties based
1102   // on min-systems-per-page and max-systems-per-page.
1103   vector<Real> page1_penalty;
1104   vector<Real> page2_penalty;
1105
1106   // page1_status and page2_status keep track of whether the min-systems-per-page
1107   // and max-systems-per-page constraints are satisfied.
1108   vector<int> page1_status;
1109   vector<int> page2_status;
1110
1111   Page_spacing page1 (page1_height, page_top_space_);
1112   Page_spacing page2 (page2_height, page_top_space_);
1113   int page1_line_count = 0;
1114   int page2_line_count = 0;
1115
1116   page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1117   page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1118   page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1119   page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1120   page1_status.resize (cached_line_details_.size () - 1, 0);
1121   page2_status.resize (cached_line_details_.size () - 1, 0);
1122
1123   /* find the page 1 and page 2 forces for each page-breaking position */
1124   for (vsize i = 0; i < page1_force.size (); i++)
1125     {
1126       page1.append_system (cached_line_details_[i]);
1127       page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1128       page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1129       page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1130
1131       page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1132       page1_penalty[i] = line_count_penalty (page1_line_count);
1133       page1_status[i] = line_count_status (page1_line_count);
1134
1135       if (ragged2)
1136         page2_force[page2_force.size () - 1 - i] =
1137           (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1138       else
1139         page2_force[page2_force.size () - 1 - i] = page2.force_;
1140       page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1141       page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1142     }
1143
1144   /* find the position that minimises the sum of the page forces */
1145   vsize best_sys_count = 1;
1146   Real best_demerits = infinity_f;
1147   for (vsize i = 0; i < page1_force.size (); i++)
1148     {
1149       Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1150
1151       // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1152       // constraints. That is, we penalize harshly when they don't happen
1153       // but we don't completely reject.
1154       Real dem = f
1155         + page1_penalty[i] + page2_penalty[i]
1156         + cached_line_details_[i+1].page_penalty_
1157         + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1158       if (dem < best_demerits)
1159         {
1160           best_demerits = dem;
1161           best_sys_count = i+1;
1162         }
1163     }
1164
1165   Page_spacing_result ret;
1166   ret.systems_per_page_.push_back (best_sys_count);
1167   ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1168   ret.force_.push_back (page1_force[best_sys_count-1]);
1169   ret.force_.push_back (page2_force[best_sys_count-1]);
1170   ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1171   ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1172     + cached_line_details_.back ().page_penalty_
1173     + cached_line_details_.back ().turn_penalty_
1174     + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1175
1176   /* don't do finalize_spacing_result () because we are only an internal function */
1177   return ret;
1178 }
1179
1180 bool
1181 Page_breaking::all_lines_stretched (vsize configuration)
1182 {
1183   cache_line_details (configuration);
1184   for (vsize i = 0; i < cached_line_details_.size (); i++)
1185     if (cached_line_details_[i].force_ < 0)
1186       return false;
1187
1188   return true;
1189 }
1190
1191 Page_breaking::Line_division
1192 Page_breaking::current_configuration (vsize configuration_index) const
1193 {
1194   return current_configurations_[configuration_index];
1195 }
1196
1197 bool
1198 Page_breaking::is_last () const
1199 {
1200   return current_end_breakpoint_ == last_break_position ();
1201 }
1202
1203 bool
1204 Page_breaking::ends_score () const
1205 {
1206   return breaks_[current_end_breakpoint_].score_ender_;
1207 }
1208
1209 vsize
1210 Page_breaking::last_break_position () const
1211 {
1212   return breaks_.size () - 1;
1213 }