]> git.donarmstrong.com Git - lilypond.git/blob - lily/simple-spacer.cc
Doc-es: update Vocal.
[lilypond.git] / 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