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_ = max (force_, block_force);
 104
 105   for (int i = l; i < r; i++)
 106     springs_[i].block_force_ = max (block_force, springs_[i].block_force_);
 107 }
 108
 109 Real
 110 Simple_spacer::range_ideal_len (int l, int r) const
 111 {
 112   Real d = 0.;
 113   for (int i = l; i < r; i++)
 114     d += springs_[i].ideal_;
 115   return d;
 116 }
 117
 118 Real
 119 Simple_spacer::range_stiffness (int l, int r) const
 120 {
 121   Real den = 0.0;
 122   for (int i = l; i < r; i++)
 123     {
 124       if (springs_[i].is_active_)
 125         den += 1 * springs_[i].inverse_hooke_;
 126     }
 127
 128   return 1 / den;
 129 }
 130
 131 Real
 132 Simple_spacer::active_blocking_force () const
 133 {
 134   Real bf = -infinity_f;
 135   for (int i = 0; i < springs_.size (); i++)
 136     if (springs_[i].is_active_)
 137       {
 138         bf = max (bf, springs_[i].block_force_);
 139       }
 140   return bf;
 141 }
 142
 143 Real
 144 Simple_spacer::active_springs_stiffness () const
 145 {
 146   Real stiff = range_stiffness (0, springs_.size ());
 147   if (isinf (stiff))
 148     {
 149       /*
 150         all springs are inactive. Take the stiffness of the
 151         latest spring to block.
 152       */
 153
 154       Real max_block_force = -infinity_f;
 155       int max_i = -1;
 156       for (int i = 0; i < springs_.size (); i++)
 157         {
 158           if (springs_[i].block_force_ > max_block_force)
 159             {
 160               max_i = i;
 161               max_block_force = springs_[i].block_force_;
 162             }
 163         }
 164
 165       stiff = 1/springs_[max_i].inverse_hooke_;
 166     }
 167   return stiff;
 168 }
 169
 170 void
 171 Simple_spacer::set_active_states ()
 172 {
 173   /* float comparison is safe, since force is only copied.  */
 174   for (int i = 0; i < springs_.size (); i++)
 175     if (springs_[i].is_active_
 176         && springs_[i].block_force_ >= force_)
 177       {
 178         springs_[i].is_active_ = false;
 179         active_count_--;
 180       }
 181 }
 182
 183 Real
 184 Simple_spacer::configuration_length () const
 185 {
 186   Real l = 0.;
 187   for (int i = 0; i < springs_.size (); i++)
 188     l += springs_[i].length (force_);
 189
 190   return l;
 191 }
 192
 193 bool
 194 Simple_spacer::is_active () const
 195 {
 196   return active_count_;
 197 }
 198
 199 void
 200 Simple_spacer::my_solve_linelen ()
 201 {
 202   while (is_active ())
 203     {
 204       force_ = active_blocking_force ();
 205       Real conf = configuration_length ();
 206
 207       if (conf < line_len_)
 208         {
 209           force_ += (line_len_ - conf) * active_springs_stiffness ();
 210           break;
 211         }
 212       else
 213         set_active_states ();
 214     }
 215 }
 216
 217 void
 218 Simple_spacer::my_solve_natural_len ()
 219 {
 220   Real line_len_force = 0.0;
 221
 222   while (is_active ())
 223     {
 224       force_ = max (active_blocking_force (), 0.0);
 225       Real conf = configuration_length ();
 226
 227       if (conf < line_len_)
 228         {
 229           line_len_force = force_
 230             + (line_len_ - conf)
 231             * active_springs_stiffness ();
 232         }
 233
 234       if (force_ < 1e-8) // ugh.,
 235         break;
 236
 237       set_active_states ();
 238     }
 239
 240   force_ = line_len_force;
 241 }
 242
 243 /****************************************************************/
 244
 245 Spring_description::Spring_description ()
 246 {
 247   ideal_ = 0.0;
 248   inverse_hooke_ = 0.0;
 249   is_active_ = true;
 250   block_force_ = 0.0;
 251 }
 252
 253 bool
 254 Spring_description::is_sane () const
 255 {
 256   return (inverse_hooke_ >= 0)
 257     && ideal_ > 0
 258     && !isinf (ideal_) && !isnan (ideal_);
 259 }
 260
 261 Real
 262 Spring_description::length (Real f) const
 263 {
 264   if (!is_active_)
 265     f = block_force_;
 266   return ideal_ + f * inverse_hooke_;
 267 }
 268 /****************************************************************/
 269
 270 /*
 271   TODO: should a add penalty for widely varying spring forces (caused
 272   by constraints, eg.
 273
 274
 275   .     =====
 276   .     |   |
 277   .o|o|x ##x
 278   .
 279
 280   The ## forces the notes apart; we shouldn't allow the O's to touch
 281   this closely.
 282 */
 283 void
 284 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
 285 {
 286   if (ragged)
 287     spacer_->my_solve_natural_len ();
 288   else
 289     spacer_->my_solve_linelen ();
 290
 291   positions->force_ = spacer_->force_;
 292
 293   /*
 294     We used to have a penalty for compression, no matter what, but that
 295     fucked up wtk1-fugue2 (taking 3 full pages.)
 296   */
 297   positions->config_.push (spacer_->indent_);
 298   for (int i = 0; i < spacer_->springs_.size (); i++)
 299     {
 300       Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
 301       positions->config_.push (positions->config_.top () + l);
 302       /*
 303         we have l>= 0 here, up to rounding errors
 304       */
 305     }
 306
 307   /*
 308     For raggedright, we must have a measure of music density: this is
 309     to prevent lots of short lines (which all have force = 0).
 310   */
 311   if (ragged)
 312     {
 313       positions->satisfies_constraints_
 314         = positions->config_.top () < spacer_->line_len_;
 315     }
 316   else
 317     positions->satisfies_constraints_ = spacer_->is_active ();
 318
 319   positions->cols_ = spaced_cols_;
 320   positions->loose_cols_ = loose_cols_;
 321
 322   /*
 323     Check if breaking constraints are met.
 324   */
 325   bool break_satisfy = true;
 326   int sz = positions->cols_.size ();
 327   for (int i = sz; i--;)
 328     {
 329       SCM p = positions->cols_[i]->get_property ("penalty");
 330       if (scm_is_number (p))
 331         {
 332           if (scm_to_double (p) < -9999)
 333             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 334           if (scm_to_double (p) > 9999)
 335             break_satisfy = break_satisfy && ! (i == 0 || i == sz -1);
 336         }
 337     }
 338
 339   positions->satisfies_constraints_
 340     = positions->satisfies_constraints_ && break_satisfy;
 341 }
 342
 343 void
 344 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
 345 {
 346   Spring_description desc;
 347
 348   desc.ideal_ = ideal;
 349   desc.inverse_hooke_ = inverse_hooke;
 350   if (!desc.is_sane ())
 351     {
 352       programming_error ("insane spring found, setting to unit");
 353
 354       desc.inverse_hooke_ = 1.0;
 355       desc.ideal_ = 1.0;
 356     }
 357
 358   if (!inverse_hooke)
 359     {
 360       desc.is_active_ = false;
 361     }
 362   else
 363     {
 364       /*
 365         desc.is_active_ ?
 366       */
 367       desc.block_force_ = - desc.ideal_ / desc.inverse_hooke_;
 368       // 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_object ("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_object ("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 inverse_hooke = (spring) ? spring->inverse_strength_ : 1.0;
 415
 416       spacer_->add_spring (ideal, inverse_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 j = binsearch_links (cols, other, &compare_paper_column_rank);
 426           if (j >= 0 && cols[j] == other)
 427             {
 428               spacer_->add_rod (i, j, scm_to_double (scm_cdar (s)));
 429             }
 430         }
 431
 432       if (i
 433           && to_boolean (cols[i]->get_property ("keep-inside-line")))
 434         {
 435           Interval e = cols[i]->extent (cols[i], X_AXIS);
 436           if (!e.is_empty ())
 437             {
 438               spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
 439               spacer_->add_rod (0, i, e[LEFT]);
 440             }
 441         }
 442     }
 443 }
 444
 445 Simple_spacer_wrapper::Simple_spacer_wrapper ()
 446 {
 447   spacer_ = new Simple_spacer ();
 448 }
 449
 450 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
 451 {
 452   delete spacer_;
 453 }
 454
 455 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)
 456 {
 457 }