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   Rod_desc (vsize r, Real d)
 294   {
 295     r_ = r;
 296     dist_ = d;
 297   }
 298 };
 299
 300 struct Column_desc
 301 {
 302   vector<Rod_desc> rods_;
 303   vector<Rod_desc> end_rods_;   /* use these if they end at the last column of the line */
 304   Real ideal_;
 305   Real inverse_hooke_;
 306   Real end_ideal_;
 307   Real end_inverse_hooke_;
 308   Interval keep_inside_line_;
 309 };
 310
 311 static int compare_paper_column_rank (Grob *const &a, Grob *const &b);
 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 /* this only returns non-NULL if the line-ending column is the next
 338    spaceable-or-breakable column */
 339 static Grob*
 340 next_line_ending_column (vector<Grob*> const &list, vsize starting)
 341 {
 342   vsize i = starting + 1;
 343   for (; i < list.size ()
 344          && is_loose (list[i])
 345          && !Paper_column::is_breakable (list[i]);
 346        i++)
 347     ;
 348   return dynamic_cast<Item*> (list[i])->find_prebroken_piece (LEFT);
 349 }
 350
 351 static void
 352 get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke)
 353 {
 354   Spring_smob *spring = 0;
 355
 356   for (SCM s = this_col->get_object ("ideal-distances");
 357        !spring && scm_is_pair (s);
 358        s = scm_cdr (s))
 359     {
 360       Spring_smob *sp = unsmob_spring (scm_car (s));
 361
 362       if (sp->other_ == next_col)
 363         spring = sp;
 364     }
 365
 366   if (!spring)
 367     programming_error (_f ("No spring between column %d and next one",
 368                            Paper_column::get_rank (this_col)));
 369
 370   *ideal = (spring) ? spring->distance_ : 5.0;
 371   *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0;
 372 }
 373
 374 static Column_desc
 375 get_column_desc (vector<Grob*> const &cols, vsize col_index, bool line_starter)
 376 {
 377   Grob *col = cols[col_index];
 378   if (line_starter)
 379     col = maybe_find_prebroken_piece (col, RIGHT);
 380
 381   Column_desc desc;
 382   Grob *next_col = next_spaceable_column (cols, col_index);
 383   if (next_col)
 384     get_column_spring (col, next_col, &desc.ideal_, &desc.inverse_hooke_);
 385   Grob *end_col = next_line_ending_column (cols, col_index);
 386   if (end_col)
 387     get_column_spring (col, end_col, &desc.end_ideal_, &desc.end_inverse_hooke_);
 388
 389   for (SCM s = Spaceable_grob::get_minimum_distances (col);
 390        scm_is_pair (s); s = scm_cdr (s))
 391     {
 392       Grob *other = unsmob_grob (scm_caar (s));
 393       vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index);
 394       if (j != VPOS)
 395         {
 396           if (cols[j] == other)
 397             desc.rods_.push_back (Rod_desc (j, scm_to_double (scm_cdar (s))));
 398           else /* it must end at the LEFT prebroken_piece */
 399             desc.end_rods_.push_back (Rod_desc (j, scm_to_double (scm_cdar (s))));
 400         }
 401     }
 402   if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
 403     desc.keep_inside_line_ = col->extent (col, X_AXIS);
 404   return desc;
 405 }
 406
 407 vector<Real>
 408 get_line_forces (vector<Grob*> const &icols, vector<vsize> breaks,
 409                  Real line_len, Real indent, bool ragged)
 410 {
 411   vector<Real> force;
 412   force.resize (breaks.size () * breaks.size ());
 413
 414   vector<Column_desc> cols;
 415   vsize b = 1;
 416   cols.push_back (Column_desc ());
 417   for (vsize i = 1; i < icols.size () - 1; i++)
 418     {
 419       if (b < breaks.size () && breaks[b] == i)
 420         {
 421           breaks[b] = cols.size ();
 422           b++;
 423         }
 424       if (!is_loose (icols[i]))
 425         cols.push_back (get_column_desc (icols, i, false));
 426     }
 427   breaks.back () = cols.size () - 1;
 428
 429   for (vsize b = 0; b < breaks.size () - 1; b++)
 430     {
 431       cols[breaks[b]] = get_column_desc (icols, breaks[b], true);
 432       vsize st = breaks[b];
 433
 434       for (vsize c = b+1; c < breaks.size (); c++)
 435         {
 436           vsize end = breaks[c];
 437           Simple_spacer spacer;
 438
 439           for (vsize i = breaks[b]; i < end - 1; i++)
 440             spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
 441           spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].inverse_hooke_);
 442
 443
 444           for (vsize i = breaks[b]; i < end; i++)
 445             {
 446               for (vsize r = 0; r < cols[i].rods_.size (); r++)
 447                 if (cols[i].rods_[r].r_ < end)
 448                   spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
 449               for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
 450                 if (cols[i].end_rods_[r].r_ == end)
 451                   spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
 452               if (!cols[i].keep_inside_line_.is_empty ())
 453                 {
 454                   spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
 455                   spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]);
 456                 }
 457             }
 458           spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
 459           force[b * breaks.size () + c] = spacer.force ();
 460           if (!spacer.fits ())
 461             {
 462               force[b * breaks.size () + c] = infinity_f;
 463               break;
 464             }
 465         }
 466     }
 467   return force;
 468 }
 469
 470 Column_x_positions
 471 get_line_configuration (vector<Grob*>const &columns,
 472                         Real line_len,
 473                         Real indent,
 474                         bool ragged)
 475 {
 476   vector<Column_desc> cols;
 477   Simple_spacer spacer;
 478   Column_x_positions ret;
 479
 480   ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
 481   for (vsize i = 1; i < columns.size () - 1; i++)
 482     {
 483       if (is_loose (columns[i]))
 484         ret.loose_cols_.push_back (columns[i]);
 485       else
 486         ret.cols_.push_back (columns[i]);
 487     }
 488   ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
 489
 490   cols.resize (ret.cols_.size () - 1);
 491
 492   /* since we've already put our line-ending column in the column list, we can ignore
 493      the end_XXX_ fields of our column_desc */
 494   for (vsize i = 0; i < cols.size (); i++)
 495     {
 496       cols[i] = get_column_desc (ret.cols_, i, i == 0);
 497       spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
 498     }
 499   for (vsize i = 0; i < cols.size (); i++)
 500     for (vsize r = 0; r < cols[i].rods_.size (); r++)
 501       spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
 502
 503   spacer.solve (line_len, ragged);
 504   ret.force_ = spacer.force ();
 505
 506   /*
 507     We used to have a penalty for compression, no matter what, but that
 508     fucked up wtk1-fugue2 (taking 3 full pages.)
 509   */
 510   ret.config_ = spacer.spring_positions ();
 511   for (vsize i = 0; i < ret.config_.size (); i++)
 512     ret.config_[i] += indent;
 513
 514   ret.satisfies_constraints_ = spacer.fits ();
 515
 516   /*
 517     Check if breaking constraints are met.
 518   */
 519   for (vsize i = 1; i < ret.cols_.size () - 1; i++)
 520     {
 521       SCM p = ret.cols_[i]->get_property ("line-break-permission");
 522       if (p == ly_symbol2scm ("force"))
 523         ret.satisfies_constraints_ = false;
 524     }
 525
 526   return ret;
 527 }
 528
 529 static int
 530 compare_paper_column_rank (Grob *const &a,
 531                            Grob *const &b)
 532 {
 533   return Paper_column::get_rank (a) - Paper_column::get_rank (b);
 534 }