]> git.donarmstrong.com Git - lilypond.git/blob - lily/page-turn-page-breaking.cc
Doc-es: Update of Input.
[lilypond.git] / lily / page-turn-page-breaking.cc
1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3
4   Copyright (C) 2006--2009 Joe Neeman <joeneeman@gmail.com>
5
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.
10
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.
15
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/>.
18 */
19
20 #include "page-turn-page-breaking.hh"
21
22 #include "international.hh"
23 #include "item.hh"
24 #include "output-def.hh"
25 #include "page-spacing.hh"
26 #include "paper-book.hh"
27 #include "paper-score.hh"
28 #include "paper-system.hh"
29 #include "system.hh"
30 #include "warn.hh"
31
32 static bool
33 is_break (Grob *g)
34 {
35   bool turnable = scm_is_symbol (g->get_property ("page-turn-permission"));
36
37   if (turnable &&
38       (!scm_is_symbol (g->get_property ("page-break-permission"))
39        || !scm_is_symbol (g->get_property ("line-break-permission"))))
40     {
41       programming_error ("found a page-turnable place which was not breakable");
42       turnable = false;
43     }
44
45   return turnable;
46 }
47
48 Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb)
49   : Page_breaking (pb, is_break)
50 {
51 }
52
53 Page_turn_page_breaking::~Page_turn_page_breaking ()
54 {
55 }
56
57 Page_turn_page_breaking::Break_node
58 Page_turn_page_breaking::put_systems_on_pages (vsize start,
59                                                vsize end,
60                                                vsize configuration,
61                                                vsize page_number)
62 {
63   vsize min_p_count = min_page_count (configuration, page_number);
64   bool auto_first = to_boolean (book_->paper_->c_variable ("auto-first-page-number"));
65
66   /* If [START, END] does not contain an intermediate
67      breakpoint, we may need to consider solutions that result in a bad turn.
68      In this case, we won't abort if the min_page_count is too big */
69   if (start < end - 1 && min_p_count + (auto_first ? 0 : (page_number % 2)) > 2)
70     return Break_node ();
71
72   /* if PAGE-NUMBER is odd, we are starting on a right hand page. That is, we
73      have the options
74      PAGE-NUMBER odd:
75        - even number of pages + a blank page
76        - odd number of pages
77      PAGE-NUMBER even:
78        - odd number of pages + a blank page
79        - even number of pages
80
81      No matter which case PAGE-NUMBER falls into, we take the second choice if
82      min_p_count has that evenness. (For example, if PAGE-NUMBER is even and
83      min_p_count is even, we don't even consider the blank page option). */
84
85   Page_spacing_result result;
86   if (start == 0 && auto_first)
87     {
88       if (min_p_count % 2)
89         result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number, 0);
90       else
91         result = space_systems_on_n_pages (configuration, min_p_count, page_number);
92     }
93   else if (page_number % 2 == min_p_count % 2)
94     result = space_systems_on_n_pages (configuration, min_p_count, page_number);
95   else
96     result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number, blank_page_penalty ());
97
98   Break_node ret;
99   ret.prev_ = start - 1;
100   ret.break_pos_ = end;
101   ret.page_count_ = result.force_.size ();
102   ret.first_page_number_ = page_number;
103   if (auto_first && start == 0)
104     ret.first_page_number_ += 1 - (ret.page_count_ % 2);
105
106   ret.div_ = current_configuration (configuration);
107   ret.system_count_ = result.systems_per_page_;
108
109   ret.too_many_lines_ = all_lines_stretched (configuration);
110   ret.demerits_ = result.demerits_;
111   if (start > 0)
112     ret.demerits_ += state_[start-1].demerits_;
113
114   return ret;
115 }
116
117 /* The number of pages taken up by a Break_node, including
118    the blank page if there is one */
119 vsize
120 Page_turn_page_breaking::total_page_count (Break_node const &b)
121 {
122   vsize end = b.first_page_number_ + b.page_count_;
123   return end - 1 + (end % 2) - b.first_page_number_;
124 }
125
126 extern bool debug_page_breaking_scoring;
127
128 void
129 Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint)
130 {
131   vsize end = ending_breakpoint + 1;
132   Break_node best;
133   Break_node cur;
134   Break_node this_start_best;
135   vsize prev_best_system_count = 0;
136
137   for (vsize start = end; start--;)
138     {
139       if (start < end-1
140           && breakpoint_property (start+1, "page-turn-permission") == ly_symbol2scm ("force"))
141         break;
142
143       if (start > 0 && best.demerits_ < state_[start-1].demerits_)
144         continue;
145
146       int p_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
147       if (start > 0)
148         {
149           /* except possibly for the first page, enforce the fact that first_page_number_
150              should always be even (left hand page).
151              TODO: are there different conventions in right-to-left languages?
152           */
153           p_num = state_[start-1].first_page_number_ + state_[start-1].page_count_;
154           p_num += p_num % 2;
155         }
156
157       Line_division min_division;
158       Line_division max_division;
159
160       vsize min_sys_count = min_system_count (start, end);
161       vsize max_sys_count = max_system_count (start, end);
162       this_start_best.demerits_ = infinity_f;
163
164       bool ok_page = true;
165
166       if (debug_page_breaking_scoring)
167         message (_f ("page-turn-page-breaking: breaking from %d to %d", (int) start, (int) end));
168
169       /* heuristic: we've just added a breakpoint, we'll need at least as
170          many systems as before */
171       min_sys_count = max (min_sys_count, prev_best_system_count);
172       for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++)
173         {
174           set_current_breakpoints (start, end, sys_count, min_division, max_division);
175           bool found = false;
176
177           for (vsize i = 0; i < current_configuration_count (); i++)
178             {
179               cur = put_systems_on_pages (start, end, i, p_num);
180
181               if (isinf (cur.demerits_)
182                   || (cur.page_count_  + (p_num % 2) > 2
183                       && (!isinf (this_start_best.demerits_))
184                       && total_page_count (cur) > total_page_count (this_start_best)))
185                 {
186                   ok_page = false;
187                   break;
188                 }
189
190               if (cur.demerits_ < this_start_best.demerits_)
191                 {
192                   if (debug_page_breaking_scoring)
193                     print_break_node (cur);
194
195                   found = true;
196                   this_start_best = cur;
197                   prev_best_system_count = sys_count;
198
199                   /* heuristic: if we increase the number of systems, we can bound the
200                      division from below by our current best division */
201                   min_division = current_configuration (i);
202                 }
203             }
204           if (!found && this_start_best.too_many_lines_)
205             break;
206         }
207       if (isinf (this_start_best.demerits_))
208         {
209           assert (!isinf (best.demerits_) && start < end - 1);
210           break;
211         }
212
213       if (start == 0 && end == 1
214           && this_start_best.first_page_number_ == 1
215           && this_start_best.page_count_ > 1)
216         warning (_ ("cannot fit the first page turn onto a single page.  "
217                     "Consider setting first-page-number to an even number."));
218
219       if (this_start_best.demerits_ < best.demerits_)
220         best = this_start_best;
221     }
222   state_.push_back (best);
223 }
224
225 SCM
226 Page_turn_page_breaking::solve ()
227 {
228   state_.clear ();
229   message (_f ("Calculating page and line breaks (%d possible page breaks)...",
230                (int) last_break_position ()));
231   for (vsize i = 0; i < last_break_position (); i++)
232     {
233       calc_subproblem (i);
234       progress_indication (string ("[") + to_string (i + 1) + "]");
235     }
236   progress_indication ("\n");
237
238   vector<Break_node> breaking;
239   int i = state_.size () - 1;
240   while (i >= 0)
241     {
242       breaking.push_back (state_[i]);
243       i = state_[i].prev_;
244     }
245   reverse (breaking);
246
247   message (_ ("Drawing systems..."));
248   SCM systems = make_lines (&breaking);
249   return make_pages (breaking, systems);
250 }
251
252 /* do the line breaking in all the scores and return a big list of systems */
253 SCM
254 Page_turn_page_breaking::make_lines (vector<Break_node> *psoln)
255 {
256   vector<Break_node> &soln = *psoln;
257   for (vsize n = 0; n < soln.size (); n++)
258     {
259       vsize start = n > 0 ? soln[n-1].break_pos_ : 0;
260       vsize end = soln[n].break_pos_;
261
262       break_into_pieces (start, end, soln[n].div_);
263     }
264
265   return systems ();
266 }
267
268 SCM
269 Page_turn_page_breaking::make_pages (vector<Break_node> const &soln, SCM systems)
270 {
271   vector<vsize> lines_per_page;
272   for (vsize i = 0; i < soln.size (); i++)
273     {
274       for (vsize j = 0; j < soln[i].page_count_; j++)
275         lines_per_page.push_back (soln[i].system_count_[j]);
276
277       if (i + 1 < soln.size () && (soln[i].first_page_number_ + soln[i].page_count_) % 2)
278         /* add a blank page */
279         lines_per_page.push_back (0);
280     }
281
282   /* this should only actually modify first-page-number if
283      auto-first-page-number was true. */
284   book_->paper_->set_variable (ly_symbol2scm ("first-page-number"),
285                                scm_from_int (soln[0].first_page_number_));
286   return Page_breaking::make_pages (lines_per_page, systems);
287 }
288
289 void
290 Page_turn_page_breaking::print_break_node (Break_node const &node)
291 {
292   int system_count = 0;
293   for (vsize i = 0; i < node.system_count_.size (); i++)
294     system_count += node.system_count_[i];
295
296   message (_f ("break starting at page %d", (int) node.first_page_number_));
297   message (_f ("\tdemerits: %f", node.demerits_));
298   message (_f ("\tsystem count: %d", system_count));
299   message (_f ("\tpage count: %d", (int) node.page_count_));
300   message (_f ("\tprevious break: %d", (int) node.prev_));
301 }