2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2014 Joe Neeman <joeneeman@gmail.com>
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.
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.
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/>.
20 #include "international.hh"
21 #include "optimal-page-breaking.hh"
22 #include "output-def.hh"
23 #include "page-spacing.hh"
24 #include "paper-book.hh"
25 #include "paper-score.hh"
29 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
30 : Page_breaking (pb, 0, 0)
34 Optimal_page_breaking::~Optimal_page_breaking ()
38 extern bool debug_page_breaking_scoring;
41 Optimal_page_breaking::solve ()
43 vsize end = last_break_position ();
44 vsize max_sys_count = max_system_count (0, end);
45 vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
47 set_to_ideal_line_configuration (0, end);
49 Page_spacing_result best;
50 SCM forced_page_count = book_->paper_->c_variable ("page-count");
51 vsize page_count = robust_scm2int (forced_page_count, 1);
52 Line_division ideal_line_division = current_configuration (0);
53 Line_division best_division = ideal_line_division;
54 vsize min_sys_count = 1;
56 // Note that system_count () only counts non-title systems.
57 vsize ideal_sys_count = system_count ();
59 if (!scm_is_integer (forced_page_count))
61 /* find out the ideal number of pages */
62 message (_ ("Finding the ideal number of pages..."));
64 best = space_systems_on_best_pages (0, first_page_num);
66 page_count = best.systems_per_page_.size ();
73 min_sys_count = ideal_sys_count - best.systems_per_page_.back ();
75 if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1)
76 min_sys_count -= best.systems_per_page_[page_count - 2];
78 if (min_sys_count > ideal_sys_count // subtraction wrapped around
79 || min_sys_count <= 0)
85 /* If systems-per-page and page-count are both specified, we know exactly
86 how many systems should be present. */
87 if (systems_per_page () > 0)
89 ideal_sys_count = systems_per_page () * page_count;
91 if (ideal_sys_count > max_system_count (0, end)
92 || ideal_sys_count < min_system_count (0, end))
94 warning (_ ("could not satisfy systems-per-page and page-count at the same time, ignoring systems-per-page"));
95 ideal_sys_count = system_count ();
96 min_sys_count = page_count;
100 set_current_breakpoints (0, end, ideal_sys_count);
101 min_sys_count = max_sys_count = ideal_sys_count;
102 ideal_line_division = best_division = current_configuration (0);
106 min_sys_count = page_count;
108 /* TODO: the following line will spit out programming errors if the
109 ideal line spacing doesn't fit on PAGE_COUNT pages */
110 best = space_systems_on_n_pages (0, page_count, first_page_num);
114 message (_ ("Fitting music on 1 page..."));
115 else if (scm_is_integer (forced_page_count) || page_count == 0)
116 message (_f ("Fitting music on %d pages...", (int)page_count));
118 message (_f ("Fitting music on %d or %d pages...", (int)page_count - 1, (int)page_count));
120 /* try a smaller number of systems than the ideal number for line breaking */
121 Line_division bound = ideal_line_division;
122 for (vsize sys_count = ideal_sys_count + 1; --sys_count >= min_sys_count;)
124 Page_spacing_result best_for_this_sys_count;
125 set_current_breakpoints (0, end, sys_count, Line_division (), bound);
127 if (debug_page_breaking_scoring)
128 message (_f ("trying %d systems", (int)sys_count));
130 for (vsize i = 0; i < current_configuration_count (); i++)
132 Page_spacing_result cur;
134 if (scm_is_integer (forced_page_count))
135 cur = space_systems_on_n_pages (i, page_count, first_page_num);
137 cur = space_systems_on_best_pages (i, first_page_num);
139 if (cur.demerits_ < best_for_this_sys_count.demerits_)
141 best_for_this_sys_count = cur;
142 bound = current_configuration (i);
146 if (debug_page_breaking_scoring)
147 message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
149 if (best_for_this_sys_count.demerits_ < best.demerits_)
151 best = best_for_this_sys_count;
152 best_division = bound;
155 /* Check to see if we already have too few systems. There are two ways
156 we check this: if we are trying one less than the ideal number of pages
157 and the pages are stretched on average then we have too
158 few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
159 have too few systems. In either case, though, we need to continue reducing
160 the number of systems if max-systems-per-page requires it. */
161 if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
163 if (best_for_this_sys_count.page_count () < page_count
164 && best_for_this_sys_count.average_force () > 0)
167 if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
172 /* try a larger number of systems than the ideal line breaking number. This
173 is more or less C&P. */
174 bound = ideal_line_division;
175 for (vsize sys_count = ideal_sys_count + 1; sys_count <= max_sys_count; sys_count++)
177 Real best_demerits_for_this_sys_count = infinity_f;
178 set_current_breakpoints (0, end, sys_count, bound);
180 if (debug_page_breaking_scoring)
181 message (_f ("trying %d systems", (int)sys_count));
183 for (vsize i = 0; i < current_configuration_count (); i++)
185 vsize min_p_count = min_page_count (i, first_page_num);
186 Page_spacing_result cur;
188 if (min_p_count > page_count)
190 else if (scm_is_integer (forced_page_count))
191 cur = space_systems_on_n_pages (i, page_count, first_page_num);
193 cur = space_systems_on_best_pages (i, first_page_num);
195 if (cur.demerits_ < best.demerits_)
198 best_division = current_configuration (i);
201 if (cur.demerits_ < best_demerits_for_this_sys_count)
203 best_demerits_for_this_sys_count = cur.demerits_;
204 bound = current_configuration (i);
208 if (debug_page_breaking_scoring)
209 message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
211 if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
212 && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
216 message (_ ("Drawing systems..."));
217 break_into_pieces (0, end, best_division);
218 SCM lines = systems ();
219 return make_pages (best.systems_per_page_, lines);