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 ()));
82 has_footnotes_ = true;
83 Interval extent = line.footnotes_[i]->extent (Y_AXIS);
84 footnote_height += extent[UP] - extent[DOWN];
85 footnote_height += breaker_->footnote_padding ();
87 return footnote_height;
91 Page_spacing::prepend_system (const Line_details &line)
94 spring_len_ += line.spring_length (first_line_);
98 rod_height_ -= first_line_.full_height ();
99 rod_height_ += first_line_.tallness_;
100 rod_height_ += line.full_height();
101 rod_height_ += account_for_footnotes (line);
102 inverse_spring_k_ += line.inverse_hooke_;
110 Page_spacing::clear ()
112 force_ = rod_height_ = spring_len_ = 0;
113 inverse_spring_k_ = 0;
114 has_footnotes_ = false;
118 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
121 first_page_num_ = first_page_num;
124 ragged_ = breaker->ragged ();
125 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
129 Page_spacer::solve ()
131 if (simple_state_.empty ())
133 simple_state_.resize (lines_.size ());
134 for (vsize i = 0; i < lines_.size (); ++i)
135 calc_subproblem (VPOS, i);
138 Page_spacing_result ret;
139 ret.penalty_ = simple_state_.back ().penalty_
140 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
141 ret.system_count_status_ = simple_state_.back ().system_count_status_;
143 vsize system = lines_.size () - 1;
144 while (system != VPOS)
146 Page_spacing_node const& cur = simple_state_[system];
147 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
149 ret.force_.push_back (cur.force_);
150 ret.systems_per_page_.push_back (system_count);
151 ret.demerits_ += cur.force_ * cur.force_;
155 reverse (ret.force_);
156 reverse (ret.systems_per_page_);
161 Page_spacer::solve (vsize page_count)
163 if (page_count > max_page_count_)
166 Page_spacing_result ret;
168 vsize system = lines_.size () - 1;
169 vsize extra_systems = 0;
170 vsize extra_pages = 0;
172 if (isinf (state_.at (system, page_count-1).demerits_))
174 programming_error ("tried to space systems on a bad number of pages");
175 /* Usually, this means that we tried to cram too many systems into
176 to few pages. To avoid crashing, we look for the largest number of
177 systems that we can fit properly onto the right number of pages.
178 All the systems that don't fit get tacked onto the last page.
181 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
186 extra_systems = system - i;
191 /* try chopping off pages from the end */
193 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
198 extra_pages = page_count - j;
202 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
206 ret.force_.resize (page_count);
207 ret.systems_per_page_.resize (page_count);
208 ret.system_count_status_ = state_.at (system, page_count-1).system_count_status_;
209 ret.penalty_ = state_.at (system, page_count-1).penalty_
210 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
213 for (vsize p = page_count; p--;)
215 assert (system != VPOS);
217 Page_spacing_node const &ps = state_.at (system, p);
218 ret.force_[p] = ps.force_;
219 ret.demerits_ += ps.force_ * ps.force_;
221 ret.systems_per_page_[p] = system + 1;
223 ret.systems_per_page_[p] = system - ps.prev_;
229 ret.systems_per_page_.back () += extra_systems;
230 ret.force_.back () = BAD_SPACING_PENALTY;
234 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
235 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
242 Page_spacer::resize (vsize page_count)
244 assert (page_count > 0);
246 if (max_page_count_ >= page_count)
249 state_.resize (lines_.size (), page_count, Page_spacing_node ());
250 for (vsize page = max_page_count_; page < page_count; page++)
251 for (vsize line = page; line < lines_.size (); line++)
252 if (!calc_subproblem (page, line))
255 max_page_count_ = page_count;
258 // Carries out one step in the dynamic programming algorithm for putting systems
259 // on a fixed number of pages. One call to this routine calculates the best
260 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
261 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
263 // This algorithm is similar to the constrained-breaking algorithm.
265 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
266 // we don't want to constrain the number of pages that the solution has. In this
267 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
268 // the subproblems look similar for both, so we reuse this method.
270 Page_spacer::calc_subproblem (vsize page, vsize line)
272 bool last = line == lines_.size () - 1;
274 // Note: if page == VPOS then we don't actually know yet which page number we're
275 // working on, so we have to recalculate the page height in the loop. Therefore
276 // our early-exit condition from the loop depends on paper_height rather than
277 // page_height (ie. we break only if we would overfill a page without margins
278 // or headers/footers). Otherwise, the algorithm would not be optimal:
279 // if our page has a very large header then perhaps
280 // we should look ahead a few systems in order to find the best solution. A
281 // good example of this is input/regression/page-spacing-tall-headfoot.ly
282 vsize page_num = page == VPOS ? 0 : page;
283 Real paper_height = breaker_->paper_height ();
284 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
286 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
287 bool ragged = ragged_ || (ragged_last_ && last);
290 for (vsize page_start = line+1; page_start > page_num && page_start--;)
292 Page_spacing_node const *prev = 0;
298 prev = &simple_state_[page_start-1];
299 space.resize (breaker_->page_height (prev->page_ + 1, last));
302 space.resize (breaker_->page_height (first_page_num_, last));
305 prev = &state_.at (page_start-1, page-1);
307 space.prepend_system (lines_[page_start]);
309 bool overfull = (space.rod_height_ > paper_height
311 && (space.rod_height_ + space.spring_len_ > paper_height)));
312 // This 'if' statement is a little hard to parse. It won't consider this configuration
313 // if it is overfull unless the current configuration is the first one with this start
314 // point. We also make an exception (and consider this configuration) if the previous
315 // configuration we tried had fewer lines than min-systems-per-page.
316 if (!breaker_->too_few_lines (line_count)
321 line_count += lines_[page_start].compressed_nontitle_lines_count_;
322 if (page > 0 || page_start == 0)
324 // If the last page is ragged, set its force to zero. This way, we will leave
325 // the last page half-empty rather than trying to balance things out
326 // (which only makes sense in non-ragged situations).
327 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
330 Real demerits = space.force_ * space.force_;
332 // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
333 // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
334 // precedence over overfull pages.
335 demerits = min (demerits, BAD_SPACING_PENALTY);
336 demerits += (prev ? prev->demerits_ : 0);
338 Real penalty = breaker_->line_count_penalty (line_count);
340 penalty += lines_[page_start-1].page_penalty_
341 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
343 /* Deal with widow/orphan lines */
344 /* Last line of paragraph is first line on the new page */
345 if ((page_start > 0) &&
346 (page_start < lines_.size ()) &&
347 (lines_[page_start].last_markup_line_))
348 penalty += breaker_->orphan_penalty ();
349 /* First line of paragraph is last line on the previous page */
350 if ((page_start > 0) &&
351 (page_start < lines_.size ()) &&
352 (lines_[page_start-1].first_markup_line_))
353 penalty += breaker_->orphan_penalty ();
356 if (demerits < cur.demerits_ || page_start == line)
358 cur.demerits_ = demerits;
359 cur.force_ = space.force_;
360 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
361 cur.system_count_status_ = breaker_->line_count_status (line_count)
362 | (prev ? prev->system_count_status_ : 0);
363 cur.prev_ = page_start - 1;
364 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
369 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
372 return !isinf (cur.demerits_);