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--2004 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].is_active_)
 126         den += 1 / springs_[i].hooke_;
 127     }
 128
 129   return 1 / den;
 130 }
 131
 132 Real
 133 Simple_spacer::is_activelocking_force () const
 134 {
 135   Real bf = - infinity_f;
 136   for (int i=0; i < springs_.size (); i++)
 137     if (springs_[i].is_active_)
 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   return range_stiffness (0, springs_.size ());
 148 }
 149
 150 void
 151 Simple_spacer::set_active_states ()
 152 {
 153   /* float comparison is safe, since force is only copied.  */
 154   for (int i=0 ; i <springs_.size (); i++)
 155     if (springs_[i].is_active_
 156         && springs_[i].block_force_ >= force_)
 157       {
 158         springs_[i].is_active_ = false;
 159         active_count_ --;
 160       }
 161 }
 162
 163 Real
 164 Simple_spacer::configuration_length () const
 165 {
 166   Real l =0.;
 167   for (int i=0; i < springs_.size (); i++)
 168     l += springs_[i].length (force_);
 169
 170   return l;
 171 }
 172
 173 bool
 174 Simple_spacer::is_active () const
 175 {
 176   return active_count_;
 177 }
 178
 179 void
 180 Simple_spacer::my_solve_linelen ()
 181 {
 182   while (is_active ())
 183     {
 184       force_ = is_activelocking_force ();
 185       Real conf = configuration_length ();
 186
 187       if (conf < line_len_)
 188         {
 189           force_ += (line_len_  - conf) * active_springs_stiffness ();
 190           break;
 191         }
 192       else
 193         set_active_states ();
 194     }
 195 }
 196
 197
 198 void
 199 Simple_spacer::my_solve_natural_len ()
 200 {
 201   while (is_active ())
 202     {
 203       force_ = is_activelocking_force () >? 0.0;
 204
 205       if (force_ < 1e-8) // ugh.,
 206         break;
 207
 208       set_active_states ();
 209     }
 210 }
 211
 212 void
 213 Simple_spacer::add_columns (Link_array<Grob> const &icols)
 214 {
 215   Link_array<Grob> cols (icols);
 216
 217   for (int i =  cols.size (); i--;)
 218     if (ly_c_pair_p (cols[i]->get_property ("between-cols")))
 219       {
 220         loose_cols_.push (cols[i]);
 221         cols.del (i);
 222       }
 223
 224   spaced_cols_ = cols;
 225   for (int i=0; i < cols.size () - 1; i++)
 226     {
 227       Spring_smob *spring = 0;
 228
 229       for (SCM s = cols[i]->get_property ("ideal-distances");
 230            !spring && ly_c_pair_p (s);
 231            s = ly_cdr (s))
 232         {
 233           Spring_smob *sp = unsmob_spring (ly_car (s));
 234
 235
 236           if (sp->other_ == cols[i+1])
 237             spring = sp;
 238         }
 239
 240       Spring_description desc;
 241       if (spring)
 242         {
 243           desc.ideal_ = spring->distance_;
 244           desc.hooke_ = spring->strength_;
 245         }
 246       else
 247         {
 248           programming_error (_f ("No spring between column %d and next one",
 249                                 Paper_column::get_rank (cols[i])
 250                                 ));
 251           desc.hooke_ = 1.0;
 252           desc.ideal_ = default_space_;
 253
 254           continue;
 255         }
 256
 257       if (!desc.is_sane ())
 258         {
 259           programming_error ("Insane spring found. Setting to unit spring.");
 260
 261           desc.hooke_ = 1.0;
 262           desc.ideal_ = 1.0;
 263         }
 264
 265       if (isinf (desc.hooke_))
 266         {
 267           desc.is_active_ = false;
 268           springs_.push (desc);
 269         }
 270       else
 271         {
 272           desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
 273           springs_.push (desc);
 274
 275           active_count_ ++;
 276         }
 277
 278       if (spring->expand_only_b_)
 279         {
 280           compression_penalty_b_ = true;
 281         }
 282
 283     }
 284
 285   for (int i=0; i < cols.size () - 1; i++)
 286     {
 287       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 288            ly_c_pair_p (s); s = ly_cdr (s))
 289         {
 290           Grob * other = unsmob_grob (ly_caar (s));
 291           int oi = cols.find_index (other);
 292           if (oi >= 0)
 293             {
 294               add_rod (i, oi, ly_scm2double (ly_cdar (s)));
 295             }
 296         }
 297     }
 298 }
 299
 300 /*
 301
 302   TODO: should a add penalty for widely varying spring forces (caused
 303   by constraints, eg.
 304
 305
 306          =====
 307          |   |
 308   o|o|  x ##x
 309
 310
 311   The ## forces the notes apart; we shouldn't allow the O's to touch
 312   this closely.
 313
 314  */
 315 void
 316 Simple_spacer::solve (Column_x_positions *positions, bool ragged)
 317 {
 318   if (ragged)
 319     my_solve_natural_len ();
 320   else
 321     my_solve_linelen ();
 322
 323   positions->force_ = force_;
 324
 325   /*
 326     We used to have a penalty for compression, no matter what, but that
 327     fucked up wtk1-fugue2 (taking 3 full pages.)
 328   */
 329   positions->config_.push (indent_);
 330   for (int i=0; i <springs_.size (); i++)
 331     {
 332       Real  l = springs_[i].length ((ragged) ? 0.0 : force_);
 333       positions->config_.push (positions->config_.top () + l);
 334       /*
 335         we have l>= 0 here, up to rounding errors
 336       */
 337     }
 338
 339   /*
 340     For raggedright, we must have a measure of music density: this is
 341     to prevent lots of short lines (which all have force = 0).
 342     */
 343   if (ragged)
 344     {
 345       Real len = positions->config_.top ();
 346       if (line_len_ - len  >= 0)
 347         positions->force_ = ((line_len_ - len) *  active_springs_stiffness ());
 348       else
 349         {
 350           positions->force_ = 0.0;
 351           /*
 352             Don't go past end-of-line in ragged right.
 353            */
 354           positions->satisfies_constraints_ = false;
 355         }
 356     }
 357
 358
 359   positions->cols_ = spaced_cols_;
 360   positions->loose_cols_ = loose_cols_;
 361   positions->satisfies_constraints_ =
 362     positions->satisfies_constraints_ && is_active ();
 363
 364   /*
 365     Check if breaking constraints are met.
 366    */
 367   bool break_satisfy = true;
 368   int sz =  positions->cols_.size ();
 369   for (int i = sz; i--; )
 370     {
 371       SCM p = positions->cols_[i]->get_property ( "penalty");
 372       if (ly_c_number_p (p))
 373         {
 374           if (ly_scm2double (p) < -9999)
 375             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 376           if (ly_scm2double (p) > 9999)
 377             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 378         }
 379
 380     }
 381
 382   positions->satisfies_constraints_ =
 383     positions->satisfies_constraints_ && break_satisfy;
 384 }
 385
 386 /****************************************************************/
 387
 388 Spring_description::Spring_description ()
 389 {
 390   ideal_ =0.0;
 391   hooke_ =0.0;
 392   is_active_ = true;
 393   block_force_ = 0.0;
 394 }
 395
 396
 397 bool
 398 Spring_description::is_sane () const
 399 {
 400   return (hooke_ > 0) &&  !isinf (ideal_) && !isnan (ideal_);
 401 }
 402
 403 Real
 404 Spring_description::length (Real f) const
 405 {
 406   if (!is_active_)
 407     f = block_force_;
 408   return ideal_ + f / hooke_ ;
 409 }