lily/simple-spacer.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1999--2012 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   6   TODO:
   7   - add support for different stretch/shrink constants?
   8
   9   LilyPond is free software: you can redistribute it and/or modify
  10   it under the terms of the GNU General Public License as published by
  11   the Free Software Foundation, either version 3 of the License, or
  12   (at your option) any later version.
  13
  14   LilyPond is distributed in the hope that it will be useful,
  15   but WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17   GNU General Public License for more details.
  18
  19   You should have received a copy of the GNU General Public License
  20   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  21 */
  22
  23 #include <cstdio>
  24
  25 #include "column-description.hh"
  26 #include "column-x-positions.hh"
  27 #include "dimensions.hh"
  28 #include "international.hh"
  29 #include "libc-extension.hh"    // isinf
  30 #include "paper-column.hh"
  31 #include "simple-spacer.hh"
  32 #include "spaceable-grob.hh"
  33 #include "spring.hh"
  34 #include "warn.hh"
  35
  36 /*
  37   A simple spacing constraint solver. The approach:
  38
  39   Stretch the line uniformly until none of the constraints (rods)
  40   block.  It then is very wide.
  41
  42   Compress until the next constraint blocks,
  43
  44   Mark the springs over the constrained part to be non-active.
  45
  46   Repeat with the smaller set of non-active constraints, until all
  47   constraints blocked, or until the line is as short as desired.
  48
  49   This is much simpler, and much much faster than full scale
  50   Constrained QP. On the other hand, a situation like this will not
  51   be typeset as dense as possible, because
  52
  53   c4                   c4           c4                  c4
  54   veryveryverylongsyllable2         veryveryverylongsyllable2
  55   " "4                 veryveryverylongsyllable2        syllable4
  56
  57
  58   can be further compressed to
  59
  60
  61   c4    c4                        c4   c4
  62   veryveryverylongsyllable2       veryveryverylongsyllable2
  63   " "4  veryveryverylongsyllable2      syllable4
  64
  65
  66   Perhaps this is not a bad thing, because the 1st looks better anyway.  */
  67
  68 /*
  69   positive force = expanding, negative force = compressing.
  70 */
  71
  72 Simple_spacer::Simple_spacer ()
  73 {
  74   line_len_ = 0.0;
  75   force_ = 0.0;
  76   fits_ = true;
  77   ragged_ = true;
  78 }
  79
  80 Real
  81 Simple_spacer::force () const
  82 {
  83   return force_;
  84 }
  85
  86 Real
  87 Simple_spacer::line_len () const
  88 {
  89   return line_len_;
  90 }
  91
  92 bool
  93 Simple_spacer::fits () const
  94 {
  95   return fits_;
  96 }
  97
  98 Real
  99 Simple_spacer::rod_force (int l, int r, Real dist)
 100 {
 101   Real d = range_ideal_len (l, r);
 102   Real c = range_stiffness (l, r, dist > d);
 103   Real block_stretch = dist - d;
 104
 105   if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */
 106     return 0;
 107   return c * block_stretch;
 108 }
 109
 110 void
 111 Simple_spacer::add_rod (int l, int r, Real dist)
 112 {
 113   if (isinf (dist) || isnan (dist))
 114     {
 115       programming_error ("ignoring weird minimum distance");
 116       return;
 117     }
 118
 119   Real block_force = rod_force (l, r, dist);
 120
 121   if (isinf (block_force))
 122     {
 123       Real spring_dist = range_ideal_len (l, r);
 124       if (spring_dist < dist)
 125         for (int i = l; i < r; i++)
 126           {
 127             if (spring_dist)
 128               springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
 129             else
 130               springs_[i].set_distance (dist / (r - l));
 131           }
 132
 133       return;
 134     }
 135   force_ = max (force_, block_force);
 136   for (int i = l; i < r; i++)
 137     springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ()));
 138 }
 139
 140 Real
 141 Simple_spacer::range_ideal_len (int l, int r) const
 142 {
 143   Real d = 0.;
 144   for (int i = l; i < r; i++)
 145     d += springs_[i].distance ();
 146   return d;
 147 }
 148
 149 Real
 150 Simple_spacer::range_stiffness (int l, int r, bool stretch) const
 151 {
 152   Real den = 0.0;
 153   for (int i = l; i < r; i++)
 154     den += stretch ? springs_[i].inverse_stretch_strength ()
 155            : springs_[i].inverse_compress_strength ();
 156
 157   return 1 / den;
 158 }
 159
 160 Real
 161 Simple_spacer::configuration_length (Real force) const
 162 {
 163   Real l = 0.;
 164   for (vsize i = 0; i < springs_.size (); i++)
 165     l += springs_[i].length (force);
 166
 167   return l;
 168 }
 169
 170 void
 171 Simple_spacer::set_force (Real force)
 172 {
 173   force_ = force;
 174 }
 175
 176 void
 177 Simple_spacer::solve (Real line_len, bool ragged)
 178 {
 179   Real conf = configuration_length (force_);
 180
 181   ragged_ = ragged;
 182   line_len_ = line_len;
 183   if (conf < line_len_)
 184     force_ = expand_line ();
 185   else if (conf > line_len_)
 186     force_ = compress_line ();
 187
 188   if (ragged && force_ < 0)
 189     fits_ = false;
 190 }
 191
 192 Real
 193 Simple_spacer::expand_line ()
 194 {
 195   double inv_hooke = 0;
 196   double cur_len = configuration_length (force_);
 197
 198   fits_ = true;
 199   for (vsize i = 0; i < springs_.size (); i++)
 200     inv_hooke += springs_[i].inverse_stretch_strength ();
 201
 202   if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
 203     return 0.0;         /* anyway, then it makes no difference what the force is */
 204
 205   assert (cur_len <= line_len_);
 206   return (line_len_ - cur_len) / inv_hooke + force_;
 207 }
 208
 209 Real
 210 Simple_spacer::compress_line ()
 211 {
 212   double cur_len = configuration_length (force_);
 213   double cur_force = force_;
 214   bool compressed = false;
 215
 216   /* just because we are in compress_line () doesn't mean that the line
 217      will actually be compressed (as in, a negative force) because
 218      we start out with a stretched line. Here, we check whether we
 219      will be compressed or stretched (so we know which spring constant to use) */
 220   if (configuration_length (0.0) > line_len_)
 221     {
 222       cur_force = 0.0;
 223       cur_len = configuration_length (0.0);
 224       compressed = true;
 225     }
 226
 227   fits_ = true;
 228
 229   assert (line_len_ <= cur_len);
 230
 231   vector<Spring> sorted_springs = springs_;
 232   sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
 233
 234   /* inv_hooke is the total flexibility of currently-active springs */
 235   double inv_hooke = 0;
 236   vsize i = sorted_springs.size ();
 237   for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
 238     inv_hooke += compressed
 239                  ? sorted_springs[i - 1].inverse_compress_strength ()
 240                  : sorted_springs[i - 1].inverse_stretch_strength ();
 241   /* i now indexes the first active spring, so */
 242   for (; i < sorted_springs.size (); i++)
 243     {
 244       Spring sp = sorted_springs[i];
 245
 246       if (isinf (sp.blocking_force ()))
 247         break;
 248
 249       double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
 250       if (cur_len - block_dist < line_len_)
 251         {
 252           cur_force += (line_len_ - cur_len) / inv_hooke;
 253           cur_len = line_len_;
 254
 255           /*
 256             Paranoia check.
 257           */
 258           assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
 259           return cur_force;
 260         }
 261
 262       cur_len -= block_dist;
 263       inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
 264       cur_force = sp.blocking_force ();
 265     }
 266
 267   fits_ = false;
 268   return cur_force;
 269 }
 270
 271 void
 272 Simple_spacer::add_spring (Spring const &sp)
 273 {
 274   force_ = max (force_, sp.blocking_force ());
 275   springs_.push_back (sp);
 276 }
 277
 278 vector<Real>
 279 Simple_spacer::spring_positions () const
 280 {
 281   vector<Real> ret;
 282   ret.push_back (0.);
 283
 284   for (vsize i = 0; i < springs_.size (); i++)
 285     ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
 286   return ret;
 287 }
 288
 289 Real
 290 Simple_spacer::force_penalty (bool ragged) const
 291 {
 292   /* If we are ragged-right, we don't want to penalise according to the force,
 293      but according to the amount of whitespace that is present after the end
 294      of the line. */
 295   if (ragged)
 296     return max (0.0, line_len_ - configuration_length (0.0));
 297
 298   /* Use a convex compression penalty. */
 299   Real f = force_;
 300   return f - (f < 0 ? f * f * f * f * 2 : 0);
 301 }
 302
 303 /****************************************************************/
 304
 305 Column_x_positions
 306 get_line_configuration (vector<Grob *> const &columns,
 307                         Real line_len,
 308                         Real indent,
 309                         bool ragged)
 310 {
 311   vector<Column_description> cols;
 312   Simple_spacer spacer;
 313   Column_x_positions ret;
 314
 315   ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
 316   for (vsize i = 1; i + 1 < columns.size (); i++)
 317     {
 318       if (Paper_column::is_loose (columns[i]))
 319         ret.loose_cols_.push_back (columns[i]);
 320       else
 321         ret.cols_.push_back (columns[i]);
 322     }
 323   ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
 324
 325   /* since we've already put our line-ending column in the column list, we can ignore
 326      the end_XXX_ fields of our column_description */
 327   for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
 328     {
 329       cols.push_back (Column_description::get_column_description (ret.cols_, i, i == 0));
 330       spacer.add_spring (cols[i].spring_);
 331     }
 332   for (vsize i = 0; i < cols.size (); i++)
 333     {
 334       for (vsize r = 0; r < cols[i].rods_.size (); r++)
 335         spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
 336
 337       if (!cols[i].keep_inside_line_.is_empty ())
 338         {
 339           spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
 340           spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
 341         }
 342     }
 343
 344   spacer.solve (line_len, ragged);
 345   ret.force_ = spacer.force_penalty (ragged);
 346
 347   ret.config_ = spacer.spring_positions ();
 348   for (vsize i = 0; i < ret.config_.size (); i++)
 349     ret.config_[i] += indent;
 350
 351   ret.satisfies_constraints_ = spacer.fits ();
 352
 353   /*
 354     Check if breaking constraints are met.
 355   */
 356   for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
 357     {
 358       SCM p = ret.cols_[i]->get_property ("line-break-permission");
 359       if (p == ly_symbol2scm ("force"))
 360         ret.satisfies_constraints_ = false;
 361     }
 362
 363   return ret;
 364 }
 365
 366 #include "ly-smobs.icc"
 367
 368 IMPLEMENT_SIMPLE_SMOBS (Simple_spacer);
 369 IMPLEMENT_DEFAULT_EQUAL_P (Simple_spacer);
 370
 371 SCM
 372 Simple_spacer::mark_smob (SCM /* x */)
 373 {
 374   return SCM_EOL;
 375 }
 376
 377 int
 378 Simple_spacer::print_smob (SCM /* x */, SCM p, scm_print_state *)
 379 {
 380   scm_puts ("#<Simple spacer>", p);
 381   return 1;
 382 }
 383