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
 279   for (int i=0; i < cols.size () - 1; i++)
 280     {
 281       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 282            ly_c_pair_p (s); s = ly_cdr (s))
 283         {
 284           Grob * other = unsmob_grob (ly_caar (s));
 285           int oi = cols.find_index (other);
 286           if (oi >= 0)
 287             {
 288               add_rod (i, oi, ly_scm2double (ly_cdar (s)));
 289             }
 290         }
 291     }
 292 }
 293
 294 /*
 295
 296   TODO: should a add penalty for widely varying spring forces (caused
 297   by constraints, eg.
 298
 299
 300          =====
 301          |   |
 302   o|o|  x ##x
 303
 304
 305   The ## forces the notes apart; we shouldn't allow the O's to touch
 306   this closely.
 307
 308  */
 309 void
 310 Simple_spacer::solve (Column_x_positions *positions, bool ragged)
 311 {
 312   if (ragged)
 313     my_solve_natural_len ();
 314   else
 315     my_solve_linelen ();
 316
 317   positions->force_ = force_;
 318
 319   /*
 320     We used to have a penalty for compression, no matter what, but that
 321     fucked up wtk1-fugue2 (taking 3 full pages.)
 322   */
 323   positions->config_.push (indent_);
 324   for (int i=0; i <springs_.size (); i++)
 325     {
 326       Real  l = springs_[i].length ((ragged) ? 0.0 : force_);
 327       positions->config_.push (positions->config_.top () + l);
 328       /*
 329         we have l>= 0 here, up to rounding errors
 330       */
 331     }
 332
 333   /*
 334     For raggedright, we must have a measure of music density: this is
 335     to prevent lots of short lines (which all have force = 0).
 336     */
 337   if (ragged)
 338     {
 339       Real len = positions->config_.top ();
 340       if (line_len_ - len  >= 0)
 341         positions->force_ = ((line_len_ - len) *  active_springs_stiffness ());
 342       else
 343         {
 344           positions->force_ = 0.0;
 345           /*
 346             Don't go past end-of-line in ragged right.
 347            */
 348           positions->satisfies_constraints_ = false;
 349         }
 350     }
 351
 352
 353   positions->cols_ = spaced_cols_;
 354   positions->loose_cols_ = loose_cols_;
 355   positions->satisfies_constraints_ =
 356     positions->satisfies_constraints_ && is_active ();
 357
 358   /*
 359     Check if breaking constraints are met.
 360    */
 361   bool break_satisfy = true;
 362   int sz =  positions->cols_.size ();
 363   for (int i = sz; i--; )
 364     {
 365       SCM p = positions->cols_[i]->get_property ( "penalty");
 366       if (ly_c_number_p (p))
 367         {
 368           if (ly_scm2double (p) < -9999)
 369             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 370           if (ly_scm2double (p) > 9999)
 371             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 372         }
 373
 374     }
 375
 376   positions->satisfies_constraints_ =
 377     positions->satisfies_constraints_ && break_satisfy;
 378 }
 379
 380 /****************************************************************/
 381
 382 Spring_description::Spring_description ()
 383 {
 384   ideal_ =0.0;
 385   hooke_ =0.0;
 386   is_active_ = true;
 387   block_force_ = 0.0;
 388 }
 389
 390
 391 bool
 392 Spring_description::is_sane () const
 393 {
 394   return (hooke_ > 0) &&  !isinf (ideal_) && !isnan (ideal_);
 395 }
 396
 397 Real
 398 Spring_description::length (Real f) const
 399 {
 400   if (!is_active_)
 401     f = block_force_;
 402   return ideal_ + f / hooke_ ;
 403 }