1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3 
4   Copyright (C) 2006--2021 Joe Neeman <joeneeman@gmail.com>
5 
6   LilyPond is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10 
11   LilyPond is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15 
16   You should have received a copy of the GNU General Public License
17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
18 */
19 
20 #ifndef CONSTRAINED_BREAKING_HH
21 #define CONSTRAINED_BREAKING_HH
22 
23 #include "lily-guile.hh"
24 #include "matrix.hh"
25 #include "prob.hh"
26 
27 #include <vector>
28 
29 class Paper_column;
30 
31 /*
32  * Begin/rest-of-line hack.  This geometrical shape is a crude approximation
33  * of Skyline, but it is better than a rectangle.
34  */
35 struct Line_shape
36 {
37   Interval begin_;
38   Interval rest_;
39 
Line_shapeLine_shape40   Line_shape ()
41   {
42   }
43   Line_shape (Interval begin, Interval rest);
44   Line_shape piggyback (Line_shape mount, Real padding) const;
45 };
46 
47 struct Line_details
48 {
49   Paper_column *last_column_;
50   Real force_;
51   Line_shape shape_;
52   std::vector<Real> footnote_heights_; /* The footnotes at the bottom of the
53                                    page, where each stencil represents
54                                    a different footnote. */
55   std::vector<Real> in_note_heights_; /* The in-notes under a system,
56                                    where each stencil represents
57                                    a different in-note. */
58   Interval refpoint_extent_; /* The refpoints of the first and last
59                                 spaceable staff in this line.  min-distance
60                                 should be measured from the bottom
61                                 refpoint_extent of one line to the
62                                 top refpoint_extent of the next. */
63   Real tallness_; /* Y-extent, adjusted according to begin/rest-of-line*/
64 
65   Real padding_;  /* compulsory space after this system (if we're not
66                      last on a page) */
67   Real title_padding_;
68   Real min_distance_;
69   Real title_min_distance_;
70   Real bottom_padding_;
71   Real space_;    /* spring length */
72   Real title_space_;
73   Real inverse_hooke_;
74 
75   SCM break_permission_;
76   SCM page_permission_;
77   SCM turn_permission_;
78   Real break_penalty_;
79   Real page_penalty_;
80   Real turn_penalty_;
81 
82   bool title_;
83 
84   /* The page-breaker deals with forbidden page breaks by "compressing"
85      two Line_detailses into one. The following fields are used by the
86      page-breaker to keep track of this. If the number of fields needed
87      by the page-breaker grows, it might be a good idea to create a separate
88      class. */
89   int compressed_lines_count_;
90   int compressed_nontitle_lines_count_;
91   bool last_markup_line_;
92   bool first_markup_line_;
93   bool tight_spacing_;
94 
Line_detailsLine_details95   Line_details ()
96   {
97     last_column_ = 0;
98     force_ = infinity_f;
99     padding_ = 0;
100     title_padding_ = 0;
101     bottom_padding_ = 0;
102     min_distance_ = 0;
103     title_min_distance_ = 0;
104     space_ = 0;
105     title_space_ = 0;
106     inverse_hooke_ = 1;
107     tight_spacing_ = false;
108     break_permission_ = ly_symbol2scm ("allow");
109     page_permission_ = ly_symbol2scm ("allow");
110     turn_permission_ = ly_symbol2scm ("allow");
111     break_penalty_ = 0;
112     page_penalty_ = 0;
113     turn_penalty_ = 0;
114     title_ = false;
115     compressed_lines_count_ = 1;
116     compressed_nontitle_lines_count_ = 1;
117     last_markup_line_ = false;
118     first_markup_line_ = false;
119     tallness_ = 0;
120     refpoint_extent_ = Interval (0, 0);
121   }
122 
123   Line_details (Prob *pb, Output_def *paper);
124   Real full_height () const;
125   Real tallness () const;
126   Real spring_length (Line_details const &next_line) const;
127 };
128 
129 /*
130    Helper to trace back an optimal path
131 */
132 struct Constrained_break_node
133 {
134   /* the number of bars in all the systems before this one
135   */
136   vsize prev_;
137 
138   /* unlike the Gourlay breaker, this is the sum of all demerits up to,
139    * and including, this line */
140   Real demerits_;
141   struct Line_details details_;
142 
Constrained_break_nodeConstrained_break_node143   Constrained_break_node ()
144   {
145     prev_ = VPOS;
146     demerits_ = infinity_f;
147   }
148 
printConstrained_break_node149   void print () const
150   {
151     printf ("prev break %zu, demerits %f\n", prev_, demerits_);
152   }
153 };
154 
155 /*
156    A dynamic programming solution to breaking scores into lines
157 */
158 class Constrained_breaking
159 {
160 public:
161   std::vector<Column_x_positions> solve (vsize start, vsize end, vsize sys_count);
162   std::vector<Column_x_positions> best_solution (vsize start, vsize end);
163   std::vector<Line_details> line_details (vsize start, vsize end, vsize sys_count);
164 
165   Constrained_breaking (Paper_score *ps);
166   Constrained_breaking (Paper_score *ps, std::vector<vsize> const &start_col_posns);
167 
168   vsize max_system_count (vsize start, vsize end) const;
169   vsize min_system_count (vsize start, vsize end);
170 
171 private:
172   Paper_score *pscore_;
173   vsize valid_systems_;
174   vsize systems_;
175   bool ragged_right_;
176   bool ragged_last_;
177 
178   Real system_system_min_distance_;
179   Real system_system_padding_;
180   Real system_system_space_;
181   Real system_markup_space_;
182   Real score_system_min_distance_;
183   Real score_system_padding_;
184   Real score_markup_min_distance_;
185   Real score_markup_padding_;
186 
187   /* the (i,j)th entry is the configuration for breaking between
188     columns i and j */
189   Matrix<Line_details> lines_;
190 
191   /* the [i](j,k)th entry is the score for fitting the first k bars onto the
192     first j systems, starting at the i'th allowed starting column */
193   std::vector<Matrix<Constrained_break_node> > state_;
194 
195   std::vector<vsize> start_;         /* the columns at which we might be asked to start breaking */
196   std::vector<vsize> starting_breakpoints_; /* the corresponding index in breaks_ */
197 
198   std::vector<Paper_column *> all_;
199   std::vector<vsize> breaks_;
200 
201   void initialize (Paper_score *, std::vector<vsize> const &break_col_indices);
202   void resize (vsize systems);
203 
204   Column_x_positions space_line (vsize start_col, vsize end_col);
205   vsize prepare_solution (vsize start, vsize end, vsize sys_count);
206 
207   Real combine_demerits (Real force, Real prev_force);
208 
209   bool calc_subproblem (vsize start, vsize systems, vsize max_break_index);
210   void fill_line_details (Line_details *, vsize, vsize);
211 };
212 #endif /* CONSTRAINED_BREAKING_HH */
213