2 gourlay-breaking.cc -- implement Gourlay_breaking
4 source file of the GNU LilyPond music typesetter
6 (c) 1997 Han-Wen Nienhuys <hanwen@stack.nl>
9 #include "gourlay-breaking.hh"
11 #include "spring-spacer.hh"
15 #include "paper-def.hh"
18 const HAPPY_DOTS_I = 3;
21 Helper to trace back an optimal path
24 /** this was the previous. If negative, this break should not be
25 considered: this path has infinite energy
30 Col_hpositions line_config_;
37 This algorithms is adapted from
41 Gourlay_breaking::do_solve()const
44 Array<Break_node> optimal_paths;
45 Line_of_cols all = all_cols();
46 Array<int> breaks = find_break_indices();
48 optimal_paths.set_size(breaks.size());
50 Break_node first_node ;
51 first_node.prev_break_i_ = -1;
52 first_node.line_config_.energy_f_ = 0;
54 optimal_paths[0] = first_node;
58 for (; break_idx< breaks.size(); break_idx++) {
59 Array<int> candidates;
60 Array<Col_hpositions> candidate_lines;
61 Pointer_list<Line_spacer*> spacer_p_list;
64 start with a short line, add measures. At some point
65 the line becomes infeasible. Then we don't try to add more
67 for (int start_idx = break_idx; start_idx--; ){
68 if (break_idx - start_idx > max_measures_i_)
71 if (optimal_paths[start_idx].prev_break_i_ < 0
72 && optimal_paths[start_idx].line_config_.energy_f_)
76 Line_of_cols line = all.slice(breaks[start_idx], breaks[break_idx]+1);
78 line[0] = line[0]->postbreak_p_;
79 line.top() = line.top()->prebreak_p_;
84 Col_hpositions approx;
87 approx.spacer_l_ = generate_spacing_problem( line );
88 spacer_p_list.bottom().add(approx.spacer_l_);
90 ((Break_algorithm*)this)->approx_stats_.add( approx.cols );
91 approx.approximate_solve_line( );
93 if (approx.energy_f_ > energy_bound_f_ ){
98 // this is a likely candidate. Store it.
99 candidate_lines.push( approx );
100 candidates.push( start_idx );
105 Real minimal_energy = infinity_f;
106 for (int j=0; j < candidates.size(); j++) {
107 int start = candidates[j];
108 if ( optimal_paths[start].line_config_.energy_f_
109 + candidate_lines[j].energy_f_ > minimal_energy)
113 if ( !candidate_lines[j].satisfies_constraints_b_) {
114 candidate_lines[j].solve_line( );
115 ((Break_algorithm*)this)->exact_stats_.add ( candidate_lines[j].cols );
119 = optimal_paths[start].line_config_.energy_f_
120 + candidate_lines[j].energy_f_ ;
122 if ( this_energy < minimal_energy ) {
124 minimal_energy = this_energy;
129 optimal_paths[break_idx].prev_break_i_ = -1;
130 optimal_paths[break_idx].line_config_.energy_f_ = infinity_f;
132 optimal_paths[break_idx].prev_break_i_ = candidates[minimal_j];
133 optimal_paths[break_idx].line_config_ = candidate_lines[minimal_j];
136 if ( !(break_idx % HAPPY_DOTS_I) )
137 *mlog << "[" << break_idx << "]"<<flush;
140 if ( break_idx % HAPPY_DOTS_I)
141 *mlog << "[" << break_idx << "]"<<flush;
146 Array<int> final_breaks;
148 /* skip 0-th element, since it is a "dummy" elt*/
149 for (int i = optimal_paths.size()-1; i> 0; ) {
150 final_breaks.push ( i );
151 assert ( i > optimal_paths[i].prev_break_i_);
152 i = optimal_paths[i].prev_break_i_;
155 Array<Col_hpositions> lines;
156 for (int i= final_breaks.size(); i--; )
157 lines.push ( optimal_paths[final_breaks[i]].line_config_ );
164 Gourlay_breaking::Gourlay_breaking()
166 get_line_spacer = Spring_spacer::constructor;
167 energy_bound_f_ = infinity_f;
168 max_measures_i_ = INT_MAX;
172 Gourlay_breaking::do_set_pscore()
174 energy_bound_f_ = pscore_l_->paper_l_->get_var( "gourlay_energybound");
175 max_measures_i_ =int (rint( pscore_l_->paper_l_->get_var( "gourlay_maxmeasures")));