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