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