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;
123 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
126 first_page_num_ = first_page_num;
129 ragged_ = breaker->ragged ();
130 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
134 Page_spacer::solve ()
136 if (simple_state_.empty ())
138 simple_state_.resize (lines_.size ());
139 for (vsize i = 0; i < lines_.size (); ++i)
140 calc_subproblem (VPOS, i);
143 Page_spacing_result ret;
144 ret.penalty_ = simple_state_.back ().penalty_
145 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
146 ret.system_count_status_ = simple_state_.back ().system_count_status_;
148 vsize system = lines_.size () - 1;
149 while (system != VPOS)
151 Page_spacing_node const& cur = simple_state_[system];
152 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
154 ret.force_.push_back (cur.force_);
155 ret.systems_per_page_.push_back (system_count);
156 ret.demerits_ += cur.force_ * cur.force_;
160 reverse (ret.force_);
161 reverse (ret.systems_per_page_);
166 Page_spacer::solve (vsize page_count)
168 if (page_count > max_page_count_)
171 Page_spacing_result ret;
173 vsize system = lines_.size () - 1;
174 vsize extra_systems = 0;
175 vsize extra_pages = 0;
177 if (isinf (state_.at (system, page_count-1).demerits_))
179 programming_error ("tried to space systems on a bad number of pages");
180 /* Usually, this means that we tried to cram too many systems into
181 to few pages. To avoid crashing, we look for the largest number of
182 systems that we can fit properly onto the right number of pages.
183 All the systems that don't fit get tacked onto the last page.
186 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
191 extra_systems = system - i;
196 /* try chopping off pages from the end */
198 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
203 extra_pages = page_count - j;
207 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
211 ret.force_.resize (page_count);
212 ret.systems_per_page_.resize (page_count);
213 ret.system_count_status_ = state_.at (system, page_count-1).system_count_status_;
214 ret.penalty_ = state_.at (system, page_count-1).penalty_
215 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
218 for (vsize p = page_count; p--;)
220 assert (system != VPOS);
222 Page_spacing_node const &ps = state_.at (system, p);
223 ret.force_[p] = ps.force_;
224 ret.demerits_ += ps.force_ * ps.force_;
226 ret.systems_per_page_[p] = system + 1;
228 ret.systems_per_page_[p] = system - ps.prev_;
234 ret.systems_per_page_.back () += extra_systems;
235 ret.force_.back () = BAD_SPACING_PENALTY;
239 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
240 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
247 Page_spacer::resize (vsize page_count)
249 assert (page_count > 0);
251 if (max_page_count_ >= page_count)
254 state_.resize (lines_.size (), page_count, Page_spacing_node ());
255 for (vsize page = max_page_count_; page < page_count; page++)
256 for (vsize line = page; line < lines_.size (); line++)
257 if (!calc_subproblem (page, line))
260 max_page_count_ = page_count;
263 // Carries out one step in the dynamic programming algorithm for putting systems
264 // on a fixed number of pages. One call to this routine calculates the best
265 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
266 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
268 // This algorithm is similar to the constrained-breaking algorithm.
270 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
271 // we don't want to constrain the number of pages that the solution has. In this
272 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
273 // the subproblems look similar for both, so we reuse this method.
275 Page_spacer::calc_subproblem (vsize page, vsize line)
277 bool last = line == lines_.size () - 1;
279 // Note: if page == VPOS then we don't actually know yet which page number we're
280 // working on, so we have to recalculate the page height in the loop. Therefore
281 // our early-exit condition from the loop depends on paper_height rather than
282 // page_height (ie. we break only if we would overfill a page without margins
283 // or headers/footers). Otherwise, the algorithm would not be optimal:
284 // if our page has a very large header then perhaps
285 // we should look ahead a few systems in order to find the best solution. A
286 // good example of this is input/regression/page-spacing-tall-headfoot.ly
287 vsize page_num = page == VPOS ? 0 : page;
288 Real paper_height = breaker_->paper_height ();
289 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
291 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
292 bool ragged = ragged_ || (ragged_last_ && last);
295 for (vsize page_start = line+1; page_start > page_num && page_start--;)
297 Page_spacing_node const *prev = 0;
303 prev = &simple_state_[page_start-1];
304 space.resize (breaker_->page_height (prev->page_ + 1, last));
307 space.resize (breaker_->page_height (first_page_num_, last));
310 prev = &state_.at (page_start-1, page-1);
312 space.prepend_system (lines_[page_start]);
314 bool overfull = (space.rod_height_ > paper_height
316 && (space.rod_height_ + space.spring_len_ > paper_height)));
317 // This 'if' statement is a little hard to parse. It won't consider this configuration
318 // if it is overfull unless the current configuration is the first one with this start
319 // point. We also make an exception (and consider this configuration) if the previous
320 // configuration we tried had fewer lines than min-systems-per-page.
321 if (!breaker_->too_few_lines (line_count)
326 line_count += lines_[page_start].compressed_nontitle_lines_count_;
327 if (page > 0 || page_start == 0)
329 // If the last page is ragged, set its force to zero. This way, we will leave
330 // the last page half-empty rather than trying to balance things out
331 // (which only makes sense in non-ragged situations).
332 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
335 Real demerits = space.force_ * space.force_;
337 // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
338 // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
339 // precedence over overfull pages.
340 demerits = min (demerits, BAD_SPACING_PENALTY);
341 demerits += (prev ? prev->demerits_ : 0);
343 Real penalty = breaker_->line_count_penalty (line_count);
345 penalty += lines_[page_start-1].page_penalty_
346 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
348 /* Deal with widow/orphan lines */
349 /* Last line of paragraph is first line on the new page */
350 if ((page_start > 0) &&
351 (page_start < lines_.size ()) &&
352 (lines_[page_start].last_markup_line_))
353 penalty += breaker_->orphan_penalty ();
354 /* First line of paragraph is last line on the previous page */
355 if ((page_start > 0) &&
356 (page_start < lines_.size ()) &&
357 (lines_[page_start-1].first_markup_line_))
358 penalty += breaker_->orphan_penalty ();
361 if (demerits < cur.demerits_ || page_start == line)
363 cur.demerits_ = demerits;
364 cur.force_ = space.force_;
365 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
366 cur.system_count_status_ = breaker_->line_count_status (line_count)
367 | (prev ? prev->system_count_status_ : 0);
368 cur.prev_ = page_start - 1;
369 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
374 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
377 return !isinf (cur.demerits_);