2 gourlay-breaking.cc -- implement Gourlay_breaking
4 source file of the GNU LilyPond music typesetter
6 (c) 1997--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
9 #include "gourlay-breaking.hh"
11 #include <cmath> // rint
16 #include "paper-column.hh"
17 #include "paper-score.hh"
18 #include "output-def.hh"
19 #include "simple-spacer.hh"
22 /// How often to print operator pacification marks?
23 const int HAPPY_DOTS_I = 3;
26 Helper to trace back an optimal path
29 /** this was the previous. If negative, this break should not be
30 considered: this path has infinite energy
35 Which system number so far?
40 Column_x_positions line_config_;
51 printf ("prev break %d, line %d, demerits %f\n",
52 prev_break_, line_, demerits_);
57 print_break_nodes (Array<Break_node> const & arr)
59 for (int i =0; i < arr.size (); i++)
61 printf ( "node %d: ", i);
67 This algorithms is adapted from the OSU Tech report on breaking lines.
69 this function is longish, but not very complicated.
71 TODO: should rewrite. See the function in scm/page-layout.scm for
75 Array<Column_x_positions>
76 Gourlay_breaking::do_solve () const
78 Array<Break_node> optimal_paths;
79 Link_array<Grob> all =
80 pscore_->system_->columns ();
82 Array<int> breaks = find_break_indices ();
84 Break_node first_node ;
85 optimal_paths.push (first_node);
87 bool ragged_right = to_boolean (pscore_->layout_->c_variable ("raggedright"));
88 bool ragged_last = to_boolean (pscore_->layout_->c_variable ("raggedlast"));
90 Real worst_force = 0.0;
91 for (int break_idx = 1; break_idx< breaks.size (); break_idx++)
94 start with a short line, add measures. At some point
95 the line becomes infeasible. Then we don't try to add more
97 int minimal_start_idx = -1;
98 Column_x_positions minimal_sol;
99 Column_x_positions backup_sol;
101 Real minimal_demerits = infinity_f;
103 for (int start_idx = break_idx; start_idx--;)
105 Link_array<Grob> line = all.slice (breaks[start_idx], breaks[break_idx]+1);
107 line[0] = dynamic_cast<Item*> (line[0])->find_prebroken_piece (RIGHT);
108 line.top () = dynamic_cast<Item*> (line.top ())->find_prebroken_piece (LEFT);
110 Column_x_positions cp;
114 = line_dimensions_int (pscore_->layout_, optimal_paths[start_idx].line_);
115 Simple_spacer_wrapper * sp = generate_spacing_problem (line, line_dims);
116 bool last_line = break_idx == breaks.size ()-1;
117 bool ragged = ragged_right
118 || (last_line && ragged_last);
120 sp->solve (&cp, ragged);
124 if (ragged && last_line)
127 if (fabs (cp.force_) > worst_force)
128 worst_force = fabs (cp.force_);
131 We remember this solution as a "should always work
132 solution", in case everything fucks up. */
133 if (start_idx == break_idx - 1)
138 if (optimal_paths[start_idx].demerits_ >= infinity_f)
139 this_demerits = infinity_f;
141 this_demerits = combine_demerits (optimal_paths[start_idx].line_config_, cp)
142 + optimal_paths[start_idx].demerits_;
144 if (this_demerits < minimal_demerits)
146 minimal_start_idx = start_idx;
148 minimal_demerits = this_demerits;
152 we couldn't satisfy the constraints, this won't get better
153 if we add more columns, so we get on with the next one
155 if (!cp.satisfies_constraints_)
161 if (minimal_start_idx < 0)
163 bnod.demerits_ = infinity_f;
164 bnod.line_config_ = backup_sol;
165 bnod.prev_break_ = break_idx - 1;
169 bnod.prev_break_ = minimal_start_idx;
170 bnod.demerits_ = minimal_demerits;
171 bnod.line_config_ = minimal_sol;
173 bnod.line_ = optimal_paths[bnod.prev_break_].line_ + 1;
174 optimal_paths.push (bnod);
176 if (! (break_idx % HAPPY_DOTS_I))
177 progress_indication (String ("[") + to_string (break_idx) + "]");
180 /* do the last one */
181 if (breaks.size () % HAPPY_DOTS_I)
182 progress_indication (String ("[") + to_string (breaks.size ()) + "]");
184 progress_indication ("\n");
186 Array<int> final_breaks;
187 Array<Column_x_positions> lines;
189 /* skip 0-th element, since it is a "dummy" elt*/
190 for (int i = optimal_paths.size ()-1; i> 0;)
192 final_breaks.push (i);
193 int prev = optimal_paths[i].prev_break_;
198 if (verbose_global_b)
200 progress_indication (_f ("Optimal demerits: %f",
201 optimal_paths.top ().demerits_) + "\n");
204 if (optimal_paths.top ().demerits_ >= infinity_f)
205 warning (_ ("No feasible line breaking found"));
207 for (int i= final_breaks.size (); i--;)
209 Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
212 if (!cp.satisfies_constraints_)
213 warning ("Could not find line breaking that satisfies constraints.");
219 Gourlay_breaking::Gourlay_breaking ()
226 TODO: uniformity parameter to control rel. importance of spacing differences.
230 mixing break penalties and constraint-failing solutions is confusing.
233 Gourlay_breaking::combine_demerits (Column_x_positions const &prev,
234 Column_x_positions const &this_one) const
236 Real break_penalties = 0.0;
237 Grob * pc = this_one.cols_.top ();
240 SCM pen = pc->get_property ("penalty");
241 if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
243 break_penalties += scm_to_double (pen);
248 Q: do we want globally non-cramped lines, or locally equally
251 There used to be an example file input/test/uniform-breaking to
252 demonstrate problems with this approach. When music is gradually
253 becoming denser, the uniformity requirement makes lines go from
254 cramped to even more cramped (because going from cramped
255 3meas/line to relatively loose 2meas/line is such a big step.
259 Real demerit = abs (this_one.force_) + abs (prev.force_ - this_one.force_)
262 if (!this_one.satisfies_constraints_)
265 If it doesn't satisfy constraints, we make this one
268 add 20000 to the demerits, so that a break penalty
269 of -10000 won't change the result */
270 demerit = (demerit + 20000) >? 2000;