lily/simple-spacer.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1999--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   6   TODO:
   7   - add support for different stretch/shrink constants?
   8
   9   LilyPond is free software: you can redistribute it and/or modify
  10   it under the terms of the GNU General Public License as published by
  11   the Free Software Foundation, either version 3 of the License, or
  12   (at your option) any later version.
  13
  14   LilyPond is distributed in the hope that it will be useful,
  15   but WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17   GNU General Public License for more details.
  18
  19   You should have received a copy of the GNU General Public License
  20   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  21 */
  22
  23 #include <cstdio>
  24
  25 #include "column-x-positions.hh"
  26 #include "dimensions.hh"
  27 #include "international.hh"
  28 #include "libc-extension.hh"    // isinf
  29 #include "paper-column.hh"
  30 #include "simple-spacer.hh"
  31 #include "spaceable-grob.hh"
  32 #include "spring.hh"
  33 #include "warn.hh"
  34
  35 /*
  36   A simple spacing constraint solver. The approach:
  37
  38   Stretch the line uniformly until none of the constraints (rods)
  39   block.  It then is very wide.
  40
  41   Compress until the next constraint blocks,
  42
  43   Mark the springs over the constrained part to be non-active.
  44
  45   Repeat with the smaller set of non-active constraints, until all
  46   constraints blocked, or until the line is as short as desired.
  47
  48   This is much simpler, and much much faster than full scale
  49   Constrained QP. On the other hand, a situation like this will not
  50   be typeset as dense as possible, because
  51
  52   c4                   c4           c4                  c4
  53   veryveryverylongsyllable2         veryveryverylongsyllable2
  54   " "4                 veryveryverylongsyllable2        syllable4
  55
  56
  57   can be further compressed to
  58
  59
  60   c4    c4                        c4   c4
  61   veryveryverylongsyllable2       veryveryverylongsyllable2
  62   " "4  veryveryverylongsyllable2      syllable4
  63
  64
  65   Perhaps this is not a bad thing, because the 1st looks better anyway.  */
  66
  67 /*
  68   positive force = expanding, negative force = compressing.
  69 */
  70
  71 Simple_spacer::Simple_spacer ()
  72 {
  73   line_len_ = 0.0;
  74   force_ = 0.0;
  75   fits_ = true;
  76   ragged_ = true;
  77 }
  78
  79 Real
  80 Simple_spacer::force () const
  81 {
  82   return force_;
  83 }
  84
  85 bool
  86 Simple_spacer::fits () const
  87 {
  88   return fits_;
  89 }
  90
  91 Real
  92 Simple_spacer::rod_force (int l, int r, Real dist)
  93 {
  94   Real d = range_ideal_len (l, r);
  95   Real c = range_stiffness (l, r, dist > d);
  96   Real block_stretch = dist - d;
  97
  98   if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */
  99     return 0;
 100   return c * block_stretch;
 101 }
 102
 103 void
 104 Simple_spacer::add_rod (int l, int r, Real dist)
 105 {
 106   if (isinf (dist) || isnan (dist))
 107     {
 108       programming_error ("ignoring weird minimum distance");
 109       return;
 110     }
 111
 112   Real block_force = rod_force (l, r, dist);
 113
 114   if (isinf (block_force))
 115     {
 116       Real spring_dist = range_ideal_len (l, r);
 117       if (spring_dist < dist)
 118         for (int i = l; i < r; i++)
 119           {
 120             if (spring_dist)
 121               springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
 122             else
 123               springs_[i].set_distance (dist / (r - l));
 124           }
 125
 126       return;
 127     }
 128   force_ = max (force_, block_force);
 129   for (int i = l; i < r; i++)
 130     springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ()));
 131 }
 132
 133 Real
 134 Simple_spacer::range_ideal_len (int l, int r) const
 135 {
 136   Real d = 0.;
 137   for (int i = l; i < r; i++)
 138     d += springs_[i].distance ();
 139   return d;
 140 }
 141
 142 Real
 143 Simple_spacer::range_stiffness (int l, int r, bool stretch) const
 144 {
 145   Real den = 0.0;
 146   for (int i = l; i < r; i++)
 147     den += stretch ? springs_[i].inverse_stretch_strength ()
 148            : springs_[i].inverse_compress_strength ();
 149
 150   return 1 / den;
 151 }
 152
 153 Real
 154 Simple_spacer::configuration_length (Real force) const
 155 {
 156   Real l = 0.;
 157   for (vsize i = 0; i < springs_.size (); i++)
 158     l += springs_[i].length (force);
 159
 160   return l;
 161 }
 162
 163 void
 164 Simple_spacer::set_force (Real force)
 165 {
 166   force_ = force;
 167 }
 168
 169 void
 170 Simple_spacer::solve (Real line_len, bool ragged)
 171 {
 172   Real conf = configuration_length (force_);
 173
 174   ragged_ = ragged;
 175   line_len_ = line_len;
 176   if (conf < line_len_)
 177     force_ = expand_line ();
 178   else if (conf > line_len_)
 179     force_ = compress_line ();
 180
 181   if (ragged && force_ < 0)
 182     fits_ = false;
 183 }
 184
 185 Real
 186 Simple_spacer::expand_line ()
 187 {
 188   double inv_hooke = 0;
 189   double cur_len = configuration_length (force_);
 190
 191   fits_ = true;
 192   for (vsize i = 0; i < springs_.size (); i++)
 193     inv_hooke += springs_[i].inverse_stretch_strength ();
 194
 195   if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
 196     inv_hooke = 1e-6;   /* then report a very large stretching force */
 197
 198   if (cur_len > (1 + 1e-6) * line_len_)
 199     programming_error ("misuse of expand_line");
 200   return (line_len_ - cur_len) / inv_hooke + force_;
 201 }
 202
 203 Real
 204 Simple_spacer::compress_line ()
 205 {
 206   double cur_len = configuration_length (force_);
 207   double cur_force = force_;
 208   bool compressed = false;
 209
 210   /* just because we are in compress_line () doesn't mean that the line
 211      will actually be compressed (as in, a negative force) because
 212      we start out with a stretched line. Here, we check whether we
 213      will be compressed or stretched (so we know which spring constant to use) */
 214   if (configuration_length (0.0) > line_len_)
 215     {
 216       cur_force = 0.0;
 217       cur_len = configuration_length (0.0);
 218       compressed = true;
 219     }
 220
 221   fits_ = true;
 222
 223   if (line_len_ > (1 + 1e-6) * cur_len)
 224     programming_error ("misuse of compress_line");
 225   vector<Spring> sorted_springs = springs_;
 226   sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
 227
 228   /* inv_hooke is the total flexibility of currently-active springs */
 229   double inv_hooke = 0;
 230   vsize i = sorted_springs.size ();
 231   for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
 232     inv_hooke += compressed
 233                  ? sorted_springs[i - 1].inverse_compress_strength ()
 234                  : sorted_springs[i - 1].inverse_stretch_strength ();
 235   /* i now indexes the first active spring, so */
 236   for (; i < sorted_springs.size (); i++)
 237     {
 238       Spring sp = sorted_springs[i];
 239
 240       if (isinf (sp.blocking_force ()))
 241         break;
 242
 243       double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
 244       if (cur_len - block_dist < line_len_)
 245         {
 246           cur_force += (line_len_ - cur_len) / inv_hooke;
 247           cur_len = line_len_;
 248
 249           /*
 250             Paranoia check.
 251           */
 252           if (fabs (configuration_length (cur_force) - cur_len) > 1e-6 * cur_len)
 253             programming_error (to_string ("mis-predicted force, %.6f ~= %.6f",
 254                                           cur_len, configuration_length(cur_force)));
 255           return cur_force;
 256         }
 257
 258       cur_len -= block_dist;
 259       inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
 260       cur_force = sp.blocking_force ();
 261     }
 262
 263   fits_ = false;
 264   return cur_force;
 265 }
 266
 267 void
 268 Simple_spacer::add_spring (Spring const &sp)
 269 {
 270   force_ = max (force_, sp.blocking_force ());
 271   springs_.push_back (sp);
 272 }
 273
 274 vector<Real>
 275 Simple_spacer::spring_positions () const
 276 {
 277   vector<Real> ret;
 278   ret.push_back (0.);
 279
 280   for (vsize i = 0; i < springs_.size (); i++)
 281     ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
 282   return ret;
 283 }
 284
 285 Real
 286 Simple_spacer::force_penalty (bool ragged) const
 287 {
 288   /* If we are ragged-right, we don't want to penalise according to the force,
 289      but according to the amount of whitespace that is present after the end
 290      of the line. */
 291   if (ragged)
 292     return max (0.0, line_len_ - configuration_length (0.0));
 293
 294   /* Use a convex compression penalty. */
 295   Real f = force_;
 296   return f - (f < 0 ? f * f * f * f * 2 : 0);
 297 }
 298
 299 /****************************************************************/
 300
 301 struct Rod_description
 302 {
 303   vsize r_;
 304   Real dist_;
 305
 306   bool operator < (const Rod_description r)
 307   {
 308     return r_ < r.r_;
 309   }
 310
 311   Rod_description ()
 312   {
 313     r_ = 0;
 314     dist_ = 0;
 315   }
 316
 317   Rod_description (vsize r, Real d)
 318   {
 319     r_ = r;
 320     dist_ = d;
 321   }
 322 };
 323
 324 struct Column_description
 325 {
 326   vector<Rod_description> rods_;
 327   vector<Rod_description> end_rods_;   /* use these if they end at the last column of the line */
 328   Spring spring_;
 329   Spring end_spring_;
 330
 331   SCM break_permission_;
 332   Interval keep_inside_line_;
 333
 334   Column_description ()
 335   {
 336     break_permission_ = SCM_EOL;
 337   }
 338 };
 339
 340 static bool
 341 is_loose (Grob *g)
 342 {
 343   return (scm_is_pair (g->get_object ("between-cols")));
 344 }
 345
 346 static Grob *
 347 maybe_find_prebroken_piece (Grob *g, Direction d)
 348 {
 349   Grob *ret = dynamic_cast<Item *> (g)->find_prebroken_piece (d);
 350   if (ret)
 351     return ret;
 352   return g;
 353 }
 354
 355 static Grob *
 356 next_spaceable_column (vector<Grob *> const &list, vsize starting)
 357 {
 358   for (vsize i = starting + 1; i < list.size (); i++)
 359     if (!is_loose (list[i]))
 360       return list[i];
 361   return 0;
 362 }
 363
 364 static Column_description
 365 get_column_description (vector<Grob *> const &cols, vsize col_index, bool line_starter)
 366 {
 367   Grob *col = cols[col_index];
 368   if (line_starter)
 369     col = maybe_find_prebroken_piece (col, RIGHT);
 370
 371   Column_description description;
 372   Grob *next_col = next_spaceable_column (cols, col_index);
 373   if (next_col)
 374     description.spring_ = Spaceable_grob::get_spring (col, next_col);
 375
 376   if (col_index + 1 < cols.size ())
 377     {
 378       Grob *end_col = dynamic_cast<Item *> (cols[col_index + 1])->find_prebroken_piece (LEFT);
 379       if (end_col)
 380         description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
 381     }
 382
 383   for (SCM s = Spaceable_grob::get_minimum_distances (col);
 384        scm_is_pair (s); s = scm_cdr (s))
 385     {
 386       Grob *other = unsmob<Grob> (scm_caar (s));
 387       vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
 388       if (j != VPOS)
 389         {
 390           if (cols[j] == other)
 391             description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
 392           else /* it must end at the LEFT prebroken_piece */
 393                /* see Spanner::set_spacing_rods for more comments on how
 394                   to deal with situations where  we don't know if we're
 395                   ending yet on the left prebroken piece */
 396             description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
 397         }
 398     }
 399
 400   if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
 401     description.keep_inside_line_ = col->extent (col, X_AXIS);
 402
 403   description.break_permission_ = col->get_property ("line-break-permission");
 404   return description;
 405 }
 406
 407 vector<Real>
 408 get_line_forces (vector<Grob *> const &columns,
 409                  Real line_len, Real indent, bool ragged)
 410 {
 411   vector<vsize> breaks;
 412   vector<Real> force;
 413   vector<Grob *> non_loose;
 414   vector<Column_description> cols;
 415   SCM force_break = ly_symbol2scm ("force");
 416
 417   for (vsize i = 0; i < columns.size (); i++)
 418     if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
 419       non_loose.push_back (columns[i]);
 420
 421   breaks.clear ();
 422   breaks.push_back (0);
 423   cols.push_back (Column_description ());
 424   for (vsize i = 1; i + 1 < non_loose.size (); i++)
 425     {
 426       if (Paper_column::is_breakable (non_loose[i]))
 427         breaks.push_back (cols.size ());
 428
 429       cols.push_back (get_column_description (non_loose, i, false));
 430     }
 431   breaks.push_back (cols.size ());
 432   force.resize (breaks.size () * breaks.size (), infinity_f);
 433
 434   for (vsize b = 0; b + 1 < breaks.size (); b++)
 435     {
 436       cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
 437       vsize st = breaks[b];
 438
 439       for (vsize c = b + 1; c < breaks.size (); c++)
 440         {
 441           vsize end = breaks[c];
 442           Simple_spacer spacer;
 443
 444           for (vsize i = breaks[b]; i < end - 1; i++)
 445             spacer.add_spring (cols[i].spring_);
 446           spacer.add_spring (cols[end - 1].end_spring_);
 447
 448           for (vsize i = breaks[b]; i < end; i++)
 449             {
 450               for (vsize r = 0; r < cols[i].rods_.size (); r++)
 451                 if (cols[i].rods_[r].r_ < end)
 452                   spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
 453               for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
 454                 if (cols[i].end_rods_[r].r_ == end)
 455                   spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
 456               if (!cols[i].keep_inside_line_.is_empty ())
 457                 {
 458                   spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
 459                   spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
 460                 }
 461             }
 462           spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
 463           force[b * breaks.size () + c] = spacer.force_penalty (ragged);
 464
 465           if (!spacer.fits ())
 466             {
 467               if (c == b + 1)
 468                 force[b * breaks.size () + c] = -200000;
 469               else
 470                 force[b * breaks.size () + c] = infinity_f;
 471               break;
 472             }
 473           if (end < cols.size () && scm_is_eq (cols[end].break_permission_, force_break))
 474             break;
 475         }
 476     }
 477   return force;
 478 }
 479
 480 Column_x_positions
 481 get_line_configuration (vector<Grob *> const &columns,
 482                         Real line_len,
 483                         Real indent,
 484                         bool ragged)
 485 {
 486   vector<Column_description> cols;
 487   Simple_spacer spacer;
 488   Column_x_positions ret;
 489
 490   ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
 491   for (vsize i = 1; i + 1 < columns.size (); i++)
 492     {
 493       if (is_loose (columns[i]))
 494         ret.loose_cols_.push_back (columns[i]);
 495       else
 496         ret.cols_.push_back (columns[i]);
 497     }
 498   ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
 499
 500   /* since we've already put our line-ending column in the column list, we can ignore
 501      the end_XXX_ fields of our column_description */
 502   for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
 503     {
 504       cols.push_back (get_column_description (ret.cols_, i, i == 0));
 505       spacer.add_spring (cols[i].spring_);
 506     }
 507   for (vsize i = 0; i < cols.size (); i++)
 508     {
 509       for (vsize r = 0; r < cols[i].rods_.size (); r++)
 510         spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
 511
 512       if (!cols[i].keep_inside_line_.is_empty ())
 513         {
 514           spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
 515           spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
 516         }
 517     }
 518
 519   spacer.solve (line_len, ragged);
 520   ret.force_ = spacer.force_penalty (ragged);
 521
 522   ret.config_ = spacer.spring_positions ();
 523   for (vsize i = 0; i < ret.config_.size (); i++)
 524     ret.config_[i] += indent;
 525
 526   ret.satisfies_constraints_ = spacer.fits ();
 527
 528   /*
 529     Check if breaking constraints are met.
 530   */
 531   for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
 532     {
 533       SCM p = ret.cols_[i]->get_property ("line-break-permission");
 534       if (scm_is_eq (p, ly_symbol2scm ("force")))
 535         ret.satisfies_constraints_ = false;
 536     }
 537
 538   return ret;
 539 }