2 optimal-page-breaking.cc -- implement a page-breaker that
3 will break pages in such a way that both horizontal and
4 vertical spacing will be acceptable
6 source file of the GNU LilyPond music typesetter
8 (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
11 #include "international.hh"
12 #include "optimal-page-breaking.hh"
13 #include "output-def.hh"
14 #include "page-spacing.hh"
15 #include "paper-book.hh"
16 #include "paper-score.hh"
26 // FIXME: divide the page breaking into subproblems wherever there is a page break.
27 // This will allow us to tweak line-breaking independently on both sides of a
28 // page break (currently, we only get to request a number of systems for an entire score
29 // at a time), which is necessary for min-systems-per-page and \pageBreak to interact
31 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
32 : Page_breaking (pb, is_break)
36 Optimal_page_breaking::~Optimal_page_breaking ()
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);
46 SCM forced_page_count = book_->paper_->c_variable ("page-count");
48 set_to_ideal_line_configuration (0, end);
50 Page_spacing_result best;
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 for (vsize i = 0; i < current_configuration_count (); i++)
102 vsize min_p_count = min_page_count (i, first_page_num);
103 Page_spacing_result cur;
105 if (min_p_count == page_count || scm_is_integer (forced_page_count))
106 cur = space_systems_on_n_pages (i, page_count, first_page_num);
108 cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num);
110 if (cur.demerits_ < best_for_this_sys_count.demerits_)
112 best_for_this_sys_count = cur;
113 bound = current_configuration (i);
117 if (best_for_this_sys_count.demerits_ < best.demerits_)
119 best = best_for_this_sys_count;
120 best_division = bound;
123 /* Check to see if we already have too few systems. There are two ways
124 we check this: if we are trying one less than the ideal number of pages
125 and the pages are stretched on average then we have too
126 few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
127 have too few systems. In either case, though, we need to continue reducing
128 the number of systems if max-systems-per-page requires it. */
129 if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
131 if (best_for_this_sys_count.page_count () < page_count
132 && best_for_this_sys_count.average_force () > 0)
135 if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
140 /* try a larger number of systems than the ideal line breaking number. This
141 is more or less C&P, but the loop bounds make it difficult to try something
142 like do {...} while (flip(&d) != UP). */
143 bound = ideal_line_division;
144 for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
146 Real best_demerits_for_this_sys_count = infinity_f;
147 set_current_breakpoints (0, end, sys_count, bound);
149 for (vsize i = 0; i < current_configuration_count (); i++)
151 vsize min_p_count = min_page_count (i, first_page_num);
152 Page_spacing_result cur;
154 if (min_p_count > page_count)
157 cur = space_systems_on_n_pages (i, page_count, first_page_num);
159 if (cur.demerits_ < best.demerits_)
162 best_division = current_configuration (i);
165 if (cur.demerits_ < best_demerits_for_this_sys_count)
167 best_demerits_for_this_sys_count = cur.demerits_;
168 bound = current_configuration (i);
171 if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
172 && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
176 message (_ ("Drawing systems..."));
177 break_into_pieces (0, end, best_division);
178 SCM lines = systems ();
179 return make_pages (best.systems_per_page_, lines);