2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
12 #include "killing-cons.tcc"
13 #include "spring-spacer.hh"
14 #include "paper-column.hh"
16 #include "dimensions.hh"
18 #include "unionfind.hh"
19 #include "idealspacing.hh"
20 #include "pointer.tcc"
21 #include "score-column.hh"
22 #include "paper-def.hh"
27 Spring_spacer::default_solution() const
29 return try_initial_solution();
33 Spring_spacer::scol_l (int i)
35 return dynamic_cast<Score_column*>(cols_[i].pcol_l_);
38 const Real COLFUDGE=1e-3;
39 template class P<Real>; // ugh.
42 Spring_spacer::contains_b (Paper_column const *w)
44 for (int i=0; i< cols_.size(); i++)
45 if (cols_[i].pcol_l_ == w)
52 Spring_spacer::OK() const
55 for (int i = 1; i < cols_.size(); i++)
56 assert (cols_[i].rank_i_ > cols_[i-1].rank_i_);
57 for (int i = 1; i < loose_col_arr_.size(); i++)
58 assert (loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
63 Make sure no unconnected columns happen.
66 Spring_spacer::handle_loose_cols()
68 Union_find connected (cols_.size());
71 for (Cons<Idealspacing> *i = ideal_p_list_; i; i = i->next_)
73 connected.connect (i->car_->cols_drul_[LEFT],i->car_->cols_drul_[RIGHT]);
75 for (int i = 0; i < cols_.size(); i++)
76 if (cols_[i].fixed_b())
78 for (int i=1; i < fixed.size(); i++)
79 connected.connect (fixed[i-1], fixed[i]);
81 for (int i = cols_.size(); i--;)
83 if (! connected.equiv (fixed[0], i))
85 warning (_f ("unconnected column: %d", i));
94 Guess a stupid position for loose columns. Put loose columns at
95 regular distances from enclosing calced columns
98 Spring_spacer::position_loose_cols (Vector &sol_vec) const
100 if (!loose_col_arr_.size())
102 assert (sol_vec.dim());
103 Array<bool> fix_b_arr;
104 fix_b_arr.set_size (cols_.size() + loose_col_arr_.size ());
105 Real utter_right_f=-infinity_f;
106 Real utter_left_f =infinity_f;
107 for (int i=0; i < loose_col_arr_.size(); i++)
109 fix_b_arr[loose_col_arr_[i].rank_i_] = false;
111 for (int i=0; i < cols_.size(); i++)
113 int r= cols_[i].rank_i_;
115 utter_right_f = utter_right_f >? sol_vec (i);
116 utter_left_f = utter_left_f <? sol_vec (i);
118 Vector v (fix_b_arr.size());
121 for (int i=0; i < v.dim(); i++)
125 assert (cols_[j].rank_i_ == i);
126 v (i) = sol_vec (j++);
131 (j>0) ?sol_vec (j-1) : utter_left_f;
133 (j < sol_vec.dim()) ? sol_vec (j) : utter_right_f;
134 int left_rank = (j>0) ? cols_[j-1].rank_i_ : 0;
135 int right_rank = (j<sol_vec.dim()) ? cols_[j].rank_i_ : sol_vec.dim ();
137 int d_r = right_rank - left_rank;
138 Column_info loose=loose_col_arr_[k++];
139 int r = loose.rank_i_ ;
140 assert (r > left_rank && r < right_rank);
142 v (i) = (r - left_rank)*left_pos_f/ d_r +
143 (right_rank - r) *right_pos_f /d_r;
150 Spring_spacer::check_constraints (Vector v) const
153 assert (dim == cols_.size());
154 DOUT << "checking " << v;
155 for (int i=0; i < dim; i++)
157 if (cols_[i].fixed_b() &&
158 abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
160 DOUT << "Fixpos broken\n";
163 Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
164 for (int j =0; j < rods.size (); j++)
166 int other =rods[j].other_idx_;
167 Real diff =v (other) - v (i) ;
168 if (COLFUDGE +diff < rods[j].distance_f_)
170 DOUT << "i, other_i: " << i << " " << other << '\n';
171 DOUT << "dist, minimal = " << diff << " "
172 << rods[j].distance_f_ << '\n';
181 /** try to generate a solution which obeys the min
182 distances and fixed positions
185 Spring_spacer::try_initial_solution() const
188 if (!try_initial_solution_and_tell (v))
190 warning (_ ("I'm too fat; call Oprah"));
197 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
199 int dim=cols_.size();
200 bool succeeded = true;
201 Vector initsol (dim);
203 assert (cols_[0].fixed_b ());
204 DOUT << "fixpos 0 " << cols_[0].fixed_position ();
205 for (int i=0; i < dim; i++)
207 Real min_x = i ? initsol (i-1) : cols_[0].fixed_position ();
208 Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
209 for (int j=0; j < sr_arr.size (); j++)
211 min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
215 if (cols_[i].fixed_b())
217 initsol (i)=cols_[i].fixed_position();
218 if (initsol (i) < min_x )
220 DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
228 DOUT << "tried and told solution: " << v;
230 DOUT << "(failed)\n";
236 // generate the matrices
238 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
244 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
246 Idealspacing *i = p->car_;
247 int l = i->cols_drul_[LEFT];
248 int r = i->cols_drul_[RIGHT];
250 quad (r,r) += i->hooke_f_;
251 quad (r,l) -= i->hooke_f_;
252 quad (l,r) -= i->hooke_f_;
253 quad (l,l) += i->hooke_f_;
255 lin (r) -= i->space_f_*i->hooke_f_;
256 lin (l) += i->space_f_*i->hooke_f_;
258 c += sqr (i->space_f_);
268 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
270 for (int j=0; j < cols_.size(); j++)
271 if (cols_[j].fixed_b())
272 qp.add_fixed_var (j,cols_[j].fixed_position());
275 // put the constraints into the LP problem
277 Spring_spacer::make_constraints (Mixed_qp& lp) const
279 int dim=cols_.size();
281 for (int j=0; j < dim -1; j++)
283 Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
284 for (int i = 0; i < rod_arr.size (); i++)
287 c1(rod_arr[i].other_idx_)=1.0 ;
290 lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
297 Spring_spacer::calculate_energy_f (Vector solution) const
300 for (Cons<Idealspacing>*p =ideal_p_list_; p; p = p->next_)
302 Idealspacing * i = p->car_;
303 e += i->energy_f(solution(i->cols_drul_[RIGHT]) - solution(i->cols_drul_[LEFT]));
309 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
311 Mixed_qp lp (cols_.size());
312 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
315 Vector start (cols_.size());
317 Vector solution_vec (lp.solve (start));
319 DOUT << "Lower bound sol: " << solution_vec;
320 positions->energy_f_ = calculate_energy_f (solution_vec);
321 positions->config = solution_vec;
322 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
325 Spring_spacer::Spring_spacer ()
328 energy_normalisation_f_ = 1.0;
332 Spring_spacer::solve (Column_x_positions*positions) const
334 DOUT << "Spring_spacer::solve ()...";
338 bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
339 if (constraint_satisfaction)
341 Mixed_qp lp (cols_.size());
342 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
343 make_constraints (lp);
346 Vector solution_vec (lp.solve (solution_try));
348 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
349 if (!positions->satisfies_constraints_b_)
351 WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
353 position_loose_cols (solution_vec);
354 positions->energy_f_ = calculate_energy_f (solution_vec);
355 positions->config = solution_vec;
356 positions->error_col_l_arr_ = error_pcol_l_arr();
360 positions->set_stupid_solution (solution_try);
363 DOUT << "Finished Spring_spacer::solve ()...";
367 add one column to the problem.
370 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
372 Column_info c (col,(fixed)? &fixpos : 0);
373 int this_rank = cols_.size();
374 c.rank_i_ = this_rank;
376 for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
378 Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
379 int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
383 if (cols_[left_idx].pcol_l_ != cr.other_l_)
387 l_rod.distance_f_ = cr.distance_f_;
388 l_rod.other_idx_ = left_idx;
389 c.rods_[LEFT].push (l_rod);
392 r_rod.distance_f_ = cr.distance_f_;
393 r_rod.other_idx_ = this_rank;
394 cols_[left_idx].rods_[RIGHT].push (r_rod);
397 for (int i=0; i < col->spring_arr_drul_[LEFT].size (); i++)
399 Column_spring &cr = col->spring_arr_drul_[LEFT][i];
400 int idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
404 if (cols_[idx].pcol_l_ != cr.other_l_)
407 Real d = cr.distance_f_;
410 connect (idx, this_rank, cr.distance_f_, cr.strength_f_); // large strength.
413 connect (idx, this_rank, cr.distance_f_,
414 cr.strength_f_ / cr.distance_f_);
421 Spring_spacer::error_pcol_l_arr() const
423 Link_array<Paper_column> retval;
424 for (int i=0; i< cols_.size(); i++)
426 retval.push (cols_[i].pcol_l_);
427 for (int i=0; i < loose_col_arr_.size(); i++)
429 retval.push (loose_col_arr_[i].pcol_l_);
435 Ugh. Should junk this.
438 Spring_spacer::loosen_column (int idx)
440 Column_info c=cols_.get (idx);
442 Cons<Idealspacing> **pp = &ideal_p_list_;
446 Idealspacing *j = (*pp)->car_;
447 if (j->cols_drul_[LEFT] == idx|| j->cols_drul_[RIGHT] == idx)
449 delete remove_cons (pp);
459 for (; j < loose_col_arr_.size(); j++)
461 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
464 loose_col_arr_.insert (c,j);
469 Spring_spacer::print() const
472 for (int i=0; i < cols_.size(); i++)
474 DOUT << "col " << i << " ";
478 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
487 Spring_spacer::connect (int i, int j, Real d, Real h)
489 assert(d >= 0 && d <= 100 CM);
492 Idealspacing * s = new Idealspacing;
494 s->cols_drul_[LEFT] = i ;
495 s->cols_drul_[RIGHT] = j;
499 ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
503 Spring_spacer::prepare()
510 Spring_spacer::constructor()
512 return new Spring_spacer;
518 Spring_spacer::~Spring_spacer()
520 delete ideal_p_list_;