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"
17 const HAPPY_DOTS_I = 3;
20 Helper to trace back an optimal path
23 /** this was the previous. If negative, this break should not be
24 considered: this path has infinite energy
30 Col_hpositions line_config_;
39 This algorithms is adapted from
43 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;
54 first_node.line_i_ = 0;
56 optimal_paths[0] = first_node;
60 for (; break_idx< breaks.size (); break_idx++)
62 Array<int> candidates;
63 Array<Col_hpositions> candidate_lines;
64 Pointer_list<Line_spacer*> spacer_p_list;
67 start with a short line, add measures. At some point
68 the line becomes infeasible. Then we don't try to add more
70 for (int start_idx = break_idx; start_idx--;)
72 if (break_idx - start_idx > max_measures_i_)
75 if (optimal_paths[start_idx].prev_break_i_ < 0
76 && optimal_paths[start_idx].line_config_.energy_f_)
80 Line_of_cols line = all.slice (breaks[start_idx], breaks[break_idx]+1);
82 line[0] = line[0]->postbreak_l ();
83 line.top () = line.top ()->prebreak_l ();
88 Col_hpositions approx;
91 approx.spacer_l_ = generate_spacing_problem (line,
92 pscore_l_->paper_l_->line_dimensions_int (optimal_paths[start_idx].line_i_));
93 spacer_p_list.bottom ().add (approx.spacer_l_);
95 ( (Break_algorithm*)this)->approx_stats_.add (approx.cols);
96 approx.approximate_solve_line ();
98 if (approx.energy_f_ > energy_bound_f_)
104 // this is a likely candidate. Store it.
105 candidate_lines.push (approx);
106 candidates.push (start_idx);
111 Real minimal_energy = infinity_f;
112 for (int j=0; j < candidates.size (); j++)
114 int start = candidates[j];
115 if (optimal_paths[start].line_config_.energy_f_
116 + candidate_lines[j].energy_f_ > minimal_energy)
120 if (!candidate_lines[j].satisfies_constraints_b_)
122 candidate_lines[j].solve_line ();
123 ( (Break_algorithm*)this)->exact_stats_.add (candidate_lines[j].cols);
127 = optimal_paths[start].line_config_.energy_f_
128 + candidate_lines[j].energy_f_ ;
130 if (this_energy < minimal_energy)
133 minimal_energy = this_energy;
139 optimal_paths[break_idx].prev_break_i_ = -1;
140 optimal_paths[break_idx].line_config_.energy_f_ = infinity_f;
144 optimal_paths[break_idx].prev_break_i_ = candidates[minimal_j];
145 optimal_paths[break_idx].line_config_ = candidate_lines[minimal_j];
146 optimal_paths[break_idx].line_i_ =
147 optimal_paths[optimal_paths[break_idx].prev_break_i_].line_i_ + 1;
150 if (! (break_idx % HAPPY_DOTS_I))
151 *mlog << "[" << break_idx << "]"<<flush;
154 if (break_idx % HAPPY_DOTS_I)
155 *mlog << "[" << break_idx << "]"<<flush;
157 Array<int> final_breaks;
159 Array<Col_hpositions> lines;
161 /* skip 0-th element, since it is a "dummy" elt*/
162 for (int i = optimal_paths.size ()-1; i> 0;)
164 final_breaks.push (i);
165 assert (i > optimal_paths[i].prev_break_i_);
167 // there was no "feasible path"
168 if (!optimal_paths[i].line_config_.config.size ()) {
169 final_breaks.set_size (0);
172 i = optimal_paths[i].prev_break_i_;
176 for (int i= final_breaks.size (); i--;)
177 lines.push (optimal_paths[final_breaks[i]].line_config_);
183 Gourlay_breaking::Gourlay_breaking ()
185 get_line_spacer = Spring_spacer::constructor;
186 energy_bound_f_ = infinity_f;
187 max_measures_i_ = INT_MAX;
191 Gourlay_breaking::do_set_pscore ()
193 energy_bound_f_ = pscore_l_->paper_l_->get_var ("gourlay_energybound");
194 max_measures_i_ =int (rint (pscore_l_->paper_l_->get_var ("gourlay_maxmeasures")));