2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2010 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"
23 #include "page-breaking.hh"
27 Page_spacing::calc_force ()
29 Real height = page_height_
30 - breaker_->min_whitespace_at_top_of_page (first_line_)
31 - breaker_->min_whitespace_at_bottom_of_page (last_line_);
33 if (rod_height_ + last_line_.bottom_padding_ >= height)
36 force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
37 / max (0.1, inverse_spring_k_);
41 Page_spacing::resize (Real new_height)
43 page_height_ = new_height;
48 Page_spacing::append_system (const Line_details &line)
52 rod_height_ += line.tallness_;
56 rod_height_ += line.full_height ();
60 // line.space_ measures the spring which goes from the bottom refpoint
61 // of one system to the top refpoint of the next. spring_len_ measures
62 // how much of that is stretchable.
63 Real refpoint_dist = last_line_.tallness_
64 + last_line_.refpoint_extent_[DOWN]
65 - line.refpoint_extent_[UP];
66 Real space = line.title_ ? last_line_.title_space_ : last_line_.space_;
67 spring_len_ += max (0.0, space - refpoint_dist);
68 inverse_spring_k_ += line.inverse_hooke_;
76 Page_spacing::prepend_system (const Line_details &line)
81 rod_height_ -= first_line_.full_height ();
82 rod_height_ += first_line_.tallness_;
83 rod_height_ += line.full_height();
85 Real refpoint_dist = line.tallness_
86 + line.refpoint_extent_[DOWN]
87 - first_line_.refpoint_extent_[UP];
88 Real space = first_line_.title_ ? line.title_space_ : line.space_;
89 spring_len_ += max (0.0, space - refpoint_dist);
90 inverse_spring_k_ += line.inverse_hooke_;
98 Page_spacing::clear ()
100 force_ = rod_height_ = spring_len_ = 0;
101 inverse_spring_k_ = 0;
105 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
108 first_page_num_ = first_page_num;
111 ragged_ = breaker->ragged ();
112 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
116 Page_spacer::solve ()
118 if (simple_state_.empty ())
120 simple_state_.resize (lines_.size ());
121 for (vsize i = 0; i < lines_.size (); ++i)
122 calc_subproblem (VPOS, i);
125 Page_spacing_result ret;
126 ret.penalty_ = simple_state_.back ().penalty_
127 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
128 ret.system_count_status_ = simple_state_.back ().system_count_status_;
130 vsize system = lines_.size () - 1;
131 while (system != VPOS)
133 Page_spacing_node const& cur = simple_state_[system];
134 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
136 ret.force_.push_back (cur.force_);
137 ret.systems_per_page_.push_back (system_count);
138 ret.demerits_ += cur.force_ * cur.force_;
142 reverse (ret.force_);
143 reverse (ret.systems_per_page_);
148 Page_spacer::solve (vsize page_count)
150 if (page_count > max_page_count_)
153 Page_spacing_result ret;
155 vsize system = lines_.size () - 1;
156 vsize extra_systems = 0;
157 vsize extra_pages = 0;
159 if (isinf (state_.at (system, page_count-1).demerits_))
161 programming_error ("tried to space systems on a bad number of pages");
162 /* Usually, this means that we tried to cram too many systems into
163 to few pages. To avoid crashing, we look for the largest number of
164 systems that we can fit properly onto the right number of pages.
165 All the systems that don't fit get tacked onto the last page.
168 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
173 extra_systems = system - i;
178 /* try chopping off pages from the end */
180 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
185 extra_pages = page_count - j;
189 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
193 ret.force_.resize (page_count);
194 ret.systems_per_page_.resize (page_count);
195 ret.system_count_status_ = state_.at (system, page_count-1).system_count_status_;
196 ret.penalty_ = state_.at (system, page_count-1).penalty_
197 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
200 for (vsize p = page_count; p--;)
202 assert (system != VPOS);
204 Page_spacing_node const &ps = state_.at (system, p);
205 ret.force_[p] = ps.force_;
206 ret.demerits_ += ps.force_ * ps.force_;
208 ret.systems_per_page_[p] = system + 1;
210 ret.systems_per_page_[p] = system - ps.prev_;
216 ret.systems_per_page_.back () += extra_systems;
217 ret.force_.back () = BAD_SPACING_PENALTY;
221 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
222 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
229 Page_spacer::resize (vsize page_count)
231 assert (page_count > 0);
233 if (max_page_count_ >= page_count)
236 state_.resize (lines_.size (), page_count, Page_spacing_node ());
237 for (vsize page = max_page_count_; page < page_count; page++)
238 for (vsize line = page; line < lines_.size (); line++)
239 if (!calc_subproblem (page, line))
242 max_page_count_ = page_count;
245 // Carries out one step in the dynamic programming algorithm for putting systems
246 // on a fixed number of pages. One call to this routine calculates the best
247 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
248 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
250 // This algorithm is similar to the constrained-breaking algorithm.
252 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
253 // we don't want to constrain the number of pages that the solution has. In this
254 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
255 // the subproblems look similar for both, so we reuse this method.
257 Page_spacer::calc_subproblem (vsize page, vsize line)
259 bool last = line == lines_.size () - 1;
261 // Note: if page == VPOS then we don't actually know yet which page number we're
262 // working on, so we have to recalculate the page height in the loop. Therefore
263 // our early-exit condition from the loop depends on paper_height rather than
264 // page_height (ie. we break only if we would overfill a page without margins
265 // or headers/footers). Otherwise, the algorithm would not be optimal:
266 // if our page has a very large header then perhaps
267 // we should look ahead a few systems in order to find the best solution. A
268 // good example of this is input/regression/page-spacing-tall-headfoot.ly
269 vsize page_num = page == VPOS ? 0 : page;
270 Real paper_height = breaker_->paper_height ();
271 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
273 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
274 bool ragged = ragged_ || (ragged_last_ && last);
277 for (vsize page_start = line+1; page_start > page_num && page_start--;)
279 Page_spacing_node const *prev = 0;
285 prev = &simple_state_[page_start-1];
286 space.resize (breaker_->page_height (prev->page_ + 1, last));
289 space.resize (breaker_->page_height (first_page_num_, last));
292 prev = &state_.at (page_start-1, page-1);
294 space.prepend_system (lines_[page_start]);
296 bool overfull = (space.rod_height_ > paper_height
298 && (space.rod_height_ + space.spring_len_ > paper_height)));
299 // This 'if' statement is a little hard to parse. It won't consider this configuration
300 // if it is overfull unless the current configuration is the first one with this start
301 // point. We also make an exception (and consider this configuration) if the previous
302 // configuration we tried had fewer lines than min-systems-per-page.
303 if (!breaker_->too_few_lines (line_count)
308 line_count += lines_[page_start].compressed_nontitle_lines_count_;
309 if (page > 0 || page_start == 0)
311 // If the last page is ragged, set its force to zero. This way, we will leave
312 // the last page half-empty rather than trying to balance things out
313 // (which only makes sense in non-ragged situations).
314 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
317 Real demerits = space.force_ * space.force_;
319 // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
320 // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
321 // precedence over overfull pages.
322 demerits = min (demerits, BAD_SPACING_PENALTY);
323 demerits += (prev ? prev->demerits_ : 0);
325 Real penalty = breaker_->line_count_penalty (line_count);
327 penalty += lines_[page_start-1].page_penalty_
328 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
330 /* Deal with widow/orphan lines */
331 /* Last line of paragraph is first line on the new page */
332 if ((page_start > 0) &&
333 (page_start < lines_.size ()) &&
334 (lines_[page_start].last_markup_line_))
335 penalty += breaker_->orphan_penalty ();
336 /* First line of paragraph is last line on the previous page */
337 if ((page_start > 0) &&
338 (page_start < lines_.size ()) &&
339 (lines_[page_start-1].first_markup_line_))
340 penalty += breaker_->orphan_penalty ();
343 if (demerits < cur.demerits_ || page_start == line)
345 cur.demerits_ = demerits;
346 cur.force_ = space.force_;
347 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
348 cur.system_count_status_ = breaker_->line_count_status (line_count)
349 | (prev ? prev->system_count_status_ : 0);
350 cur.prev_ = page_start - 1;
351 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
356 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
359 return !isinf (cur.demerits_);