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--2006 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 /****************************************************************/
 251
 252 Spring_description::Spring_description ()
 253 {
 254   ideal_ = 0.0;
 255   inverse_hooke_ = 0.0;
 256   block_force_ = 0.0;
 257 }
 258
 259 bool
 260 Spring_description::is_sane () const
 261 {
 262   return (inverse_hooke_ >= 0)
 263     && ideal_ > 0
 264     && !isinf (ideal_) && !isnan (ideal_)
 265     && (inverse_hooke_ == 0.0 || fabs (inverse_hooke_) > 1e-8)
 266     ;
 267 }
 268
 269 Real
 270 Spring_description::length (Real f) const
 271 {
 272   return ideal_ + max (f, block_force_) * inverse_hooke_;
 273 }
 274
 275 /****************************************************************/
 276
 277 /*
 278   TODO: should a add penalty for widely varying spring forces (caused
 279   by constraints, eg.
 280
 281
 282   .     =====
 283   .     |   |
 284   .o|o|x ##x
 285   .
 286
 287   The ## forces the notes apart; we shouldn't allow the O's to touch
 288   this closely.
 289 */
 290
 291 struct Rod_description
 292 {
 293   vsize r_;
 294   Real dist_;
 295
 296   bool operator< (const Rod_description r)
 297   {
 298     return r_ < r.r_;
 299   }
 300
 301   Rod_description ()
 302   {
 303     r_ = 0;
 304     dist_ = 0;
 305   }
 306
 307   Rod_description (vsize r, Real d)
 308   {
 309     r_ = r;
 310     dist_ = d;
 311   }
 312 };
 313
 314 struct Column_description
 315 {
 316   vector<Rod_description> rods_;
 317   vector<Rod_description> end_rods_;   /* use these if they end at the last column of the line */
 318   Real ideal_;
 319   Real inverse_hooke_;
 320   Real end_ideal_;
 321   Real end_inverse_hooke_;
 322   SCM break_permission_;
 323   Interval keep_inside_line_;
 324
 325   Column_description ()
 326   {
 327     ideal_ = 0;
 328     inverse_hooke_ = 0;
 329     end_ideal_ = 0;
 330     end_inverse_hooke_ = 0;
 331     break_permission_ = SCM_EOL;
 332   }
 333 };
 334
 335 static int compare_paper_column_rank (Grob *const &a, Grob *const &b);
 336
 337 static bool
 338 is_loose (Grob *g)
 339 {
 340   return (scm_is_pair (g->get_object ("between-cols")));
 341 }
 342
 343 static Grob*
 344 maybe_find_prebroken_piece (Grob *g, Direction d)
 345 {
 346   Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
 347   if (ret)
 348     return ret;
 349   return g;
 350 }
 351
 352 static Grob*
 353 next_spaceable_column (vector<Grob*> const &list, vsize starting)
 354 {
 355   for (vsize i = starting+1; i < list.size (); i++)
 356     if (!is_loose (list[i]))
 357       return list[i];
 358   return 0;
 359 }
 360
 361 /* this only returns non-NULL if the line-ending column is the next
 362    spaceable-or-breakable column */
 363 static Grob*
 364 next_line_ending_column (vector<Grob*> const &list, vsize starting)
 365 {
 366   vsize i = starting + 1;
 367   for (; i < list.size ()
 368          && is_loose (list[i])
 369          && !Paper_column::is_breakable (list[i]);
 370        i++)
 371     ;
 372   return dynamic_cast<Item*> (list[i])->find_prebroken_piece (LEFT);
 373 }
 374
 375 static void
 376 get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke)
 377 {
 378   Spring_smob *spring = 0;
 379
 380   for (SCM s = this_col->get_object ("ideal-distances");
 381        !spring && scm_is_pair (s);
 382        s = scm_cdr (s))
 383     {
 384       Spring_smob *sp = unsmob_spring (scm_car (s));
 385
 386       if (sp->other_ == next_col)
 387         spring = sp;
 388     }
 389
 390   if (!spring)
 391     programming_error (_f ("No spring between column %d and next one",
 392                            Paper_column::get_rank (this_col)));
 393
 394   *ideal = (spring) ? spring->distance_ : 5.0;
 395   *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0;
 396 }
 397
 398 static Column_description
 399 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
 400 {
 401   Grob *col = cols[col_index];
 402   if (line_starter)
 403     col = maybe_find_prebroken_piece (col, RIGHT);
 404
 405   Column_description description;
 406   Grob *next_col = next_spaceable_column (cols, col_index);
 407   if (next_col)
 408     get_column_spring (col, next_col, &description.ideal_, &description.inverse_hooke_);
 409   Grob *end_col = next_line_ending_column (cols, col_index);
 410   if (end_col)
 411     get_column_spring (col, end_col, &description.end_ideal_, &description.end_inverse_hooke_);
 412
 413   for (SCM s = Spaceable_grob::get_minimum_distances (col);
 414        scm_is_pair (s); s = scm_cdr (s))
 415     {
 416       Grob *other = unsmob_grob (scm_caar (s));
 417       vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index);
 418       if (j != VPOS)
 419         {
 420           if (cols[j] == other)
 421             description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
 422           else /* it must end at the LEFT prebroken_piece */
 423             description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
 424         }
 425     }
 426   if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
 427     description.keep_inside_line_ = col->extent (col, X_AXIS);
 428   description.break_permission_ = col->get_property ("line-break-permission");
 429   return description;
 430 }
 431
 432 vector<Real>
 433 get_line_forces (vector<Grob*> const &icols, vector<vsize> breaks,
 434                  Real line_len, Real indent, bool ragged)
 435 {
 436   vector<Real> force;
 437   force.resize (breaks.size () * breaks.size (), infinity_f);
 438
 439   vector<Column_description> cols;
 440   vsize b = 1;
 441   SCM force_break = ly_symbol2scm ("force");
 442
 443   cols.push_back (Column_description ());
 444   for (vsize i = 1; i < icols.size () - 1; i++)
 445     {
 446       if (b < breaks.size () && breaks[b] == i)
 447         {
 448           breaks[b] = cols.size ();
 449           b++;
 450         }
 451       if (!is_loose (icols[i]))
 452         cols.push_back (get_column_description (icols, i, false));
 453     }
 454   breaks.back () = cols.size ();
 455
 456   for (vsize b = 0; b < breaks.size () - 1; b++)
 457     {
 458       cols[breaks[b]] = get_column_description (icols, breaks[b], true);
 459       vsize st = breaks[b];
 460
 461       for (vsize c = b+1; c < breaks.size (); c++)
 462         {
 463           vsize end = breaks[c];
 464           Simple_spacer spacer;
 465
 466           for (vsize i = breaks[b]; i < end - 1; i++)
 467             spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
 468           spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].inverse_hooke_);
 469
 470
 471           for (vsize i = breaks[b]; i < end; i++)
 472             {
 473               for (vsize r = 0; r < cols[i].rods_.size (); r++)
 474                 if (cols[i].rods_[r].r_ < end)
 475                   spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
 476               for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
 477                 if (cols[i].end_rods_[r].r_ == end)
 478                   spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
 479               if (!cols[i].keep_inside_line_.is_empty ())
 480                 {
 481                   spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
 482                   spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]);
 483                 }
 484             }
 485           spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
 486
 487           /* add a (convex) penalty for compression. We do this _only_ in get_line_forces,
 488              not get_line_configuration. This is temporary, for backwards compatibility;
 489              the old line/page-breaking stuff ignores page breaks when it calculates line
 490              breaks, so compression penalties can result in scores (eg. wtk-fugue) blowing
 491              up to too many pages. */
 492           Real f = spacer.force ();
 493           force[b * breaks.size () + c] = f - (f < 0 ? f*f*6 : 0);
 494
 495           if (end < cols.size () && cols[end].break_permission_ == force_break)
 496             break;
 497           if (!spacer.fits ())
 498             {
 499               force[b * breaks.size () + c] = infinity_f;
 500               break;
 501             }
 502         }
 503     }
 504   return force;
 505 }
 506
 507 Column_x_positions
 508 get_line_configuration (vector<Grob*> const &columns,
 509                         Real line_len,
 510                         Real indent,
 511                         bool ragged)
 512 {
 513   vector<Column_description> cols;
 514   Simple_spacer spacer;
 515   Column_x_positions ret;
 516
 517   ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
 518   for (vsize i = 1; i < columns.size () - 1; i++)
 519     {
 520       if (is_loose (columns[i]))
 521         ret.loose_cols_.push_back (columns[i]);
 522       else
 523         ret.cols_.push_back (columns[i]);
 524     }
 525   ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
 526
 527   /* since we've already put our line-ending column in the column list, we can ignore
 528      the end_XXX_ fields of our column_description */
 529   for (vsize i = 0; i < ret.cols_.size () - 1; i++)
 530     {
 531       cols.push_back (get_column_description (ret.cols_, i, i == 0));
 532       spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
 533     }
 534   for (vsize i = 0; i < cols.size (); i++)
 535     {
 536       for (vsize r = 0; r < cols[i].rods_.size (); r++)
 537         spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
 538       if (!cols[i].keep_inside_line_.is_empty ())
 539         {
 540           spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
 541           spacer.add_rod (0, i, cols[i].keep_inside_line_[LEFT]);
 542         }
 543     }
 544
 545   spacer.solve (line_len, ragged);
 546   ret.force_ = spacer.force ();
 547
 548   /*
 549     We used to have a penalty for compression, no matter what, but that
 550     fucked up wtk1-fugue2 (taking 3 full pages.)
 551   */
 552   ret.config_ = spacer.spring_positions ();
 553   for (vsize i = 0; i < ret.config_.size (); i++)
 554     ret.config_[i] += indent;
 555
 556   ret.satisfies_constraints_ = spacer.fits ();
 557
 558   /*
 559     Check if breaking constraints are met.
 560   */
 561   for (vsize i = 1; i < ret.cols_.size () - 1; i++)
 562     {
 563       SCM p = ret.cols_[i]->get_property ("line-break-permission");
 564       if (p == ly_symbol2scm ("force"))
 565         ret.satisfies_constraints_ = false;
 566     }
 567
 568   return ret;
 569 }
 570
 571 static int
 572 compare_paper_column_rank (Grob *const &a,
 573                            Grob *const &b)
 574 {
 575   return Paper_column::get_rank (a) - Paper_column::get_rank (b);
 576 }