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