lilypond-0.1.45
[lilypond.git] / lily / spring-spacer.cc
blob94fd515d3911dba6a14e74ec7d17d5d17430ec5b
1 /*
2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996,1997 Han-Wen Nienhuys <hanwen@stack.nl>
7 */
10 #include <math.h>
11 #include <limits.h>
12 #include "spring-spacer.hh"
13 #include "p-col.hh"
14 #include "debug.hh"
15 #include "qlp.hh"
16 #include "unionfind.hh"
17 #include "idealspacing.hh"
18 #include "pointer.tcc"
19 #include "score-column.hh"
20 #include "paper-def.hh"
21 #include "dimen.hh"
22 #include "colhpos.hh"
23 #include "main.hh" // experimental_fietsers
25 Vector
26 Spring_spacer::default_solution() const
28 return try_initial_solution() ;
31 Score_column*
32 Spring_spacer::scol_l (int i)
34 return (Score_column*)cols[i].pcol_l_;
37 const Real COLFUDGE=1e-3;
38 template class P<Real>; // ugh.
40 bool
41 Spring_spacer::contains (Paper_column const *w)
43 for (int i=0; i< cols.size(); i++)
44 if (cols[i].pcol_l_ == w)
45 return true;
46 return false;
50 void
51 Spring_spacer::OK() const
53 #ifndef NDEBUG
54 for (int i = 1; i < cols.size(); i++)
55 assert (cols[i].rank_i_ > cols[i-1].rank_i_);
56 for (int i = 1; i < loose_col_arr_.size(); i++)
57 assert (loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
58 #endif
61 /**
62 Make sure no unconnected columns happen.
64 void
65 Spring_spacer::handle_loose_cols()
67 Union_find connected (cols.size());
68 Array<int> fixed;
69 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
71 connected.connect (i->left_i_,i->right_i_);
73 for (int i = 0; i < cols.size(); i++)
74 if (cols[i].fixed())
75 fixed.push (i);
76 for (int i=1; i < fixed.size(); i++)
77 connected.connect (fixed[i-1], fixed[i]);
79 for (int i = cols.size(); i--;)
81 if (! connected.equiv (fixed[0], i))
83 warning (_("unconnected column: ") + String (i));
84 loosen_column (i);
87 OK();
91 /**
92 Guess a stupid position for loose columns. Put loose columns at
93 regular distances from enclosing calced columns
95 void
96 Spring_spacer::position_loose_cols (Vector &sol_vec) const
98 if (!loose_col_arr_.size())
99 return ;
100 assert (sol_vec.dim());
101 Array<bool> fix_b_arr;
102 fix_b_arr.set_size (cols.size() + loose_col_arr_.size ());
103 Real utter_right_f=-infinity_f;
104 Real utter_left_f =infinity_f;
105 for (int i=0; i < loose_col_arr_.size(); i++)
107 fix_b_arr[loose_col_arr_[i].rank_i_] = false;
109 for (int i=0; i < cols.size(); i++)
111 int r= cols[i].rank_i_;
112 fix_b_arr[r] = true;
113 utter_right_f = utter_right_f >? sol_vec (i);
114 utter_left_f = utter_left_f <? sol_vec (i);
116 Vector v (fix_b_arr.size());
117 int j =0;
118 int k =0;
119 for (int i=0; i < v.dim(); i++)
121 if (fix_b_arr[i])
123 assert (cols[j].rank_i_ == i);
124 v (i) = sol_vec (j++);
126 else
128 Real left_pos_f =
129 (j>0) ?sol_vec (j-1) : utter_left_f;
130 Real right_pos_f =
131 (j < sol_vec.dim()) ? sol_vec (j) : utter_right_f;
132 int left_rank = (j>0) ? cols[j-1].rank_i_ : 0;
133 int right_rank = (j<sol_vec.dim()) ? cols[j].rank_i_ : sol_vec.dim ();
135 int d_r = right_rank - left_rank;
136 Colinfo loose=loose_col_arr_[k++];
137 int r = loose.rank_i_ ;
138 assert (r > left_rank && r < right_rank);
140 v (i) = (r - left_rank)*left_pos_f/ d_r +
141 (right_rank - r) *right_pos_f /d_r;
144 sol_vec = v;
147 bool
148 Spring_spacer::check_constraints (Vector v) const
150 int dim=v.dim();
151 assert (dim == cols.size());
153 for (int i=0; i < dim; i++)
156 if (cols[i].fixed()&&
157 abs (cols[i].fixed_position() - v (i)) > COLFUDGE)
158 return false;
160 if (!i)
161 continue;
163 Real mindist=cols[i-1].width_[RIGHT]
164 -cols[i].width_[LEFT];
166 // ugh... compares
167 Real dif =v (i) - v (i-1)- mindist;
168 bool b = (dif > - COLFUDGE);
171 if (!b)
172 return false;
175 return true;
178 /// try to generate a solution which obeys the min distances and fixed
179 /// positions
180 Vector
181 Spring_spacer::try_initial_solution() const
183 int dim=cols.size();
184 Vector initsol (dim);
185 for (int i=0; i < dim; i++)
187 if (cols[i].fixed())
189 initsol (i)=cols[i].fixed_position();
191 if (i > 0)
193 Real r =initsol (i-1) + cols[i-1].width_[RIGHT];
194 if (initsol (i) < r)
195 initsol (i) =r;
199 else
201 Real mindist=cols[i-1].width_[RIGHT]
202 - cols[i].width_[LEFT];
203 if (mindist < 0.0)
204 warning (_("Excentric column"));
205 initsol (i)=initsol (i-1)+mindist;
209 return initsol;
214 // generate the matrices
215 void
216 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
218 quad.fill (0);
219 lin.fill (0);
220 c = 0;
222 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
224 int l = i->left_i_;
225 int r = i->right_i_;
227 quad (r,r) += i->hooke_f_;
228 quad (r,l) -= i->hooke_f_;
229 quad (l,r) -= i->hooke_f_;
230 quad (l,l) += i->hooke_f_;
232 lin (r) -= i->space_f_*i->hooke_f_;
233 lin (l) += i->space_f_*i->hooke_f_;
235 c += sqr (i->space_f_);
239 void
240 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
242 for (int j=0; j < cols.size(); j++)
243 if (cols[j].fixed())
244 qp.add_fixed_var (j,cols[j].fixed_position());
247 // put the constraints into the LP problem
248 void
249 Spring_spacer::make_constraints (Mixed_qp& lp) const
251 int dim=cols.size();
252 Real nw_f = paper_l ()->note_width ();
253 for (int j=0; j < dim; j++)
255 Colinfo c=cols[j];
256 if (j > 0)
258 Vector c1(dim);
260 c1(j)=1.0 ;
261 c1(j-1)=-1.0 ;
263 lp.add_inequality_cons (c1, cols[j-1].width_[RIGHT]
264 - cols[j].width_[LEFT]);
270 Real
271 Spring_spacer::calculate_energy_f (Vector solution) const
273 Real e = 0.0;
274 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
276 e += i->energy_f(solution(i->right_i_) - solution(i->left_i_));
279 return e;
281 void
282 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
284 Mixed_qp lp (cols.size());
285 make_matrices (lp.quad,lp.lin, lp.const_term);
286 set_fixed_cols (lp);
288 Vector start (cols.size());
289 start.fill (0.0);
290 Vector solution_vec (lp.solve (start));
292 DOUT << "Lower bound sol: " << solution_vec;
293 positions->energy_f_ = calculate_energy_f (solution_vec);
294 positions->config = solution_vec;
295 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
298 void
299 Spring_spacer::solve (Col_hpositions*positions) const
301 Vector solution_try (try_initial_solution());
303 if (check_constraints (solution_try))
305 Mixed_qp lp (cols.size());
306 make_matrices (lp.quad,lp.lin, lp.const_term);
307 make_constraints (lp);
308 set_fixed_cols (lp);
310 Vector solution_vec (lp.solve (solution_try));
313 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
314 if (!positions->satisfies_constraints_b_)
316 WARN << _("solution doesn't satisfy constraints.\n") ;
318 position_loose_cols (solution_vec);
319 positions->energy_f_ = calculate_energy_f (solution_vec);
320 positions->config = solution_vec;
321 positions->error_col_l_arr_ = error_pcol_l_arr();
323 else
325 positions->set_stupid_solution (solution_try);
330 add one column to the problem.
332 void
333 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
335 Colinfo c (col,(fixed)? &fixpos : 0);
336 if (cols.size())
337 c.rank_i_ = cols.top().rank_i_+1;
338 else
339 c.rank_i_ = 0;
340 cols.push (c);
343 Line_of_cols
344 Spring_spacer::error_pcol_l_arr() const
346 Array<Paper_column*> retval;
347 for (int i=0; i< cols.size(); i++)
348 if (cols[i].ugh_b_)
349 retval.push (cols[i].pcol_l_);
350 for (int i=0; i < loose_col_arr_.size(); i++)
352 retval.push (loose_col_arr_[i].pcol_l_);
354 return retval;
357 void
358 Spring_spacer::loosen_column (int i)
360 Colinfo c=cols.get (i);
361 for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
363 if (j->left_i_ == i|| j->right_i_ == i)
364 j.del();
365 else
366 j++;
368 c.ugh_b_ = true;
370 int j=0;
371 for (; j < loose_col_arr_.size(); j++)
373 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
374 break;
376 loose_col_arr_.insert (c,j);
380 void
381 Spring_spacer::print() const
383 #ifndef NPRINT
384 for (int i=0; i < cols.size(); i++)
386 DOUT << "col " << i<<' ';
387 cols[i].print();
389 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
391 i->print();
393 #endif
397 void
398 Spring_spacer::connect (int i, int j, Real d, Real h)
400 assert(d >= 0 && d <= 100 CM);
401 assert(h >=0);
403 Idealspacing * s = new Idealspacing;
405 s->left_i_ = i ;
406 s->right_i_ = j;
407 s->space_f_ = d;
408 s->hooke_f_ = h;
410 ideal_p_list_.bottom().add (s);
416 void
417 Spring_spacer::prepare()
419 calc_idealspacing();
420 handle_loose_cols();
421 print();
424 Line_spacer*
425 Spring_spacer::constructor()
427 return new Spring_spacer;
433 get the shortest_playing running note at a time. */
434 void
435 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
436 Array<Moment> &context_shortest_arr)
438 for (int i=0; i < cols.size(); i++)
440 scol_l (i)->preprocess();
441 scol_l (i)->print ();
443 int start_context_i=0;
444 Moment context_shortest = infinity_mom;
445 context_shortest_arr.set_size(cols.size());
447 for (int i=0; i < cols.size(); i++)
449 Moment now = scol_l (i)->when();
450 Moment shortest_playing = infinity_mom;
452 if (scol_l (i)->breakable_b_)
454 for (int ji=i; ji >= start_context_i; ji--)
455 context_shortest_arr[ji] = context_shortest;
456 start_context_i = i;
457 context_shortest = infinity_mom;
459 if (scol_l (i)->durations.size())
461 context_shortest = context_shortest <? scol_l(i)->durations[0];
464 // ji was j, but triggered ICE
465 for (int ji=i+1; ji --;)
467 if (scol_l(ji)->durations.size() &&
468 now - scol_l(ji)->when() >= shortest_playing)
469 break;
471 for (int k = scol_l (ji)->durations.size();
472 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
475 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
478 shortest_playing_arr.push(shortest_playing);
481 #ifndef NPRINT
482 DOUT << "shortest_playing/:[ ";
483 for (int i=0; i < shortest_playing_arr.size(); i++)
485 DOUT << shortest_playing_arr[i] << " ";
486 DOUT << context_shortest_arr[i] << ", ";
488 DOUT << "]\n";
489 #endif
493 generate springs between columns.
495 UNDER DESTRUCTION
497 TODO: This needs rethinking. Spacing should take optical
498 effects into account, and should be local (measure wide)
500 The algorithm is taken from :
502 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
503 OSU-CISRC-10/87-TR35, Department of Computer and Information
504 Science, The Ohio State University, 1987.
507 void
508 Spring_spacer::calc_idealspacing()
510 Array<Moment> shortest_playing_arr;
511 Array<Moment> context_shortest_arr;
512 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
514 Real interline_f = paper_l ()->interline_f ();
515 Real nw_f = paper_l ()->note_width ();
517 Array<Real> ideal_arr_;
518 Array<Real> hooke_arr_;
519 for (int i=0; i < cols.size() - 1; i++){
520 ideal_arr_.push (-1.0);
521 hooke_arr_.push (1.0);
525 First do all non-musical columns
527 for (int i=0; i < cols.size(); i++)
529 if (!scol_l (i)->musical_b() && i+1 < cols.size())
531 Real symbol_distance =cols[i].width_[RIGHT] + 2 PT;
532 Real durational_distance = 0;
535 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
537 Real k= paper_l()->arithmetic_constant(context_shortest_arr[i]);
539 ugh should use shortest_playing distance
541 if (delta_t)
542 durational_distance = paper_l()->duration_to_dist (delta_t,k);
543 symbol_distance += -cols[i+1].width_[LEFT];
546 ideal_arr_[i] = symbol_distance >? durational_distance;
547 hooke_arr_[i] = 1; //2.0;
552 Then musicals
554 for (int i=0; i < cols.size(); i++)
556 if (scol_l (i)->musical_b())
558 Moment shortest_playing_len = shortest_playing_arr[i];
559 Moment context_shortest = context_shortest_arr[i];
560 if (! shortest_playing_len)
562 warning (_("Can't find a ruling note at ")
563 +String (scol_l (i)->when()));
564 shortest_playing_len = 1;
566 if (! context_shortest)
568 warning(_("No minimum in measure at ")
569 + String (scol_l (i)->when()));
570 context_shortest = 1;
572 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
573 Real k= paper_l()->arithmetic_constant(context_shortest);
574 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
575 dist *= delta_t / shortest_playing_len;
578 According to [Ross] and [Wanske], and from what i've seen:
580 * whitespace at the begin of the bar should be fixed at
581 (about) one interline.
582 [Ross]:
583 when spacing gets real tight, a smaller fixed value may be
584 used, so that there are two discrete amounts of whitespace
585 possible at the begin of a bar; but this is not implemented
586 right now.
588 * whitespace at the end of the bar is the normal amount of
589 "hinterfleish" that would have been used, had there been
590 yet another note in the bar.
591 [Ross]:
592 some editors argue that the bar line should not take any
593 space, not to hinder the flow of music spaced around a bar
594 line.
595 [Ross] and [Wanske] do not suggest this, however. Further,
596 it introduces some spacing problems and think that it is ugly
597 too.
598 [jcn]
602 first musical column of bar
604 if (i && scol_l (i - 1)->breakable_b_)
606 // fixed: probably should set minimum (rod/spring)?
607 cols[i-1].width_[RIGHT] += interline_f;
608 // should adjust dist too?
609 ideal_arr_[i-1] = ideal_arr_[i-1] >? interline_f;
613 last musical column of bar
615 if (i + 1 < cols.size () && scol_l(i+1)->breakable_b_)
617 // hmm, how bout?
618 dist = dist >? interline_f;
621 uhuh, this code looks fine, already?
622 someone was junking this last "hinterfleisch" whitespace?!
624 but this seems to be fixed now :-)
626 // set minimum rod
627 cols[i].width_[RIGHT] += interline_f;
630 // ugh, do we need this?
631 if (i < cols.size () - 1 && !scol_l (i + 1)->musical_b ())
633 Real minimum = -cols[i + 1].width_[LEFT] + cols[i].width_[RIGHT]
634 + interline_f / 2;
635 dist = dist >? minimum;
638 ideal_arr_[i] = dist;
642 for (int i=0; i < ideal_arr_.size(); i++)
644 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
645 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);