2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2009 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"
32 return g->get_property ("page-break-permission") == ly_symbol2scm ("force");
35 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
36 : Page_breaking (pb, is_break)
40 Optimal_page_breaking::~Optimal_page_breaking ()
44 // Solves the subproblem betwen the (END-1)th \pageBreak and the
46 // Returns a vector of systems per page for the pages within this chunk.
48 Optimal_page_breaking::solve_chunk (vsize end)
50 vsize max_sys_count = max_system_count (end-1, end);
51 vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
52 SCM forced_page_count = book_->paper_->c_variable ("page-count");
54 set_to_ideal_line_configuration (end-1, end);
56 Page_spacing_result best;
57 vsize page_count = robust_scm2int (forced_page_count, 1);
58 Line_division ideal_line_division = current_configuration (0);
59 Line_division best_division = ideal_line_division;
60 vsize min_sys_count = 1;
61 vsize ideal_sys_count = system_count ();
63 if (!scm_is_integer (forced_page_count))
65 if (systems_per_page () > 0)
66 best = space_systems_with_fixed_number_per_page (0, first_page_num);
68 best = space_systems_on_best_pages (0, first_page_num);
70 page_count = best.systems_per_page_.size ();
71 ideal_sys_count = best.system_count ();
72 min_sys_count = ideal_sys_count - best.systems_per_page_.back ();
74 if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1)
75 min_sys_count -= best.systems_per_page_[page_count - 2];
77 min_sys_count = max (min_sys_count, (vsize)1);
81 /* TODO: the following line will spit out programming errors if the
82 ideal line spacing doesn't fit on PAGE_COUNT pages */
83 /* TODO: the interaction between systems_per_page and page_count needs to
85 best = space_systems_on_n_pages (0, page_count, first_page_num);
86 min_sys_count = page_count;
89 if (page_count == 1 || scm_is_integer (forced_page_count))
90 progress_indication (_f ("[%d: %d pages]", (int) end, (int) page_count));
92 progress_indication (_f ("[%d: %d or %d pages]", (int) end, (int) page_count-1, (int)page_count));
94 /* try a smaller number of systems than the ideal number for line breaking */
95 Line_division bound = ideal_line_division;
96 for (vsize sys_count = ideal_sys_count; --sys_count >= min_sys_count;)
98 Page_spacing_result best_for_this_sys_count;
99 set_current_breakpoints (end-1, end, sys_count, Line_division (), bound);
101 for (vsize i = 0; i < current_configuration_count (); i++)
103 vsize min_p_count = min_page_count (i, first_page_num);
104 Page_spacing_result cur;
106 if (min_p_count == page_count || scm_is_integer (forced_page_count))
107 cur = space_systems_on_n_pages (i, page_count, first_page_num);
109 cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num);
111 if (cur.demerits_ < best_for_this_sys_count.demerits_)
113 best_for_this_sys_count = cur;
114 bound = current_configuration (i);
118 if (best_for_this_sys_count.demerits_ < best.demerits_)
120 best = best_for_this_sys_count;
121 best_division = bound;
124 /* Check to see if we already have too few systems. There are two ways
125 we check this: if we are trying one less than the ideal number of pages
126 and the pages are stretched on average then we have too
127 few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
128 have too few systems. In either case, though, we need to continue reducing
129 the number of systems if max-systems-per-page requires it. */
130 if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
132 if (best_for_this_sys_count.page_count () < page_count
133 && best_for_this_sys_count.average_force () > 0)
136 if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
141 /* try a larger number of systems than the ideal line breaking number. This
142 is more or less C&P, but the loop bounds make it difficult to try something
143 like do {...} while (flip(&d) != UP). */
144 bound = ideal_line_division;
145 for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
147 Real best_demerits_for_this_sys_count = infinity_f;
148 set_current_breakpoints (end-1, end, sys_count, bound);
150 for (vsize i = 0; i < current_configuration_count (); i++)
152 vsize min_p_count = min_page_count (i, first_page_num);
153 Page_spacing_result cur;
155 if (min_p_count > page_count)
158 cur = space_systems_on_n_pages (i, page_count, first_page_num);
160 if (cur.demerits_ < best.demerits_)
163 best_division = current_configuration (i);
166 if (cur.demerits_ < best_demerits_for_this_sys_count)
168 best_demerits_for_this_sys_count = cur.demerits_;
169 bound = current_configuration (i);
172 if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
173 && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
176 break_into_pieces (end-1, end, best_division);
178 return best.systems_per_page_;
182 Optimal_page_breaking::solve ()
184 vector<vsize> systems_per_page;
186 message (_f ("Solving %d page-breaking chunks...", last_break_position ()));
187 for (vsize end = 1; end <= last_break_position (); ++end)
189 vector<vsize> chunk_systems = solve_chunk (end);
190 systems_per_page.insert (systems_per_page.end (), chunk_systems.begin (), chunk_systems.end ());
193 message (_ ("Drawing systems..."));
194 SCM lines = systems ();
195 return make_pages (systems_per_page, lines);