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