2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996, 1997--1998, 1998 Han-Wen Nienhuys <hanwen@cs.uu.nl>
12 #include "spring-spacer.hh"
15 #include "dimensions.hh"
17 #include "unionfind.hh"
18 #include "idealspacing.hh"
19 #include "pointer.tcc"
20 #include "score-column.hh"
21 #include "paper-def.hh"
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 (_f ("unconnected column: %d", 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 Column_info 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_);
264 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
266 for (int j=0; j < cols_.size(); j++)
267 if (cols_[j].fixed_b())
268 qp.add_fixed_var (j,cols_[j].fixed_position());
271 // put the constraints into the LP problem
273 Spring_spacer::make_constraints (Mixed_qp& lp) const
275 int dim=cols_.size();
277 for (int j=0; j < dim -1; j++)
279 Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
280 for (int i = 0; i < rod_arr.size (); i++)
283 c1(rod_arr[i].other_idx_)=1.0 ;
286 lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
293 Spring_spacer::calculate_energy_f (Vector solution) const
296 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
298 e += i->energy_f(solution(i->right_i_) - solution(i->left_i_));
304 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
306 Mixed_qp lp (cols_.size());
307 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
310 Vector start (cols_.size());
312 Vector solution_vec (lp.solve (start));
314 DOUT << "Lower bound sol: " << solution_vec;
315 positions->energy_f_ = calculate_energy_f (solution_vec);
316 positions->config = solution_vec;
317 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
320 Spring_spacer::Spring_spacer ()
322 energy_normalisation_f_ = 1.0;
326 Spring_spacer::solve (Column_x_positions*positions) const
328 DOUT << "Spring_spacer::solve ()...";
332 bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
333 if (constraint_satisfaction)
335 Mixed_qp lp (cols_.size());
336 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
337 make_constraints (lp);
340 Vector solution_vec (lp.solve (solution_try));
342 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
343 if (!positions->satisfies_constraints_b_)
345 WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
347 position_loose_cols (solution_vec);
348 positions->energy_f_ = calculate_energy_f (solution_vec);
349 positions->config = solution_vec;
350 positions->error_col_l_arr_ = error_pcol_l_arr();
354 positions->set_stupid_solution (solution_try);
357 DOUT << "Finished Spring_spacer::solve ()...";
361 add one column to the problem.
364 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
366 Column_info c (col,(fixed)? &fixpos : 0);
367 int this_rank = cols_.size();
368 c.rank_i_ = this_rank;
370 for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
372 Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
373 int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
377 if (cols_[left_idx].pcol_l_ != cr.other_l_)
381 l_rod.distance_f_ = cr.distance_f_;
382 l_rod.other_idx_ = left_idx;
383 c.rods_[LEFT].push (l_rod);
386 r_rod.distance_f_ = cr.distance_f_;
387 r_rod.other_idx_ = this_rank;
388 cols_[left_idx].rods_[RIGHT].push (r_rod);
395 Spring_spacer::error_pcol_l_arr() const
397 Array<Paper_column*> retval;
398 for (int i=0; i< cols_.size(); i++)
400 retval.push (cols_[i].pcol_l_);
401 for (int i=0; i < loose_col_arr_.size(); i++)
403 retval.push (loose_col_arr_[i].pcol_l_);
409 Spring_spacer::loosen_column (int i)
411 Column_info c=cols_.get (i);
412 for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
414 if (j->left_i_ == i|| j->right_i_ == i)
422 for (; j < loose_col_arr_.size(); j++)
424 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
427 loose_col_arr_.insert (c,j);
432 Spring_spacer::print() const
435 for (int i=0; i < cols_.size(); i++)
437 DOUT << "col " << i << " ";
440 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
449 Spring_spacer::connect (int i, int j, Real d, Real h)
451 assert(d >= 0 && d <= 100 CM);
454 Idealspacing * s = new Idealspacing;
461 ideal_p_list_.bottom().add (s);
468 Spring_spacer::prepare()
470 DOUT << "Preparing..";
474 DOUT << "finished preparing.\n";
478 Spring_spacer::constructor()
480 return new Spring_spacer;
486 get the shortest_playing running note at a time. */
488 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
489 Array<Moment> &context_shortest_arr)
491 for (int i=0; i < cols_.size(); i++)
493 scol_l (i)->preprocess();
494 scol_l (i)->print ();
496 int start_context_i=0;
497 Moment context_shortest;
498 context_shortest.set_infinite (1);
499 context_shortest_arr.set_size(cols_.size());
501 for (int i=0; i < cols_.size(); i++)
503 Moment now = scol_l (i)->when();
504 Moment shortest_playing;
505 shortest_playing.set_infinite (1);
507 if (scol_l (i)->breakable_b_)
509 for (int ji=i; ji >= start_context_i; ji--)
510 context_shortest_arr[ji] = context_shortest;
512 context_shortest.set_infinite (1);
514 if (scol_l (i)->durations.size())
516 context_shortest = context_shortest <? scol_l(i)->durations[0];
519 // ji was j, but triggered ICE
520 for (int ji=i+1; ji --;)
522 if (scol_l(ji)->durations.size() &&
523 now - scol_l(ji)->when() >= shortest_playing)
526 for (int k = scol_l (ji)->durations.size();
527 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
530 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
533 shortest_playing_arr.push(shortest_playing);
537 DOUT << "shortest_playing/:[ ";
538 for (int i=0; i < shortest_playing_arr.size(); i++)
540 DOUT << shortest_playing_arr[i] << " ";
541 DOUT << context_shortest_arr[i] << ", ";
548 TODO: take out the refs to width
551 generate springs between columns.
553 TODO: This needs rethinking.
555 * Spacing should take optical
558 * Should be decentralised
560 The algorithm is taken from :
562 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
563 OSU-CISRC-10/87-TR35, Department of Computer and Information
564 Science, The Ohio State University, 1987.
568 Spring_spacer::calc_idealspacing()
570 Array<Moment> shortest_playing_arr;
571 Array<Moment> context_shortest_arr;
572 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
574 Real interline_f = paper_l ()->interline_f ();
577 Array<Real> ideal_arr_;
578 Array<Real> hooke_arr_;
579 for (int i=0; i < cols_.size() - 1; i++){
580 ideal_arr_.push (-1.0);
581 hooke_arr_.push (1.0);
585 First do all non-musical columns
587 for (int i=0; i < cols_.size(); i++)
589 if (!scol_l (i)->musical_b() && i+1 < cols_.size())
591 Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
592 Real durational_distance = 0;
595 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
599 ugh should use shortest_playing distance
603 Real k= paper_l()->arithmetic_constant (context_shortest_arr[i]);
604 durational_distance = paper_l()->duration_to_dist (delta_t,k);
606 symbol_distance += -cols_[i+1].width_[LEFT];
609 ideal_arr_[i] = symbol_distance >? durational_distance;
610 hooke_arr_[i] = 1; //2.0;
617 for (int i=0; i < cols_.size(); i++)
619 if (scol_l (i)->musical_b())
621 Moment shortest_playing_len = shortest_playing_arr[i];
622 Moment context_shortest = context_shortest_arr[i];
623 if (! shortest_playing_len)
625 warning (_f ("can't find a ruling note at %s",
626 scol_l (i)->when().str ()));
627 shortest_playing_len = 1;
629 if (! context_shortest)
631 warning (_f ("no minimum in measure at %s",
632 scol_l (i)->when().str ()));
633 context_shortest = 1;
635 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
636 Real k= paper_l()->arithmetic_constant(context_shortest);
637 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
638 dist *= (double)(delta_t / shortest_playing_len);
641 According to [Ross] and [Wanske], and from what i've seen:
643 * whitespace at the begin of the bar should be fixed at
644 (about) one interline.
646 when spacing gets real tight, a smaller fixed value may be
647 used, so that there are two discrete amounts of whitespace
648 possible at the begin of a bar; but this is not implemented
651 * whitespace at the end of the bar is the normal amount of
652 "hinterfleish" that would have been used, had there been
653 yet another note in the bar.
655 some editors argue that the bar line should not take any
656 space, not to hinder the flow of music spaced around a bar
658 [Ross] and [Wanske] do not suggest this, however. Further,
659 it introduces some spacing problems and think that it is ugly
665 first musical column of bar
667 if (i && scol_l (i - 1)->breakable_b_)
669 // fixed: probably should set minimum (rod/spring)?
670 cols_[i-1].width_[RIGHT] += interline_f;
671 // should adjust dist too?
672 ideal_arr_[i-1] = ideal_arr_[i-1] >? (2 * interline_f);
676 last musical column of bar
678 if (i + 1 < cols_.size () && scol_l(i+1)->breakable_b_)
681 dist = dist >? interline_f;
684 uhuh, this code looks fine, already?
685 someone was junking this last "hinterfleisch" whitespace?!
687 but this seems to be fixed now :-)
690 cols_[i].width_[RIGHT] += interline_f;
693 // ugh, do we need this?
694 if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
696 Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
698 dist = dist >? minimum;
700 ideal_arr_[i] = dist;
704 for (int i=0; i < ideal_arr_.size(); i++)
706 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
707 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);