2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2015 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"
30 Page_spacing::calc_force ()
32 Real height = page_height_
33 - breaker_->min_whitespace_at_top_of_page (first_line_)
34 - breaker_->min_whitespace_at_bottom_of_page (last_line_);
36 if (rod_height_ + last_line_.bottom_padding_ >= height)
39 force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
40 / max (0.1, inverse_spring_k_);
44 Page_spacing::resize (Real new_height)
46 page_height_ = new_height;
51 Page_spacing::append_system (const Line_details &line)
55 rod_height_ += line.tallness_;
56 spring_len_ += last_line_.spring_length (line);
61 rod_height_ += line.full_height ();
65 rod_height_ += account_for_footnotes (line);
66 inverse_spring_k_ += line.inverse_hooke_;
74 Page_spacing::account_for_footnotes (Line_details const &line)
76 Real footnote_height = 0.0;
77 Real in_note_height = 0.0;
78 bool has_in_notes = false;
79 for (vsize i = 0; i < line.in_note_heights_.size (); i++)
81 in_note_height += (has_in_notes
83 : breaker_->in_note_padding ());
85 in_note_height += line.in_note_heights_[i];
88 for (vsize i = 0; i < line.footnote_heights_.size (); i++)
90 footnote_height += (has_footnotes_
92 : (breaker_->footnote_separator_stencil_height ()
93 + breaker_->footnote_padding ()
94 + breaker_->footnote_number_raise ()));
96 has_footnotes_ = true;
97 footnote_height += line.footnote_heights_[i];
98 footnote_height += breaker_->footnote_padding ();
101 return (in_note_height
103 ? breaker_->in_note_padding ()
108 ? - breaker_->footnote_padding () + breaker_->footnote_footer_padding ()
113 Page_spacing::prepend_system (const Line_details &line)
116 spring_len_ += line.spring_length (first_line_);
120 rod_height_ -= first_line_.full_height ();
121 rod_height_ += first_line_.tallness_;
122 rod_height_ += line.full_height ();
123 rod_height_ += account_for_footnotes (line);
124 inverse_spring_k_ += line.inverse_hooke_;
132 Page_spacing::clear ()
134 force_ = rod_height_ = spring_len_ = 0;
135 inverse_spring_k_ = 0;
136 has_footnotes_ = false;
139 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
142 first_page_num_ = first_page_num;
145 ragged_ = breaker->ragged ();
146 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
150 Page_spacer::solve ()
152 if (simple_state_.empty ())
154 simple_state_.resize (lines_.size ());
155 for (vsize i = 0; i < lines_.size (); ++i)
156 calc_subproblem (VPOS, i);
159 Page_spacing_result ret;
160 if (simple_state_.empty ())
163 ret.penalty_ = simple_state_.back ().penalty_
164 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
165 ret.system_count_status_ = simple_state_.back ().system_count_status_;
167 vsize system = lines_.size () - 1;
168 while (system != VPOS)
170 Page_spacing_node const &cur = simple_state_[system];
171 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
173 ret.force_.push_back (cur.force_);
174 ret.systems_per_page_.push_back (system_count);
175 ret.demerits_ += cur.force_ * cur.force_;
179 reverse (ret.force_);
180 reverse (ret.systems_per_page_);
185 Page_spacer::solve (vsize page_count)
187 if (page_count > max_page_count_)
190 Page_spacing_result ret;
192 vsize system = lines_.size () - 1;
193 vsize extra_systems = 0;
194 vsize extra_pages = 0;
196 if (isinf (state_.at (system, page_count - 1).demerits_))
198 programming_error ("tried to space systems on a bad number of pages");
199 /* Usually, this means that we tried to cram too many systems into
200 to few pages. To avoid crashing, we look for the largest number of
201 systems that we can fit properly onto the right number of pages.
202 All the systems that don't fit get tacked onto the last page.
205 for (i = system; isinf (state_.at (i, page_count - 1).demerits_) && i; i--)
210 extra_systems = system - i;
215 /* try chopping off pages from the end */
217 for (j = page_count; j && isinf (state_.at (system, j - 1).demerits_); j--)
222 extra_pages = page_count - j;
226 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
230 ret.force_.resize (page_count);
231 ret.systems_per_page_.resize (page_count);
232 ret.system_count_status_ = state_.at (system, page_count - 1).system_count_status_;
233 ret.penalty_ = state_.at (system, page_count - 1).penalty_
234 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
237 for (vsize p = page_count; p--;)
239 assert (system != VPOS);
241 Page_spacing_node const &ps = state_.at (system, p);
242 ret.force_[p] = ps.force_;
243 ret.demerits_ += ps.force_ * ps.force_;
245 ret.systems_per_page_[p] = system + 1;
247 ret.systems_per_page_[p] = system - ps.prev_;
253 ret.systems_per_page_.back () += extra_systems;
254 ret.force_.back () = BAD_SPACING_PENALTY;
258 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
259 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
266 Page_spacer::resize (vsize page_count)
268 assert (page_count > 0);
270 if (max_page_count_ >= page_count)
273 state_.resize (lines_.size (), page_count, Page_spacing_node ());
274 for (vsize page = max_page_count_; page < page_count; page++)
275 for (vsize line = page; line < lines_.size (); line++)
276 if (!calc_subproblem (page, line))
279 max_page_count_ = page_count;
282 // Carries out one step in the dynamic programming algorithm for putting systems
283 // on a fixed number of pages. One call to this routine calculates the best
284 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
285 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
287 // This algorithm is similar to the constrained-breaking algorithm.
289 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
290 // we don't want to constrain the number of pages that the solution has. In this
291 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
292 // the subproblems look similar for both, so we reuse this method.
294 Page_spacer::calc_subproblem (vsize page, vsize line)
296 bool last = line == lines_.size () - 1;
298 // Note: if page == VPOS then we don't actually know yet which page number we're
299 // working on, so we have to recalculate the page height in the loop. Therefore
300 // our early-exit condition from the loop depends on paper_height rather than
301 // page_height (ie. we break only if we would overfill a page without margins
302 // or headers/footers). Otherwise, the algorithm would not be optimal:
303 // if our page has a very large header then perhaps
304 // we should look ahead a few systems in order to find the best solution. A
305 // good example of this is input/regression/page-spacing-tall-headfoot.ly
306 vsize page_num = page == VPOS ? 0 : page;
307 Real paper_height = breaker_->paper_height ();
308 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
310 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
311 bool ragged = ragged_ || (ragged_last_ && last);
314 for (vsize page_start = line + 1; page_start > page_num && page_start--;)
316 Page_spacing_node const *prev = 0;
322 prev = &simple_state_[page_start - 1];
323 space.resize (breaker_->page_height (prev->page_ + 1, last));
326 space.resize (breaker_->page_height (first_page_num_, last));
329 prev = &state_.at (page_start - 1, page - 1);
331 space.prepend_system (lines_[page_start]);
333 bool overfull = (space.rod_height_ > paper_height
335 && (space.rod_height_ + space.spring_len_ > paper_height)));
336 // This 'if' statement is a little hard to parse. It won't consider this configuration
337 // if it is overfull unless the current configuration is the first one with this start
338 // point. We also make an exception (and consider this configuration) if the previous
339 // configuration we tried had fewer lines than min-systems-per-page.
340 if (!breaker_->too_few_lines (line_count)
345 line_count += lines_[page_start].compressed_nontitle_lines_count_;
346 if (page > 0 || page_start == 0)
348 // If the last page is ragged, set its force to zero. This way, we will leave
349 // the last page half-empty rather than trying to balance things out
350 // (which only makes sense in non-ragged situations).
351 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
354 Real demerits = space.force_ * space.force_;
356 // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
357 // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
358 // precedence over overfull pages.
359 demerits = min (demerits, BAD_SPACING_PENALTY);
360 demerits += (prev ? prev->demerits_ : 0);
362 Real penalty = breaker_->line_count_penalty (line_count);
364 penalty += lines_[page_start - 1].page_penalty_
365 + (page % 2 == 0) ? lines_[page_start - 1].turn_penalty_ : 0;
367 /* Deal with widow/orphan lines */
368 /* Last line of paragraph is first line on the new page */
370 && (page_start < lines_.size ())
371 && (lines_[page_start].last_markup_line_))
372 penalty += breaker_->orphan_penalty ();
373 /* First line of paragraph is last line on the previous page */
375 && (page_start < lines_.size ())
376 && (lines_[page_start - 1].first_markup_line_))
377 penalty += breaker_->orphan_penalty ();
380 if (demerits < cur.demerits_ || page_start == line)
382 cur.demerits_ = demerits;
383 cur.force_ = space.force_;
384 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
385 cur.system_count_status_ = breaker_->line_count_status (line_count)
386 | (prev ? prev->system_count_status_ : 0);
387 cur.prev_ = page_start - 1;
388 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
393 && scm_is_eq (lines_[page_start - 1].page_permission_,
394 ly_symbol2scm ("force")))
397 return !isinf (cur.demerits_);