2 gourlay-breaking.cc -- implement Gourlay_breaking
4 source file of the GNU LilyPond music typesetter
6 (c) 1997--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
9 #include "gourlay-breaking.hh"
11 #include <cmath> // rint
15 #include "international.hh"
17 #include "output-def.hh"
18 #include "paper-column.hh"
19 #include "paper-score.hh"
20 #include "simple-spacer.hh"
24 /// How often to print operator pacification marks?
25 const int HAPPY_DOTS = 3;
28 Helper to trace back an optimal path
32 /** this was the previous. If negative, this break should not be
33 considered: this path has infinite energy
38 Which system number so far?
43 Column_x_positions line_config_;
54 printf ("prev break %d, line %d, demerits %f\n",
55 prev_break_, line_, demerits_);
60 print_break_nodes (std::vector<Break_node> const &arr)
62 for (vsize i = 0; i < arr.size (); i++)
64 printf ("node %d: ", i);
70 This algorithms is adapted from the OSU Tech report on breaking lines.
72 this function is longish, but not very complicated.
74 TODO: should rewrite. See the function in scm/page-layout.scm for
77 std::vector<Column_x_positions>
78 Gourlay_breaking::do_solve () const
80 std::vector<Break_node> optimal_paths;
82 = pscore_->root_system ()->columns ();
84 std::vector<int> breaks = find_break_indices ();
86 Break_node first_node;
87 optimal_paths.push_back (first_node);
89 bool ragged_right = to_boolean (pscore_->layout ()->c_variable ("raggedright"));
90 bool ragged_last = to_boolean (pscore_->layout ()->c_variable ("raggedlast"));
92 Real worst_force = 0.0;
93 for (vsize break_idx = 1; break_idx < breaks.size (); break_idx++)
96 start with a short line, add measures. At some point
97 the line becomes infeasible. Then we don't try to add more
99 int minimal_start_idx = -1;
100 Column_x_positions minimal_sol;
101 Column_x_positions backup_sol;
103 Real minimal_demerits = infinity_f;
105 for (vsize start_idx = break_idx; start_idx--;)
107 Link_array__Grob_ line (all.begin () + breaks[start_idx],
108 all.begin () + breaks[break_idx] + 1);
110 line[0] = dynamic_cast<Item *> (line[0])->find_prebroken_piece (RIGHT);
111 line.back () = dynamic_cast<Item *> (line.back ())->find_prebroken_piece (LEFT);
113 Column_x_positions cp;
117 = line_dimensions_int (pscore_->layout (), optimal_paths[start_idx].line_);
118 Simple_spacer_wrapper *sp = generate_spacing_problem (line, line_dims);
119 bool last_line = break_idx == breaks.size () - 1;
120 bool ragged = ragged_right
121 || (last_line && ragged_last);
123 sp->solve (&cp, ragged);
127 if (ragged && last_line)
130 if (fabs (cp.force_) > worst_force)
131 worst_force = fabs (cp.force_);
134 We remember this solution as a "should always work
135 solution", in case everything fucks up. */
136 if (start_idx == break_idx - 1)
141 if (optimal_paths[start_idx].demerits_ >= infinity_f)
142 this_demerits = infinity_f;
144 this_demerits = combine_demerits (optimal_paths[start_idx].line_config_, cp)
145 + optimal_paths[start_idx].demerits_;
147 if (this_demerits < minimal_demerits)
149 minimal_start_idx = start_idx;
151 minimal_demerits = this_demerits;
155 we couldn't satisfy the constraints, this won't get better
156 if we add more columns, so we get on with the next one
158 if (!cp.satisfies_constraints_)
163 if (minimal_start_idx < 0)
165 bnod.demerits_ = infinity_f;
166 bnod.line_config_ = backup_sol;
167 bnod.prev_break_ = break_idx - 1;
171 bnod.prev_break_ = minimal_start_idx;
172 bnod.demerits_ = minimal_demerits;
173 bnod.line_config_ = minimal_sol;
175 bnod.line_ = optimal_paths[bnod.prev_break_].line_ + 1;
176 optimal_paths.push_back (bnod);
178 if (! (break_idx % HAPPY_DOTS))
179 progress_indication (std::string ("[") + to_string (break_idx) + "]");
182 /* do the last one */
183 if (breaks.size () % HAPPY_DOTS)
184 progress_indication (std::string ("[") + to_string (breaks.size ()) + "]");
186 progress_indication ("\n");
188 std::vector<int> final_breaks;
189 std::vector<Column_x_positions> lines;
191 /* skip 0-th element, since it is a "dummy" elt*/
192 for (vsize i = optimal_paths.size () - 1; i > 0;)
194 final_breaks.push_back (i);
195 vsize prev = optimal_paths[i].prev_break_;
200 if (be_verbose_global)
202 message (_f ("Optimal demerits: %f",
203 optimal_paths.back ().demerits_) + "\n");
206 if (optimal_paths.back ().demerits_ >= infinity_f)
207 warning (_ ("no feasible line breaking found"));
209 for (vsize i = final_breaks.size (); i--;)
211 Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
213 lines.push_back (cp);
214 if (!cp.satisfies_constraints_)
215 warning (_ ("can't find line breaking that satisfies constraints"));
220 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_.back ();
239 SCM pen = pc->get_property ("penalty");
240 if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
241 break_penalties += scm_to_double (pen);
245 Q: do we want globally non-cramped lines, or locally equally
248 There used to be an example file input/test/uniform-breaking to
249 demonstrate problems with this approach. When music is gradually
250 becoming denser, the uniformity requirement makes lines go from
251 cramped to even more cramped (because going from cramped
252 3meas/line to relatively loose 2meas/line is such a big step.
256 Real demerit = abs (this_one.force_) + abs (prev.force_ - this_one.force_)
259 if (!this_one.satisfies_constraints_)
262 If it doesn't satisfy constraints, we make this one
265 add 20000 to the demerits, so that a break penalty
266 of -10000 won't change the result */
267 demerit = max ((demerit + 20000), 2000.0);