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