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--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7
   8   TODO:
   9   - add support for different stretch/shrink constants?
  10 */
  11
  12 #include <cstdio>
  13 #include <cmath>
  14 using namespace std;
  15
  16 #include "libc-extension.hh"    // isinf
  17 #include "simple-spacer.hh"
  18 #include "paper-column.hh"
  19 #include "spring.hh"
  20 #include "warn.hh"
  21 #include "column-x-positions.hh"
  22 #include "spaceable-grob.hh"
  23 #include "dimensions.hh"
  24
  25 /*
  26   A simple spacing constraint solver. The approach:
  27
  28   Stretch the line uniformly until none of the constraints (rods)
  29   block.  It then is very wide.
  30
  31   Compress until the next constraint blocks,
  32
  33   Mark the springs over the constrained part to be non-active.
  34
  35   Repeat with the smaller set of non-active constraints, until all
  36   constraints blocked, or until the line is as short as desired.
  37
  38   This is much simpler, and much much faster than full scale
  39   Constrained QP. On the other hand, a situation like this will not
  40   be typeset as dense as possible, because
  41
  42   c4                   c4           c4                  c4
  43   veryveryverylongsyllable2         veryveryverylongsyllable2
  44   " "4                 veryveryverylongsyllable2        syllable4
  45
  46
  47   can be further compressed to
  48
  49
  50   c4    c4                        c4   c4
  51   veryveryverylongsyllable2       veryveryverylongsyllable2
  52   " "4  veryveryverylongsyllable2      syllable4
  53
  54
  55   Perhaps this is not a bad thing, because the 1st looks better anyway.  */
  56
  57 /*
  58   positive force = expanding, negative force = compressing.
  59 */
  60
  61 Simple_spacer::Simple_spacer ()
  62 {
  63   /*
  64     Give an extra penalty for compression. Needed to avoid compressing
  65     tightly spaced lines.
  66   */
  67   active_count_ = 0;
  68   force_ = 0.;
  69   indent_ = 0.0;
  70   default_space_ = 20 PT;
  71 }
  72
  73 void
  74 Simple_spacer::add_rod (int l, int r, Real dist)
  75 {
  76   if (isinf (dist) || isnan (dist))
  77     {
  78       programming_error ("ignoring weird minimum distance");
  79       return;
  80     }
  81
  82   Real c = range_stiffness (l, r);
  83   if (isinf (c))
  84     {
  85       /*
  86         If a spring is fixed, we have to do something here:
  87         we let the rod override the spring.
  88       */
  89       Real total_dist = 0.;
  90       for (int i = l; i < r; i++)
  91         total_dist += springs_[i].ideal_;
  92
  93       if (total_dist < dist)
  94         for (int i = l; i < r; i++)
  95           springs_[i].ideal_ *= dist / total_dist;
  96
  97       return;
  98     }
  99
 100   Real d = range_ideal_len (l, r);
 101   Real block_stretch = dist - d;
 102
 103   Real block_force = c * block_stretch;
 104   force_ = max (force_, block_force);
 105
 106   for (int i = l; i < r; i++)
 107     springs_[i].block_force_ = max (block_force, springs_[i].block_force_);
 108 }
 109
 110 Real
 111 Simple_spacer::range_ideal_len (int l, int r) const
 112 {
 113   Real d = 0.;
 114   for (int i = l; i < r; i++)
 115     d += springs_[i].ideal_;
 116   return d;
 117 }
 118
 119 Real
 120 Simple_spacer::range_stiffness (int l, int r) const
 121 {
 122   Real den = 0.0;
 123   for (int i = l; i < r; i++)
 124     {
 125       if (springs_[i].is_active_)
 126         den += 1 * springs_[i].inverse_hooke_;
 127     }
 128
 129   return 1 / den;
 130 }
 131
 132 Real
 133 Simple_spacer::active_blocking_force () const
 134 {
 135   Real bf = -infinity_f;
 136   for (int i = 0; i < springs_.size (); i++)
 137     if (springs_[i].is_active_)
 138       bf = max (bf, springs_[i].block_force_);
 139   return bf;
 140 }
 141
 142 Real
 143 Simple_spacer::active_springs_stiffness () const
 144 {
 145   Real stiff = range_stiffness (0, springs_.size ());
 146   if (isinf (stiff))
 147     {
 148       /*
 149         all springs are inactive. Take the stiffness of the
 150         latest spring to block.
 151       */
 152
 153       Real max_block_force = -infinity_f;
 154       int max_i = -1;
 155       for (int i = 0; i < springs_.size (); i++)
 156         {
 157           if (springs_[i].block_force_ > max_block_force)
 158             {
 159               max_i = i;
 160               max_block_force = springs_[i].block_force_;
 161             }
 162         }
 163
 164       stiff = 1/springs_[max_i].inverse_hooke_;
 165     }
 166   return stiff;
 167 }
 168
 169 void
 170 Simple_spacer::set_active_states ()
 171 {
 172   /* float comparison is safe, since force is only copied.  */
 173   for (int i = 0; i < springs_.size (); i++)
 174     if (springs_[i].is_active_
 175         && springs_[i].block_force_ >= force_)
 176       {
 177         springs_[i].is_active_ = false;
 178         active_count_--;
 179       }
 180 }
 181
 182 Real
 183 Simple_spacer::configuration_length () const
 184 {
 185   Real l = 0.;
 186   for (int i = 0; i < springs_.size (); i++)
 187     l += springs_[i].length (force_);
 188
 189   return l;
 190 }
 191
 192 bool
 193 Simple_spacer::is_active () const
 194 {
 195   return active_count_;
 196 }
 197
 198 void
 199 Simple_spacer::my_solve_linelen ()
 200 {
 201   while (is_active ())
 202     {
 203       force_ = active_blocking_force ();
 204       Real conf = configuration_length ();
 205
 206       if (conf < line_len_)
 207         {
 208           force_ += (line_len_ - conf) * active_springs_stiffness ();
 209           break;
 210         }
 211       else
 212         set_active_states ();
 213     }
 214 }
 215
 216 void
 217 Simple_spacer::my_solve_natural_len ()
 218 {
 219   Real line_len_force = 0.0;
 220
 221   while (is_active ())
 222     {
 223       force_ = max (active_blocking_force (), 0.0);
 224       Real conf = configuration_length ();
 225
 226       if (conf < line_len_)
 227         {
 228           line_len_force = force_
 229             + (line_len_ - conf)
 230             * active_springs_stiffness ();
 231         }
 232
 233       if (force_ < 1e-8) // ugh.,
 234         break;
 235
 236       set_active_states ();
 237     }
 238
 239   force_ = line_len_force;
 240 }
 241
 242 /****************************************************************/
 243
 244 Spring_description::Spring_description ()
 245 {
 246   ideal_ = 0.0;
 247   inverse_hooke_ = 0.0;
 248   is_active_ = true;
 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   if (!is_active_)
 264     f = block_force_;
 265   return ideal_ + f * inverse_hooke_;
 266 }
 267 /****************************************************************/
 268
 269 /*
 270   TODO: should a add penalty for widely varying spring forces (caused
 271   by constraints, eg.
 272
 273
 274   .     =====
 275   .     |   |
 276   .o|o|x ##x
 277   .
 278
 279   The ## forces the notes apart; we shouldn't allow the O's to touch
 280   this closely.
 281 */
 282 void
 283 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
 284 {
 285   if (ragged)
 286     spacer_->my_solve_natural_len ();
 287   else
 288     spacer_->my_solve_linelen ();
 289
 290   positions->force_ = spacer_->force_;
 291
 292   /*
 293     We used to have a penalty for compression, no matter what, but that
 294     fucked up wtk1-fugue2 (taking 3 full pages.)
 295   */
 296   positions->config_.push (spacer_->indent_);
 297   for (int i = 0; i < spacer_->springs_.size (); i++)
 298     {
 299       Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
 300       positions->config_.push (positions->config_.top () + l);
 301       /*
 302         we have l>= 0 here, up to rounding errors
 303       */
 304     }
 305
 306   /*
 307     For raggedright, we must have a measure of music density: this is
 308     to prevent lots of short lines (which all have force = 0).
 309   */
 310   if (ragged)
 311     {
 312       positions->satisfies_constraints_
 313         = positions->config_.top () < spacer_->line_len_;
 314     }
 315   else
 316     positions->satisfies_constraints_ = spacer_->is_active ();
 317
 318   positions->cols_ = spaced_cols_;
 319   positions->loose_cols_ = loose_cols_;
 320
 321   /*
 322     Check if breaking constraints are met.
 323   */
 324   bool break_satisfy = true;
 325   int sz = positions->cols_.size ();
 326   for (int i = sz; i--;)
 327     {
 328       SCM p = positions->cols_[i]->get_property ("penalty");
 329       if (scm_is_number (p))
 330         {
 331           if (scm_to_double (p) < -9999)
 332             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 333           if (scm_to_double (p) > 9999)
 334             break_satisfy = break_satisfy && ! (i == 0 || i == sz -1);
 335         }
 336     }
 337
 338   positions->satisfies_constraints_
 339     = positions->satisfies_constraints_ && break_satisfy;
 340 }
 341
 342 void
 343 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
 344 {
 345   Spring_description desc;
 346
 347   desc.ideal_ = ideal;
 348   desc.inverse_hooke_ = inverse_hooke;
 349   if (!desc.is_sane ())
 350     {
 351       programming_error ("insane spring found, setting to unit");
 352
 353       desc.inverse_hooke_ = 1.0;
 354       desc.ideal_ = 1.0;
 355     }
 356
 357   if (!inverse_hooke)
 358     desc.is_active_ = false;
 359   else
 360     {
 361       /*
 362         desc.is_active_ ?
 363       */
 364       desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_;
 365       // block at distance 0
 366
 367       active_count_++;
 368     }
 369   springs_.push (desc);
 370 }
 371
 372 static int
 373 compare_paper_column_rank (Grob *const &a,
 374                            Grob *const &b)
 375 {
 376   return Paper_column::get_rank (a) - Paper_column::get_rank (b);
 377 }
 378
 379 void
 380 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
 381 {
 382   Link_array<Grob> cols (icols);
 383   cols.clear ();
 384
 385   for (int i = 0; i < icols.size (); i++)
 386     if (scm_is_pair (icols[i]->get_object ("between-cols")))
 387       loose_cols_.push (icols[i]);
 388     else
 389       cols.push (icols[i]);
 390
 391   spaced_cols_ = cols;
 392   for (int i = 0; i < cols.size () - 1; i++)
 393     {
 394       Spring_smob *spring = 0;
 395
 396       for (SCM s = cols[i]->get_object ("ideal-distances");
 397            !spring && scm_is_pair (s);
 398            s = scm_cdr (s))
 399         {
 400           Spring_smob *sp = unsmob_spring (scm_car (s));
 401
 402           if (sp->other_ == cols[i + 1])
 403             spring = sp;
 404         }
 405
 406       if (!spring)
 407         programming_error (_f ("No spring between column %d and next one",
 408                                Paper_column::get_rank (cols[i])));
 409
 410       Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
 411       Real inverse_hooke = (spring) ? spring->inverse_strength_ : 1.0;
 412
 413       spacer_->add_spring (ideal, inverse_hooke);
 414     }
 415
 416   for (int i = 0; i < cols.size () - 1; i++)
 417     {
 418       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 419            scm_is_pair (s); s = scm_cdr (s))
 420         {
 421           Grob *other = unsmob_grob (scm_caar (s));
 422           int j = binsearch_links (cols, other, &compare_paper_column_rank);
 423           if (j >= 0 && cols[j] == other)
 424             spacer_->add_rod (i, j, scm_to_double (scm_cdar (s)));
 425         }
 426
 427       if (i
 428           && to_boolean (cols[i]->get_property ("keep-inside-line")))
 429         {
 430           Interval e = cols[i]->extent (cols[i], X_AXIS);
 431           if (!e.is_empty ())
 432             {
 433               spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
 434               spacer_->add_rod (0, i, e[LEFT]);
 435             }
 436         }
 437     }
 438 }
 439
 440 Simple_spacer_wrapper::Simple_spacer_wrapper ()
 441 {
 442   spacer_ = new Simple_spacer ();
 443 }
 444
 445 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
 446 {
 447   delete spacer_;
 448 }
 449
 450 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)
 451 {
 452 }