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