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