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 }
 307
 308 /*
 309
 310   TODO: should a add penalty for widely varying spring forces (caused
 311   by constraints, eg.
 312
 313
 314          =====
 315          |   |
 316   o|o|  x ##x
 317
 318
 319   The ## forces the notes apart; we shouldn't allow the O's to touch
 320   this closely.
 321
 322  */
 323 void
 324 Simple_spacer::solve (Column_x_positions *positions, bool ragged)
 325 {
 326   /*
 327     TODO: should support natural length on only the last line.
 328    */
 329   ragged = ragged || (line_len_ < 0) ;
 330   if (ragged)
 331     my_solve_natural_len ();
 332   else
 333     my_solve_linelen ();
 334
 335
 336   positions->force_ = force_;
 337   if ((force_ < 0))
 338     {
 339
 340       /*
 341         We used to have a penalty for compression, no matter what, but that
 342         fucked up wtk1-fugue2 (taking 3 full pages.)
 343
 344         maybe this should be tunable?
 345        */
 346       if (compression_penalty_b_)
 347         ; //    positions->force_ *= 2; //  hmm.
 348     }
 349
 350   positions->config_.push (indent_);
 351   for (int i=0; i <springs_.size (); i++)
 352     {
 353       Real  l = springs_[i].length ((ragged) ? 0.0 : force_);
 354       positions->config_.push (positions->config_.top () + l);
 355       /*
 356         we have l>= 0 here, up to rounding errors
 357       */
 358     }
 359   positions->cols_ = spaced_cols_;
 360   positions->loose_cols_ = loose_cols_;
 361
 362   positions->satisfies_constraints_b_ = (line_len_ < 0) || active_b ();
 363
 364
 365   /*
 366     Check if breaking constraints are met.
 367    */
 368   bool break_satisfy = true;
 369   int sz =  positions->cols_.size ();
 370   for (int i = sz; i--; )
 371     {
 372       SCM p = positions->cols_[i]->get_grob_property( "penalty");
 373       if (gh_number_p (p))
 374         {
 375           if (gh_scm2double (p) < -9999)
 376             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 377           if (gh_scm2double (p) > 9999)
 378             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 379         }
 380
 381     }
 382
 383   positions->satisfies_constraints_b_ =
 384     positions->satisfies_constraints_b_ && break_satisfy;
 385
 386   if (ragged && force_ < 0)
 387     positions->satisfies_constraints_b_ = false;
 388 }
 389
 390 /****************************************************************/
 391
 392 Spring_description::Spring_description ()
 393 {
 394   ideal_ =0.0;
 395   hooke_ =0.0;
 396   active_b_ = true;
 397   block_force_ = 0.0;
 398 }
 399
 400
 401 bool
 402 Spring_description::sane_b () const
 403 {
 404   return (hooke_ > 0) &&  !isinf (ideal_) && !isnan (ideal_);
 405 }
 406
 407 Real
 408 Spring_description::length (Real f) const
 409 {
 410   if (!active_b_)
 411     f = block_force_;
 412   return ideal_ + f / hooke_ ;
 413 }