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