2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2011 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 "page-spacing.hh"
22 #include "international.hh"
24 #include "page-breaking.hh"
28 Page_spacing::calc_force ()
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_);
34 if (rod_height_ + last_line_.bottom_padding_ >= height)
37 force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
38 / max (0.1, inverse_spring_k_);
42 Page_spacing::resize (Real new_height)
44 page_height_ = new_height;
49 Page_spacing::append_system (const Line_details &line)
53 rod_height_ += line.tallness_;
54 spring_len_ += last_line_.spring_length (line);
59 rod_height_ += line.full_height ();
63 rod_height_ += account_for_footnotes (line);
64 inverse_spring_k_ += line.inverse_hooke_;
72 Page_spacing::account_for_footnotes (Line_details const &line)
74 Real footnote_height = 0.0;
75 for (vsize i = 0; i < line.footnotes_.size (); i++)
77 footnote_height += (has_footnotes_
79 : (breaker_->footnote_separator_stencil_height ()
80 + breaker_->footnote_padding ()
81 + breaker_->footnote_number_raise ()));
83 has_footnotes_ = true;
84 Interval extent = line.footnotes_[i]->extent (Y_AXIS);
85 footnote_height += extent[UP] - extent[DOWN];
86 footnote_height += breaker_->footnote_padding ();
89 return (footnote_height
91 ? breaker_->footnote_padding () + breaker_->footnote_footer_padding ()
96 Page_spacing::prepend_system (const Line_details &line)
99 spring_len_ += line.spring_length (first_line_);
103 rod_height_ -= first_line_.full_height ();
104 rod_height_ += first_line_.tallness_;
105 rod_height_ += line.full_height ();
106 rod_height_ += account_for_footnotes (line);
107 inverse_spring_k_ += line.inverse_hooke_;
115 Page_spacing::clear ()
117 force_ = rod_height_ = spring_len_ = 0;
118 inverse_spring_k_ = 0;
119 has_footnotes_ = false;
122 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
125 first_page_num_ = first_page_num;
128 ragged_ = breaker->ragged ();
129 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
133 Page_spacer::solve ()
135 if (simple_state_.empty ())
137 simple_state_.resize (lines_.size ());
138 for (vsize i = 0; i < lines_.size (); ++i)
139 calc_subproblem (VPOS, i);
142 Page_spacing_result ret;
143 ret.penalty_ = simple_state_.back ().penalty_
144 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
145 ret.system_count_status_ = simple_state_.back ().system_count_status_;
147 vsize system = lines_.size () - 1;
148 while (system != VPOS)
150 Page_spacing_node const &cur = simple_state_[system];
151 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
153 ret.force_.push_back (cur.force_);
154 ret.systems_per_page_.push_back (system_count);
155 ret.demerits_ += cur.force_ * cur.force_;
159 reverse (ret.force_);
160 reverse (ret.systems_per_page_);
165 Page_spacer::solve (vsize page_count)
167 if (page_count > max_page_count_)
170 Page_spacing_result ret;
172 vsize system = lines_.size () - 1;
173 vsize extra_systems = 0;
174 vsize extra_pages = 0;
176 if (isinf (state_.at (system, page_count - 1).demerits_))
178 programming_error ("tried to space systems on a bad number of pages");
179 /* Usually, this means that we tried to cram too many systems into
180 to few pages. To avoid crashing, we look for the largest number of
181 systems that we can fit properly onto the right number of pages.
182 All the systems that don't fit get tacked onto the last page.
185 for (i = system; isinf (state_.at (i, page_count - 1).demerits_) && i; i--)
190 extra_systems = system - i;
195 /* try chopping off pages from the end */
197 for (j = page_count; j && isinf (state_.at (system, j - 1).demerits_); j--)
202 extra_pages = page_count - j;
206 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
210 ret.force_.resize (page_count);
211 ret.systems_per_page_.resize (page_count);
212 ret.system_count_status_ = state_.at (system, page_count - 1).system_count_status_;
213 ret.penalty_ = state_.at (system, page_count - 1).penalty_
214 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
217 for (vsize p = page_count; p--;)
219 assert (system != VPOS);
221 Page_spacing_node const &ps = state_.at (system, p);
222 ret.force_[p] = ps.force_;
223 ret.demerits_ += ps.force_ * ps.force_;
225 ret.systems_per_page_[p] = system + 1;
227 ret.systems_per_page_[p] = system - ps.prev_;
233 ret.systems_per_page_.back () += extra_systems;
234 ret.force_.back () = BAD_SPACING_PENALTY;
238 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
239 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
246 Page_spacer::resize (vsize page_count)
248 assert (page_count > 0);
250 if (max_page_count_ >= page_count)
253 state_.resize (lines_.size (), page_count, Page_spacing_node ());
254 for (vsize page = max_page_count_; page < page_count; page++)
255 for (vsize line = page; line < lines_.size (); line++)
256 if (!calc_subproblem (page, line))
259 max_page_count_ = page_count;
262 // Carries out one step in the dynamic programming algorithm for putting systems
263 // on a fixed number of pages. One call to this routine calculates the best
264 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
265 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
267 // This algorithm is similar to the constrained-breaking algorithm.
269 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
270 // we don't want to constrain the number of pages that the solution has. In this
271 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
272 // the subproblems look similar for both, so we reuse this method.
274 Page_spacer::calc_subproblem (vsize page, vsize line)
276 bool last = line == lines_.size () - 1;
278 // Note: if page == VPOS then we don't actually know yet which page number we're
279 // working on, so we have to recalculate the page height in the loop. Therefore
280 // our early-exit condition from the loop depends on paper_height rather than
281 // page_height (ie. we break only if we would overfill a page without margins
282 // or headers/footers). Otherwise, the algorithm would not be optimal:
283 // if our page has a very large header then perhaps
284 // we should look ahead a few systems in order to find the best solution. A
285 // good example of this is input/regression/page-spacing-tall-headfoot.ly
286 vsize page_num = page == VPOS ? 0 : page;
287 Real paper_height = breaker_->paper_height ();
288 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
290 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
291 bool ragged = ragged_ || (ragged_last_ && last);
294 for (vsize page_start = line + 1; page_start > page_num && page_start--;)
296 Page_spacing_node const *prev = 0;
302 prev = &simple_state_[page_start - 1];
303 space.resize (breaker_->page_height (prev->page_ + 1, last));
306 space.resize (breaker_->page_height (first_page_num_, last));
309 prev = &state_.at (page_start - 1, page - 1);
311 space.prepend_system (lines_[page_start]);
313 bool overfull = (space.rod_height_ > paper_height
315 && (space.rod_height_ + space.spring_len_ > paper_height)));
316 // This 'if' statement is a little hard to parse. It won't consider this configuration
317 // if it is overfull unless the current configuration is the first one with this start
318 // point. We also make an exception (and consider this configuration) if the previous
319 // configuration we tried had fewer lines than min-systems-per-page.
320 if (!breaker_->too_few_lines (line_count)
325 line_count += lines_[page_start].compressed_nontitle_lines_count_;
326 if (page > 0 || page_start == 0)
328 // If the last page is ragged, set its force to zero. This way, we will leave
329 // the last page half-empty rather than trying to balance things out
330 // (which only makes sense in non-ragged situations).
331 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
334 Real demerits = space.force_ * space.force_;
336 // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
337 // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
338 // precedence over overfull pages.
339 demerits = min (demerits, BAD_SPACING_PENALTY);
340 demerits += (prev ? prev->demerits_ : 0);
342 Real penalty = breaker_->line_count_penalty (line_count);
344 penalty += lines_[page_start - 1].page_penalty_
345 + (page % 2 == 0) ? lines_[page_start - 1].turn_penalty_ : 0;
347 /* Deal with widow/orphan lines */
348 /* Last line of paragraph is first line on the new page */
350 && (page_start < lines_.size ())
351 && (lines_[page_start].last_markup_line_))
352 penalty += breaker_->orphan_penalty ();
353 /* First line of paragraph is last line on the previous page */
355 && (page_start < lines_.size ())
356 && (lines_[page_start - 1].first_markup_line_))
357 penalty += breaker_->orphan_penalty ();
360 if (demerits < cur.demerits_ || page_start == line)
362 cur.demerits_ = demerits;
363 cur.force_ = space.force_;
364 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
365 cur.system_count_status_ = breaker_->line_count_status (line_count)
366 | (prev ? prev->system_count_status_ : 0);
367 cur.prev_ = page_start - 1;
368 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
373 && lines_[page_start - 1].page_permission_ == ly_symbol2scm ("force"))
376 return !isinf (cur.demerits_);