2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2012 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 min_sys_count = max (min_sys_count, (vsize)1);
83 /* If systems-per-page and page-count are both specified, we know exactly
84 how many systems should be present. */
85 if (systems_per_page () > 0)
87 ideal_sys_count = systems_per_page () * page_count;
89 if (ideal_sys_count > max_system_count (0, end)
90 || ideal_sys_count < min_system_count (0, end))
92 warning (_ ("could not satisfy systems-per-page and page-count at the same time, ignoring systems-per-page"));
93 ideal_sys_count = system_count ();
94 min_sys_count = page_count;
98 set_current_breakpoints (0, end, ideal_sys_count);
99 min_sys_count = max_sys_count = ideal_sys_count;
100 ideal_line_division = best_division = current_configuration (0);
104 min_sys_count = page_count;
106 /* TODO: the following line will spit out programming errors if the
107 ideal line spacing doesn't fit on PAGE_COUNT pages */
108 best = space_systems_on_n_pages (0, page_count, first_page_num);
112 message (_ ("Fitting music on 1 page..."));
113 else if (scm_is_integer (forced_page_count) || page_count == 0)
114 message (_f ("Fitting music on %d pages...", (int)page_count));
116 message (_f ("Fitting music on %d or %d pages...", (int)page_count - 1, (int)page_count));
118 /* try a smaller number of systems than the ideal number for line breaking */
119 Line_division bound = ideal_line_division;
120 for (vsize sys_count = ideal_sys_count + 1; --sys_count >= min_sys_count;)
122 Page_spacing_result best_for_this_sys_count;
123 set_current_breakpoints (0, end, sys_count, Line_division (), bound);
125 if (debug_page_breaking_scoring)
126 message (_f ("trying %d systems", (int)sys_count));
128 for (vsize i = 0; i < current_configuration_count (); i++)
130 Page_spacing_result cur;
132 if (scm_is_integer (forced_page_count))
133 cur = space_systems_on_n_pages (i, page_count, first_page_num);
135 cur = space_systems_on_best_pages (i, first_page_num);
137 if (cur.demerits_ < best_for_this_sys_count.demerits_)
139 best_for_this_sys_count = cur;
140 bound = current_configuration (i);
144 if (debug_page_breaking_scoring)
145 message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
147 if (best_for_this_sys_count.demerits_ < best.demerits_)
149 best = best_for_this_sys_count;
150 best_division = bound;
153 /* Check to see if we already have too few systems. There are two ways
154 we check this: if we are trying one less than the ideal number of pages
155 and the pages are stretched on average then we have too
156 few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
157 have too few systems. In either case, though, we need to continue reducing
158 the number of systems if max-systems-per-page requires it. */
159 if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
161 if (best_for_this_sys_count.page_count () < page_count
162 && best_for_this_sys_count.average_force () > 0)
165 if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
170 /* try a larger number of systems than the ideal line breaking number. This
171 is more or less C&P. */
172 bound = ideal_line_division;
173 for (vsize sys_count = ideal_sys_count + 1; sys_count <= max_sys_count; sys_count++)
175 Real best_demerits_for_this_sys_count = infinity_f;
176 set_current_breakpoints (0, end, sys_count, bound);
178 if (debug_page_breaking_scoring)
179 message (_f ("trying %d systems", (int)sys_count));
181 for (vsize i = 0; i < current_configuration_count (); i++)
183 vsize min_p_count = min_page_count (i, first_page_num);
184 Page_spacing_result cur;
186 if (min_p_count > page_count)
188 else if (scm_is_integer (forced_page_count))
189 cur = space_systems_on_n_pages (i, page_count, first_page_num);
191 cur = space_systems_on_best_pages (i, first_page_num);
193 if (cur.demerits_ < best.demerits_)
196 best_division = current_configuration (i);
199 if (cur.demerits_ < best_demerits_for_this_sys_count)
201 best_demerits_for_this_sys_count = cur.demerits_;
202 bound = current_configuration (i);
206 if (debug_page_breaking_scoring)
207 message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
209 if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
210 && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
214 message (_ ("Drawing systems..."));
215 break_into_pieces (0, end, best_division);
216 SCM lines = systems ();
217 return make_pages (best.systems_per_page_, lines);