2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2011 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;
55 vsize ideal_sys_count = system_count ();
57 if (!scm_is_integer (forced_page_count))
59 /* find out the ideal number of pages */
60 message (_ ("Finding the ideal number of pages..."));
62 best = space_systems_on_best_pages (0, first_page_num);
64 page_count = best.systems_per_page_.size ();
65 ideal_sys_count = best.system_count ();
66 min_sys_count = ideal_sys_count - best.systems_per_page_.back ();
68 if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1)
69 min_sys_count -= best.systems_per_page_[page_count - 2];
71 min_sys_count = max (min_sys_count, (vsize)1);
75 /* If systems-per-page and page-count are both specified, we know exactly
76 how many systems should be present. */
77 if (systems_per_page () > 0)
79 ideal_sys_count = systems_per_page () * page_count;
81 if (ideal_sys_count > max_system_count (0, end)
82 || ideal_sys_count < min_system_count (0, end))
84 warning (_ ("could not satisfy systems-per-page and page-count at the same time, ignoring systems-per-page"));
85 ideal_sys_count = best.system_count ();
86 min_sys_count = page_count;
90 set_current_breakpoints (0, end, ideal_sys_count);
91 min_sys_count = max_sys_count = ideal_sys_count;
92 ideal_line_division = best_division = current_configuration (0);
96 min_sys_count = page_count;
98 /* TODO: the following line will spit out programming errors if the
99 ideal line spacing doesn't fit on PAGE_COUNT pages */
100 best = space_systems_on_n_pages (0, page_count, first_page_num);
104 message (_ ("Fitting music on 1 page..."));
105 else if (scm_is_integer (forced_page_count))
106 message (_f ("Fitting music on %d pages...", (int)page_count));
108 message (_f ("Fitting music on %d or %d pages...", (int)page_count-1, (int)page_count));
110 /* try a smaller number of systems than the ideal number for line breaking */
111 Line_division bound = ideal_line_division;
112 for (vsize sys_count = ideal_sys_count + 1; --sys_count >= min_sys_count;)
114 Page_spacing_result best_for_this_sys_count;
115 set_current_breakpoints (0, end, sys_count, Line_division (), bound);
117 if (debug_page_breaking_scoring)
118 message (_f ("trying %d systems", (int)sys_count));
120 for (vsize i = 0; i < current_configuration_count (); i++)
122 Page_spacing_result cur;
124 if (scm_is_integer (forced_page_count))
125 cur = space_systems_on_n_pages (i, page_count, first_page_num);
127 cur = space_systems_on_best_pages (i, first_page_num);
129 if (cur.demerits_ < best_for_this_sys_count.demerits_)
131 best_for_this_sys_count = cur;
132 bound = current_configuration (i);
136 if (debug_page_breaking_scoring)
137 message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
139 if (best_for_this_sys_count.demerits_ < best.demerits_)
141 best = best_for_this_sys_count;
142 best_division = bound;
145 /* Check to see if we already have too few systems. There are two ways
146 we check this: if we are trying one less than the ideal number of pages
147 and the pages are stretched on average then we have too
148 few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
149 have too few systems. In either case, though, we need to continue reducing
150 the number of systems if max-systems-per-page requires it. */
151 if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
153 if (best_for_this_sys_count.page_count () < page_count
154 && best_for_this_sys_count.average_force () > 0)
157 if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
162 /* try a larger number of systems than the ideal line breaking number. This
163 is more or less C&P, but the loop bounds make it difficult to try something
164 like do {...} while (flip(&d) != UP). */
165 bound = ideal_line_division;
166 for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
168 Real best_demerits_for_this_sys_count = infinity_f;
169 set_current_breakpoints (0, end, sys_count, bound);
171 if (debug_page_breaking_scoring)
172 message (_f ("trying %d systems", (int)sys_count));
174 for (vsize i = 0; i < current_configuration_count (); i++)
176 vsize min_p_count = min_page_count (i, first_page_num);
177 Page_spacing_result cur;
179 if (min_p_count > page_count)
181 else if (scm_is_integer (forced_page_count))
182 cur = space_systems_on_n_pages (i, page_count, first_page_num);
184 cur = space_systems_on_best_pages (i, first_page_num);
186 if (cur.demerits_ < best.demerits_)
189 best_division = current_configuration (i);
192 if (cur.demerits_ < best_demerits_for_this_sys_count)
194 best_demerits_for_this_sys_count = cur.demerits_;
195 bound = current_configuration (i);
199 if (debug_page_breaking_scoring)
200 message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
202 if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
203 && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
207 message (_ ("Drawing systems..."));
208 break_into_pieces (0, end, best_division);
209 SCM lines = systems ();
210 return make_pages (best.systems_per_page_, lines);