lily/simple-spacer.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1999--2011 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::solve (Real line_len, bool ragged)
 172 {
 173   Real conf = configuration_length (force_);
 174
 175   ragged_ = ragged;
 176   line_len_ = line_len;
 177   if (conf < line_len_)
 178     force_ = expand_line ();
 179   else if (conf > line_len_)
 180     force_ = compress_line ();
 181
 182   if (ragged && force_ < 0)
 183     fits_ = false;
 184 }
 185
 186 Real
 187 Simple_spacer::expand_line ()
 188 {
 189   double inv_hooke = 0;
 190   double cur_len = configuration_length (force_);
 191
 192   fits_ = true;
 193   for (vsize i = 0; i < springs_.size (); i++)
 194     inv_hooke += springs_[i].inverse_stretch_strength ();
 195
 196   if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
 197     return 0.0;         /* anyway, then it makes no difference what the force is */
 198
 199   assert (cur_len <= line_len_);
 200   return (line_len_ - cur_len) / inv_hooke + force_;
 201 }
 202
 203 Real
 204 Simple_spacer::compress_line ()
 205 {
 206   double cur_len = configuration_length (force_);
 207   double cur_force = force_;
 208   bool compressed = false;
 209
 210   /* just because we are in compress_line () doesn't mean that the line
 211      will actually be compressed (as in, a negative force) because
 212      we start out with a stretched line. Here, we check whether we
 213      will be compressed or stretched (so we know which spring constant to use) */
 214   if (configuration_length (0.0) > line_len_)
 215     {
 216       cur_force = 0.0;
 217       cur_len = configuration_length (0.0);
 218       compressed = true;
 219     }
 220
 221   fits_ = true;
 222
 223   assert (line_len_ <= cur_len);
 224
 225   vector<Spring> sorted_springs = springs_;
 226   sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
 227
 228   /* inv_hooke is the total flexibility of currently-active springs */
 229   double inv_hooke = 0;
 230   vsize i = sorted_springs.size ();
 231   for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
 232     inv_hooke += compressed
 233                  ? sorted_springs[i - 1].inverse_compress_strength ()
 234                  : sorted_springs[i - 1].inverse_stretch_strength ();
 235   /* i now indexes the first active spring, so */
 236   for (; i < sorted_springs.size (); i++)
 237     {
 238       Spring sp = sorted_springs[i];
 239
 240       if (isinf (sp.blocking_force ()))
 241         break;
 242
 243       double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
 244       if (cur_len - block_dist < line_len_)
 245         {
 246           cur_force += (line_len_ - cur_len) / inv_hooke;
 247           cur_len = line_len_;
 248
 249           /*
 250             Paranoia check.
 251           */
 252           assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
 253           return cur_force;
 254         }
 255
 256       cur_len -= block_dist;
 257       inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
 258       cur_force = sp.blocking_force ();
 259     }
 260
 261   fits_ = false;
 262   return cur_force;
 263 }
 264
 265 void
 266 Simple_spacer::add_spring (Spring const &sp)
 267 {
 268   force_ = max (force_, sp.blocking_force ());
 269   springs_.push_back (sp);
 270 }
 271
 272 vector<Real>
 273 Simple_spacer::spring_positions () const
 274 {
 275   vector<Real> ret;
 276   ret.push_back (0.);
 277
 278   for (vsize i = 0; i < springs_.size (); i++)
 279     ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
 280   return ret;
 281 }
 282
 283 Real
 284 Simple_spacer::force_penalty (bool ragged) const
 285 {
 286   /* If we are ragged-right, we don't want to penalise according to the force,
 287      but according to the amount of whitespace that is present after the end
 288      of the line. */
 289   if (ragged)
 290     return max (0.0, line_len_ - configuration_length (0.0));
 291
 292   /* Use a convex compression penalty. */
 293   Real f = force_;
 294   return f - (f < 0 ? f * f * f * f * 2 : 0);
 295 }
 296
 297 /****************************************************************/
 298
 299 Column_x_positions
 300 get_line_configuration (vector<Grob *> const &columns,
 301                         Real line_len,
 302                         Real indent,
 303                         bool ragged)
 304 {
 305   vector<Column_description> cols;
 306   Simple_spacer spacer;
 307   Column_x_positions ret;
 308
 309   ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
 310   for (vsize i = 1; i + 1 < columns.size (); i++)
 311     {
 312       if (Paper_column::is_loose (columns[i]))
 313         ret.loose_cols_.push_back (columns[i]);
 314       else
 315         ret.cols_.push_back (columns[i]);
 316     }
 317   ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
 318
 319   /* since we've already put our line-ending column in the column list, we can ignore
 320      the end_XXX_ fields of our column_description */
 321   for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
 322     {
 323       cols.push_back (Column_description::get_column_description (ret.cols_, i, i == 0));
 324       spacer.add_spring (cols[i].spring_);
 325     }
 326   for (vsize i = 0; i < cols.size (); i++)
 327     {
 328       for (vsize r = 0; r < cols[i].rods_.size (); r++)
 329         spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
 330
 331       if (!cols[i].keep_inside_line_.is_empty ())
 332         {
 333           spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
 334           spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
 335         }
 336     }
 337
 338   spacer.solve (line_len, ragged);
 339   ret.force_ = spacer.force_penalty (ragged);
 340
 341   ret.config_ = spacer.spring_positions ();
 342   for (vsize i = 0; i < ret.config_.size (); i++)
 343     ret.config_[i] += indent;
 344
 345   ret.satisfies_constraints_ = spacer.fits ();
 346
 347   /*
 348     Check if breaking constraints are met.
 349   */
 350   for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
 351     {
 352       SCM p = ret.cols_[i]->get_property ("line-break-permission");
 353       if (p == ly_symbol2scm ("force"))
 354         ret.satisfies_constraints_ = false;
 355     }
 356
 357   return ret;
 358 }
 359
 360 #include "ly-smobs.icc"
 361
 362 IMPLEMENT_SIMPLE_SMOBS (Simple_spacer);
 363 IMPLEMENT_DEFAULT_EQUAL_P (Simple_spacer);
 364
 365 SCM
 366 Simple_spacer::mark_smob (SCM /* x */)
 367 {
 368   return SCM_EOL;
 369 }
 370
 371 int
 372 Simple_spacer::print_smob (SCM /* x */, SCM p, scm_print_state *)
 373 {
 374   scm_puts ("#<Simple spacer>", p);
 375   return 1;
 376 }
 377