lily/simple-spacer.cc

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