2 constrained-breaking.hh -- declare a line breaker that
3 supports limits on the number of systems
5 source file of the GNU LilyPond music typesetter
7 (c) 2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
10 #ifndef CONSTRAINED_BREAKING_HH
11 #define CONSTRAINED_BREAKING_HH
13 #include "break-algorithm.hh"
16 Helper to trace back an optimal path
18 struct Constrained_break_node
20 /* the number of bars in all the systems before this one
24 /* unlike the Gourlay breaker, this is the sum of all demerits up to,
25 * and including, this line */
29 Column_x_positions const *line_config_;
31 Constrained_break_node ()
34 demerits_ = infinity_f;
42 printf ("prev break %d, demerits %f\n",
48 A dynamic programming solution to breaking scores into lines
50 class Constrained_breaking : public Break_algorithm
53 std::vector<Column_x_positions> solve ();
54 Constrained_breaking ();
55 Constrained_breaking (std::vector<int> const &start_col_posns);
57 std::vector<Column_x_positions> get_solution(vsize start, vsize end, vsize sys_count);
58 Real get_demerits (vsize start, vsize end, vsize sys_count);
59 Real get_force (vsize start, vsize end, vsize sys_count);
60 Real get_penalty (vsize start, vsize end, vsize sys_count);
61 int get_max_systems (vsize start, vsize end);
62 int get_min_systems (vsize start, vsize end);
64 /* get the page penalty of system number sys with the given breaking */
65 Real get_page_penalty (vsize start, vsize end, vsize sys_count, vsize sys, bool turn);
67 void resize (vsize systems);
73 /* the (i,j)th entry is the column configuration for breaking between
75 std::vector<Column_x_positions> cols_;
78 /* the [i](j,k)th entry is the score for fitting the first k bars onto the
79 first j systems, starting at the i'th allowed starting column */
80 std::vector<std::vector<Constrained_break_node> > state_;
82 vector<int> start_; /* the columns at which we might be asked to start breaking */
83 vector<int> starting_breakpoints_; /* the corresponding index in breaks_ */
86 std::vector<int> breaks_;
88 Column_x_positions space_line (vsize start_col, vsize end_col);
89 void prepare_solution (vsize start, vsize end, vsize sys_count, vsize *rank, vsize *brk);
91 void combine_demerits (Column_x_positions const *, Column_x_positions const *,
92 Real *force, Real *pen, Real *dem) const;
94 bool calc_subproblem(vsize start, vsize systems, vsize max_break_index);
96 #endif /* CONSTRAINED_BREAKING_HH */