2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2010 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 if (systems_per_page () > 0)
63 best = space_systems_with_fixed_number_per_page (0, first_page_num);
65 best = space_systems_on_best_pages (0, first_page_num);
67 page_count = best.systems_per_page_.size ();
68 ideal_sys_count = best.system_count ();
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 /* TODO: the following line will spit out programming errors if the
79 ideal line spacing doesn't fit on PAGE_COUNT pages */
80 /* TODO: the interaction between systems_per_page and page_count needs to
82 best = space_systems_on_n_pages (0, page_count, first_page_num);
83 min_sys_count = page_count;
87 message (_ ("Fitting music on 1 page..."));
88 else if (scm_is_integer (forced_page_count))
89 message (_f ("Fitting music on %d pages...", (int)page_count));
91 message (_f ("Fitting music on %d or %d pages...", (int)page_count-1, (int)page_count));
93 /* try a smaller number of systems than the ideal number for line breaking */
94 Line_division bound = ideal_line_division;
95 for (vsize sys_count = ideal_sys_count; --sys_count >= min_sys_count;)
97 Page_spacing_result best_for_this_sys_count;
98 set_current_breakpoints (0, end, sys_count, Line_division (), bound);
100 if (debug_page_breaking_scoring)
101 message (_f ("trying %d systems", (int)sys_count));
103 for (vsize i = 0; i < current_configuration_count (); i++)
105 vsize min_p_count = min_page_count (i, first_page_num);
106 Page_spacing_result cur;
108 if (min_p_count == page_count || scm_is_integer (forced_page_count))
109 cur = space_systems_on_n_pages (i, page_count, first_page_num);
111 cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num, 0);
113 if (cur.demerits_ < best_for_this_sys_count.demerits_)
115 best_for_this_sys_count = cur;
116 bound = current_configuration (i);
120 if (debug_page_breaking_scoring)
121 message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
123 if (best_for_this_sys_count.demerits_ < best.demerits_)
125 best = best_for_this_sys_count;
126 best_division = bound;
129 /* Check to see if we already have too few systems. There are two ways
130 we check this: if we are trying one less than the ideal number of pages
131 and the pages are stretched on average then we have too
132 few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
133 have too few systems. In either case, though, we need to continue reducing
134 the number of systems if max-systems-per-page requires it. */
135 if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
137 if (best_for_this_sys_count.page_count () < page_count
138 && best_for_this_sys_count.average_force () > 0)
141 if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
146 /* try a larger number of systems than the ideal line breaking number. This
147 is more or less C&P, but the loop bounds make it difficult to try something
148 like do {...} while (flip(&d) != UP). */
149 bound = ideal_line_division;
150 for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
152 Real best_demerits_for_this_sys_count = infinity_f;
153 set_current_breakpoints (0, end, sys_count, bound);
155 if (debug_page_breaking_scoring)
156 message (_f ("trying %d systems", (int)sys_count));
158 for (vsize i = 0; i < current_configuration_count (); i++)
160 vsize min_p_count = min_page_count (i, first_page_num);
161 Page_spacing_result cur;
163 if (min_p_count > page_count)
166 cur = space_systems_on_n_pages (i, page_count, first_page_num);
168 if (cur.demerits_ < best.demerits_)
171 best_division = current_configuration (i);
174 if (cur.demerits_ < best_demerits_for_this_sys_count)
176 best_demerits_for_this_sys_count = cur.demerits_;
177 bound = current_configuration (i);
181 if (debug_page_breaking_scoring)
182 message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
184 if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
185 && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
189 message (_ ("Drawing systems..."));
190 break_into_pieces (0, end, best_division);
191 SCM lines = systems ();
192 return make_pages (best.systems_per_page_, lines);