lily/constrained-breaking.cc

   1 /*
   2   constrained-breaking.cc -- implement a line breaker that
   3   support limits on the number of systems
   4
   5   source file of the GNU LilyPond music typesetter
   6
   7   (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
   8 */
   9
  10 #include "constrained-breaking.hh"
  11
  12 #include "international.hh"
  13 #include "main.hh"
  14 #include "output-def.hh"
  15 #include "page-layout-problem.hh"
  16 #include "paper-column.hh"
  17 #include "paper-score.hh"
  18 #include "simple-spacer.hh"
  19 #include "system.hh"
  20 #include "warn.hh"
  21
  22 /*
  23   We use the following optimal substructure. Let W (A) be our weight function.
  24
  25   Let A_{k, n} = (a_{k, n, 1}, ... a_{k, n, k}) be the optimal set of line breaks
  26   for k systems and n potential breakpoints. a_{k, n, k} = n (it is the end of
  27   the piece)
  28
  29   Then A_{k+1, m} is contructed from
  30   min_ {k < j < m} ( W (A_{k, j} :: m) )
  31   where by A::m we denote appending m to the list A
  32
  33   Indices in the code:
  34
  35   The above algorithm makes it easy to end at a point before the end of the
  36   score (just find A_{k, m} for some m < breaks_.size () - 1). However, we must
  37   add information for starting at a point after the beginning. One constructor
  38   allows the specification of a list of starting columns, start_. We then have
  39   start_.size () different solution arrays. state_[i] is the array for the
  40   solution starting at column number start_[i].
  41
  42   The indices "start" and "end" refer to the index in the start_ array of the
  43   desired starting and ending columns.
  44
  45   each solution array looks like
  46    a_{1,1,1} a_{2,1,2} a_{3,1,3} . . .
  47        X     a_{2,2,2} a_{3,2,3} . . .
  48        X         X     a_{3,3,3} . . .
  49        .         .         .     .
  50        .         .         .       .
  51   where the X's mark invalid solutions (can't have more systems than
  52   breakpoints). Note that each value is of the form a_{x, n, x}. This is because
  53   a breakpoint of the form a_{x, n, x-1} will also be called a_{x-1, m, x-1} for
  54   some m < n. Each cell in the array stores the value of its m (ie. the
  55   ending breakpoint of the previous line) as "prev_".
  56
  57   For finding A_{sys, brk}, let "me" be the (sys_count, brk) cell in our
  58   solution array (state_[start][sys * rank + brk]).
  59
  60   Then A_{sys, brk} = A_{sys - 1, me.prev_} :: me
  61 */
  62
  63 /*
  64   start and sys here are indexed from 0.
  65   brk is indexed from starting_breakpoints_[start]
  66   (for brk, starting_breakpoints_[start] is the beginning
  67   of the piece; the smallest value we should ever see here is
  68   starting_breakpoints_[start] + 1) */
  69 bool
  70 Constrained_breaking::calc_subproblem (vsize start, vsize sys, vsize brk)
  71 {
  72   assert (sys < systems_);
  73   assert (start < start_.size ());
  74   assert (brk < breaks_.size ());
  75
  76   bool found_something = false;
  77   vsize start_col = starting_breakpoints_[start];
  78   Matrix<Constrained_break_node> &st = state_[start];
  79   vsize max_index = brk - start_col;
  80   for (vsize j=max_index; j-- > sys;)
  81     {
  82       if (0 == sys && j > 0)
  83         continue; /* the first line cannot have its first break after the beginning */
  84
  85       Line_details const &cur = lines_.at (brk, j + start_col);
  86       if (isinf (cur.force_))
  87         break;
  88
  89       Real prev_f = 0;
  90       Real prev_dem = 0;
  91
  92       if (sys > 0)
  93         {
  94           prev_f = st.at (j, sys-1).details_.force_;
  95           prev_dem = st.at (j, sys-1).demerits_;
  96         }
  97       if (isinf (prev_dem))
  98         continue;
  99
 100       Real dem = combine_demerits (cur.force_, prev_f) + prev_dem + cur.break_penalty_;
 101       Constrained_break_node &n = st.at (max_index, sys);
 102       if (dem < n.demerits_)
 103         {
 104           found_something = true;
 105           n.demerits_ = dem;
 106           n.details_ = cur;
 107           n.prev_ = j;
 108         }
 109     }
 110   return found_something;
 111 }
 112
 113
 114 Column_x_positions
 115 Constrained_breaking::space_line (vsize i, vsize j)
 116 {
 117   bool ragged_right = to_boolean (pscore_->layout ()->c_variable ("ragged-right"));
 118   bool ragged_last = to_boolean (pscore_->layout ()->c_variable ("ragged-last"));
 119   Column_x_positions col;
 120
 121   vector<Grob*> line (all_.begin () + breaks_[i],
 122                       all_.begin () + breaks_[j] + 1);
 123   Interval line_dims = line_dimensions_int (pscore_->layout (), i);
 124   bool last = j == breaks_.size () - 1;
 125   bool ragged = ragged_right || (last && ragged_last);
 126
 127   /* As a special case, if there is only one line in the score and ragged-right
 128      hasn't been specifically forbidden and the line is stretched, use
 129      ragged spacing. */
 130   if (last && i == 0
 131       && lines_.at (i, j).force_ >= 0
 132       && !scm_is_bool (pscore_->layout ()->c_variable ("ragged-right"))
 133       && !scm_is_bool (pscore_->layout ()->c_variable ("ragged-last")))
 134     ragged = true;
 135
 136   return get_line_configuration (line, line_dims[RIGHT] - line_dims[LEFT], line_dims[LEFT], ragged);
 137 }
 138
 139 void
 140 Constrained_breaking::resize (vsize systems)
 141 {
 142   systems_ = systems;
 143
 144   if (pscore_ && systems_ > valid_systems_)
 145     {
 146       for (vsize i = 0; i < state_.size (); i++)
 147         state_[i].resize (breaks_.size () - starting_breakpoints_[i], systems_, Constrained_break_node ());
 148
 149       /* fill out the matrices */
 150       for (vsize i = 0; i < state_.size (); i++)
 151         for (vsize j = valid_systems_; j < systems_; j++)
 152           for (vsize k = starting_breakpoints_[i] + j + 1; k < breaks_.size (); k++)
 153             if (!calc_subproblem (i, j, k))
 154               break; /* if we couldn't break this, it is too cramped already */
 155       valid_systems_ = systems_;
 156     }
 157 }
 158
 159 vector<Column_x_positions>
 160 Constrained_breaking::solve (vsize start, vsize end, vsize sys_count)
 161 {
 162   vsize start_brk = starting_breakpoints_[start];
 163   vsize end_brk = prepare_solution (start, end, sys_count);
 164
 165   Matrix<Constrained_break_node> const &st = state_[start];
 166   vector<Column_x_positions> ret;
 167
 168   /* find the first solution that satisfies constraints */
 169   for (vsize sys = sys_count-1; sys != VPOS; sys--)
 170     {
 171       for (vsize brk = end_brk; brk != VPOS; brk--)
 172         {
 173           if (!isinf (st.at (brk, sys).details_.force_))
 174             {
 175               if (brk != end_brk)
 176                 {
 177                   brk = st.at (brk, sys).prev_;
 178                   sys--;
 179                   warning (_ ("cannot find line breaking that satisfies constraints"));
 180                   ret.push_back (space_line (brk, end_brk));
 181                 }
 182
 183               /* build up the good part of the solution */
 184               for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--)
 185                 {
 186                   vsize prev_brk = st.at (brk, cur_sys).prev_;
 187                   assert (brk != VPOS);
 188                   ret.push_back (space_line (prev_brk + start_brk, brk + start_brk));
 189                   brk = prev_brk;
 190                 }
 191               reverse (ret);
 192               return ret;
 193             }
 194         }
 195     }
 196   /* if we get to here, just put everything on one line */
 197   warning (_ ("cannot find line breaking that satisfies constraints"));
 198   ret.push_back (space_line (0, end_brk));
 199   return ret;
 200 }
 201
 202 vector<Column_x_positions>
 203 Constrained_breaking::best_solution (vsize start, vsize end)
 204 {
 205   vsize min_systems = min_system_count (start, end);
 206   vsize max_systems = max_system_count (start, end);
 207   Real best_demerits = infinity_f;
 208   vector<Column_x_positions> best_so_far;
 209
 210   for (vsize i = min_systems; i <= max_systems; i++)
 211     {
 212       vsize brk = prepare_solution (start, end, i);
 213       Real dem = state_[start].at (brk, i-1).demerits_;
 214
 215       if (dem < best_demerits)
 216         {
 217           best_demerits = dem;
 218           best_so_far = solve (start, end, i);
 219         }
 220       else
 221         {
 222           vector<Column_x_positions> cur = solve (start, end, i);
 223           bool too_many_lines = true;
 224
 225           for (vsize j = 0; j < cur.size (); j++)
 226             if (cur[j].force_ < 0)
 227               {
 228                 too_many_lines = false;
 229                 break;
 230               }
 231           if (too_many_lines)
 232             return best_so_far;
 233         }
 234     }
 235   if (best_so_far.size ())
 236     return best_so_far;
 237   return solve (start, end, max_systems);
 238 }
 239
 240 std::vector<Line_details>
 241 Constrained_breaking::line_details (vsize start, vsize end, vsize sys_count)
 242 {
 243   vsize end_brk = prepare_solution (start, end, sys_count);
 244   Matrix<Constrained_break_node> const &st = state_[start];
 245   vector<Line_details> ret;
 246
 247   /* This loop structure is C&Ped from solve(). */
 248   /* find the first solution that satisfies constraints */
 249   for (vsize sys = sys_count-1; sys != VPOS; sys--)
 250     {
 251       for (vsize brk = end_brk; brk != VPOS; brk--)
 252         {
 253           if (!isinf (st.at (brk, sys).details_.force_))
 254             {
 255               if (brk != end_brk)
 256                 {
 257                   /*
 258                     During initialize(), we only fill out a
 259                     Line_details for lines that are valid (ie. not too
 260                     long), otherwise line breaking becomes O(n^3).
 261                     In case sys_count is such that no valid solution
 262                     is found, we need to fill in the Line_details.
 263                   */
 264                   Line_details details;
 265                   brk = st.at (brk, sys).prev_;
 266                   sys--;
 267                   fill_line_details (&details, brk, end_brk);
 268                   ret.push_back (details);
 269                 }
 270
 271               /* build up the good part of the solution */
 272               for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--)
 273                 {
 274                   vsize prev_brk = st.at (brk, cur_sys).prev_;
 275                   assert (brk != VPOS);
 276                   ret.push_back (st.at (brk, cur_sys).details_);
 277                   brk = prev_brk;
 278                 }
 279               reverse (ret);
 280               return ret;
 281             }
 282         }
 283     }
 284
 285   /* if we get to here, just put everything on one line */
 286   Line_details details;
 287   fill_line_details (&details, 0, end_brk);
 288   ret.push_back (details);
 289   return ret;
 290 }
 291
 292 int
 293 Constrained_breaking::min_system_count (vsize start, vsize end)
 294 {
 295   vsize sys_count;
 296   vsize brk = prepare_solution (start, end, 1);
 297   vsize rank = breaks_.size () - starting_breakpoints_[start];
 298   Matrix<Constrained_break_node> const &st = state_[start];
 299
 300   /* sys_count < rank : rank is the # of breakpoints, we can't have more systems */
 301   for (sys_count = 0; sys_count < rank; sys_count++)
 302     {
 303       if (sys_count >= valid_systems_)
 304         {
 305           resize (sys_count + 3);
 306         }
 307       if (!isinf (st.at (brk, sys_count).details_.force_))
 308         return sys_count + 1;
 309     }
 310   /* no possible breaks satisfy constraints */
 311   return 1;
 312 }
 313
 314 int
 315 Constrained_breaking::max_system_count (vsize start, vsize end)
 316 {
 317   vsize brk = (end >= start_.size ()) ? breaks_.size () - 1 : starting_breakpoints_[end];
 318   return brk - starting_breakpoints_[start];
 319 }
 320
 321 vsize
 322 Constrained_breaking::prepare_solution (vsize start, vsize end, vsize sys_count)
 323 {
 324   assert (start < start_.size () && (end == VPOS || end <= start_.size ()));
 325   assert (start < end);
 326
 327   resize (sys_count);
 328   if (end == start_.size ())
 329     end = VPOS;
 330
 331   vsize brk;
 332   brk = end == VPOS ? breaks_.size () - 1 : starting_breakpoints_[end];
 333   brk -= starting_breakpoints_[start];
 334   return brk;
 335 }
 336
 337 Constrained_breaking::Constrained_breaking (Paper_score *ps)
 338 {
 339   valid_systems_ = systems_ = 0;
 340   start_.push_back (0);
 341   pscore_ = ps;
 342   initialize ();
 343 }
 344
 345 Constrained_breaking::Constrained_breaking (Paper_score *ps, vector<vsize> const &start)
 346   : start_ (start)
 347 {
 348   valid_systems_ = systems_ = 0;
 349   pscore_ = ps;
 350   initialize ();
 351 }
 352
 353 static SCM
 354 min_permission (SCM perm1, SCM perm2)
 355 {
 356   if (perm1 == ly_symbol2scm ("force"))
 357     return perm2;
 358   if (perm1 == ly_symbol2scm ("allow")
 359      && perm2 != ly_symbol2scm ("force"))
 360     return perm2;
 361   return SCM_EOL;
 362 }
 363
 364 /* find the forces for all possible lines and cache ragged_ and ragged_right_ */
 365 void
 366 Constrained_breaking::initialize ()
 367 {
 368   if (!pscore_)
 369     return;
 370
 371   ragged_right_ = to_boolean (pscore_->layout ()->c_variable ("ragged-right"));
 372   ragged_last_ = to_boolean (pscore_->layout ()->c_variable ("ragged-last"));
 373   /* NOTE: currently, we aren't using the space_ field of a
 374      Line_details for anything.  That's because the approximations
 375      used for scoring a page configuration don't actually space things
 376      properly (for speed reasong) using springs anchored at the staff
 377      refpoints.  Rather, the "space" is placed between the extent
 378      boxes.  To get a good result, therefore, the "space" value for
 379      page breaking needs to be much smaller than the "space" value for
 380      page layout.  Currently, we just make it zero always.
 381   */
 382   between_system_space_ = 0;
 383   between_system_padding_ = 0;
 384
 385   Output_def *l = pscore_->layout ();
 386
 387   SCM spacing_spec = l->c_variable ("between-system-spacing");
 388   SCM page_breaking_spacing_spec = l->c_variable ("page-breaking-between-system-spacing");
 389   Page_layout_problem::read_spacing_spec (spacing_spec,
 390                                           &between_system_padding_,
 391                                           ly_symbol2scm ("padding"));
 392   Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec,
 393                                           &between_system_padding_,
 394                                           ly_symbol2scm ("padding"));
 395
 396   Interval first_line = line_dimensions_int (pscore_->layout (), 0);
 397   Interval other_lines = line_dimensions_int (pscore_->layout (), 1);
 398   /* do all the rod/spring problems */
 399   breaks_ = pscore_->find_break_indices ();
 400   all_ = pscore_->root_system ()->used_columns ();
 401   lines_.resize (breaks_.size (), breaks_.size (), Line_details ());
 402   vector<Real> forces = get_line_forces (all_,
 403                                          other_lines.length (),
 404                                          other_lines.length () - first_line.length (),
 405                                          ragged_right_);
 406   for (vsize i = 0; i + 1 < breaks_.size (); i++)
 407     {
 408       for (vsize j = i + 1; j < breaks_.size (); j++)
 409         {
 410           bool last = j == breaks_.size () - 1;
 411           bool ragged = ragged_right_ || (last && ragged_last_);
 412           Line_details &line = lines_.at (j, i);
 413
 414           line.force_ = forces[i*breaks_.size () + j];
 415           if (ragged && last && !isinf (line.force_))
 416             line.force_ = (line.force_ < 0 && j > i + 1) ? infinity_f : 0;
 417           if (isinf (line.force_))
 418             break;
 419
 420           fill_line_details (&line, i, j);
 421         }
 422     }
 423
 424   /* work out all the starting indices */
 425   for (vsize i = 0; i < start_.size (); i++)
 426     {
 427       vsize j;
 428       for (j = 0; j + 1 < breaks_.size () && breaks_[j] < start_[i]; j++)
 429         ;
 430       starting_breakpoints_.push_back (j);
 431       start_[i] = breaks_[j];
 432     }
 433   state_.resize (start_.size ());
 434 }
 435
 436 /*
 437   Fills out all of the information contained in a Line_details,
 438   except for information about horizontal spacing.
 439 */
 440 void
 441 Constrained_breaking::fill_line_details (Line_details *const out, vsize start, vsize end)
 442 {
 443   int start_rank = Paper_column::get_rank (all_[breaks_[start]]);
 444   int end_rank = Paper_column::get_rank (all_[breaks_[end]]);
 445   System *sys = pscore_->root_system ();
 446   Interval extent = sys->pure_height (sys, start_rank, end_rank);
 447
 448   Grob *c = all_[breaks_[end]];
 449   out->last_column_ = c;
 450   out->break_penalty_ = robust_scm2double (c->get_property ("line-break-penalty"), 0);
 451   out->page_penalty_ = robust_scm2double (c->get_property ("page-break-penalty"), 0);
 452   out->turn_penalty_ = robust_scm2double (c->get_property ("page-turn-penalty"), 0);
 453   out->break_permission_ = c->get_property ("line-break-permission");
 454   out->page_permission_ = c->get_property ("page-break-permission");
 455   out->turn_permission_ = c->get_property ("page-turn-permission");
 456
 457   /* turn permission should always be stricter than page permission
 458      and page permission should always be stricter than line permission */
 459   out->page_permission_ = min_permission (out->break_permission_,
 460                                           out->page_permission_);
 461   out->turn_permission_ = min_permission (out->page_permission_,
 462                                           out->turn_permission_);
 463
 464   // TODO: see the hack regarding begin_of_line and
 465   // rest_of_line extents in align-interface.  Perhaps we
 466   // should do the same thing here so that the effect extends
 467   // between systems as well as within systems.  It isn't as
 468   // crucial here, however, because the effect is largest when
 469   // dealing with large systems.
 470   out->extent_ = (extent.is_empty ()
 471                   || isnan (extent[LEFT])
 472                   || isnan (extent[RIGHT]))
 473     ? Interval (0, 0) : extent;
 474   out->padding_ = between_system_padding_;
 475   out->space_ = between_system_space_;
 476   out->inverse_hooke_ = extent.length () + between_system_space_;
 477 }
 478
 479 Real
 480 Constrained_breaking::combine_demerits (Real force, Real prev_force)
 481 {
 482   if (ragged_right_)
 483     return force * force;
 484
 485   return force * force + (prev_force - force) * (prev_force - force);
 486 }
 487