lily/constrained-breaking.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2010 Joe Neeman <joeneeman@gmail.com>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "constrained-breaking.hh"
  21
  22 #include "international.hh"
  23 #include "main.hh"
  24 #include "output-def.hh"
  25 #include "page-layout-problem.hh"
  26 #include "paper-column.hh"
  27 #include "paper-score.hh"
  28 #include "simple-spacer.hh"
  29 #include "system.hh"
  30 #include "warn.hh"
  31
  32 /*
  33   We use the following optimal substructure. Let W (A) be our weight function.
  34
  35   Let A_{k, n} = (a_{k, n, 1}, ... a_{k, n, k}) be the optimal set of line breaks
  36   for k systems and n potential breakpoints. a_{k, n, k} = n (it is the end of
  37   the piece)
  38
  39   Then A_{k+1, m} is contructed from
  40   min_ {k < j < m} ( W (A_{k, j} :: m) )
  41   where by A::m we denote appending m to the list A
  42
  43   Indices in the code:
  44
  45   The above algorithm makes it easy to end at a point before the end of the
  46   score (just find A_{k, m} for some m < breaks_.size () - 1). However, we must
  47   add information for starting at a point after the beginning. One constructor
  48   allows the specification of a list of starting columns, start_. We then have
  49   start_.size () different solution arrays. state_[i] is the array for the
  50   solution starting at column number start_[i].
  51
  52   The indices "start" and "end" refer to the index in the start_ array of the
  53   desired starting and ending columns.
  54
  55   each solution array looks like
  56    a_{1,1,1} a_{2,1,2} a_{3,1,3} . . .
  57        X     a_{2,2,2} a_{3,2,3} . . .
  58        X         X     a_{3,3,3} . . .
  59        .         .         .     .
  60        .         .         .       .
  61   where the X's mark invalid solutions (can't have more systems than
  62   breakpoints). Note that each value is of the form a_{x, n, x}. This is because
  63   a breakpoint of the form a_{x, n, x-1} will also be called a_{x-1, m, x-1} for
  64   some m < n. Each cell in the array stores the value of its m (ie. the
  65   ending breakpoint of the previous line) as "prev_".
  66
  67   For finding A_{sys, brk}, let "me" be the (sys_count, brk) cell in our
  68   solution array (state_[start][sys * rank + brk]).
  69
  70   Then A_{sys, brk} = A_{sys - 1, me.prev_} :: me
  71 */
  72
  73 /*
  74   start and sys here are indexed from 0.
  75   brk is indexed from starting_breakpoints_[start]
  76   (for brk, starting_breakpoints_[start] is the beginning
  77   of the piece; the smallest value we should ever see here is
  78   starting_breakpoints_[start] + 1) */
  79 bool
  80 Constrained_breaking::calc_subproblem (vsize start, vsize sys, vsize brk)
  81 {
  82   assert (sys < systems_);
  83   assert (start < start_.size ());
  84   assert (brk < breaks_.size ());
  85
  86   bool found_something = false;
  87   vsize start_col = starting_breakpoints_[start];
  88   Matrix<Constrained_break_node> &st = state_[start];
  89   vsize max_index = brk - start_col;
  90   for (vsize j=max_index; j-- > sys;)
  91     {
  92       if (0 == sys && j > 0)
  93         continue; /* the first line cannot have its first break after the beginning */
  94
  95       Line_details const &cur = lines_.at (brk, j + start_col);
  96       if (isinf (cur.force_))
  97         break;
  98
  99       Real prev_f = 0;
 100       Real prev_dem = 0;
 101
 102       if (sys > 0)
 103         {
 104           prev_f = st.at (j, sys-1).details_.force_;
 105           prev_dem = st.at (j, sys-1).demerits_;
 106         }
 107       if (isinf (prev_dem))
 108         continue;
 109
 110       Real dem = combine_demerits (cur.force_, prev_f) + prev_dem + cur.break_penalty_;
 111       Constrained_break_node &n = st.at (max_index, sys);
 112       if (dem < n.demerits_)
 113         {
 114           found_something = true;
 115           n.demerits_ = dem;
 116           n.details_ = cur;
 117           n.prev_ = j;
 118         }
 119     }
 120   return found_something;
 121 }
 122
 123
 124 Column_x_positions
 125 Constrained_breaking::space_line (vsize i, vsize j)
 126 {
 127   bool ragged_right = to_boolean (pscore_->layout ()->c_variable ("ragged-right"));
 128   bool ragged_last = to_boolean (pscore_->layout ()->c_variable ("ragged-last"));
 129   Column_x_positions col;
 130
 131   vector<Grob*> line (all_.begin () + breaks_[i],
 132                       all_.begin () + breaks_[j] + 1);
 133   Interval line_dims = line_dimensions_int (pscore_->layout (), i);
 134   bool last = j == breaks_.size () - 1;
 135   bool ragged = ragged_right || (last && ragged_last);
 136
 137   /* As a special case, if there is only one line in the score and ragged-right
 138      hasn't been specifically forbidden and the line is stretched, use
 139      ragged spacing. */
 140   if (last && i == 0
 141       && lines_.at (i, j).force_ >= 0
 142       && !scm_is_bool (pscore_->layout ()->c_variable ("ragged-right"))
 143       && !scm_is_bool (pscore_->layout ()->c_variable ("ragged-last")))
 144     ragged = true;
 145
 146   return get_line_configuration (line, line_dims[RIGHT] - line_dims[LEFT], line_dims[LEFT], ragged);
 147 }
 148
 149 void
 150 Constrained_breaking::resize (vsize systems)
 151 {
 152   systems_ = systems;
 153
 154   if (pscore_ && systems_ > valid_systems_)
 155     {
 156       for (vsize i = 0; i < state_.size (); i++)
 157         state_[i].resize (breaks_.size () - starting_breakpoints_[i], systems_, Constrained_break_node ());
 158
 159       /* fill out the matrices */
 160       for (vsize i = 0; i < state_.size (); i++)
 161         for (vsize j = valid_systems_; j < systems_; j++)
 162           for (vsize k = starting_breakpoints_[i] + j + 1; k < breaks_.size (); k++)
 163             if (!calc_subproblem (i, j, k))
 164               break; /* if we couldn't break this, it is too cramped already */
 165       valid_systems_ = systems_;
 166     }
 167 }
 168
 169 vector<Column_x_positions>
 170 Constrained_breaking::solve (vsize start, vsize end, vsize sys_count)
 171 {
 172   vsize start_brk = starting_breakpoints_[start];
 173   vsize end_brk = prepare_solution (start, end, sys_count);
 174
 175   Matrix<Constrained_break_node> const &st = state_[start];
 176   vector<Column_x_positions> ret;
 177
 178   /* find the first solution that satisfies constraints */
 179   for (vsize sys = sys_count-1; sys != VPOS; sys--)
 180     {
 181       for (vsize brk = end_brk; brk != VPOS; brk--)
 182         {
 183           if (!isinf (st.at (brk, sys).details_.force_))
 184             {
 185               if (brk != end_brk)
 186                 {
 187                   brk = st.at (brk, sys).prev_;
 188                   sys--;
 189                   warning (_ ("cannot find line breaking that satisfies constraints"));
 190                   ret.push_back (space_line (brk, end_brk));
 191                 }
 192
 193               /* build up the good part of the solution */
 194               for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--)
 195                 {
 196                   vsize prev_brk = st.at (brk, cur_sys).prev_;
 197                   assert (brk != VPOS);
 198                   ret.push_back (space_line (prev_brk + start_brk, brk + start_brk));
 199                   brk = prev_brk;
 200                 }
 201               reverse (ret);
 202               return ret;
 203             }
 204         }
 205     }
 206   /* if we get to here, just put everything on one line */
 207   warning (_ ("cannot find line breaking that satisfies constraints"));
 208   ret.push_back (space_line (0, end_brk));
 209   return ret;
 210 }
 211
 212 vector<Column_x_positions>
 213 Constrained_breaking::best_solution (vsize start, vsize end)
 214 {
 215   vsize min_systems = min_system_count (start, end);
 216   vsize max_systems = max_system_count (start, end);
 217   Real best_demerits = infinity_f;
 218   vector<Column_x_positions> best_so_far;
 219
 220   for (vsize i = min_systems; i <= max_systems; i++)
 221     {
 222       vsize brk = prepare_solution (start, end, i);
 223       Real dem = state_[start].at (brk, i-1).demerits_;
 224
 225       if (dem < best_demerits)
 226         {
 227           best_demerits = dem;
 228           best_so_far = solve (start, end, i);
 229         }
 230       else
 231         {
 232           vector<Column_x_positions> cur = solve (start, end, i);
 233           bool too_many_lines = true;
 234
 235           for (vsize j = 0; j < cur.size (); j++)
 236             if (cur[j].force_ < 0)
 237               {
 238                 too_many_lines = false;
 239                 break;
 240               }
 241           if (too_many_lines)
 242             return best_so_far;
 243         }
 244     }
 245   if (best_so_far.size ())
 246     return best_so_far;
 247   return solve (start, end, max_systems);
 248 }
 249
 250 std::vector<Line_details>
 251 Constrained_breaking::line_details (vsize start, vsize end, vsize sys_count)
 252 {
 253   vsize end_brk = prepare_solution (start, end, sys_count);
 254   Matrix<Constrained_break_node> const &st = state_[start];
 255   vector<Line_details> ret;
 256
 257   /* This loop structure is C&Ped from solve(). */
 258   /* find the first solution that satisfies constraints */
 259   for (vsize sys = sys_count-1; sys != VPOS; sys--)
 260     {
 261       for (vsize brk = end_brk; brk != VPOS; brk--)
 262         {
 263           if (!isinf (st.at (brk, sys).details_.force_))
 264             {
 265               if (brk != end_brk)
 266                 {
 267                   /*
 268                     During initialize(), we only fill out a
 269                     Line_details for lines that are valid (ie. not too
 270                     long), otherwise line breaking becomes O(n^3).
 271                     In case sys_count is such that no valid solution
 272                     is found, we need to fill in the Line_details.
 273                   */
 274                   Line_details details;
 275                   brk = st.at (brk, sys).prev_;
 276                   sys--;
 277                   fill_line_details (&details, brk, end_brk);
 278                   ret.push_back (details);
 279                 }
 280
 281               /* build up the good part of the solution */
 282               for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--)
 283                 {
 284                   vsize prev_brk = st.at (brk, cur_sys).prev_;
 285                   assert (brk != VPOS);
 286                   ret.push_back (st.at (brk, cur_sys).details_);
 287                   brk = prev_brk;
 288                 }
 289               reverse (ret);
 290               return ret;
 291             }
 292         }
 293     }
 294
 295   /* if we get to here, just put everything on one line */
 296   Line_details details;
 297   fill_line_details (&details, 0, end_brk);
 298   ret.push_back (details);
 299   return ret;
 300 }
 301
 302 int
 303 Constrained_breaking::min_system_count (vsize start, vsize end)
 304 {
 305   vsize sys_count;
 306   vsize brk = prepare_solution (start, end, 1);
 307   vsize rank = breaks_.size () - starting_breakpoints_[start];
 308   Matrix<Constrained_break_node> const &st = state_[start];
 309
 310   /* sys_count < rank : rank is the # of breakpoints, we can't have more systems */
 311   for (sys_count = 0; sys_count < rank; sys_count++)
 312     {
 313       if (sys_count >= valid_systems_)
 314         {
 315           resize (sys_count + 3);
 316         }
 317       if (!isinf (st.at (brk, sys_count).details_.force_))
 318         return sys_count + 1;
 319     }
 320   /* no possible breaks satisfy constraints */
 321   return 1;
 322 }
 323
 324 int
 325 Constrained_breaking::max_system_count (vsize start, vsize end)
 326 {
 327   vsize brk = (end >= start_.size ()) ? breaks_.size () - 1 : starting_breakpoints_[end];
 328   return brk - starting_breakpoints_[start];
 329 }
 330
 331 vsize
 332 Constrained_breaking::prepare_solution (vsize start, vsize end, vsize sys_count)
 333 {
 334   assert (start < start_.size () && (end == VPOS || end <= start_.size ()));
 335   assert (start < end);
 336
 337   resize (sys_count);
 338   if (end == start_.size ())
 339     end = VPOS;
 340
 341   vsize brk;
 342   brk = end == VPOS ? breaks_.size () - 1 : starting_breakpoints_[end];
 343   brk -= starting_breakpoints_[start];
 344   return brk;
 345 }
 346
 347 Constrained_breaking::Constrained_breaking (Paper_score *ps)
 348 {
 349   valid_systems_ = systems_ = 0;
 350   start_.push_back (0);
 351   pscore_ = ps;
 352   initialize ();
 353 }
 354
 355 Constrained_breaking::Constrained_breaking (Paper_score *ps, vector<vsize> const &start)
 356   : start_ (start)
 357 {
 358   valid_systems_ = systems_ = 0;
 359   pscore_ = ps;
 360   initialize ();
 361 }
 362
 363 static SCM
 364 min_permission (SCM perm1, SCM perm2)
 365 {
 366   if (perm1 == ly_symbol2scm ("force"))
 367     return perm2;
 368   if (perm1 == ly_symbol2scm ("allow")
 369      && perm2 != ly_symbol2scm ("force"))
 370     return perm2;
 371   return SCM_EOL;
 372 }
 373
 374 /* find the forces for all possible lines and cache ragged_ and ragged_right_ */
 375 void
 376 Constrained_breaking::initialize ()
 377 {
 378   if (!pscore_)
 379     return;
 380
 381   ragged_right_ = to_boolean (pscore_->layout ()->c_variable ("ragged-right"));
 382   ragged_last_ = to_boolean (pscore_->layout ()->c_variable ("ragged-last"));
 383   /* NOTE: currently, we aren't using the space_ field of a
 384      Line_details for anything.  That's because the approximations
 385      used for scoring a page configuration don't actually space things
 386      properly (for speed reasons) using springs anchored at the staff
 387      refpoints.  Rather, the "space" is placed between the extent
 388      boxes.  To get a good result, therefore, the "space" value for
 389      page breaking needs to be much smaller than the "space" value for
 390      page layout.  Currently, we just make it zero always, which means
 391      that we will always prefer a tighter vertical layout.
 392   */
 393   between_system_space_ = 0;
 394   between_system_padding_ = 0;
 395   between_system_min_distance_ = 0;
 396   between_scores_system_padding_ = 0;
 397   between_scores_system_min_distance_ = 0;
 398   before_title_padding_ = 0;
 399   before_title_min_distance_ = 0;
 400
 401   Output_def *l = pscore_->layout ();
 402
 403   SCM spacing_spec = l->c_variable ("between-system-spacing");
 404   SCM between_scores_spec = l->c_variable ("between-scores-system-spacing");
 405   SCM title_spec = l->c_variable ("before-title-spacing");
 406   SCM page_breaking_spacing_spec = l->c_variable ("page-breaking-between-system-spacing");
 407   Page_layout_problem::read_spacing_spec (spacing_spec,
 408                                           &between_system_padding_,
 409                                           ly_symbol2scm ("padding"));
 410   Page_layout_problem::read_spacing_spec (between_scores_spec,
 411                                           &between_scores_system_padding_,
 412                                           ly_symbol2scm ("padding"));
 413   Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec,
 414                                           &between_system_padding_,
 415                                           ly_symbol2scm ("padding"));
 416   Page_layout_problem::read_spacing_spec (title_spec,
 417                                           &before_title_padding_,
 418                                           ly_symbol2scm ("padding"));
 419   Page_layout_problem::read_spacing_spec (between_scores_spec,
 420                                           &between_scores_system_min_distance_,
 421                                           ly_symbol2scm ("minimum-distance"));
 422   Page_layout_problem::read_spacing_spec (spacing_spec,
 423                                           &between_system_min_distance_,
 424                                           ly_symbol2scm ("minimum-distance"));
 425   Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec,
 426                                           &between_system_min_distance_,
 427                                           ly_symbol2scm ("minimum-distance"));
 428   Page_layout_problem::read_spacing_spec (title_spec,
 429                                           &before_title_min_distance_,
 430                                           ly_symbol2scm ("minimum-distance"));
 431
 432   Interval first_line = line_dimensions_int (pscore_->layout (), 0);
 433   Interval other_lines = line_dimensions_int (pscore_->layout (), 1);
 434   /* do all the rod/spring problems */
 435   breaks_ = pscore_->find_break_indices ();
 436   all_ = pscore_->root_system ()->used_columns ();
 437   lines_.resize (breaks_.size (), breaks_.size (), Line_details ());
 438   vector<Real> forces = get_line_forces (all_,
 439                                          other_lines.length (),
 440                                          other_lines.length () - first_line.length (),
 441                                          ragged_right_);
 442   for (vsize i = 0; i + 1 < breaks_.size (); i++)
 443     {
 444       for (vsize j = i + 1; j < breaks_.size (); j++)
 445         {
 446           bool last = j == breaks_.size () - 1;
 447           bool ragged = ragged_right_ || (last && ragged_last_);
 448           Line_details &line = lines_.at (j, i);
 449
 450           line.force_ = forces[i*breaks_.size () + j];
 451           if (ragged && last && !isinf (line.force_))
 452             line.force_ = (line.force_ < 0 && j > i + 1) ? infinity_f : 0;
 453           if (isinf (line.force_))
 454             break;
 455
 456           fill_line_details (&line, i, j);
 457         }
 458     }
 459
 460   /* work out all the starting indices */
 461   for (vsize i = 0; i < start_.size (); i++)
 462     {
 463       vsize j;
 464       for (j = 0; j + 1 < breaks_.size () && breaks_[j] < start_[i]; j++)
 465         ;
 466       starting_breakpoints_.push_back (j);
 467       start_[i] = breaks_[j];
 468     }
 469   state_.resize (start_.size ());
 470 }
 471
 472 /*
 473   Fills out all of the information contained in a Line_details,
 474   except for information about horizontal spacing.
 475 */
 476 void
 477 Constrained_breaking::fill_line_details (Line_details *const out, vsize start, vsize end)
 478 {
 479   int start_rank = Paper_column::get_rank (all_[breaks_[start]]);
 480   int end_rank = Paper_column::get_rank (all_[breaks_[end]]);
 481   System *sys = pscore_->root_system ();
 482   Interval begin_of_line_extent = sys->begin_of_line_pure_height (start_rank, end_rank);
 483   Interval rest_of_line_extent = sys->rest_of_line_pure_height (start_rank, end_rank);
 484   bool last = (end == breaks_.size () - 1);
 485
 486   Grob *c = all_[breaks_[end]];
 487   out->last_column_ = c;
 488   out->break_penalty_ = robust_scm2double (c->get_property ("line-break-penalty"), 0);
 489   out->page_penalty_ = robust_scm2double (c->get_property ("page-break-penalty"), 0);
 490   out->turn_penalty_ = robust_scm2double (c->get_property ("page-turn-penalty"), 0);
 491   out->break_permission_ = c->get_property ("line-break-permission");
 492   out->page_permission_ = c->get_property ("page-break-permission");
 493   out->turn_permission_ = c->get_property ("page-turn-permission");
 494
 495   /* turn permission should always be stricter than page permission
 496      and page permission should always be stricter than line permission */
 497   out->page_permission_ = min_permission (out->break_permission_,
 498                                           out->page_permission_);
 499   out->turn_permission_ = min_permission (out->page_permission_,
 500                                           out->turn_permission_);
 501
 502   begin_of_line_extent = (begin_of_line_extent.is_empty ()
 503                           || isnan (begin_of_line_extent[LEFT])
 504                           || isnan (begin_of_line_extent[RIGHT]))
 505     ? Interval (0, 0) : begin_of_line_extent;
 506   rest_of_line_extent = (rest_of_line_extent.is_empty ()
 507                          || isnan (rest_of_line_extent[LEFT])
 508                          || isnan (rest_of_line_extent[RIGHT]))
 509     ? Interval (0, 0) : rest_of_line_extent;
 510   out->shape_ = Line_shape (begin_of_line_extent, rest_of_line_extent);
 511   out->padding_ = last ? between_scores_system_padding_ : between_system_padding_;
 512   out->title_padding_ = before_title_padding_;
 513   out->min_distance_ = last ? between_scores_system_min_distance_ : between_system_min_distance_;
 514   out->title_min_distance_ = before_title_min_distance_;
 515   out->space_ = between_system_space_;
 516   out->inverse_hooke_ = out->full_height () + between_system_space_;
 517 }
 518
 519 Real
 520 Constrained_breaking::combine_demerits (Real force, Real prev_force)
 521 {
 522   if (ragged_right_)
 523     return force * force;
 524
 525   return force * force + (prev_force - force) * (prev_force - force);
 526 }
 527
 528 Line_details::Line_details (Prob *pb, Output_def *paper)
 529 {
 530   SCM spec = paper->c_variable ("after-title-spacing");
 531   SCM title_spec = paper->c_variable ("between-title-spacing");
 532   padding_ = 0;
 533   title_padding_ = 0;
 534   Page_layout_problem::read_spacing_spec (spec, &padding_, ly_symbol2scm ("padding"));
 535   Page_layout_problem::read_spacing_spec (title_spec, &title_padding_, ly_symbol2scm ("padding"));
 536   Page_layout_problem::read_spacing_spec (spec, &min_distance_, ly_symbol2scm ("minimum-distance"));
 537   Page_layout_problem::read_spacing_spec (title_spec, &title_min_distance_, ly_symbol2scm ("minimum-distance"));
 538
 539   last_column_ = 0;
 540   force_ = 0;
 541   Interval stencil_extent = unsmob_stencil (pb->get_property ("stencil"))->extent (Y_AXIS);
 542   shape_ = Line_shape (stencil_extent, stencil_extent); // pretend it goes all the way across
 543   tallness_ = 0;
 544   bottom_padding_ = 0;
 545   space_ = 0.0;
 546   inverse_hooke_ = 1.0;
 547   break_permission_ = ly_symbol2scm ("allow");
 548   page_permission_ = pb->get_property ("page-break-permission");
 549   turn_permission_ = pb->get_property ("page-turn-permission");
 550   break_penalty_ = 0;
 551   page_penalty_ = robust_scm2double (pb->get_property ("page-break-penalty"), 0);
 552   turn_penalty_ = robust_scm2double (pb->get_property ("page-turn-penalty"), 0);
 553   title_ = to_boolean (pb->get_property ("is-title"));
 554   compressed_lines_count_ = 1;
 555   compressed_nontitle_lines_count_ = title_ ? 0 : 1;
 556   SCM last_scm  = pb->get_property ("last-markup-line");
 557   last_markup_line_  = to_boolean (last_scm);
 558   SCM first_scm = pb->get_property ("first-markup-line");
 559   first_markup_line_ = to_boolean (first_scm);
 560   tight_spacing_ = to_boolean (pb->get_property ("tight-spacing"));
 561   first_refpoint_offset_ = 0;
 562 }
 563
 564 Real
 565 Line_details::full_height () const
 566 {
 567   Interval ret;
 568   ret.unite(shape_.begin_);
 569   ret.unite(shape_.rest_);
 570   return ret.length();
 571 }
 572
 573 Real
 574 Line_details::tallness () const
 575 {
 576   return tallness_;
 577 }
 578
 579 Line_shape::Line_shape (Interval begin, Interval rest)
 580 {
 581   begin_ = begin;
 582   rest_ = rest;
 583 }
 584
 585 Line_shape
 586 Line_shape::piggyback (Line_shape mount, Real padding) const
 587 {
 588   Real elevation = max (begin_[UP]-mount.begin_[DOWN], rest_[UP]-mount.rest_[DOWN]);
 589   Interval begin = Interval (begin_[DOWN], elevation + mount.begin_[UP] + padding);
 590   Interval rest = Interval (rest_[DOWN], elevation + mount.rest_[UP] + padding);
 591   return Line_shape (begin, rest);
 592 }