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>
8 #include <math.h> // rint
11 #include "gourlay-breaking.hh"
12 #include "column-x-positions.hh"
15 #include "paper-column.hh"
16 #include "paper-score.hh"
17 #include "output-def.hh"
18 #include "simple-spacer.hh"
21 /// How often to print operator pacification marks?
22 const int HAPPY_DOTS_I = 3;
25 Helper to trace back an optimal path
28 /** this was the previous. If negative, this break should not be
29 considered: this path has infinite energy
34 Which system number so far?
39 Column_x_positions line_config_;
50 printf ("prev break %d, line %d, demerits %f\n",
51 prev_break_, line_, demerits_);
56 print_break_nodes (Array<Break_node> const & arr)
58 for (int i =0; i < arr.size (); i++)
60 printf ( "node %d: ", i);
66 This algorithms is adapted from the OSU Tech report on breaking lines.
68 this function is longish, but not very complicated.
70 TODO: should rewrite. See the function in scm/page-layout.scm for
74 Array<Column_x_positions>
75 Gourlay_breaking::do_solve () const
77 Array<Break_node> optimal_paths;
78 Link_array<Grob> all =
79 pscore_->system_->columns ();
81 Array<int> breaks = find_break_indices ();
83 Break_node first_node ;
84 optimal_paths.push (first_node);
86 bool ragged_right = to_boolean (pscore_->paper_->c_variable ("raggedright"));
87 bool ragged_last = to_boolean (pscore_->paper_->c_variable ("raggedlast"));
89 Real worst_force = 0.0;
90 for (int break_idx = 1; break_idx< breaks.size (); break_idx++)
93 start with a short line, add measures. At some point
94 the line becomes infeasible. Then we don't try to add more
96 int minimal_start_idx = -1;
97 Column_x_positions minimal_sol;
98 Column_x_positions backup_sol;
100 Real minimal_demerits = infinity_f;
102 for (int start_idx = break_idx; start_idx--;)
104 Link_array<Grob> line = all.slice (breaks[start_idx], breaks[break_idx]+1);
106 line[0] = dynamic_cast<Item*> (line[0])->find_prebroken_piece (RIGHT);
107 line.top () = dynamic_cast<Item*> (line.top ())->find_prebroken_piece (LEFT);
109 Column_x_positions cp;
113 = line_dimensions_int (pscore_->paper_, optimal_paths[start_idx].line_);
114 Simple_spacer_wrapper * sp = generate_spacing_problem (line, line_dims);
115 bool last_line = break_idx == breaks.size ()-1;
116 bool ragged = ragged_right
117 || (last_line && ragged_last);
119 sp->solve (&cp, ragged);
123 if (ragged && last_line)
126 if (fabs (cp.force_) > worst_force)
127 worst_force = fabs (cp.force_);
130 We remember this solution as a "should always work
131 solution", in case everything fucks up. */
132 if (start_idx == break_idx - 1)
137 if (optimal_paths[start_idx].demerits_ >= infinity_f)
138 this_demerits = infinity_f;
140 this_demerits = combine_demerits (optimal_paths[start_idx].line_config_, cp)
141 + optimal_paths[start_idx].demerits_;
143 if (this_demerits < minimal_demerits)
145 minimal_start_idx = start_idx;
147 minimal_demerits = this_demerits;
151 we couldn't satisfy the constraints, this won't get better
152 if we add more columns, so we get on with the next one
154 if (!cp.satisfies_constraints_)
160 if (minimal_start_idx < 0)
162 bnod.demerits_ = infinity_f;
163 bnod.line_config_ = backup_sol;
164 bnod.prev_break_ = break_idx - 1;
168 bnod.prev_break_ = minimal_start_idx;
169 bnod.demerits_ = minimal_demerits;
170 bnod.line_config_ = minimal_sol;
172 bnod.line_ = optimal_paths[bnod.prev_break_].line_ + 1;
173 optimal_paths.push (bnod);
175 if (! (break_idx % HAPPY_DOTS_I))
176 progress_indication (String ("[") + to_string (break_idx) + "]");
179 /* do the last one */
180 if (breaks.size () % HAPPY_DOTS_I)
181 progress_indication (String ("[") + to_string (breaks.size ()) + "]");
183 progress_indication ("\n");
185 Array<int> final_breaks;
186 Array<Column_x_positions> lines;
188 /* skip 0-th element, since it is a "dummy" elt*/
189 for (int i = optimal_paths.size ()-1; i> 0;)
191 final_breaks.push (i);
192 int prev = optimal_paths[i].prev_break_;
197 if (verbose_global_b)
199 progress_indication (_f ("Optimal demerits: %f",
200 optimal_paths.top ().demerits_) + "\n");
203 if (optimal_paths.top ().demerits_ >= infinity_f)
204 warning (_ ("No feasible line breaking found"));
206 for (int i= final_breaks.size (); i--;)
208 Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
211 if (!cp.satisfies_constraints_)
212 warning ("Could not find line breaking that satisfies constraints.");
218 Gourlay_breaking::Gourlay_breaking ()
225 TODO: uniformity parameter to control rel. importance of spacing differences.
229 mixing break penalties and constraint-failing solutions is confusing.
232 Gourlay_breaking::combine_demerits (Column_x_positions const &prev,
233 Column_x_positions const &this_one) const
235 Real break_penalties = 0.0;
236 Grob * pc = this_one.cols_.top ();
239 SCM pen = pc->get_property ("penalty");
240 if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
242 break_penalties += scm_to_double (pen);
247 Q: do we want globally non-cramped lines, or locally equally
250 There used to be an example file input/test/uniform-breaking to
251 demonstrate problems with this approach. When music is gradually
252 becoming denser, the uniformity requirement makes lines go from
253 cramped to even more cramped (because going from cramped
254 3meas/line to relatively loose 2meas/line is such a big step.
258 Real demerit = abs (this_one.force_) + abs (prev.force_ - this_one.force_)
261 if (!this_one.satisfies_constraints_)
264 If it doesn't satisfy constraints, we make this one
267 add 20000 to the demerits, so that a break penalty
268 of -10000 won't change the result */
269 demerit = (demerit + 20000) >? 2000;