lily/simple-spacer.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1999--2012 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     return 0.0;         /* anyway, then it makes no difference what the force is */
 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             description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
 391         }
 392     }
 393
 394   if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
 395     description.keep_inside_line_ = col->extent (col, X_AXIS);
 396
 397   description.break_permission_ = col->get_property ("line-break-permission");
 398   return description;
 399 }
 400
 401 vector<Real>
 402 get_line_forces (vector<Grob *> const &columns,
 403                  Real line_len, Real indent, bool ragged)
 404 {
 405   vector<vsize> breaks;
 406   vector<Real> force;
 407   vector<Grob *> non_loose;
 408   vector<Column_description> cols;
 409   SCM force_break = ly_symbol2scm ("force");
 410
 411   for (vsize i = 0; i < columns.size (); i++)
 412     if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
 413       non_loose.push_back (columns[i]);
 414
 415   breaks.clear ();
 416   breaks.push_back (0);
 417   cols.push_back (Column_description ());
 418   for (vsize i = 1; i + 1 < non_loose.size (); i++)
 419     {
 420       if (Paper_column::is_breakable (non_loose[i]))
 421         breaks.push_back (cols.size ());
 422
 423       cols.push_back (get_column_description (non_loose, i, false));
 424     }
 425   breaks.push_back (cols.size ());
 426   force.resize (breaks.size () * breaks.size (), infinity_f);
 427
 428   for (vsize b = 0; b + 1 < breaks.size (); b++)
 429     {
 430       cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
 431       vsize st = breaks[b];
 432
 433       for (vsize c = b + 1; c < breaks.size (); c++)
 434         {
 435           vsize end = breaks[c];
 436           Simple_spacer spacer;
 437
 438           for (vsize i = breaks[b]; i < end - 1; i++)
 439             spacer.add_spring (cols[i].spring_);
 440           spacer.add_spring (cols[end - 1].end_spring_);
 441
 442           for (vsize i = breaks[b]; i < end; i++)
 443             {
 444               for (vsize r = 0; r < cols[i].rods_.size (); r++)
 445                 if (cols[i].rods_[r].r_ < end)
 446                   spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
 447               for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
 448                 if (cols[i].end_rods_[r].r_ == end)
 449                   spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
 450               if (!cols[i].keep_inside_line_.is_empty ())
 451                 {
 452                   spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
 453                   spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
 454                 }
 455             }
 456           spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
 457           force[b * breaks.size () + c] = spacer.force_penalty (ragged);
 458
 459           if (!spacer.fits ())
 460             {
 461               if (c == b + 1)
 462                 force[b * breaks.size () + c] = -200000;
 463               else
 464                 force[b * breaks.size () + c] = infinity_f;
 465               break;
 466             }
 467           if (end < cols.size () && cols[end].break_permission_ == force_break)
 468             break;
 469         }
 470     }
 471   return force;
 472 }
 473
 474 Column_x_positions
 475 get_line_configuration (vector<Grob *> const &columns,
 476                         Real line_len,
 477                         Real indent,
 478                         bool ragged)
 479 {
 480   vector<Column_description> cols;
 481   Simple_spacer spacer;
 482   Column_x_positions ret;
 483
 484   ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
 485   for (vsize i = 1; i + 1 < columns.size (); i++)
 486     {
 487       if (is_loose (columns[i]))
 488         ret.loose_cols_.push_back (columns[i]);
 489       else
 490         ret.cols_.push_back (columns[i]);
 491     }
 492   ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
 493
 494   /* since we've already put our line-ending column in the column list, we can ignore
 495      the end_XXX_ fields of our column_description */
 496   for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
 497     {
 498       cols.push_back (get_column_description (ret.cols_, i, i == 0));
 499       spacer.add_spring (cols[i].spring_);
 500     }
 501   for (vsize i = 0; i < cols.size (); i++)
 502     {
 503       for (vsize r = 0; r < cols[i].rods_.size (); r++)
 504         spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
 505
 506       if (!cols[i].keep_inside_line_.is_empty ())
 507         {
 508           spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
 509           spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
 510         }
 511     }
 512
 513   spacer.solve (line_len, ragged);
 514   ret.force_ = spacer.force_penalty (ragged);
 515
 516   ret.config_ = spacer.spring_positions ();
 517   for (vsize i = 0; i < ret.config_.size (); i++)
 518     ret.config_[i] += indent;
 519
 520   ret.satisfies_constraints_ = spacer.fits ();
 521
 522   /*
 523     Check if breaking constraints are met.
 524   */
 525   for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
 526     {
 527       SCM p = ret.cols_[i]->get_property ("line-break-permission");
 528       if (p == ly_symbol2scm ("force"))
 529         ret.satisfies_constraints_ = false;
 530     }
 531
 532   return ret;
 533 }
 534
 535 #include "ly-smobs.icc"
 536
 537 IMPLEMENT_SIMPLE_SMOBS (Simple_spacer);
 538 IMPLEMENT_DEFAULT_EQUAL_P (Simple_spacer);
 539
 540 SCM
 541 Simple_spacer::mark_smob (SCM /* x */)
 542 {
 543   return SCM_EOL;
 544 }
 545
 546 int
 547 Simple_spacer::print_smob (SCM /* x */, SCM p, scm_print_state *)
 548 {
 549   scm_puts ("#<Simple spacer>", p);
 550   return 1;
 551 }
 552