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--2003 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7
   8   TODO:
   9   - add support for different stretch/shrink constants?
  10
  11 */
  12 #include <stdio.h>
  13 #include <math.h>
  14 #include <libc-extension.hh>    // isinf
  15
  16 #include "simple-spacer.hh"
  17 #include "paper-column.hh"
  18 #include "spring.hh"
  19 #include "rod.hh"
  20 #include "warn.hh"
  21 #include "column-x-positions.hh"
  22 #include "spaceable-grob.hh"
  23 #include "dimensions.hh"
  24
  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 Simple_spacer::Simple_spacer ()
  60 {
  61   /*
  62     Give an extra penalty for compression. Needed to avoid compressing
  63     tightly spaced lines.
  64   */
  65   compression_penalty_b_ = false;
  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 ("Weird minimum distance. Ignoring");
  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].active_b_)
 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].active_b_)
 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 den = 0.0;
 148   for (int i=0; i < springs_.size (); i++)
 149     if (springs_[i].active_b_)
 150       {
 151         den += 1 / springs_[i].hooke_;
 152       }
 153   return 1/den;
 154 }
 155
 156 void
 157 Simple_spacer::set_active_states ()
 158 {
 159   /* float comparison is safe, since force is only copied.  */
 160   for (int i=0 ; i <springs_.size (); i++)
 161     if (springs_[i].active_b_
 162         && springs_[i].block_force_ >= force_)
 163       {
 164         springs_[i].active_b_ = false;
 165         active_count_ --;
 166       }
 167 }
 168
 169 Real
 170 Simple_spacer::configuration_length () const
 171 {
 172   Real l =0.;
 173   for (int i=0; i < springs_.size (); i++)
 174     l += springs_[i].length (force_);
 175
 176   return l;
 177 }
 178
 179 bool
 180 Simple_spacer::active_b () const
 181 {
 182   return active_count_;
 183 }
 184
 185 void
 186 Simple_spacer::my_solve_linelen ()
 187 {
 188   while (active_b ())
 189     {
 190       force_ = active_blocking_force ();
 191       Real conf = configuration_length ();
 192
 193       if (conf < line_len_)
 194         {
 195           force_ += (line_len_  - conf) * active_springs_stiffness ();
 196           break;
 197         }
 198       else
 199         set_active_states ();
 200     }
 201 }
 202
 203
 204 void
 205 Simple_spacer::my_solve_natural_len ()
 206 {
 207   while (active_b ())
 208     {
 209       force_ = active_blocking_force () >? 0.0;
 210
 211       if (force_ < 1e-8) // ugh.,
 212         break;
 213
 214       set_active_states ();
 215     }
 216 }
 217
 218 void
 219 Simple_spacer::add_columns (Link_array<Grob> const &icols)
 220 {
 221   Link_array<Grob> cols(icols);
 222
 223   for (int i =  cols.size (); i--;)
 224     if (gh_pair_p (cols[i]->get_grob_property ("between-cols")))
 225       {
 226         loose_cols_.push (cols[i]);
 227         cols.del (i);
 228       }
 229
 230   spaced_cols_ = cols;
 231   for (int i=0; i < cols.size () - 1; i++)
 232     {
 233       Spring_smob *spring = 0;
 234
 235       for (SCM s = cols[i]->get_grob_property ("ideal-distances");
 236            !spring && gh_pair_p (s);
 237            s = ly_cdr (s))
 238         {
 239           Spring_smob *sp = unsmob_spring (ly_car (s));
 240
 241
 242           if (sp->other_ == cols[i+1])
 243             spring = sp;
 244         }
 245
 246       Spring_description desc;
 247       if (spring)
 248         {
 249           desc.ideal_ = spring->distance_;
 250           desc.hooke_ = spring->strength_;
 251         }
 252       else
 253         {
 254           programming_error (_f("No spring between column %d and next one",
 255                                 Paper_column::get_rank (cols[i])
 256                                 ));
 257           desc.hooke_ = 1.0;
 258           desc.ideal_ = default_space_;
 259
 260           continue;
 261         }
 262
 263       if (!desc.sane_b ())
 264         {
 265           programming_error ("Insane spring found. Setting to unit spring.");
 266
 267           desc.hooke_ = 1.0;
 268           desc.ideal_ = 1.0;
 269         }
 270
 271       if (isinf (desc.hooke_))
 272         {
 273           desc.active_b_ = false;
 274           springs_.push (desc);
 275         }
 276       else
 277         {
 278           desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
 279           springs_.push (desc);
 280
 281           active_count_ ++;
 282         }
 283
 284       if (spring->expand_only_b_)
 285         {
 286           compression_penalty_b_ = true;
 287         }
 288
 289     }
 290
 291   for (int i=0; i < cols.size () - 1; i++)
 292     {
 293       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 294            gh_pair_p (s); s = ly_cdr (s))
 295         {
 296           Grob * other = unsmob_grob (ly_caar (s));
 297           int oi = cols.find_index (other);
 298           if (oi >= 0)
 299             {
 300               add_rod (i, oi, gh_scm2double (ly_cdar (s)));
 301             }
 302         }
 303     }
 304
 305   /*
 306     TODO: should support natural length on only the last line.
 307    */
 308   if (line_len_ < 0)
 309     my_solve_natural_len ();
 310   else
 311     my_solve_linelen ();
 312 }
 313
 314 /*
 315
 316   TODO: should a add penalty for widely varying spring forces (caused
 317   by constraints, eg.
 318
 319
 320          =====
 321          |   |
 322   o|o|  x ##x
 323
 324
 325   The ## forces the notes apart; we shouldn't allow the O's to touch
 326   this closely.
 327
 328  */
 329 void
 330 Simple_spacer::solve (Column_x_positions *positions, bool ragged) const
 331 {
 332   positions->force_ = force_;
 333   if ((force_ < 0))
 334     {
 335
 336       /*
 337         We used to have a penalty for compression, no matter what, but that
 338         fucked up wtk1-fugue2 (taking 3 full pages.)
 339
 340         maybe this should be tunable?
 341        */
 342       if (compression_penalty_b_)
 343         ; //    positions->force_ *= 2; //  hmm.
 344     }
 345
 346   positions->config_.push (indent_);
 347   for (int i=0; i <springs_.size (); i++)
 348     {
 349       Real  l = springs_[i].length ((ragged) ? 0.0 : force_);
 350       positions->config_.push (positions->config_.top () + l);
 351       /*
 352         we have l>= 0 here, up to rounding errors
 353       */
 354     }
 355   positions->cols_ = spaced_cols_;
 356   positions->loose_cols_ = loose_cols_;
 357
 358   positions->satisfies_constraints_b_ = (line_len_ < 0) || active_b ();
 359
 360
 361   /*
 362     Check if breaking constraints are met.
 363    */
 364   bool break_satisfy = true;
 365   int sz =  positions->cols_.size ();
 366   for (int i = sz; i--; )
 367     {
 368       SCM p = positions->cols_[i]->get_grob_property( "penalty");
 369       if (gh_number_p (p))
 370         {
 371           if (gh_scm2double (p) < -9999)
 372             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 373           if (gh_scm2double (p) > 9999)
 374             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 375         }
 376
 377     }
 378
 379   positions->satisfies_constraints_b_ =
 380     positions->satisfies_constraints_b_ && break_satisfy;
 381
 382   if (ragged && force_ < 0)
 383     positions->satisfies_constraints_b_ = false;
 384 }
 385
 386 /****************************************************************/
 387
 388 Spring_description::Spring_description ()
 389 {
 390   ideal_ =0.0;
 391   hooke_ =0.0;
 392   active_b_ = true;
 393   block_force_ = 0.0;
 394 }
 395
 396
 397 bool
 398 Spring_description::sane_b () const
 399 {
 400   return (hooke_ > 0) &&  !isinf (ideal_) && !isnan (ideal_);
 401 }
 402
 403 Real
 404 Spring_description::length (Real f) const
 405 {
 406   if (!active_b_)
 407     f = block_force_;
 408   return ideal_ + f / hooke_ ;
 409 }