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