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 ADD_SMOB_INIT (Simple_spacer);
  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   assert (cur_len <= line_len_);
 201   return (line_len_ - cur_len) / inv_hooke + force_;
 202 }
 203
 204 Real
 205 Simple_spacer::compress_line ()
 206 {
 207   double cur_len = configuration_length (force_);
 208   double cur_force = force_;
 209   bool compressed = false;
 210
 211   /* just because we are in compress_line () doesn't mean that the line
 212      will actually be compressed (as in, a negative force) because
 213      we start out with a stretched line. Here, we check whether we
 214      will be compressed or stretched (so we know which spring constant to use) */
 215   if (configuration_length (0.0) > line_len_)
 216     {
 217       cur_force = 0.0;
 218       cur_len = configuration_length (0.0);
 219       compressed = true;
 220     }
 221
 222   fits_ = true;
 223
 224   assert (line_len_ <= cur_len);
 225
 226   vector<Spring> sorted_springs = springs_;
 227   sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
 228
 229   /* inv_hooke is the total flexibility of currently-active springs */
 230   double inv_hooke = 0;
 231   vsize i = sorted_springs.size ();
 232   for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
 233     inv_hooke += compressed
 234                  ? sorted_springs[i - 1].inverse_compress_strength ()
 235                  : sorted_springs[i - 1].inverse_stretch_strength ();
 236   /* i now indexes the first active spring, so */
 237   for (; i < sorted_springs.size (); i++)
 238     {
 239       Spring sp = sorted_springs[i];
 240
 241       if (isinf (sp.blocking_force ()))
 242         break;
 243
 244       double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
 245       if (cur_len - block_dist < line_len_)
 246         {
 247           cur_force += (line_len_ - cur_len) / inv_hooke;
 248           cur_len = line_len_;
 249
 250           /*
 251             Paranoia check.
 252           */
 253           assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
 254           return cur_force;
 255         }
 256
 257       cur_len -= block_dist;
 258       inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
 259       cur_force = sp.blocking_force ();
 260     }
 261
 262   fits_ = false;
 263   return cur_force;
 264 }
 265
 266 void
 267 Simple_spacer::add_spring (Spring const &sp)
 268 {
 269   force_ = max (force_, sp.blocking_force ());
 270   springs_.push_back (sp);
 271 }
 272
 273 vector<Real>
 274 Simple_spacer::spring_positions () const
 275 {
 276   vector<Real> ret;
 277   ret.push_back (0.);
 278
 279   for (vsize i = 0; i < springs_.size (); i++)
 280     ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
 281   return ret;
 282 }
 283
 284 Real
 285 Simple_spacer::force_penalty (bool ragged) const
 286 {
 287   /* If we are ragged-right, we don't want to penalise according to the force,
 288      but according to the amount of whitespace that is present after the end
 289      of the line. */
 290   if (ragged)
 291     return max (0.0, line_len_ - configuration_length (0.0));
 292
 293   /* Use a convex compression penalty. */
 294   Real f = force_;
 295   return f - (f < 0 ? f * f * f * f * 2 : 0);
 296 }
 297
 298 /****************************************************************/
 299
 300 struct Rod_description
 301 {
 302   vsize r_;
 303   Real dist_;
 304
 305   bool operator < (const Rod_description r)
 306   {
 307     return r_ < r.r_;
 308   }
 309
 310   Rod_description ()
 311   {
 312     r_ = 0;
 313     dist_ = 0;
 314   }
 315
 316   Rod_description (vsize r, Real d)
 317   {
 318     r_ = r;
 319     dist_ = d;
 320   }
 321 };
 322
 323 struct Column_description
 324 {
 325   vector<Rod_description> rods_;
 326   vector<Rod_description> end_rods_;   /* use these if they end at the last column of the line */
 327   Spring spring_;
 328   Spring end_spring_;
 329
 330   SCM break_permission_;
 331   Interval keep_inside_line_;
 332
 333   Column_description ()
 334   {
 335     break_permission_ = SCM_EOL;
 336   }
 337 };
 338
 339 static bool
 340 is_loose (Grob *g)
 341 {
 342   return (scm_is_pair (g->get_object ("between-cols")));
 343 }
 344
 345 static Grob *
 346 maybe_find_prebroken_piece (Grob *g, Direction d)
 347 {
 348   Grob *ret = dynamic_cast<Item *> (g)->find_prebroken_piece (d);
 349   if (ret)
 350     return ret;
 351   return g;
 352 }
 353
 354 static Grob *
 355 next_spaceable_column (vector<Grob *> const &list, vsize starting)
 356 {
 357   for (vsize i = starting + 1; i < list.size (); i++)
 358     if (!is_loose (list[i]))
 359       return list[i];
 360   return 0;
 361 }
 362
 363 static Column_description
 364 get_column_description (vector<Grob *> const &cols, vsize col_index, bool line_starter)
 365 {
 366   Grob *col = cols[col_index];
 367   if (line_starter)
 368     col = maybe_find_prebroken_piece (col, RIGHT);
 369
 370   Column_description description;
 371   Grob *next_col = next_spaceable_column (cols, col_index);
 372   if (next_col)
 373     description.spring_ = Spaceable_grob::get_spring (col, next_col);
 374
 375   if (col_index + 1 < cols.size ())
 376     {
 377       Grob *end_col = dynamic_cast<Item *> (cols[col_index + 1])->find_prebroken_piece (LEFT);
 378       if (end_col)
 379         description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
 380     }
 381
 382   for (SCM s = Spaceable_grob::get_minimum_distances (col);
 383        scm_is_pair (s); s = scm_cdr (s))
 384     {
 385       Grob *other = Grob::unsmob (scm_caar (s));
 386       vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
 387       if (j != VPOS)
 388         {
 389           if (cols[j] == other)
 390             description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
 391           else /* it must end at the LEFT prebroken_piece */
 392                /* see Spanner::set_spacing_rods for more comments on how
 393                   to deal with situations where  we don't know if we're
 394                   ending yet on the left prebroken piece */
 395             description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
 396         }
 397     }
 398
 399   if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
 400     description.keep_inside_line_ = col->extent (col, X_AXIS);
 401
 402   description.break_permission_ = col->get_property ("line-break-permission");
 403   return description;
 404 }
 405
 406 vector<Real>
 407 get_line_forces (vector<Grob *> const &columns,
 408                  Real line_len, Real indent, bool ragged)
 409 {
 410   vector<vsize> breaks;
 411   vector<Real> force;
 412   vector<Grob *> non_loose;
 413   vector<Column_description> cols;
 414   SCM force_break = ly_symbol2scm ("force");
 415
 416   for (vsize i = 0; i < columns.size (); i++)
 417     if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
 418       non_loose.push_back (columns[i]);
 419
 420   breaks.clear ();
 421   breaks.push_back (0);
 422   cols.push_back (Column_description ());
 423   for (vsize i = 1; i + 1 < non_loose.size (); i++)
 424     {
 425       if (Paper_column::is_breakable (non_loose[i]))
 426         breaks.push_back (cols.size ());
 427
 428       cols.push_back (get_column_description (non_loose, i, false));
 429     }
 430   breaks.push_back (cols.size ());
 431   force.resize (breaks.size () * breaks.size (), infinity_f);
 432
 433   for (vsize b = 0; b + 1 < breaks.size (); b++)
 434     {
 435       cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
 436       vsize st = breaks[b];
 437
 438       for (vsize c = b + 1; c < breaks.size (); c++)
 439         {
 440           vsize end = breaks[c];
 441           Simple_spacer spacer;
 442
 443           for (vsize i = breaks[b]; i < end - 1; i++)
 444             spacer.add_spring (cols[i].spring_);
 445           spacer.add_spring (cols[end - 1].end_spring_);
 446
 447           for (vsize i = breaks[b]; i < end; i++)
 448             {
 449               for (vsize r = 0; r < cols[i].rods_.size (); r++)
 450                 if (cols[i].rods_[r].r_ < end)
 451                   spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
 452               for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
 453                 if (cols[i].end_rods_[r].r_ == end)
 454                   spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
 455               if (!cols[i].keep_inside_line_.is_empty ())
 456                 {
 457                   spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
 458                   spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
 459                 }
 460             }
 461           spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
 462           force[b * breaks.size () + c] = spacer.force_penalty (ragged);
 463
 464           if (!spacer.fits ())
 465             {
 466               if (c == b + 1)
 467                 force[b * breaks.size () + c] = -200000;
 468               else
 469                 force[b * breaks.size () + c] = infinity_f;
 470               break;
 471             }
 472           if (end < cols.size () && cols[end].break_permission_ == force_break)
 473             break;
 474         }
 475     }
 476   return force;
 477 }
 478
 479 Column_x_positions
 480 get_line_configuration (vector<Grob *> const &columns,
 481                         Real line_len,
 482                         Real indent,
 483                         bool ragged)
 484 {
 485   vector<Column_description> cols;
 486   Simple_spacer spacer;
 487   Column_x_positions ret;
 488
 489   ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
 490   for (vsize i = 1; i + 1 < columns.size (); i++)
 491     {
 492       if (is_loose (columns[i]))
 493         ret.loose_cols_.push_back (columns[i]);
 494       else
 495         ret.cols_.push_back (columns[i]);
 496     }
 497   ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
 498
 499   /* since we've already put our line-ending column in the column list, we can ignore
 500      the end_XXX_ fields of our column_description */
 501   for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
 502     {
 503       cols.push_back (get_column_description (ret.cols_, i, i == 0));
 504       spacer.add_spring (cols[i].spring_);
 505     }
 506   for (vsize i = 0; i < cols.size (); i++)
 507     {
 508       for (vsize r = 0; r < cols[i].rods_.size (); r++)
 509         spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
 510
 511       if (!cols[i].keep_inside_line_.is_empty ())
 512         {
 513           spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
 514           spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
 515         }
 516     }
 517
 518   spacer.solve (line_len, ragged);
 519   ret.force_ = spacer.force_penalty (ragged);
 520
 521   ret.config_ = spacer.spring_positions ();
 522   for (vsize i = 0; i < ret.config_.size (); i++)
 523     ret.config_[i] += indent;
 524
 525   ret.satisfies_constraints_ = spacer.fits ();
 526
 527   /*
 528     Check if breaking constraints are met.
 529   */
 530   for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
 531     {
 532       SCM p = ret.cols_[i]->get_property ("line-break-permission");
 533       if (scm_is_eq (p, ly_symbol2scm ("force")))
 534         ret.satisfies_constraints_ = false;
 535     }
 536
 537   return ret;
 538 }