lily/constrained-breaking.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2009 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 reasong) 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.
 391   */
 392   between_system_space_ = 0;
 393   between_system_padding_ = 0;
 394   before_title_padding_ = 0;
 395
 396   Output_def *l = pscore_->layout ();
 397
 398   SCM spacing_spec = l->c_variable ("between-system-spacing");
 399   SCM title_spec = l->c_variable ("before-title-spacing");
 400   SCM page_breaking_spacing_spec = l->c_variable ("page-breaking-between-system-spacing");
 401   Page_layout_problem::read_spacing_spec (spacing_spec,
 402                                           &between_system_padding_,
 403                                           ly_symbol2scm ("padding"));
 404   Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec,
 405                                           &between_system_padding_,
 406                                           ly_symbol2scm ("padding"));
 407   Page_layout_problem::read_spacing_spec (title_spec,
 408                                           &before_title_padding_,
 409                                           ly_symbol2scm ("padding"));
 410
 411   Interval first_line = line_dimensions_int (pscore_->layout (), 0);
 412   Interval other_lines = line_dimensions_int (pscore_->layout (), 1);
 413   /* do all the rod/spring problems */
 414   breaks_ = pscore_->find_break_indices ();
 415   all_ = pscore_->root_system ()->used_columns ();
 416   lines_.resize (breaks_.size (), breaks_.size (), Line_details ());
 417   vector<Real> forces = get_line_forces (all_,
 418                                          other_lines.length (),
 419                                          other_lines.length () - first_line.length (),
 420                                          ragged_right_);
 421   for (vsize i = 0; i + 1 < breaks_.size (); i++)
 422     {
 423       for (vsize j = i + 1; j < breaks_.size (); j++)
 424         {
 425           bool last = j == breaks_.size () - 1;
 426           bool ragged = ragged_right_ || (last && ragged_last_);
 427           Line_details &line = lines_.at (j, i);
 428
 429           line.force_ = forces[i*breaks_.size () + j];
 430           if (ragged && last && !isinf (line.force_))
 431             line.force_ = (line.force_ < 0 && j > i + 1) ? infinity_f : 0;
 432           if (isinf (line.force_))
 433             break;
 434
 435           fill_line_details (&line, i, j);
 436         }
 437     }
 438
 439   /* work out all the starting indices */
 440   for (vsize i = 0; i < start_.size (); i++)
 441     {
 442       vsize j;
 443       for (j = 0; j + 1 < breaks_.size () && breaks_[j] < start_[i]; j++)
 444         ;
 445       starting_breakpoints_.push_back (j);
 446       start_[i] = breaks_[j];
 447     }
 448   state_.resize (start_.size ());
 449 }
 450
 451 /*
 452   Fills out all of the information contained in a Line_details,
 453   except for information about horizontal spacing.
 454 */
 455 void
 456 Constrained_breaking::fill_line_details (Line_details *const out, vsize start, vsize end)
 457 {
 458   int start_rank = Paper_column::get_rank (all_[breaks_[start]]);
 459   int end_rank = Paper_column::get_rank (all_[breaks_[end]]);
 460   System *sys = pscore_->root_system ();
 461   Interval extent = sys->pure_height (sys, start_rank, end_rank);
 462
 463   Grob *c = all_[breaks_[end]];
 464   out->last_column_ = c;
 465   out->break_penalty_ = robust_scm2double (c->get_property ("line-break-penalty"), 0);
 466   out->page_penalty_ = robust_scm2double (c->get_property ("page-break-penalty"), 0);
 467   out->turn_penalty_ = robust_scm2double (c->get_property ("page-turn-penalty"), 0);
 468   out->break_permission_ = c->get_property ("line-break-permission");
 469   out->page_permission_ = c->get_property ("page-break-permission");
 470   out->turn_permission_ = c->get_property ("page-turn-permission");
 471
 472   /* turn permission should always be stricter than page permission
 473      and page permission should always be stricter than line permission */
 474   out->page_permission_ = min_permission (out->break_permission_,
 475                                           out->page_permission_);
 476   out->turn_permission_ = min_permission (out->page_permission_,
 477                                           out->turn_permission_);
 478
 479   // TODO: see the hack regarding begin_of_line and
 480   // rest_of_line extents in align-interface.  Perhaps we
 481   // should do the same thing here so that the effect extends
 482   // between systems as well as within systems.  It isn't as
 483   // crucial here, however, because the effect is largest when
 484   // dealing with large systems.
 485   out->extent_ = (extent.is_empty ()
 486                   || isnan (extent[LEFT])
 487                   || isnan (extent[RIGHT]))
 488     ? Interval (0, 0) : extent;
 489   out->padding_ = between_system_padding_;
 490   out->title_padding_ = before_title_padding_;
 491   out->space_ = between_system_space_;
 492   out->inverse_hooke_ = extent.length () + between_system_space_;
 493 }
 494
 495 Real
 496 Constrained_breaking::combine_demerits (Real force, Real prev_force)
 497 {
 498   if (ragged_right_)
 499     return force * force;
 500
 501   return force * force + (prev_force - force) * (prev_force - force);
 502 }
 503
 504 Line_details::Line_details (Prob *pb, Output_def *paper)
 505 {
 506   SCM spec = paper->c_variable ("after-title-spacing");
 507   SCM title_spec = paper->c_variable ("between-title-spacing");
 508   padding_ = 0;
 509   title_padding_ = 0;
 510   Page_layout_problem::read_spacing_spec (spec, &padding_, ly_symbol2scm ("padding"));
 511   Page_layout_problem::read_spacing_spec (title_spec, &title_padding_, ly_symbol2scm ("padding"));
 512
 513   last_column_ = 0;
 514   force_ = 0;
 515   extent_ = unsmob_stencil (pb->get_property ("stencil")) ->extent (Y_AXIS);
 516   bottom_padding_ = 0;
 517   space_ = robust_scm2double (pb->get_property ("next-space"), 1.0);
 518   inverse_hooke_ = 1.0;
 519   break_permission_ = ly_symbol2scm ("allow");
 520   page_permission_ = pb->get_property ("page-break-permission");
 521   turn_permission_ = pb->get_property ("page-turn-permission");
 522   break_penalty_ = 0;
 523   page_penalty_ = robust_scm2double (pb->get_property ("page-break-penalty"), 0);
 524   turn_penalty_ = robust_scm2double (pb->get_property ("page-turn-penalty"), 0);
 525   title_ = to_boolean (pb->get_property ("is-title"));
 526   compressed_lines_count_ = 1;
 527   compressed_nontitle_lines_count_ = title_ ? 0 : 1;
 528   SCM last_scm  = pb->get_property ("last-markup-line");
 529   last_markup_line_  = to_boolean (last_scm);
 530   SCM first_scm = pb->get_property ("first-markup-line");
 531   first_markup_line_ = to_boolean (first_scm);
 532 }