lily/simple-spacer.cc

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