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].active_b_)
 126         den += 1 / springs_[i].hooke_;
 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_;
 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].active_b_
 156         && springs_[i].block_force_ >= force_)
 157       {
 158         springs_[i].active_b_ = 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::active_b () const
 175 {
 176   return active_count_;
 177 }
 178
 179 void
 180 Simple_spacer::my_solve_linelen ()
 181 {
 182   while (active_b ())
 183     {
 184       force_ = active_blocking_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 (active_b ())
 202     {
 203       force_ = active_blocking_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 (gh_pair_p (cols[i]->get_grob_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_grob_property ("ideal-distances");
 230            !spring && gh_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.sane_b ())
 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.active_b_ = 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            gh_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, gh_scm2double (ly_cdar (s)));
 295             }
 296         }
 297     }
 298
 299
 300 }
 301
 302 /*
 303
 304   TODO: should a add penalty for widely varying spring forces (caused
 305   by constraints, eg.
 306
 307
 308          =====
 309          |   |
 310   o|o|  x ##x
 311
 312
 313   The ## forces the notes apart; we shouldn't allow the O's to touch
 314   this closely.
 315
 316  */
 317 void
 318 Simple_spacer::solve (Column_x_positions *positions, bool ragged)
 319 {
 320   /*
 321     TODO: should support natural length on only the last line.
 322    */
 323   ragged = ragged || (line_len_ < 0) ;
 324   if (ragged)
 325     my_solve_natural_len ();
 326   else
 327     my_solve_linelen ();
 328
 329   positions->force_ = force_;
 330   /*
 331     We used to have a penalty for compression, no matter what, but that
 332     fucked up wtk1-fugue2 (taking 3 full pages.)
 333   */
 334
 335   positions->config_.push (indent_);
 336   for (int i=0; i <springs_.size (); i++)
 337     {
 338       Real  l = springs_[i].length ((ragged) ? 0.0 : force_);
 339       positions->config_.push (positions->config_.top () + l);
 340       /*
 341         we have l>= 0 here, up to rounding errors
 342       */
 343     }
 344
 345   /*
 346     For raggedright, we must have a measure of music density: this is
 347     to prevent lots of short lines (which all have force = 0).
 348     */
 349   if (ragged && line_len_ > 0)
 350     {
 351       Real len = positions->config_.top ();
 352       positions->force_ = (line_len_ - len) *  active_springs_stiffness ();
 353     }
 354
 355
 356   positions->cols_ = spaced_cols_;
 357   positions->loose_cols_ = loose_cols_;
 358   positions->satisfies_constraints_b_ = (line_len_ < 0) || active_b ();
 359
 360   /*
 361     Check if breaking constraints are met.
 362    */
 363   bool break_satisfy = true;
 364   int sz =  positions->cols_.size ();
 365   for (int i = sz; i--; )
 366     {
 367       SCM p = positions->cols_[i]->get_grob_property( "penalty");
 368       if (gh_number_p (p))
 369         {
 370           if (gh_scm2double (p) < -9999)
 371             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 372           if (gh_scm2double (p) > 9999)
 373             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 374         }
 375
 376     }
 377
 378   positions->satisfies_constraints_b_ =
 379     positions->satisfies_constraints_b_ && break_satisfy;
 380
 381   if (ragged && force_ < 0)
 382     positions->satisfies_constraints_b_ = false;
 383 }
 384
 385 /****************************************************************/
 386
 387 Spring_description::Spring_description ()
 388 {
 389   ideal_ =0.0;
 390   hooke_ =0.0;
 391   active_b_ = true;
 392   block_force_ = 0.0;
 393 }
 394
 395
 396 bool
 397 Spring_description::sane_b () const
 398 {
 399   return (hooke_ > 0) &&  !isinf (ideal_) && !isnan (ideal_);
 400 }
 401
 402 Real
 403 Spring_description::length (Real f) const
 404 {
 405   if (!active_b_)
 406     f = block_force_;
 407   return ideal_ + f / hooke_ ;
 408 }