2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1999--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
7 - add support for different stretch/shrink constants?
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.
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.
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/>.
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"
37 A simple spacing constraint solver. The approach:
39 Stretch the line uniformly until none of the constraints (rods)
40 block. It then is very wide.
42 Compress until the next constraint blocks,
44 Mark the springs over the constrained part to be non-active.
46 Repeat with the smaller set of non-active constraints, until all
47 constraints blocked, or until the line is as short as desired.
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
54 veryveryverylongsyllable2 veryveryverylongsyllable2
55 " "4 veryveryverylongsyllable2 syllable4
58 can be further compressed to
62 veryveryverylongsyllable2 veryveryverylongsyllable2
63 " "4 veryveryverylongsyllable2 syllable4
66 Perhaps this is not a bad thing, because the 1st looks better anyway. */
69 positive force = expanding, negative force = compressing.
72 Simple_spacer::Simple_spacer ()
81 Simple_spacer::force () const
87 Simple_spacer::line_len () const
93 Simple_spacer::fits () const
99 Simple_spacer::rod_force (int l, int r, Real dist)
101 Real d = range_ideal_len (l, r);
102 Real c = range_stiffness (l, r, dist > d);
103 Real block_stretch = dist - d;
105 if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */
107 return c * block_stretch;
111 Simple_spacer::add_rod (int l, int r, Real dist)
113 if (isinf (dist) || isnan (dist))
115 programming_error ("ignoring weird minimum distance");
119 Real block_force = rod_force (l, r, dist);
121 if (isinf (block_force))
123 Real spring_dist = range_ideal_len (l, r);
124 if (spring_dist < dist)
125 for (int i = l; i < r; i++)
128 springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
130 springs_[i].set_distance (dist / (r - l));
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 ()));
141 Simple_spacer::range_ideal_len (int l, int r) const
144 for (int i = l; i < r; i++)
145 d += springs_[i].distance ();
150 Simple_spacer::range_stiffness (int l, int r, bool stretch) const
153 for (int i = l; i < r; i++)
154 den += stretch ? springs_[i].inverse_stretch_strength ()
155 : springs_[i].inverse_compress_strength ();
161 Simple_spacer::configuration_length (Real force) const
164 for (vsize i = 0; i < springs_.size (); i++)
165 l += springs_[i].length (force);
171 Simple_spacer::set_force (Real force)
177 Simple_spacer::solve (Real line_len, bool ragged)
179 Real conf = configuration_length (force_);
182 line_len_ = line_len;
183 if (conf < line_len_)
184 force_ = expand_line ();
185 else if (conf > line_len_)
186 force_ = compress_line ();
188 if (ragged && force_ < 0)
193 Simple_spacer::expand_line ()
195 double inv_hooke = 0;
196 double cur_len = configuration_length (force_);
199 for (vsize i = 0; i < springs_.size (); i++)
200 inv_hooke += springs_[i].inverse_stretch_strength ();
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 */
205 assert (cur_len <= line_len_);
206 return (line_len_ - cur_len) / inv_hooke + force_;
210 Simple_spacer::compress_line ()
212 double cur_len = configuration_length (force_);
213 double cur_force = force_;
214 bool compressed = false;
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_)
223 cur_len = configuration_length (0.0);
229 assert (line_len_ <= cur_len);
231 vector<Spring> sorted_springs = springs_;
232 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
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++)
244 Spring sp = sorted_springs[i];
246 if (isinf (sp.blocking_force ()))
249 double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
250 if (cur_len - block_dist < line_len_)
252 cur_force += (line_len_ - cur_len) / inv_hooke;
258 assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
262 cur_len -= block_dist;
263 inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
264 cur_force = sp.blocking_force ();
272 Simple_spacer::add_spring (Spring const &sp)
274 force_ = max (force_, sp.blocking_force ());
275 springs_.push_back (sp);
279 Simple_spacer::spring_positions () const
284 for (vsize i = 0; i < springs_.size (); i++)
285 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
290 Simple_spacer::force_penalty (bool ragged) const
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
296 return max (0.0, line_len_ - configuration_length (0.0));
298 /* Use a convex compression penalty. */
300 return f - (f < 0 ? f * f * f * f * 2 : 0);
303 /****************************************************************/
306 get_line_configuration (vector<Grob *> const &columns,
311 vector<Column_description> cols;
312 Simple_spacer spacer;
313 Column_x_positions ret;
315 ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
316 for (vsize i = 1; i + 1 < columns.size (); i++)
318 if (Paper_column::is_loose (columns[i]))
319 ret.loose_cols_.push_back (columns[i]);
321 ret.cols_.push_back (columns[i]);
323 ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
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++)
329 cols.push_back (Column_description::get_column_description (ret.cols_, i, i == 0));
330 spacer.add_spring (cols[i].spring_);
332 for (vsize i = 0; i < cols.size (); i++)
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_);
337 if (!cols[i].keep_inside_line_.is_empty ())
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]);
344 spacer.solve (line_len, ragged);
345 ret.force_ = spacer.force_penalty (ragged);
347 ret.config_ = spacer.spring_positions ();
348 for (vsize i = 0; i < ret.config_.size (); i++)
349 ret.config_[i] += indent;
351 ret.satisfies_constraints_ = spacer.fits ();
354 Check if breaking constraints are met.
356 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
358 SCM p = ret.cols_[i]->get_property ("line-break-permission");
359 if (p == ly_symbol2scm ("force"))
360 ret.satisfies_constraints_ = false;
366 #include "ly-smobs.icc"
368 IMPLEMENT_SIMPLE_SMOBS (Simple_spacer);
369 IMPLEMENT_DEFAULT_EQUAL_P (Simple_spacer);
372 Simple_spacer::mark_smob (SCM /* x */)
378 Simple_spacer::print_smob (SCM /* x */, SCM p, scm_print_state *)
380 scm_puts ("#<Simple spacer>", p);