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_);
61 Make sure no unconnected columns happen.
64 Spring_spacer::handle_loose_cols()
66 Union_find connected (cols_.size());
69 for (Cons<Idealspacing> *i = ideal_p_list_; i; i = i->next_)
71 connected.connect (i->car_->cols_drul_[LEFT],i->car_->cols_drul_[RIGHT]);
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]);
80 If columns do not have spacing information set, we need to supply our own.
82 Real d = paper_l ()->get_var ("loose_column_distance");
83 for (int i = cols_.size(); i--;)
85 if (! connected.equiv (fixed[0], i))
87 connected.connect (i-1, i);
88 connect (i-1, i, d, 1.0);
94 Spring_spacer::check_constraints (Vector v) const
97 assert (dim == cols_.size());
98 DOUT << "checking " << v;
99 for (int i=0; i < dim; i++)
101 if (cols_[i].fixed_b() &&
102 abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
104 DOUT << "Fixpos broken\n";
107 Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
108 for (int j =0; j < rods.size (); j++)
110 int other =rods[j].other_idx_;
111 Real diff =v (other) - v (i) ;
112 if (COLFUDGE +diff < rods[j].distance_f_)
114 DOUT << "i, other_i: " << i << " " << other << '\n';
115 DOUT << "dist, minimal = " << diff << " "
116 << rods[j].distance_f_ << '\n';
125 /** try to generate a solution which obeys the min
126 distances and fixed positions
129 Spring_spacer::try_initial_solution() const
132 if (!try_initial_solution_and_tell (v))
134 warning (_ ("I'm too fat; call Oprah"));
141 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
143 int dim=cols_.size();
144 bool succeeded = true;
145 Vector initsol (dim);
147 assert (cols_[0].fixed_b ());
148 DOUT << "fixpos 0 " << cols_[0].fixed_position ();
149 for (int i=0; i < dim; i++)
151 Real min_x = i ? initsol (i-1) : cols_[0].fixed_position ();
152 Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
153 for (int j=0; j < sr_arr.size (); j++)
155 min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
159 if (cols_[i].fixed_b())
161 initsol (i)=cols_[i].fixed_position();
162 if (initsol (i) < min_x )
164 DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
172 DOUT << "tried and told solution: " << v;
174 DOUT << "(failed)\n";
180 // generate the matrices
182 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
188 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
190 Idealspacing *i = p->car_;
191 int l = i->cols_drul_[LEFT];
192 int r = i->cols_drul_[RIGHT];
194 quad (r,r) += i->hooke_f_;
195 quad (r,l) -= i->hooke_f_;
196 quad (l,r) -= i->hooke_f_;
197 quad (l,l) += i->hooke_f_;
199 lin (r) -= i->space_f_*i->hooke_f_;
200 lin (l) += i->space_f_*i->hooke_f_;
202 c += sqr (i->space_f_);
212 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
214 for (int j=0; j < cols_.size(); j++)
215 if (cols_[j].fixed_b())
216 qp.add_fixed_var (j,cols_[j].fixed_position());
219 // put the constraints into the LP problem
221 Spring_spacer::make_constraints (Mixed_qp& lp) const
223 int dim=cols_.size();
225 for (int j=0; j < dim -1; j++)
227 Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
228 for (int i = 0; i < rod_arr.size (); i++)
231 c1(rod_arr[i].other_idx_)=1.0 ;
234 lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
241 Spring_spacer::calculate_energy_f (Vector solution) const
244 for (Cons<Idealspacing>*p =ideal_p_list_; p; p = p->next_)
246 Idealspacing * i = p->car_;
247 e += i->energy_f(solution(i->cols_drul_[RIGHT]) - solution(i->cols_drul_[LEFT]));
253 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
255 Mixed_qp lp (cols_.size());
256 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
259 Vector start (cols_.size());
261 Vector solution_vec (lp.solve (start));
263 DOUT << "Lower bound sol: " << solution_vec;
264 positions->energy_f_ = calculate_energy_f (solution_vec);
265 positions->config_ = solution_vec;
266 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
269 Spring_spacer::Spring_spacer ()
272 energy_normalisation_f_ = 1.0;
276 Spring_spacer::solve (Column_x_positions*positions) const
278 DOUT << "Spring_spacer::solve ()...";
282 bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
283 if (constraint_satisfaction)
285 Mixed_qp lp (cols_.size());
286 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
287 make_constraints (lp);
290 Vector solution_vec (lp.solve (solution_try));
292 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
293 if (!positions->satisfies_constraints_b_)
295 WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
297 positions->energy_f_ = calculate_energy_f (solution_vec);
298 positions->config_ = solution_vec;
302 positions->set_stupid_solution (solution_try);
305 DOUT << "Finished Spring_spacer::solve ()...";
309 add one column to the problem.
312 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
314 Column_info c (col,(fixed)? &fixpos : 0);
315 int this_rank = cols_.size();
316 c.rank_i_ = this_rank;
318 for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
320 Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
321 int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
325 if (cols_[left_idx].pcol_l_ != cr.other_l_)
329 l_rod.distance_f_ = cr.distance_f_;
330 l_rod.other_idx_ = left_idx;
331 c.rods_[LEFT].push (l_rod);
334 r_rod.distance_f_ = cr.distance_f_;
335 r_rod.other_idx_ = this_rank;
336 cols_[left_idx].rods_[RIGHT].push (r_rod);
339 for (int i=0; i < col->spring_arr_drul_[LEFT].size (); i++)
341 Column_spring &cr = col->spring_arr_drul_[LEFT][i];
342 int idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
346 if (cols_[idx].pcol_l_ != cr.other_l_)
348 connect (idx, this_rank, cr.distance_f_, cr.strength_f_);
356 Spring_spacer::print() const
359 for (int i=0; i < cols_.size(); i++)
361 DOUT << "col " << i << " ";
365 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
374 Spring_spacer::connect (int i, int j, Real d, Real h)
376 assert(d >= 0 && d <= 100 CM);
379 Idealspacing * s = new Idealspacing;
381 s->cols_drul_[LEFT] = i ;
382 s->cols_drul_[RIGHT] = j;
386 ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
390 Spring_spacer::prepare()
397 Spring_spacer::constructor()
399 return new Spring_spacer;
405 Spring_spacer::~Spring_spacer()
407 delete ideal_p_list_;