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> cols)
 220 {
 221   for (int i =  cols.size (); i--;)
 222     if (gh_pair_p (cols[i]->get_grob_property ("between-cols")))
 223       {
 224         loose_cols_.push (cols[i]);
 225         cols.del (i);
 226       }
 227
 228   spaced_cols_ = cols;
 229   for (int i=0; i < cols.size () - 1; i++)
 230     {
 231       Spring_smob *spring = 0;
 232
 233       for (SCM s = cols[i]->get_grob_property ("ideal-distances");
 234            !spring && gh_pair_p (s);
 235            s = ly_cdr (s))
 236         {
 237           Spring_smob *sp = unsmob_spring (ly_car (s));
 238
 239
 240           if (sp->other_ == cols[i+1])
 241             spring = sp;
 242         }
 243
 244       Spring_description desc;
 245       if (spring)
 246         {
 247           desc.ideal_f_ = spring->distance_f_;
 248           desc.hooke_f_ = spring->strength_f_;
 249         }
 250       else
 251         {
 252           programming_error (_f("No spring between column %d and next one",
 253                                 Paper_column::rank_i (cols[i])
 254                                 ));
 255           desc.hooke_f_ = 1.0;
 256           desc.ideal_f_ = default_space_f_;
 257
 258           continue;
 259         }
 260
 261       if (!desc.sane_b ())
 262         {
 263           programming_error ("Insane spring found. Setting to unit spring.");
 264
 265           cout << "columns " << Paper_column::rank_i (cols[i])
 266                << " " << Paper_column::rank_i (cols[i+1]) << endl;
 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) const
 318 {
 319   positions->force_f_ = force_f_;
 320   if (compression_penalty_b_ &&  (force_f_ < 0))
 321     {
 322
 323         positions->force_f_ *= 2; //  hmm.
 324     }
 325
 326   positions->config_.push (indent_f_);
 327   for (int i=0; i <springs_.size (); i++)
 328     {
 329       positions->config_.push (positions->config_.top () + springs_[i].length (force_f_));
 330     }
 331   positions->cols_ = spaced_cols_;
 332   positions->loose_cols_ = loose_cols_;
 333
 334   positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b ();
 335
 336
 337   /*
 338     Check if breaking constraints are met.
 339    */
 340   bool break_satisfy = true;
 341   int sz =  positions->cols_.size ();
 342   for (int i = sz; i--; )
 343     {
 344       SCM p = positions->cols_[i]->get_grob_property( "penalty");
 345       if (gh_number_p (p))
 346         {
 347           if (gh_scm2double (p) < -9999)
 348             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 349           if (gh_scm2double (p) > 9999)
 350             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 351         }
 352
 353     }
 354
 355   positions->satisfies_constraints_b_ =
 356     positions->satisfies_constraints_b_ && break_satisfy;
 357 }
 358
 359 /****************************************************************/
 360
 361 Spring_description::Spring_description ()
 362 {
 363   ideal_f_ =0.0;
 364   hooke_f_ =0.0;
 365   active_b_ = true;
 366   block_force_f_ = 0.0;
 367 }
 368
 369
 370 bool
 371 Spring_description::sane_b () const
 372 {
 373   return (hooke_f_ > 0) &&  !isinf (ideal_f_) && !isnan (ideal_f_);
 374 }
 375
 376 Real
 377 Spring_description::length (Real f) const
 378 {
 379   if (!active_b_)
 380     f = block_force_f_;
 381   return ideal_f_ + f / hooke_f_ ;
 382 }