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;
56 // Note that Page_breaking only counts non-title systems in
57 // system_count (whereas Page_spacing_result::system_count counts
58 // titles and non-titles).
59 vsize ideal_sys_count = system_count ();
61 if (!scm_is_integer (forced_page_count))
63 /* find out the ideal number of pages */
64 message (_ ("Finding the ideal number of pages..."));
66 best = space_systems_on_best_pages (0, first_page_num);
68 page_count = best.systems_per_page_.size ();
69 min_sys_count = ideal_sys_count - best.systems_per_page_.back ();
71 if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1)
72 min_sys_count -= best.systems_per_page_[page_count - 2];
74 min_sys_count = max (min_sys_count, (vsize)1);
78 /* If systems-per-page and page-count are both specified, we know exactly
79 how many systems should be present. */
80 if (systems_per_page () > 0)
82 ideal_sys_count = systems_per_page () * page_count;
84 if (ideal_sys_count > max_system_count (0, end)
85 || ideal_sys_count < min_system_count (0, end))
87 warning (_ ("could not satisfy systems-per-page and page-count at the same time, ignoring systems-per-page"));
88 ideal_sys_count = system_count ();
89 min_sys_count = page_count;
93 set_current_breakpoints (0, end, ideal_sys_count);
94 min_sys_count = max_sys_count = ideal_sys_count;
95 ideal_line_division = best_division = current_configuration (0);
99 min_sys_count = page_count;
101 /* TODO: the following line will spit out programming errors if the
102 ideal line spacing doesn't fit on PAGE_COUNT pages */
103 best = space_systems_on_n_pages (0, page_count, first_page_num);
107 message (_ ("Fitting music on 1 page..."));
108 else if (scm_is_integer (forced_page_count))
109 message (_f ("Fitting music on %d pages...", (int)page_count));
111 message (_f ("Fitting music on %d or %d pages...", (int)page_count-1, (int)page_count));
113 /* try a smaller number of systems than the ideal number for line breaking */
114 Line_division bound = ideal_line_division;
115 for (vsize sys_count = ideal_sys_count + 1; --sys_count >= min_sys_count;)
117 Page_spacing_result best_for_this_sys_count;
118 set_current_breakpoints (0, end, sys_count, Line_division (), bound);
120 if (debug_page_breaking_scoring)
121 message (_f ("trying %d systems", (int)sys_count));
123 for (vsize i = 0; i < current_configuration_count (); i++)
125 Page_spacing_result cur;
127 if (scm_is_integer (forced_page_count))
128 cur = space_systems_on_n_pages (i, page_count, first_page_num);
130 cur = space_systems_on_best_pages (i, first_page_num);
132 if (cur.demerits_ < best_for_this_sys_count.demerits_)
134 best_for_this_sys_count = cur;
135 bound = current_configuration (i);
139 if (debug_page_breaking_scoring)
140 message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
142 if (best_for_this_sys_count.demerits_ < best.demerits_)
144 best = best_for_this_sys_count;
145 best_division = bound;
148 /* Check to see if we already have too few systems. There are two ways
149 we check this: if we are trying one less than the ideal number of pages
150 and the pages are stretched on average then we have too
151 few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
152 have too few systems. In either case, though, we need to continue reducing
153 the number of systems if max-systems-per-page requires it. */
154 if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
156 if (best_for_this_sys_count.page_count () < page_count
157 && best_for_this_sys_count.average_force () > 0)
160 if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
165 /* try a larger number of systems than the ideal line breaking number. This
166 is more or less C&P, but the loop bounds make it difficult to try something
167 like do {...} while (flip(&d) != UP). */
168 bound = ideal_line_division;
169 for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
171 Real best_demerits_for_this_sys_count = infinity_f;
172 set_current_breakpoints (0, end, sys_count, bound);
174 if (debug_page_breaking_scoring)
175 message (_f ("trying %d systems", (int)sys_count));
177 for (vsize i = 0; i < current_configuration_count (); i++)
179 vsize min_p_count = min_page_count (i, first_page_num);
180 Page_spacing_result cur;
182 if (min_p_count > page_count)
184 else if (scm_is_integer (forced_page_count))
185 cur = space_systems_on_n_pages (i, page_count, first_page_num);
187 cur = space_systems_on_best_pages (i, first_page_num);
189 if (cur.demerits_ < best.demerits_)
192 best_division = current_configuration (i);
195 if (cur.demerits_ < best_demerits_for_this_sys_count)
197 best_demerits_for_this_sys_count = cur.demerits_;
198 bound = current_configuration (i);
202 if (debug_page_breaking_scoring)
203 message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
205 if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
206 && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
210 message (_ ("Drawing systems..."));
211 break_into_pieces (0, end, best_division);
212 SCM lines = systems ();
213 return make_pages (best.systems_per_page_, lines);