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
  82   Real c = range_stiffness (l,r);
  83   Real d = range_ideal_len (l,r);
  84   Real block_stretch = dist - d;
  85
  86   Real block_force = c * block_stretch;
  87   force_f_ = force_f_ >? block_force;
  88
  89   for (int i=l; i < r; i++)
  90     springs_[i].block_force_f_ = block_force >?
  91       springs_[i].block_force_f_ ;
  92 }
  93
  94 Real
  95 Simple_spacer::range_ideal_len (int l, int r)   const
  96 {
  97   Real d =0.;
  98   for (int i=l; i < r; i++)
  99     d += springs_[i].ideal_f_;
 100   return d;
 101 }
 102
 103 Real
 104 Simple_spacer::range_stiffness (int l, int r) const
 105 {
 106   Real den =0.0;
 107   for (int i=l; i < r; i++)
 108     {
 109       if (springs_[i].active_b_)
 110         den += 1 / springs_[i].hooke_f_;
 111     }
 112
 113   return 1 / den;
 114 }
 115
 116 Real
 117 Simple_spacer::active_blocking_force () const
 118 {
 119   Real bf = - infinity_f;
 120   for (int i=0; i < springs_.size (); i++)
 121     if (springs_[i].active_b_)
 122       {
 123         bf = bf >? springs_[i].block_force_f_;
 124       }
 125   return bf;
 126 }
 127
 128 Real
 129 Simple_spacer::active_springs_stiffness () const
 130 {
 131   Real den = 0.0;
 132   for (int i=0; i < springs_.size (); i++)
 133     if (springs_[i].active_b_)
 134       {
 135         den += 1 / springs_[i].hooke_f_;
 136       }
 137   return 1/den;
 138 }
 139
 140 void
 141 Simple_spacer::set_active_states ()
 142 {
 143   /* float comparison is safe, since force is only copied.  */
 144   for (int i=0 ; i <springs_.size (); i++)
 145     if (springs_[i].active_b_
 146         && springs_[i].block_force_f_ >= force_f_)
 147       {
 148         springs_[i].active_b_ = false;
 149         active_count_ --;
 150       }
 151 }
 152
 153 Real
 154 Simple_spacer::configuration_length () const
 155 {
 156   Real l =0.;
 157   for (int i=0; i < springs_.size (); i++)
 158     l += springs_[i].length (force_f_);
 159
 160   return l;
 161 }
 162
 163 bool
 164 Simple_spacer::active_b () const
 165 {
 166   return active_count_;
 167 }
 168
 169 void
 170 Simple_spacer::my_solve_linelen ()
 171 {
 172   while (active_b ())
 173     {
 174       force_f_ = active_blocking_force ();
 175       Real conf = configuration_length ();
 176
 177       if (conf < line_len_f_)
 178         {
 179           force_f_ += (line_len_f_  - conf) * active_springs_stiffness ();
 180           break;
 181         }
 182       else
 183         set_active_states ();
 184     }
 185 }
 186
 187
 188 void
 189 Simple_spacer::my_solve_natural_len ()
 190 {
 191   while (active_b ())
 192     {
 193       force_f_ = active_blocking_force () >? 0.0;
 194
 195       if (force_f_ < 1e-8) // ugh.,
 196         break;
 197
 198       set_active_states ();
 199     }
 200 }
 201
 202 void
 203 Simple_spacer::add_columns (Link_array<Grob> cols)
 204 {
 205   for (int i =  cols.size (); i--;)
 206     if (gh_pair_p (cols[i]->get_grob_property ("between-cols")))
 207       {
 208         loose_cols_.push (cols[i]);
 209         cols.del (i);
 210       }
 211
 212   spaced_cols_ = cols;
 213   for (int i=0; i < cols.size () - 1; i++)
 214     {
 215       Spring_smob *spring = 0;
 216
 217       for (SCM s = cols[i]->get_grob_property ("ideal-distances");
 218            !spring && gh_pair_p (s);
 219            s = ly_cdr (s))
 220         {
 221           Spring_smob *sp = unsmob_spring (ly_car (s));
 222
 223
 224           if (sp->other_ == cols[i+1])
 225             spring = sp;
 226         }
 227
 228       Spring_description desc;
 229       if (spring)
 230         {
 231           desc.ideal_f_ = spring->distance_f_;
 232           desc.hooke_f_ = spring->strength_f_;
 233         }
 234       else
 235         {
 236           programming_error (_f("No spring between column %d and next one",
 237                                 Paper_column::rank_i (cols[i])
 238                                 ));
 239           desc.hooke_f_ = 1.0;
 240           desc.ideal_f_ = default_space_f_;
 241
 242           continue;
 243         }
 244
 245       if (!desc.sane_b ())
 246         {
 247           programming_error ("Insane spring found. Setting to unit spring.");
 248
 249           cout << "columns " << Paper_column::rank_i (cols[i])
 250                << " " << Paper_column::rank_i (cols[i+1]) << endl;
 251           desc.hooke_f_ = 1.0;
 252           desc.ideal_f_ = 1.0;
 253         }
 254
 255       if (isinf (desc.hooke_f_))
 256         {
 257           desc.active_b_ = false;
 258           springs_.push (desc);
 259         }
 260       else
 261         {
 262           desc.block_force_f_ = - desc.hooke_f_ * desc.ideal_f_; // block at distance 0
 263           springs_.push (desc);
 264
 265           active_count_ ++;
 266         }
 267
 268       if (spring->expand_only_b_)
 269         {
 270           compression_penalty_b_ = true;
 271         }
 272
 273     }
 274
 275   for (int i=0; i < cols.size () - 1; i++)
 276     {
 277       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 278            gh_pair_p (s); s = ly_cdr (s))
 279         {
 280           Grob * other = unsmob_grob (ly_caar (s));
 281           int oi = cols.find_i (other);
 282           if (oi >= 0)
 283             {
 284               add_rod (i, oi, gh_scm2double (ly_cdar (s)));
 285             }
 286         }
 287     }
 288
 289   /*
 290     TODO: should support natural length on only the last line.
 291    */
 292   if (line_len_f_ < 0)
 293     my_solve_natural_len ();
 294   else
 295     my_solve_linelen ();
 296 }
 297
 298 #include <stdio.h>
 299
 300 void
 301 Simple_spacer::solve (Column_x_positions *positions) const
 302 {
 303   positions->force_f_ = force_f_;
 304   if (compression_penalty_b_ &&  (force_f_ < 0))
 305     {
 306
 307         positions->force_f_ *= 2; //  hmm.
 308     }
 309
 310   positions->config_.push (indent_f_);
 311   for (int i=0; i <springs_.size (); i++)
 312     {
 313       positions->config_.push (positions->config_.top () + springs_[i].length (force_f_));
 314     }
 315   positions->cols_ = spaced_cols_;
 316   positions->loose_cols_ = loose_cols_;
 317
 318   positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b ();
 319
 320
 321   /*
 322     Check if breaking constraints are met.
 323    */
 324   bool break_satisfy = true;
 325   int sz =  positions->cols_.size ();
 326   for (int i = sz; i--; )
 327     {
 328       SCM p = positions->cols_[i]->get_grob_property( "penalty");
 329       if (gh_number_p (p))
 330         {
 331           if (gh_scm2double (p) < -9999)
 332             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 333           if (gh_scm2double (p) > 9999)
 334             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 335         }
 336
 337     }
 338
 339   positions->satisfies_constraints_b_ =
 340     positions->satisfies_constraints_b_ && break_satisfy;
 341 }
 342
 343 /****************************************************************/
 344
 345 Spring_description::Spring_description ()
 346 {
 347   ideal_f_ =0.0;
 348   hooke_f_ =0.0;
 349   active_b_ = true;
 350   block_force_f_ = 0.0;
 351 }
 352
 353
 354 bool
 355 Spring_description::sane_b () const
 356 {
 357   return (hooke_f_ > 0) &&  !isinf (ideal_f_) && !isnan (ideal_f_);
 358 }
 359
 360 Real
 361 Spring_description::length (Real f) const
 362 {
 363   if (!active_b_)
 364     f = block_force_f_;
 365   return ideal_f_ + f / hooke_f_ ;
 366 }