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--2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7
   8   TODO:
   9   - add support for different stretch/shrink constants?
  10
  11 */
  12
  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_f_ = 0.;
  68   indent_f_ =0.0;
  69   default_space_f_ = 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_f_;
  91
  92       if (total_dist < dist)
  93         for (int i = l ; i < r; i++)
  94           springs_[i].ideal_f_ *= 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_f_ = force_f_ >? block_force;
 104
 105   for (int i=l; i < r; i++)
 106     springs_[i].block_force_f_ = block_force >?
 107       springs_[i].block_force_f_ ;
 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_f_;
 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_f_;
 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_f_;
 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_f_;
 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_f_ >= force_f_)
 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_f_);
 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_f_ = active_blocking_force ();
 191       Real conf = configuration_length ();
 192
 193       if (conf < line_len_f_)
 194         {
 195           force_f_ += (line_len_f_  - 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_f_ = active_blocking_force () >? 0.0;
 210
 211       if (force_f_ < 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_f_ = spring->distance_f_;
 250           desc.hooke_f_ = spring->strength_f_;
 251         }
 252       else
 253         {
 254           programming_error (_f("No spring between column %d and next one",
 255                                 Paper_column::rank_i (cols[i])
 256                                 ));
 257           desc.hooke_f_ = 1.0;
 258           desc.ideal_f_ = default_space_f_;
 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_f_ = 1.0;
 268           desc.ideal_f_ = 1.0;
 269         }
 270
 271       if (isinf (desc.hooke_f_))
 272         {
 273           desc.active_b_ = false;
 274           springs_.push (desc);
 275         }
 276       else
 277         {
 278           desc.block_force_f_ = - desc.hooke_f_ * desc.ideal_f_; // 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_i (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_f_ < 0)
 309     my_solve_natural_len ();
 310   else
 311     my_solve_linelen ();
 312 }
 313
 314 #include <stdio.h>
 315
 316 void
 317 Simple_spacer::solve (Column_x_positions *positions, bool ragged) const
 318 {
 319   positions->force_f_ = force_f_;
 320   if ((force_f_ < 0))
 321     {
 322
 323       /*
 324         We used to have a penalty for compression, no matter what, but that
 325         fucked up wtk1-fugue2 (taking 3 full pages.)
 326
 327         maybe this should be tunable?
 328        */
 329       if (compression_penalty_b_)
 330         ; //    positions->force_f_ *= 2; //  hmm.
 331     }
 332
 333   positions->config_.push (indent_f_);
 334   for (int i=0; i <springs_.size (); i++)
 335     {
 336       if (ragged)
 337         {
 338           // ragged right operation: do not apply any force
 339           positions->config_.push (positions->config_.top () + springs_[i].length (0.0));
 340         }
 341       else
 342         {
 343           positions->config_.push (positions->config_.top () + springs_[i].length (force_f_));
 344         }
 345     }
 346   positions->cols_ = spaced_cols_;
 347   positions->loose_cols_ = loose_cols_;
 348
 349   positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b ();
 350
 351
 352   /*
 353     Check if breaking constraints are met.
 354    */
 355   bool break_satisfy = true;
 356   int sz =  positions->cols_.size ();
 357   for (int i = sz; i--; )
 358     {
 359       SCM p = positions->cols_[i]->get_grob_property( "penalty");
 360       if (gh_number_p (p))
 361         {
 362           if (gh_scm2double (p) < -9999)
 363             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 364           if (gh_scm2double (p) > 9999)
 365             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 366         }
 367
 368     }
 369
 370   positions->satisfies_constraints_b_ =
 371     positions->satisfies_constraints_b_ && break_satisfy;
 372 }
 373
 374 /****************************************************************/
 375
 376 Spring_description::Spring_description ()
 377 {
 378   ideal_f_ =0.0;
 379   hooke_f_ =0.0;
 380   active_b_ = true;
 381   block_force_f_ = 0.0;
 382 }
 383
 384
 385 bool
 386 Spring_description::sane_b () const
 387 {
 388   return (hooke_f_ > 0) &&  !isinf (ideal_f_) && !isnan (ideal_f_);
 389 }
 390
 391 Real
 392 Spring_description::length (Real f) const
 393 {
 394   if (!active_b_)
 395     f = block_force_f_;
 396   return ideal_f_ + f / hooke_f_ ;
 397 }