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