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