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