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
29 Col_hpositions line_config_
;
37 This algorithms is adapted from
41 Gourlay_breaking::do_solve() const
43 Array
<Break_node
> optimal_paths
;
44 Line_of_cols all
= all_cols();
45 Array
<int> breaks
= find_break_indices();
47 optimal_paths
.set_size (breaks
.size());
49 Break_node first_node
;
50 first_node
.prev_break_i_
= -1;
51 first_node
.line_config_
.energy_f_
= 0;
53 optimal_paths
[0] = first_node
;
57 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
--;)
69 if (break_idx
- start_idx
> max_measures_i_
)
72 if (optimal_paths
[start_idx
].prev_break_i_
< 0
73 && optimal_paths
[start_idx
].line_config_
.energy_f_
)
77 Line_of_cols line
= all
.slice (breaks
[start_idx
], breaks
[break_idx
]+1);
79 line
[0] = line
[0]->postbreak_l();
80 line
.top() = line
.top ()->prebreak_l();
85 Col_hpositions approx
;
88 approx
.spacer_l_
= generate_spacing_problem (line
);
89 spacer_p_list
.bottom().add (approx
.spacer_l_
);
91 ((Break_algorithm
*)this)->approx_stats_
.add (approx
.cols
);
92 approx
.approximate_solve_line();
94 if (approx
.energy_f_
> energy_bound_f_
)
100 // this is a likely candidate. Store it.
101 candidate_lines
.push (approx
);
102 candidates
.push (start_idx
);
107 Real minimal_energy
= infinity_f
;
108 for (int j
=0; j
< candidates
.size(); j
++)
110 int start
= candidates
[j
];
111 if (optimal_paths
[start
].line_config_
.energy_f_
112 + candidate_lines
[j
].energy_f_
> minimal_energy
)
116 if (!candidate_lines
[j
].satisfies_constraints_b_
)
118 candidate_lines
[j
].solve_line();
119 ((Break_algorithm
*)this)->exact_stats_
.add (candidate_lines
[j
].cols
);
123 = optimal_paths
[start
].line_config_
.energy_f_
124 + candidate_lines
[j
].energy_f_
;
126 if (this_energy
< minimal_energy
)
129 minimal_energy
= this_energy
;
135 optimal_paths
[break_idx
].prev_break_i_
= -1;
136 optimal_paths
[break_idx
].line_config_
.energy_f_
= infinity_f
;
140 optimal_paths
[break_idx
].prev_break_i_
= candidates
[minimal_j
];
141 optimal_paths
[break_idx
].line_config_
= candidate_lines
[minimal_j
];
144 if (!(break_idx
% HAPPY_DOTS_I
))
145 *mlog
<< "[" << break_idx
<< "]"<<flush
;
148 if (break_idx
% HAPPY_DOTS_I
)
149 *mlog
<< "[" << break_idx
<< "]"<<flush
;
151 Array
<int> final_breaks
;
153 Array
<Col_hpositions
> lines
;
155 /* skip 0-th element, since it is a "dummy" elt*/
156 for (int i
= optimal_paths
.size()-1; i
> 0;)
158 final_breaks
.push (i
);
159 assert (i
> optimal_paths
[i
].prev_break_i_
);
161 // there was no "feasible path"
162 if (!optimal_paths
[i
].line_config_
.config
.size()) {
163 final_breaks
.set_size (0);
166 i
= optimal_paths
[i
].prev_break_i_
;
170 for (int i
= final_breaks
.size(); i
--;)
171 lines
.push (optimal_paths
[final_breaks
[i
]].line_config_
);
177 Gourlay_breaking::Gourlay_breaking()
179 get_line_spacer
= Spring_spacer::constructor
;
180 energy_bound_f_
= infinity_f
;
181 max_measures_i_
= INT_MAX
;
185 Gourlay_breaking::do_set_pscore()
187 energy_bound_f_
= pscore_l_
->paper_l_
->get_var ("gourlay_energybound");
188 max_measures_i_
=int (rint (pscore_l_
->paper_l_
->get_var ("gourlay_maxmeasures")));