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--2007 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"
23 (void) g
; /* shutup warning */
27 Optimal_page_breaking::Optimal_page_breaking (Paper_book
*pb
)
28 : Page_breaking (pb
, is_break
)
32 Optimal_page_breaking::~Optimal_page_breaking ()
37 Optimal_page_breaking::solve ()
39 vsize end
= last_break_position ();
40 vsize max_sys_count
= max_system_count (0, end
);
41 vsize first_page_num
= robust_scm2int (book_
->paper_
->c_variable ("first-page-number"), 1);
43 /* find out the ideal number of pages */
44 message (_ ("Finding the ideal number of pages..."));
45 set_to_ideal_line_configuration (0, end
);
47 Page_spacing_result best
= space_systems_on_best_pages (0, first_page_num
);
48 vsize page_count
= best
.systems_per_page_
.size ();
49 Line_division ideal_line_division
= current_configuration (0);
50 Line_division best_division
= ideal_line_division
;
52 vsize ideal_sys_count
= best
.system_count ();
53 vsize min_sys_count
= ideal_sys_count
- best
.systems_per_page_
.back ();
56 min_sys_count
-= best
.systems_per_page_
[page_count
- 2];
59 message (_ ("Fitting music on 1 page..."));
61 message (_f ("Fitting music on %d or %d pages...", (int)page_count
-1, (int)page_count
));
63 /* try a smaller number of systems than the ideal number for line breaking */
64 Line_division bound
= ideal_line_division
;
65 for (vsize sys_count
= ideal_sys_count
; --sys_count
>= min_sys_count
;)
67 Page_spacing_result best_for_this_sys_count
;
68 set_current_breakpoints (0, end
, sys_count
, Line_division (), bound
);
70 for (vsize i
= 0; i
< current_configuration_count (); i
++)
72 vsize min_p_count
= min_page_count (i
, first_page_num
);
73 Page_spacing_result cur
;
75 if (min_p_count
> page_count
)
77 else if (min_p_count
== page_count
)
78 cur
= space_systems_on_n_pages (i
, page_count
, first_page_num
);
80 cur
= space_systems_on_n_or_one_more_pages (i
, page_count
-1, first_page_num
);
82 if (cur
.demerits_
< best_for_this_sys_count
.demerits_
|| isinf (best_for_this_sys_count
.demerits_
))
84 best_for_this_sys_count
= cur
;
85 bound
= current_configuration (i
);
89 if (best_for_this_sys_count
.demerits_
< best
.demerits_
|| isinf (best
.demerits_
))
91 best
= best_for_this_sys_count
;
92 best_division
= bound
;
95 /* if the pages are stretched on average, stop trying to reduce sys_count */
96 if (best_for_this_sys_count
.page_count () < page_count
97 && best_for_this_sys_count
.average_force () > 0)
101 if (isinf (best_for_this_sys_count
.demerits_
))
105 /* try a larger number of systems than the ideal line breaking number. This
106 is more or less C&P, but the loop bounds make it difficult to try something
107 like do {...} while (flip(&d) != UP). */
108 bound
= ideal_line_division
;
109 for (vsize sys_count
= ideal_sys_count
+1; sys_count
<= max_sys_count
; sys_count
++)
111 Real best_demerits_for_this_sys_count
= infinity_f
;
112 set_current_breakpoints (0, end
, sys_count
, bound
);
114 for (vsize i
= 0; i
< current_configuration_count (); i
++)
116 vsize min_p_count
= min_page_count (i
, first_page_num
);
117 Page_spacing_result cur
;
119 if (min_p_count
> page_count
)
122 cur
= space_systems_on_n_pages (i
, page_count
, first_page_num
);
124 if (cur
.demerits_
< best
.demerits_
|| isinf (best
.demerits_
))
127 best_division
= current_configuration (i
);
130 if (cur
.demerits_
< best_demerits_for_this_sys_count
|| isinf (best_demerits_for_this_sys_count
))
132 best_demerits_for_this_sys_count
= cur
.demerits_
;
133 bound
= current_configuration (i
);
136 if (isinf (best_demerits_for_this_sys_count
))
140 message ("Drawing systems...");
141 break_into_pieces (0, end
, best_division
);
142 SCM lines
= systems ();
143 return make_pages (best
.systems_per_page_
, lines
);