]> git.donarmstrong.com Git - lilypond.git/blob - lily/page-spacing.cc
Doc-es: update Vocal.
[lilypond.git] / lily / page-spacing.cc
1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3
4   Copyright (C) 2006--2011 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-spacing.hh"
21
22 #include "international.hh"
23 #include "matrix.hh"
24 #include "page-breaking.hh"
25 #include "warn.hh"
26
27 void
28 Page_spacing::calc_force ()
29 {
30   Real height = page_height_
31                 - breaker_->min_whitespace_at_top_of_page (first_line_)
32                 - breaker_->min_whitespace_at_bottom_of_page (last_line_);
33
34   if (rod_height_ + last_line_.bottom_padding_ >= height)
35     force_ = -infinity_f;
36   else
37     force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
38              / max (0.1, inverse_spring_k_);
39 }
40
41 void
42 Page_spacing::resize (Real new_height)
43 {
44   page_height_ = new_height;
45   calc_force ();
46 }
47
48 void
49 Page_spacing::append_system (const Line_details &line)
50 {
51   if (rod_height_)
52     {
53       rod_height_ += line.tallness_;
54       spring_len_ += last_line_.spring_length (line);
55
56     }
57   else
58     {
59       rod_height_ += line.full_height ();
60       first_line_ = line;
61     }
62
63   rod_height_ += account_for_footnotes (line);
64   inverse_spring_k_ += line.inverse_hooke_;
65
66   last_line_ = line;
67
68   calc_force ();
69 }
70
71 Real
72 Page_spacing::account_for_footnotes (Line_details const &line)
73 {
74   Real footnote_height = 0.0;
75   Real in_note_height = 0.0;
76   bool has_in_notes = false;
77   for (vsize i = 0; i < line.in_note_heights_.size (); i++)
78     {
79       in_note_height += (has_in_notes
80                          ? 0.0
81                          : breaker_->in_note_padding ());
82       has_in_notes = true;
83       in_note_height += line.in_note_heights_[i];
84     }
85
86   for (vsize i = 0; i < line.footnote_heights_.size (); i++)
87     {
88       footnote_height += (has_footnotes_
89                           ? 0.0
90                           : (breaker_->footnote_separator_stencil_height ()
91                              + breaker_->footnote_padding ()
92                              + breaker_->footnote_number_raise ()));
93
94       has_footnotes_ = true;
95       footnote_height += line.footnote_heights_[i];
96       footnote_height += breaker_->footnote_padding ();
97     }
98
99   return (in_note_height
100           - (has_in_notes
101              ? breaker_->in_note_padding ()
102              : 0.0))
103          +
104          (footnote_height
105           - (has_footnotes_
106              ? breaker_->footnote_padding () + breaker_->footnote_footer_padding ()
107              : 0.0));
108 }
109
110 void
111 Page_spacing::prepend_system (const Line_details &line)
112 {
113   if (rod_height_)
114     spring_len_ += line.spring_length (first_line_);
115   else
116     last_line_ = line;
117
118   rod_height_ -= first_line_.full_height ();
119   rod_height_ += first_line_.tallness_;
120   rod_height_ += line.full_height ();
121   rod_height_ += account_for_footnotes (line);
122   inverse_spring_k_ += line.inverse_hooke_;
123
124   first_line_ = line;
125
126   calc_force ();
127 }
128
129 void
130 Page_spacing::clear ()
131 {
132   force_ = rod_height_ = spring_len_ = 0;
133   inverse_spring_k_ = 0;
134   has_footnotes_ = false;
135 }
136
137 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
138   : lines_ (lines)
139 {
140   first_page_num_ = first_page_num;
141   breaker_ = breaker;
142   max_page_count_ = 0;
143   ragged_ = breaker->ragged ();
144   ragged_last_ = breaker->is_last () && breaker->ragged_last ();
145 }
146
147 Page_spacing_result
148 Page_spacer::solve ()
149 {
150   if (simple_state_.empty ())
151     {
152       simple_state_.resize (lines_.size ());
153       for (vsize i = 0; i < lines_.size (); ++i)
154         calc_subproblem (VPOS, i);
155     }
156
157   Page_spacing_result ret;
158   ret.penalty_ = simple_state_.back ().penalty_
159                  + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
160   ret.system_count_status_ = simple_state_.back ().system_count_status_;
161
162   vsize system = lines_.size () - 1;
163   while (system != VPOS)
164     {
165       Page_spacing_node const &cur = simple_state_[system];
166       vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
167
168       ret.force_.push_back (cur.force_);
169       ret.systems_per_page_.push_back (system_count);
170       ret.demerits_ += cur.force_ * cur.force_;
171       system = cur.prev_;
172     }
173
174   reverse (ret.force_);
175   reverse (ret.systems_per_page_);
176   return ret;
177 }
178
179 Page_spacing_result
180 Page_spacer::solve (vsize page_count)
181 {
182   if (page_count > max_page_count_)
183     resize (page_count);
184
185   Page_spacing_result ret;
186
187   vsize system = lines_.size () - 1;
188   vsize extra_systems = 0;
189   vsize extra_pages = 0;
190
191   if (isinf (state_.at (system, page_count - 1).demerits_))
192     {
193       programming_error ("tried to space systems on a bad number of pages");
194       /* Usually, this means that we tried to cram too many systems into
195          to few pages. To avoid crashing, we look for the largest number of
196          systems that we can fit properly onto the right number of pages.
197          All the systems that don't fit get tacked onto the last page.
198       */
199       vsize i;
200       for (i = system; isinf (state_.at (i, page_count - 1).demerits_) && i; i--)
201         ;
202
203       if (i)
204         {
205           extra_systems = system - i;
206           system = i;
207         }
208       else
209         {
210           /* try chopping off pages from the end */
211           vsize j;
212           for (j = page_count; j && isinf (state_.at (system, j - 1).demerits_); j--)
213             ;
214
215           if (j)
216             {
217               extra_pages = page_count - j;
218               page_count = j;
219             }
220           else
221             return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
222         }
223     }
224
225   ret.force_.resize (page_count);
226   ret.systems_per_page_.resize (page_count);
227   ret.system_count_status_ = state_.at (system, page_count - 1).system_count_status_;
228   ret.penalty_ = state_.at (system, page_count - 1).penalty_
229                  + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
230
231   ret.demerits_ = 0;
232   for (vsize p = page_count; p--;)
233     {
234       assert (system != VPOS);
235
236       Page_spacing_node const &ps = state_.at (system, p);
237       ret.force_[p] = ps.force_;
238       ret.demerits_ += ps.force_ * ps.force_;
239       if (p == 0)
240         ret.systems_per_page_[p] = system + 1;
241       else
242         ret.systems_per_page_[p] = system - ps.prev_;
243       system = ps.prev_;
244     }
245
246   if (extra_systems)
247     {
248       ret.systems_per_page_.back () += extra_systems;
249       ret.force_.back () = BAD_SPACING_PENALTY;
250     }
251   if (extra_pages)
252     {
253       ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
254       ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
255     }
256
257   return ret;
258 }
259
260 void
261 Page_spacer::resize (vsize page_count)
262 {
263   assert (page_count > 0);
264
265   if (max_page_count_ >= page_count)
266     return;
267
268   state_.resize (lines_.size (), page_count, Page_spacing_node ());
269   for (vsize page = max_page_count_; page < page_count; page++)
270     for (vsize line = page; line < lines_.size (); line++)
271       if (!calc_subproblem (page, line))
272         break;
273
274   max_page_count_ = page_count;
275 }
276
277 // Carries out one step in the dynamic programming algorithm for putting systems
278 // on a fixed number of pages. One call to this routine calculates the best
279 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
280 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
281 //
282 // This algorithm is similar to the constrained-breaking algorithm.
283 //
284 // If page == VPOS, we act on simple_state_ instead of state_.  This is useful if
285 // we don't want to constrain the number of pages that the solution has.  In this
286 // case, the algorithm looks more like the page-turn-page-breaking algorithm.  But
287 // the subproblems look similar for both, so we reuse this method.
288 bool
289 Page_spacer::calc_subproblem (vsize page, vsize line)
290 {
291   bool last = line == lines_.size () - 1;
292
293   // Note: if page == VPOS then we don't actually know yet which page number we're
294   // working on, so we have to recalculate the page height in the loop.  Therefore
295   // our early-exit condition from the loop depends on paper_height rather than
296   // page_height (ie. we break only if we would overfill a page without margins
297   // or headers/footers).  Otherwise, the algorithm would not be optimal:
298   // if our page has a very large header then perhaps
299   // we should look ahead a few systems in order to find the best solution.  A
300   // good example of this is input/regression/page-spacing-tall-headfoot.ly
301   vsize page_num = page == VPOS ? 0 : page;
302   Real paper_height = breaker_->paper_height ();
303   Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
304                       breaker_);
305   Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
306   bool ragged = ragged_ || (ragged_last_ && last);
307   int line_count = 0;
308
309   for (vsize page_start = line + 1; page_start > page_num && page_start--;)
310     {
311       Page_spacing_node const *prev = 0;
312
313       if (page == VPOS)
314         {
315           if (page_start > 0)
316             {
317               prev = &simple_state_[page_start - 1];
318               space.resize (breaker_->page_height (prev->page_ + 1, last));
319             }
320           else
321             space.resize (breaker_->page_height (first_page_num_, last));
322         }
323       else if (page > 0)
324         prev = &state_.at (page_start - 1, page - 1);
325
326       space.prepend_system (lines_[page_start]);
327
328       bool overfull = (space.rod_height_ > paper_height
329                        || (ragged
330                            && (space.rod_height_ + space.spring_len_ > paper_height)));
331       // This 'if' statement is a little hard to parse. It won't consider this configuration
332       // if it is overfull unless the current configuration is the first one with this start
333       // point. We also make an exception (and consider this configuration) if the previous
334       // configuration we tried had fewer lines than min-systems-per-page.
335       if (!breaker_->too_few_lines (line_count)
336           && page_start < line
337           && overfull)
338         break;
339
340       line_count += lines_[page_start].compressed_nontitle_lines_count_;
341       if (page > 0 || page_start == 0)
342         {
343           // If the last page is ragged, set its force to zero. This way, we will leave
344           // the last page half-empty rather than trying to balance things out
345           // (which only makes sense in non-ragged situations).
346           if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
347             space.force_ = 0;
348
349           Real demerits = space.force_ * space.force_;
350
351           // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
352           // is overfull.  This ensures that TERRIBLE_SPACING_PENALTY takes
353           // precedence over overfull pages.
354           demerits = min (demerits, BAD_SPACING_PENALTY);
355           demerits += (prev ? prev->demerits_ : 0);
356
357           Real penalty = breaker_->line_count_penalty (line_count);
358           if (page_start > 0)
359             penalty += lines_[page_start - 1].page_penalty_
360                        + (page % 2 == 0) ? lines_[page_start - 1].turn_penalty_ : 0;
361
362           /* Deal with widow/orphan lines */
363           /* Last line of paragraph is first line on the new page */
364           if ((page_start > 0)
365               && (page_start < lines_.size ())
366               && (lines_[page_start].last_markup_line_))
367             penalty += breaker_->orphan_penalty ();
368           /* First line of paragraph is last line on the previous page */
369           if ((page_start > 0)
370               && (page_start < lines_.size ())
371               && (lines_[page_start - 1].first_markup_line_))
372             penalty += breaker_->orphan_penalty ();
373
374           demerits += penalty;
375           if (demerits < cur.demerits_ || page_start == line)
376             {
377               cur.demerits_ = demerits;
378               cur.force_ = space.force_;
379               cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
380               cur.system_count_status_ = breaker_->line_count_status (line_count)
381                                          | (prev ? prev->system_count_status_ : 0);
382               cur.prev_ = page_start - 1;
383               cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
384             }
385         }
386
387       if (page_start > 0
388           && lines_[page_start - 1].page_permission_ == ly_symbol2scm ("force"))
389         break;
390     }
391   return !isinf (cur.demerits_);
392 }
393