2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996, 1997, 1998 Han-Wen Nienhuys <hanwen@stack.nl>
12 #include "spring-spacer.hh"
16 #include "unionfind.hh"
17 #include "idealspacing.hh"
18 #include "pointer.tcc"
19 #include "score-column.hh"
20 #include "paper-def.hh"
23 #include "main.hh" // experimental_fietsers
26 Spring_spacer::default_solution() const
28 return try_initial_solution() ;
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.
41 Spring_spacer::contains_b (Paper_column const *w)
43 for (int i=0; i< cols_.size(); i++)
44 if (cols_[i].pcol_l_ == w)
51 Spring_spacer::OK() const
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_);
62 Make sure no unconnected columns happen.
65 Spring_spacer::handle_loose_cols()
67 Union_find connected (cols_.size());
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_b())
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));
92 Guess a stupid position for loose columns. Put loose columns at
93 regular distances from enclosing calced columns
96 Spring_spacer::position_loose_cols (Vector &sol_vec) const
98 if (!loose_col_arr_.size())
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_;
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());
119 for (int i=0; i < v.dim(); i++)
123 assert (cols_[j].rank_i_ == i);
124 v (i) = sol_vec (j++);
129 (j>0) ?sol_vec (j-1) : utter_left_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;
148 Spring_spacer::check_constraints (Vector v) const
151 assert (dim == cols_.size());
152 DOUT << "checking " << v;
153 for (int i=0; i < dim; i++)
155 if (cols_[i].fixed_b() &&
156 abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
158 DOUT << "Fixpos broken\n";
161 Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
162 for (int j =0; j < rods.size (); j++)
164 int other =rods[j].other_idx_;
165 Real diff =v (other) - v (i) ;
166 if (COLFUDGE +diff < rods[j].distance_f_)
168 DOUT << "i, other_i: " << i << " " << other << "\n";
169 DOUT << "dist, minimal = " << diff <<" "
170 << rods[j].distance_f_<<'\n';
179 /** try to generate a solution which obeys the min distances and fixed positions
182 Spring_spacer::try_initial_solution() const
185 if (!try_initial_solution_and_tell (v))
187 warning ("I'm too fat; call Oprah");
194 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
196 int dim=cols_.size();
197 bool succeeded = true;
198 Vector initsol (dim);
200 assert (cols_[0].fixed_b ());
201 DOUT << "fixpos 0 " << cols_[0].fixed_position ();
202 for (int i=0; i < dim; i++)
204 Real min_x = i ? initsol (i-1) : cols_[0].fixed_position ();
205 Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
206 for (int j=0; j < sr_arr.size (); j++)
208 min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
212 if (cols_[i].fixed_b())
214 initsol (i)=cols_[i].fixed_position();
215 if (initsol (i) < min_x )
217 DOUT << "failing: init, min : " << initsol (i) << " " << min_x << "\n";
225 DOUT << "tried and told solution: " << v;
227 DOUT << "(failed)\n";
233 // generate the matrices
235 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
241 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
246 quad (r,r) += i->hooke_f_;
247 quad (r,l) -= i->hooke_f_;
248 quad (l,r) -= i->hooke_f_;
249 quad (l,l) += i->hooke_f_;
251 lin (r) -= i->space_f_*i->hooke_f_;
252 lin (l) += i->space_f_*i->hooke_f_;
254 c += sqr (i->space_f_);
259 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
261 for (int j=0; j < cols_.size(); j++)
262 if (cols_[j].fixed_b())
263 qp.add_fixed_var (j,cols_[j].fixed_position());
266 // put the constraints into the LP problem
268 Spring_spacer::make_constraints (Mixed_qp& lp) const
270 int dim=cols_.size();
271 int last_rank = cols_.top ().pcol_l_->rank_i ();
273 for (int j=0; j < dim -1; j++)
275 Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
276 for (int i = 0; i < rod_arr.size (); i++)
279 c1(rod_arr[i].other_idx_)=1.0 ;
282 lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
289 Spring_spacer::calculate_energy_f (Vector solution) const
292 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
294 e += i->energy_f(solution(i->right_i_) - solution(i->left_i_));
300 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
302 Mixed_qp lp (cols_.size());
303 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
306 Vector start (cols_.size());
308 Vector solution_vec (lp.solve (start));
310 DOUT << "Lower bound sol: " << solution_vec;
311 positions->energy_f_ = calculate_energy_f (solution_vec);
312 positions->config = solution_vec;
313 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
317 Spring_spacer::solve (Col_hpositions*positions) const
320 DOUT << "Spring_spacer::solve ()...";
323 bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
324 if (constraint_satisfaction)
326 Mixed_qp lp (cols_.size());
327 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
328 make_constraints (lp);
331 Vector solution_vec (lp.solve (solution_try));
333 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
334 if (!positions->satisfies_constraints_b_)
336 WARN << _("solution doesn't satisfy constraints.\n") ;
338 position_loose_cols (solution_vec);
339 positions->energy_f_ = calculate_energy_f (solution_vec);
340 positions->config = solution_vec;
341 positions->error_col_l_arr_ = error_pcol_l_arr();
345 positions->set_stupid_solution (solution_try);
347 DOUT << "Finished Spring_spacer::solve ()...";
351 add one column to the problem.
354 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
356 Colinfo c (col,(fixed)? &fixpos : 0);
357 int this_rank = cols_.size();
358 c.rank_i_ = this_rank;
360 for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
362 Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
363 int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
367 if (cols_[left_idx].pcol_l_ != cr.other_l_)
371 l_rod.distance_f_ = cr.distance_f_;
372 l_rod.other_idx_ = left_idx;
373 c.rods_[LEFT].push (l_rod);
376 r_rod.distance_f_ = cr.distance_f_;
377 r_rod.other_idx_ = this_rank;
378 cols_[left_idx].rods_[RIGHT].push (r_rod);
385 Spring_spacer::error_pcol_l_arr() const
387 Array<Paper_column*> retval;
388 for (int i=0; i< cols_.size(); i++)
390 retval.push (cols_[i].pcol_l_);
391 for (int i=0; i < loose_col_arr_.size(); i++)
393 retval.push (loose_col_arr_[i].pcol_l_);
399 Spring_spacer::loosen_column (int i)
401 Colinfo c=cols_.get (i);
402 for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
404 if (j->left_i_ == i|| j->right_i_ == i)
412 for (; j < loose_col_arr_.size(); j++)
414 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
417 loose_col_arr_.insert (c,j);
422 Spring_spacer::print() const
425 for (int i=0; i < cols_.size(); i++)
427 DOUT << "col " << i<<' ';
430 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
439 Spring_spacer::connect (int i, int j, Real d, Real h)
441 assert(d >= 0 && d <= 100 CM);
444 Idealspacing * s = new Idealspacing;
451 ideal_p_list_.bottom().add (s);
458 Spring_spacer::prepare()
460 DOUT << "Preparing..";
464 DOUT << "finished preparing.\n";
468 Spring_spacer::constructor()
470 return new Spring_spacer;
476 get the shortest_playing running note at a time. */
478 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
479 Array<Moment> &context_shortest_arr)
481 for (int i=0; i < cols_.size(); i++)
483 scol_l (i)->preprocess();
484 scol_l (i)->print ();
486 int start_context_i=0;
487 Moment context_shortest;
488 context_shortest.set_infinite (1);
489 context_shortest_arr.set_size(cols_.size());
491 for (int i=0; i < cols_.size(); i++)
493 Moment now = scol_l (i)->when();
494 Moment shortest_playing;
495 shortest_playing.set_infinite (1);
497 if (scol_l (i)->breakable_b_)
499 for (int ji=i; ji >= start_context_i; ji--)
500 context_shortest_arr[ji] = context_shortest;
502 context_shortest.set_infinite (1);
504 if (scol_l (i)->durations.size())
506 context_shortest = context_shortest <? scol_l(i)->durations[0];
509 // ji was j, but triggered ICE
510 for (int ji=i+1; ji --;)
512 if (scol_l(ji)->durations.size() &&
513 now - scol_l(ji)->when() >= shortest_playing)
516 for (int k = scol_l (ji)->durations.size();
517 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
520 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
523 shortest_playing_arr.push(shortest_playing);
527 DOUT << "shortest_playing/:[ ";
528 for (int i=0; i < shortest_playing_arr.size(); i++)
530 DOUT << shortest_playing_arr[i] << " ";
531 DOUT << context_shortest_arr[i] << ", ";
538 TODO: take out the refs to width
541 generate springs between columns.
543 TODO: This needs rethinking. Spacing should take optical
546 The algorithm is taken from :
548 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
549 OSU-CISRC-10/87-TR35, Department of Computer and Information
550 Science, The Ohio State University, 1987.
554 Spring_spacer::calc_idealspacing()
556 Array<Moment> shortest_playing_arr;
557 Array<Moment> context_shortest_arr;
558 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
560 Real interline_f = paper_l ()->interline_f ();
561 Real nw_f = paper_l ()->note_width ();
563 Array<Real> ideal_arr_;
564 Array<Real> hooke_arr_;
565 for (int i=0; i < cols_.size() - 1; i++){
566 ideal_arr_.push (-1.0);
567 hooke_arr_.push (1.0);
571 First do all non-musical columns
573 for (int i=0; i < cols_.size(); i++)
575 if (!scol_l (i)->musical_b() && i+1 < cols_.size())
577 Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
578 Real durational_distance = 0;
581 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
583 Real k= paper_l()->arithmetic_constant (context_shortest_arr[i]);
585 ugh should use shortest_playing distance
588 durational_distance = paper_l()->duration_to_dist (delta_t,k);
589 symbol_distance += -cols_[i+1].width_[LEFT];
592 ideal_arr_[i] = symbol_distance >? durational_distance;
593 hooke_arr_[i] = 1; //2.0;
600 for (int i=0; i < cols_.size(); i++)
602 if (scol_l (i)->musical_b())
604 Moment shortest_playing_len = shortest_playing_arr[i];
605 Moment context_shortest = context_shortest_arr[i];
606 if (! shortest_playing_len)
608 warning (_("Can't find a ruling note at ")
609 +scol_l (i)->when().str ());
610 shortest_playing_len = 1;
612 if (! context_shortest)
614 warning(_("No minimum in measure at ")
615 + scol_l (i)->when().str ());
616 context_shortest = 1;
618 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
619 Real k= paper_l()->arithmetic_constant(context_shortest);
620 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
621 dist *= (double)(delta_t / shortest_playing_len);
624 According to [Ross] and [Wanske], and from what i've seen:
626 * whitespace at the begin of the bar should be fixed at
627 (about) one interline.
629 when spacing gets real tight, a smaller fixed value may be
630 used, so that there are two discrete amounts of whitespace
631 possible at the begin of a bar; but this is not implemented
634 * whitespace at the end of the bar is the normal amount of
635 "hinterfleish" that would have been used, had there been
636 yet another note in the bar.
638 some editors argue that the bar line should not take any
639 space, not to hinder the flow of music spaced around a bar
641 [Ross] and [Wanske] do not suggest this, however. Further,
642 it introduces some spacing problems and think that it is ugly
648 first musical column of bar
650 if (i && scol_l (i - 1)->breakable_b_)
652 // fixed: probably should set minimum (rod/spring)?
653 cols_[i-1].width_[RIGHT] += interline_f;
654 // should adjust dist too?
655 ideal_arr_[i-1] = ideal_arr_[i-1] >? interline_f;
659 last musical column of bar
661 if (i + 1 < cols_.size () && scol_l(i+1)->breakable_b_)
664 dist = dist >? interline_f;
667 uhuh, this code looks fine, already?
668 someone was junking this last "hinterfleisch" whitespace?!
670 but this seems to be fixed now :-)
673 cols_[i].width_[RIGHT] += interline_f;
676 // ugh, do we need this?
677 if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
679 Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
681 dist = dist >? minimum;
684 // ugh: never let columns touch... try to set over here...
685 // ugh: use j iso i triggers ice in gcc-2.7.2.3
686 cols_[i].width_[LEFT] -= nw_f / 4;
687 ideal_arr_[i] = dist;
691 for (int i=0; i < ideal_arr_.size(); i++)
693 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
694 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);