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_;
38 This algorithms is adapted from
42 Gourlay_breaking::do_solve() const
45 Array<Break_node> optimal_paths;
46 Line_of_cols all = all_cols();
47 Array<int> breaks = find_break_indices();
49 optimal_paths.set_size (breaks.size());
51 Break_node first_node ;
52 first_node.prev_break_i_ = -1;
53 first_node.line_config_.energy_f_ = 0;
55 optimal_paths[0] = first_node;
59 for (; break_idx< breaks.size(); break_idx++)
61 Array<int> candidates;
62 Array<Col_hpositions> candidate_lines;
63 Pointer_list<Line_spacer*> spacer_p_list;
66 start with a short line, add measures. At some point
67 the line becomes infeasible. Then we don't try to add more
69 for (int start_idx = break_idx; start_idx--;)
71 if (break_idx - start_idx > max_measures_i_)
74 if (optimal_paths[start_idx].prev_break_i_ < 0
75 && optimal_paths[start_idx].line_config_.energy_f_)
79 Line_of_cols line = all.slice (breaks[start_idx], breaks[break_idx]+1);
81 line[0] = line[0]->postbreak_l();
82 line.top() = line.top ()->prebreak_l();
87 Col_hpositions approx;
90 approx.spacer_l_ = generate_spacing_problem (line);
91 spacer_p_list.bottom().add (approx.spacer_l_);
93 ((Break_algorithm*)this)->approx_stats_.add (approx.cols);
94 approx.approximate_solve_line();
96 if (approx.energy_f_ > energy_bound_f_)
102 // this is a likely candidate. Store it.
103 candidate_lines.push (approx);
104 candidates.push (start_idx);
109 Real minimal_energy = infinity_f;
110 for (int j=0; j < candidates.size(); j++)
112 int start = candidates[j];
113 if (optimal_paths[start].line_config_.energy_f_
114 + candidate_lines[j].energy_f_ > minimal_energy)
118 if (!candidate_lines[j].satisfies_constraints_b_)
120 candidate_lines[j].solve_line();
121 ((Break_algorithm*)this)->exact_stats_.add (candidate_lines[j].cols);
125 = optimal_paths[start].line_config_.energy_f_
126 + candidate_lines[j].energy_f_ ;
128 if (this_energy < minimal_energy)
131 minimal_energy = this_energy;
137 optimal_paths[break_idx].prev_break_i_ = -1;
138 optimal_paths[break_idx].line_config_.energy_f_ = infinity_f;
142 optimal_paths[break_idx].prev_break_i_ = candidates[minimal_j];
143 optimal_paths[break_idx].line_config_ = candidate_lines[minimal_j];
146 if (!(break_idx % HAPPY_DOTS_I))
147 *mlog << "[" << break_idx << "]"<<flush;
150 if (break_idx % HAPPY_DOTS_I)
151 *mlog << "[" << break_idx << "]"<<flush;
153 Array<int> final_breaks;
155 Array<Col_hpositions> lines;
157 Real max_energy_f = 0;
159 /* skip 0-th element, since it is a "dummy" elt*/
160 for (int i = optimal_paths.size()-1; i> 0;)
162 final_breaks.push (i);
163 assert (i > optimal_paths[i].prev_break_i_);
165 // there was no "feasible path"
166 if (!optimal_paths[i].line_config_.config.size()) {
167 final_breaks.set_size (0);
170 i = optimal_paths[i].prev_break_i_;
175 TODO print variation in energy
184 for (int i= final_breaks.size(); i--;)
185 lines.push (optimal_paths[final_breaks[i]].line_config_);
192 Gourlay_breaking::Gourlay_breaking()
194 get_line_spacer = Spring_spacer::constructor;
195 energy_bound_f_ = infinity_f;
196 max_measures_i_ = INT_MAX;
200 Gourlay_breaking::do_set_pscore()
202 energy_bound_f_ = pscore_l_->paper_l_->get_var ("gourlay_energybound");
203 max_measures_i_ =int (rint (pscore_l_->paper_l_->get_var ("gourlay_maxmeasures")));