lily/simple-spacer.cc

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