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--2009 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, dist > d);
  85   Real block_stretch = dist - d;
  86
  87   if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */
  88     return 0;
  89   return c * block_stretch;
  90 }
  91
  92 void
  93 Simple_spacer::add_rod (int l, int r, Real dist)
  94 {
  95   if (isinf (dist) || isnan (dist))
  96     {
  97       programming_error ("ignoring weird minimum distance");
  98       return;
  99     }
 100
 101   Real block_force = rod_force (l, r, dist);
 102
 103   if (isinf (block_force))
 104     {
 105       Real spring_dist = range_ideal_len (l, r);
 106       if (spring_dist < dist)
 107         for (int i = l; i < r; i++)
 108           {
 109             if (spring_dist)
 110               springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
 111             else
 112               springs_[i].set_distance (dist / (r - l));
 113           }
 114
 115       return;
 116     }
 117   force_ = max (force_, block_force);
 118   for (int i = l; i < r; i++)
 119     springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ()));
 120 }
 121
 122 Real
 123 Simple_spacer::range_ideal_len (int l, int r) const
 124 {
 125   Real d = 0.;
 126   for (int i = l; i < r; i++)
 127     d += springs_[i].distance ();
 128   return d;
 129 }
 130
 131 Real
 132 Simple_spacer::range_stiffness (int l, int r, bool stretch) const
 133 {
 134   Real den = 0.0;
 135   for (int i = l; i < r; i++)
 136     den += stretch ? springs_[i].inverse_stretch_strength ()
 137       : springs_[i].inverse_compress_strength ();
 138
 139   return 1 / den;
 140 }
 141
 142 Real
 143 Simple_spacer::configuration_length (Real force) const
 144 {
 145   Real l = 0.;
 146   for (vsize i = 0; i < springs_.size (); i++)
 147     l += springs_[i].length (force);
 148
 149   return l;
 150 }
 151
 152 void
 153 Simple_spacer::solve (Real line_len, bool ragged)
 154 {
 155   Real conf = configuration_length (force_);
 156
 157   ragged_ = ragged;
 158   line_len_ = line_len;
 159   if (conf < line_len_)
 160     force_ = expand_line ();
 161   else if (conf > line_len_)
 162     force_ = compress_line ();
 163
 164   if (ragged && force_ < 0)
 165     fits_ = false;
 166 }
 167
 168 Real
 169 Simple_spacer::expand_line ()
 170 {
 171   double inv_hooke = 0;
 172   double cur_len = configuration_length (force_);
 173
 174   fits_ = true;
 175   for (vsize i=0; i < springs_.size (); i++)
 176     inv_hooke += springs_[i].inverse_stretch_strength ();
 177
 178   if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
 179     return 0.0;         /* anyway, then it makes no difference what the force is */
 180
 181   assert (cur_len <= line_len_);
 182   return (line_len_ - cur_len) / inv_hooke + force_;
 183 }
 184
 185 Real
 186 Simple_spacer::compress_line ()
 187 {
 188   double inv_hooke = 0;
 189   double cur_len = configuration_length (force_);
 190   double cur_force = force_;
 191   bool compressed = false;
 192
 193   /* just because we are in compress_line () doesn't mean that the line
 194      will actually be compressed (as in, a negative force) because
 195      we start out with a stretched line. Here, we check whether we
 196      will be compressed or stretched (so we know which spring constant to use) */
 197   if (configuration_length (0.0) > line_len_)
 198     {
 199       cur_force = 0.0;
 200       cur_len = configuration_length (0.0);
 201       compressed = true;
 202     }
 203
 204   fits_ = true;
 205   for (vsize i=0; i < springs_.size (); i++)
 206     inv_hooke += compressed
 207       ? springs_[i].inverse_compress_strength ()
 208       : springs_[i].inverse_stretch_strength ();
 209
 210   assert (line_len_ <= cur_len);
 211
 212   vector<Spring> sorted_springs = springs_;
 213   sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
 214
 215   for (vsize i = 0; i < sorted_springs.size (); i++)
 216     {
 217       Spring sp = sorted_springs[i];
 218
 219       if (sp.blocking_force () > cur_force)
 220         continue;
 221
 222       if (isinf (sp.blocking_force ()))
 223         break;
 224
 225       double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
 226       if (cur_len - block_dist < line_len_)
 227         {
 228           cur_force += (line_len_ - cur_len) / inv_hooke;
 229           cur_len = line_len_;
 230
 231           /*
 232             Paranoia check.
 233           */
 234           assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
 235           return cur_force;
 236         }
 237
 238       cur_len -= block_dist;
 239       inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
 240       cur_force = sp.blocking_force ();
 241     }
 242
 243   fits_ = false;
 244   return cur_force;
 245 }
 246
 247 void
 248 Simple_spacer::add_spring (Spring const &sp)
 249 {
 250   force_ = max (force_, sp.blocking_force ());
 251   springs_.push_back (sp);
 252 }
 253
 254 vector<Real>
 255 Simple_spacer::spring_positions () const
 256 {
 257   vector<Real> ret;
 258   ret.push_back (0.);
 259
 260   for (vsize i = 0; i < springs_.size (); i++)
 261     ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
 262   return ret;
 263 }
 264
 265 Real
 266 Simple_spacer::force_penalty (bool ragged) const
 267 {
 268   /* If we are ragged-right, we don't want to penalise according to the force,
 269      but according to the amount of whitespace that is present after the end
 270      of the line. */
 271   if (ragged)
 272     return max (0.0, line_len_ - configuration_length (0.0));
 273
 274   /* Use a convex compression penalty. */
 275   Real f = force_;
 276   return f - (f < 0 ? f*f*f*f*2 : 0);
 277 }
 278
 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