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