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 spring_len_ += line.space_;
61 inverse_spring_k_ += line.inverse_hooke_;
69 Page_spacing::prepend_system (const Line_details &line)
74 rod_height_ -= first_line_.full_height ();
75 rod_height_ += first_line_.tallness_;
76 rod_height_ += line.full_height();
77 spring_len_ += line.space_;
78 inverse_spring_k_ += line.inverse_hooke_;
86 Page_spacing::clear ()
88 force_ = rod_height_ = spring_len_ = 0;
89 inverse_spring_k_ = 0;
93 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
96 first_page_num_ = first_page_num;
99 ragged_ = breaker->ragged ();
100 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
104 Page_spacer::solve ()
106 if (simple_state_.empty ())
108 simple_state_.resize (lines_.size ());
109 for (vsize i = 0; i < lines_.size (); ++i)
110 calc_subproblem (VPOS, i);
113 Page_spacing_result ret;
114 ret.penalty_ = simple_state_.back ().penalty_
115 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
116 ret.system_count_status_ = simple_state_.back ().system_count_status_;
118 vsize system = lines_.size () - 1;
119 while (system != VPOS)
121 Page_spacing_node const& cur = simple_state_[system];
122 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
124 ret.force_.push_back (cur.force_);
125 ret.systems_per_page_.push_back (system_count);
126 ret.demerits_ += cur.force_ * cur.force_;
130 reverse (ret.force_);
131 reverse (ret.systems_per_page_);
136 Page_spacer::solve (vsize page_count)
138 if (page_count > max_page_count_)
141 Page_spacing_result ret;
143 vsize system = lines_.size () - 1;
144 vsize extra_systems = 0;
145 vsize extra_pages = 0;
147 if (isinf (state_.at (system, page_count-1).demerits_))
149 programming_error ("tried to space systems on a bad number of pages");
150 /* Usually, this means that we tried to cram too many systems into
151 to few pages. To avoid crashing, we look for the largest number of
152 systems that we can fit properly onto the right number of pages.
153 All the systems that don't fit get tacked onto the last page.
156 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
161 extra_systems = system - i;
166 /* try chopping off pages from the end */
168 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
173 extra_pages = page_count - j;
177 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
181 ret.force_.resize (page_count);
182 ret.systems_per_page_.resize (page_count);
183 ret.system_count_status_ = state_.at (system, page_count-1).system_count_status_;
184 ret.penalty_ = state_.at (system, page_count-1).penalty_
185 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
188 for (vsize p = page_count; p--;)
190 assert (system != VPOS);
192 Page_spacing_node const &ps = state_.at (system, p);
193 ret.force_[p] = ps.force_;
194 ret.demerits_ += ps.force_ * ps.force_;
196 ret.systems_per_page_[p] = system + 1;
198 ret.systems_per_page_[p] = system - ps.prev_;
204 ret.systems_per_page_.back () += extra_systems;
205 ret.force_.back () = BAD_SPACING_PENALTY;
209 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
210 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
217 Page_spacer::resize (vsize page_count)
219 assert (page_count > 0);
221 if (max_page_count_ >= page_count)
224 state_.resize (lines_.size (), page_count, Page_spacing_node ());
225 for (vsize page = max_page_count_; page < page_count; page++)
226 for (vsize line = page; line < lines_.size (); line++)
227 if (!calc_subproblem (page, line))
230 max_page_count_ = page_count;
233 // Carries out one step in the dynamic programming algorithm for putting systems
234 // on a fixed number of pages. One call to this routine calculates the best
235 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
236 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
238 // This algorithm is similar to the constrained-breaking algorithm.
240 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
241 // we don't want to constrain the number of pages that the solution has. In this
242 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
243 // the subproblems look similar for both, so we reuse this method.
245 Page_spacer::calc_subproblem (vsize page, vsize line)
247 bool last = line == lines_.size () - 1;
249 // Note: if page == VPOS then we don't actually know yet which page number we're
250 // working on, so we have to recalculate the page height in the loop. Therefore
251 // our early-exit condition from the loop depends on paper_height rather than
252 // page_height (ie. we break only if we would overfill a page without margins
253 // or headers/footers). Otherwise, the algorithm would not be optimal:
254 // if our page has a very large header then perhaps
255 // we should look ahead a few systems in order to find the best solution. A
256 // good example of this is input/regression/page-spacing-tall-headfoot.ly
257 vsize page_num = page == VPOS ? 0 : page;
258 Real paper_height = breaker_->paper_height ();
259 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
261 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
262 bool ragged = ragged_ || (ragged_last_ && last);
265 for (vsize page_start = line+1; page_start > page_num && page_start--;)
267 Page_spacing_node const *prev = 0;
273 prev = &simple_state_[page_start-1];
274 space.resize (breaker_->page_height (prev->page_ + 1, last));
277 space.resize (breaker_->page_height (first_page_num_, last));
280 prev = &state_.at (page_start-1, page-1);
282 space.prepend_system (lines_[page_start]);
284 bool overfull = (space.rod_height_ > paper_height
286 && (space.rod_height_ + space.spring_len_ > paper_height)));
287 // This 'if' statement is a little hard to parse. It won't consider this configuration
288 // if it is overfull unless the current configuration is the first one with this start
289 // point. We also make an exception (and consider this configuration) if the previous
290 // configuration we tried had fewer lines than min-systems-per-page.
291 if (!breaker_->too_few_lines (line_count)
296 line_count += lines_[page_start].compressed_nontitle_lines_count_;
297 if (page > 0 || page_start == 0)
299 // If the last page is ragged, set its force to zero. This way, we will leave
300 // the last page half-empty rather than trying to balance things out
301 // (which only makes sense in non-ragged situations).
302 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
305 Real demerits = space.force_ * space.force_;
307 // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
308 // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
309 // precedence over overfull pages.
310 demerits = min (demerits, BAD_SPACING_PENALTY);
311 demerits += (prev ? prev->demerits_ : 0);
313 Real penalty = breaker_->line_count_penalty (line_count);
315 penalty += lines_[page_start-1].page_penalty_
316 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
318 /* Deal with widow/orphan lines */
319 /* Last line of paragraph is first line on the new page */
320 if ((page_start > 0) &&
321 (page_start < lines_.size ()) &&
322 (lines_[page_start].last_markup_line_))
323 penalty += breaker_->orphan_penalty ();
324 /* First line of paragraph is last line on the previous page */
325 if ((page_start > 0) &&
326 (page_start < lines_.size ()) &&
327 (lines_[page_start-1].first_markup_line_))
328 penalty += breaker_->orphan_penalty ();
331 if (demerits < cur.demerits_ || page_start == line)
333 cur.demerits_ = demerits;
334 cur.force_ = space.force_;
335 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
336 cur.system_count_status_ = breaker_->line_count_status (line_count)
337 | (prev ? prev->system_count_status_ : 0);
338 cur.prev_ = page_start - 1;
339 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
344 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
347 return !isinf (cur.demerits_);