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"
23 #include "column-x-positions.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
= default_space_f_
;
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
));
262 for (int i
=0; i
< solution_vec
.dim (); i
++)
263 solution_vec(i
) += indent_f_
;
265 DOUT
<< "Lower bound sol: " << solution_vec
;
266 positions
->energy_f_
= calculate_energy_f (solution_vec
);
267 positions
->config_
= solution_vec
;
268 positions
->satisfies_constraints_b_
= check_constraints (solution_vec
);
271 Spring_spacer::Spring_spacer ()
274 energy_normalisation_f_
= 1.0;
278 Spring_spacer::solve (Column_x_positions
*positions
) const
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
);
291 Vector
solution_vec (lp
.solve (solution_try
));
292 for (int i
=0; i
< solution_vec
.dim (); i
++)
293 solution_vec(i
) += indent_f_
;
296 positions
->satisfies_constraints_b_
= check_constraints (solution_vec
);
297 if (!positions
->satisfies_constraints_b_
)
299 warning (_("Solution doesn't satisfy constraints"));
302 positions
->energy_f_
= calculate_energy_f (solution_vec
);
303 positions
->config_
= solution_vec
;
307 positions
->set_stupid_solution (solution_try
);
313 add one column to the problem.
315 TODO: ugh merge with add_columns.
318 Spring_spacer::add_column (Paper_column
*col
, bool fixed
, Real fixpos
)
320 Column_info
c (col
,(fixed
)? &fixpos
: 0);
321 int this_rank
= cols_
.size();
322 c
.rank_i_
= this_rank
;
324 for (int i
=0; i
< col
->minimal_dists_arr_drul_
[LEFT
].size (); i
++)
326 Column_rod
&cr
= col
->minimal_dists_arr_drul_
[LEFT
][i
];
327 int left_idx
= cr
.other_l_
->rank_i () - cols_
[0].pcol_l_
->rank_i ();
331 if (cols_
[left_idx
].pcol_l_
!= cr
.other_l_
)
335 l_rod
.distance_f_
= cr
.distance_f_
;
336 l_rod
.other_idx_
= left_idx
;
337 c
.rods_
[LEFT
].push (l_rod
);
340 r_rod
.distance_f_
= cr
.distance_f_
;
341 r_rod
.other_idx_
= this_rank
;
342 cols_
[left_idx
].rods_
[RIGHT
].push (r_rod
);
345 for (int i
=0; i
< col
->spring_arr_drul_
[LEFT
].size (); i
++)
347 Column_spring
&cr
= col
->spring_arr_drul_
[LEFT
][i
];
348 int idx
= cr
.other_l_
->rank_i () - cols_
[0].pcol_l_
->rank_i ();
352 if (cols_
[idx
].pcol_l_
!= cr
.other_l_
)
354 connect (idx
, this_rank
, cr
.distance_f_
, cr
.strength_f_
);
362 Spring_spacer::add_columns (Link_array
<Paper_column
> cols
)
364 energy_normalisation_f_
= sqr (line_len_f_
);
365 add_column (cols
[0], true, 0.0);
366 for (int i
=1; i
< cols
.size ()-1; i
++)
367 add_column (cols
[i
],false,0.0);
370 add_column (cols
.top (), true, line_len_f_
);
372 add_column (cols
.top (), false, 0);
378 Spring_spacer::print() const
381 for (int i
=0; i
< cols_
.size(); i
++)
383 DOUT
<< "col " << i
<< " ";
387 for (Cons
<Idealspacing
> *p
=ideal_p_list_
; p
; p
= p
->next_
)
396 Spring_spacer::connect (int i
, int j
, Real d
, Real h
)
400 programming_error( _f ("Improbable distance: %f point, setting to 10 mm", d
));
405 programming_error (_ ("Negative distance, setting to 10 mm"));
411 Idealspacing
* s
= new Idealspacing
;
413 s
->cols_drul_
[LEFT
] = i
;
414 s
->cols_drul_
[RIGHT
] = j
;
418 ideal_p_list_
= new Killing_cons
<Idealspacing
> (s
, ideal_p_list_
);
422 Spring_spacer::prepare()
429 Spring_spacer::~Spring_spacer()
431 delete ideal_p_list_
;