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