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 <math.h>
  14
  15 #include "libc-extension.hh"    // isinf
  16 #include "simple-spacer.hh"
  17 #include "paper-column.hh"
  18 #include "spring.hh"
  19 #include "warn.hh"
  20 #include "column-x-positions.hh"
  21 #include "spaceable-grob.hh"
  22 #include "dimensions.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   /*
  63     Give an extra penalty for compression. Needed to avoid compressing
  64     tightly spaced lines.
  65   */
  66   active_count_ = 0;
  67   force_ = 0.;
  68   indent_ = 0.0;
  69   default_space_ = 20 PT;
  70 }
  71
  72 void
  73 Simple_spacer::add_rod (int l, int r, Real dist)
  74 {
  75   if (isinf (dist) || isnan (dist))
  76     {
  77       programming_error ("ignoring weird minimum distance");
  78       return;
  79     }
  80
  81   Real c = range_stiffness (l, r);
  82   if (isinf (c))
  83     {
  84       /*
  85         If a spring is fixed, we have to do something here:
  86         we let the rod override the spring.
  87       */
  88       Real total_dist = 0.;
  89       for (int i = l; i < r; i++)
  90         total_dist += springs_[i].ideal_;
  91
  92       if (total_dist < dist)
  93         for (int i = l; i < r; i++)
  94           springs_[i].ideal_ *= dist / total_dist;
  95
  96       return;
  97     }
  98
  99   Real d = range_ideal_len (l, r);
 100   Real block_stretch = dist - d;
 101
 102   Real block_force = c * block_stretch;
 103   force_ = force_ >? block_force;
 104
 105   for (int i = l; i < r; i++)
 106     springs_[i].block_force_ = block_force >?
 107       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].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       {
 139         bf = bf >? springs_[i].block_force_;
 140       }
 141   return bf;
 142 }
 143
 144 Real
 145 Simple_spacer::active_springs_stiffness () const
 146 {
 147   Real stiff = range_stiffness (0, springs_.size ());
 148   if (isinf (stiff))
 149     {
 150       /*
 151         all springs are inactive. Take the stiffness of the
 152         latest spring to block.
 153       */
 154
 155       Real max_block_force = -infinity_f;
 156       int max_i = -1;
 157       for (int i = 0; i < springs_.size (); i++)
 158         {
 159           if (springs_[i].block_force_ > max_block_force)
 160             {
 161               max_i = i;
 162               max_block_force = springs_[i].block_force_;
 163             }
 164         }
 165
 166       stiff = springs_[max_i].hooke_;
 167     }
 168   return stiff;
 169 }
 170
 171 void
 172 Simple_spacer::set_active_states ()
 173 {
 174   /* float comparison is safe, since force is only copied.  */
 175   for (int i = 0; i < springs_.size (); i++)
 176     if (springs_[i].is_active_
 177         && springs_[i].block_force_ >= force_)
 178       {
 179         springs_[i].is_active_ = false;
 180         active_count_--;
 181       }
 182 }
 183
 184 Real
 185 Simple_spacer::configuration_length () const
 186 {
 187   Real l = 0.;
 188   for (int i = 0; i < springs_.size (); i++)
 189     l += springs_[i].length (force_);
 190
 191   return l;
 192 }
 193
 194 bool
 195 Simple_spacer::is_active () const
 196 {
 197   return active_count_;
 198 }
 199
 200 void
 201 Simple_spacer::my_solve_linelen ()
 202 {
 203   while (is_active ())
 204     {
 205       force_ = active_blocking_force ();
 206       Real conf = configuration_length ();
 207
 208       if (conf < line_len_)
 209         {
 210           force_ += (line_len_ - conf) * active_springs_stiffness ();
 211           break;
 212         }
 213       else
 214         set_active_states ();
 215     }
 216 }
 217
 218 void
 219 Simple_spacer::my_solve_natural_len ()
 220 {
 221   Real line_len_force = 0.0;
 222
 223   while (is_active ())
 224     {
 225       force_ = active_blocking_force () >? 0.0;
 226       Real conf = configuration_length ();
 227
 228       if (conf < line_len_)
 229         {
 230           line_len_force = force_
 231             + (line_len_ - conf)
 232             * active_springs_stiffness ();
 233         }
 234
 235       if (force_ < 1e-8) // ugh.,
 236         break;
 237
 238       set_active_states ();
 239     }
 240
 241   force_ = line_len_force;
 242 }
 243
 244 /****************************************************************/
 245
 246 Spring_description::Spring_description ()
 247 {
 248   ideal_ = 0.0;
 249   hooke_ = 0.0;
 250   is_active_ = true;
 251   block_force_ = 0.0;
 252 }
 253
 254 bool
 255 Spring_description::is_sane () const
 256 {
 257   return (hooke_ > 0)
 258     && ideal_ > 0
 259     && !isinf (ideal_) && !isnan (ideal_);
 260 }
 261
 262 Real
 263 Spring_description::length (Real f) const
 264 {
 265   if (!is_active_)
 266     f = block_force_;
 267   return ideal_ + f / hooke_;
 268 }
 269 /****************************************************************/
 270
 271 /*
 272   TODO: should a add penalty for widely varying spring forces (caused
 273   by constraints, eg.
 274
 275
 276   =====
 277   |   |
 278   o|o|  x ##x
 279
 280
 281   The ## forces the notes apart; we shouldn't allow the O's to touch
 282   this closely.
 283 */
 284 void
 285 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
 286 {
 287   if (ragged)
 288     spacer_->my_solve_natural_len ();
 289   else
 290     spacer_->my_solve_linelen ();
 291
 292   positions->force_ = spacer_->force_;
 293
 294   /*
 295     We used to have a penalty for compression, no matter what, but that
 296     fucked up wtk1-fugue2 (taking 3 full pages.)
 297   */
 298   positions->config_.push (spacer_->indent_);
 299   for (int i = 0; i < spacer_->springs_.size (); i++)
 300     {
 301       Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
 302       positions->config_.push (positions->config_.top () + l);
 303       /*
 304         we have l>= 0 here, up to rounding errors
 305       */
 306     }
 307
 308   /*
 309     For raggedright, we must have a measure of music density: this is
 310     to prevent lots of short lines (which all have force = 0).
 311   */
 312   if (ragged)
 313     {
 314       positions->satisfies_constraints_
 315         = positions->config_.top () < spacer_->line_len_;
 316     }
 317   else
 318     positions->satisfies_constraints_ = spacer_->is_active ();
 319
 320   positions->cols_ = spaced_cols_;
 321   positions->loose_cols_ = loose_cols_;
 322
 323   /*
 324     Check if breaking constraints are met.
 325   */
 326   bool break_satisfy = true;
 327   int sz = positions->cols_.size ();
 328   for (int i = sz; i--;)
 329     {
 330       SCM p = positions->cols_[i]->get_property ("penalty");
 331       if (scm_is_number (p))
 332         {
 333           if (scm_to_double (p) < -9999)
 334             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 335           if (scm_to_double (p) > 9999)
 336             break_satisfy = break_satisfy && ! (i == 0 || i == sz -1);
 337         }
 338     }
 339
 340   positions->satisfies_constraints_
 341     = positions->satisfies_constraints_ && break_satisfy;
 342 }
 343
 344 void
 345 Simple_spacer::add_spring (Real ideal, Real hooke)
 346 {
 347   Spring_description desc;
 348
 349   desc.ideal_ = ideal;
 350   desc.hooke_ = hooke;
 351   if (!desc.is_sane ())
 352     {
 353       programming_error ("insane spring found, setting to unit");
 354
 355       desc.hooke_ = 1.0;
 356       desc.ideal_ = 1.0;
 357     }
 358
 359   if (isinf (hooke))
 360     {
 361       desc.is_active_ = false;
 362     }
 363   else
 364     {
 365       /*
 366         desc.is_active_ ?
 367       */
 368       desc.block_force_ = -desc.hooke_ * desc.ideal_; // block at distance 0
 369
 370       active_count_++;
 371     }
 372   springs_.push (desc);
 373 }
 374
 375 static int
 376 compare_paper_column_rank (Grob *const &a,
 377                            Grob *const &b)
 378 {
 379   return Paper_column::get_rank (a) - Paper_column::get_rank (b);
 380 }
 381
 382 void
 383 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
 384 {
 385   Link_array<Grob> cols (icols);
 386
 387   for (int i = cols.size (); i--;)
 388     if (scm_is_pair (cols[i]->get_property ("between-cols")))
 389       {
 390         loose_cols_.push (cols[i]);
 391         cols.del (i);
 392       }
 393
 394   spaced_cols_ = cols;
 395   for (int i = 0; i < cols.size () - 1; i++)
 396     {
 397       Spring_smob *spring = 0;
 398
 399       for (SCM s = cols[i]->get_property ("ideal-distances");
 400            !spring && scm_is_pair (s);
 401            s = scm_cdr (s))
 402         {
 403           Spring_smob *sp = unsmob_spring (scm_car (s));
 404
 405           if (sp->other_ == cols[i + 1])
 406             spring = sp;
 407         }
 408
 409       if (!spring)
 410         programming_error (_f ("No spring between column %d and next one",
 411                                Paper_column::get_rank (cols[i])));
 412
 413       Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
 414       Real hooke = (spring) ? spring->strength_ : 1.0;
 415
 416       spacer_->add_spring (ideal, hooke);
 417     }
 418
 419   for (int i = 0; i < cols.size () - 1; i++)
 420     {
 421       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 422            scm_is_pair (s); s = scm_cdr (s))
 423         {
 424           Grob *other = unsmob_grob (scm_caar (s));
 425           int oi = binsearch_links (cols, other, &compare_paper_column_rank);
 426           if (oi >= 0
 427               && cols[oi] == other)
 428             {
 429               spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s)));
 430             }
 431         }
 432
 433       if (i
 434           && !to_boolean (cols[i]->get_property ("allow-outside-line")))
 435         {
 436           Interval e = cols[i]->extent (cols[i], X_AXIS);
 437           if (!e.is_empty ())
 438             {
 439               spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
 440               spacer_->add_rod (0, i, e[LEFT]);
 441             }
 442         }
 443     }
 444 }
 445
 446 Simple_spacer_wrapper::Simple_spacer_wrapper ()
 447 {
 448   spacer_ = new Simple_spacer ();
 449 }
 450
 451 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
 452 {
 453   delete spacer_;
 454 }
 455
 456 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)
 457 {
 458 }