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           desc.hooke_f_ = 1.0;
 266           desc.ideal_f_ = 1.0;
 267         }
 268
 269       if (isinf (desc.hooke_f_))
 270         {
 271           desc.active_b_ = false;
 272           springs_.push (desc);
 273         }
 274       else
 275         {
 276           desc.block_force_f_ = - desc.hooke_f_ * desc.ideal_f_; // block at distance 0
 277           springs_.push (desc);
 278
 279           active_count_ ++;
 280         }
 281
 282       if (spring->expand_only_b_)
 283         {
 284           compression_penalty_b_ = true;
 285         }
 286
 287     }
 288
 289   for (int i=0; i < cols.size () - 1; i++)
 290     {
 291       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 292            gh_pair_p (s); s = ly_cdr (s))
 293         {
 294           Grob * other = unsmob_grob (ly_caar (s));
 295           int oi = cols.find_i (other);
 296           if (oi >= 0)
 297             {
 298               add_rod (i, oi, gh_scm2double (ly_cdar (s)));
 299             }
 300         }
 301     }
 302
 303   /*
 304     TODO: should support natural length on only the last line.
 305    */
 306   if (line_len_f_ < 0)
 307     my_solve_natural_len ();
 308   else
 309     my_solve_linelen ();
 310 }
 311
 312 #include <stdio.h>
 313
 314 void
 315 Simple_spacer::solve (Column_x_positions *positions, bool ragged) const
 316 {
 317   positions->force_f_ = force_f_;
 318   if ((force_f_ < 0))
 319     {
 320
 321       /*
 322         We used to have a penalty for compression, no matter what, but that
 323         fucked up wtk1-fugue2 (taking 3 full pages.)
 324
 325         maybe this should be tunable?
 326        */
 327       if (compression_penalty_b_)
 328         ; //    positions->force_f_ *= 2; //  hmm.
 329     }
 330
 331   positions->config_.push (indent_f_);
 332   for (int i=0; i <springs_.size (); i++)
 333     {
 334       if (ragged)
 335         {
 336           // ragged right operation: do not apply any force
 337           positions->config_.push (positions->config_.top () + springs_[i].length (0.0));
 338         }
 339       else
 340         {
 341           positions->config_.push (positions->config_.top () + springs_[i].length (force_f_));
 342         }
 343     }
 344   positions->cols_ = spaced_cols_;
 345   positions->loose_cols_ = loose_cols_;
 346
 347   positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b ();
 348
 349
 350   /*
 351     Check if breaking constraints are met.
 352    */
 353   bool break_satisfy = true;
 354   int sz =  positions->cols_.size ();
 355   for (int i = sz; i--; )
 356     {
 357       SCM p = positions->cols_[i]->get_grob_property( "penalty");
 358       if (gh_number_p (p))
 359         {
 360           if (gh_scm2double (p) < -9999)
 361             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 362           if (gh_scm2double (p) > 9999)
 363             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 364         }
 365
 366     }
 367
 368   positions->satisfies_constraints_b_ =
 369     positions->satisfies_constraints_b_ && break_satisfy;
 370 }
 371
 372 /****************************************************************/
 373
 374 Spring_description::Spring_description ()
 375 {
 376   ideal_f_ =0.0;
 377   hooke_f_ =0.0;
 378   active_b_ = true;
 379   block_force_f_ = 0.0;
 380 }
 381
 382
 383 bool
 384 Spring_description::sane_b () const
 385 {
 386   return (hooke_f_ > 0) &&  !isinf (ideal_f_) && !isnan (ideal_f_);
 387 }
 388
 389 Real
 390 Spring_description::length (Real f) const
 391 {
 392   if (!active_b_)
 393     f = block_force_f_;
 394   return ideal_f_ + f / hooke_f_ ;
 395 }