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"
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_;
53 spring_len_ += last_line_.spring_length (line);
58 rod_height_ += line.full_height ();
62 inverse_spring_k_ += line.inverse_hooke_;
70 Page_spacing::prepend_system (const Line_details &line)
73 spring_len_ += line.spring_length (first_line_);
77 rod_height_ -= first_line_.full_height ();
78 rod_height_ += first_line_.tallness_;
79 rod_height_ += line.full_height();
81 inverse_spring_k_ += line.inverse_hooke_;
89 Page_spacing::clear ()
91 force_ = rod_height_ = spring_len_ = 0;
92 inverse_spring_k_ = 0;
96 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
99 first_page_num_ = first_page_num;
102 ragged_ = breaker->ragged ();
103 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
107 Page_spacer::solve ()
109 if (simple_state_.empty ())
111 simple_state_.resize (lines_.size ());
112 for (vsize i = 0; i < lines_.size (); ++i)
113 calc_subproblem (VPOS, i);
116 Page_spacing_result ret;
117 ret.penalty_ = simple_state_.back ().penalty_
118 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
119 ret.system_count_status_ = simple_state_.back ().system_count_status_;
121 vsize system = lines_.size () - 1;
122 while (system != VPOS)
124 Page_spacing_node const& cur = simple_state_[system];
125 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
127 ret.force_.push_back (cur.force_);
128 ret.systems_per_page_.push_back (system_count);
129 ret.demerits_ += cur.force_ * cur.force_;
133 reverse (ret.force_);
134 reverse (ret.systems_per_page_);
139 Page_spacer::solve (vsize page_count)
141 if (page_count > max_page_count_)
144 Page_spacing_result ret;
146 vsize system = lines_.size () - 1;
147 vsize extra_systems = 0;
148 vsize extra_pages = 0;
150 if (isinf (state_.at (system, page_count-1).demerits_))
152 programming_error ("tried to space systems on a bad number of pages");
153 /* Usually, this means that we tried to cram too many systems into
154 to few pages. To avoid crashing, we look for the largest number of
155 systems that we can fit properly onto the right number of pages.
156 All the systems that don't fit get tacked onto the last page.
159 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
164 extra_systems = system - i;
169 /* try chopping off pages from the end */
171 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
176 extra_pages = page_count - j;
180 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
184 ret.force_.resize (page_count);
185 ret.systems_per_page_.resize (page_count);
186 ret.system_count_status_ = state_.at (system, page_count-1).system_count_status_;
187 ret.penalty_ = state_.at (system, page_count-1).penalty_
188 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
191 for (vsize p = page_count; p--;)
193 assert (system != VPOS);
195 Page_spacing_node const &ps = state_.at (system, p);
196 ret.force_[p] = ps.force_;
197 ret.demerits_ += ps.force_ * ps.force_;
199 ret.systems_per_page_[p] = system + 1;
201 ret.systems_per_page_[p] = system - ps.prev_;
207 ret.systems_per_page_.back () += extra_systems;
208 ret.force_.back () = BAD_SPACING_PENALTY;
212 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
213 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
220 Page_spacer::resize (vsize page_count)
222 assert (page_count > 0);
224 if (max_page_count_ >= page_count)
227 state_.resize (lines_.size (), page_count, Page_spacing_node ());
228 for (vsize page = max_page_count_; page < page_count; page++)
229 for (vsize line = page; line < lines_.size (); line++)
230 if (!calc_subproblem (page, line))
233 max_page_count_ = page_count;
236 // Carries out one step in the dynamic programming algorithm for putting systems
237 // on a fixed number of pages. One call to this routine calculates the best
238 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
239 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
241 // This algorithm is similar to the constrained-breaking algorithm.
243 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
244 // we don't want to constrain the number of pages that the solution has. In this
245 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
246 // the subproblems look similar for both, so we reuse this method.
248 Page_spacer::calc_subproblem (vsize page, vsize line)
250 bool last = line == lines_.size () - 1;
252 // Note: if page == VPOS then we don't actually know yet which page number we're
253 // working on, so we have to recalculate the page height in the loop. Therefore
254 // our early-exit condition from the loop depends on paper_height rather than
255 // page_height (ie. we break only if we would overfill a page without margins
256 // or headers/footers). Otherwise, the algorithm would not be optimal:
257 // if our page has a very large header then perhaps
258 // we should look ahead a few systems in order to find the best solution. A
259 // good example of this is input/regression/page-spacing-tall-headfoot.ly
260 vsize page_num = page == VPOS ? 0 : page;
261 Real paper_height = breaker_->paper_height ();
262 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
264 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
265 bool ragged = ragged_ || (ragged_last_ && last);
268 for (vsize page_start = line+1; page_start > page_num && page_start--;)
270 Page_spacing_node const *prev = 0;
276 prev = &simple_state_[page_start-1];
277 space.resize (breaker_->page_height (prev->page_ + 1, last));
280 space.resize (breaker_->page_height (first_page_num_, last));
283 prev = &state_.at (page_start-1, page-1);
285 space.prepend_system (lines_[page_start]);
287 bool overfull = (space.rod_height_ > paper_height
289 && (space.rod_height_ + space.spring_len_ > paper_height)));
290 // This 'if' statement is a little hard to parse. It won't consider this configuration
291 // if it is overfull unless the current configuration is the first one with this start
292 // point. We also make an exception (and consider this configuration) if the previous
293 // configuration we tried had fewer lines than min-systems-per-page.
294 if (!breaker_->too_few_lines (line_count)
299 line_count += lines_[page_start].compressed_nontitle_lines_count_;
300 if (page > 0 || page_start == 0)
302 // If the last page is ragged, set its force to zero. This way, we will leave
303 // the last page half-empty rather than trying to balance things out
304 // (which only makes sense in non-ragged situations).
305 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
308 Real demerits = space.force_ * space.force_;
310 // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
311 // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
312 // precedence over overfull pages.
313 demerits = min (demerits, BAD_SPACING_PENALTY);
314 demerits += (prev ? prev->demerits_ : 0);
316 Real penalty = breaker_->line_count_penalty (line_count);
318 penalty += lines_[page_start-1].page_penalty_
319 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
321 /* Deal with widow/orphan lines */
322 /* Last line of paragraph is first line on the new page */
323 if ((page_start > 0) &&
324 (page_start < lines_.size ()) &&
325 (lines_[page_start].last_markup_line_))
326 penalty += breaker_->orphan_penalty ();
327 /* First line of paragraph is last line on the previous page */
328 if ((page_start > 0) &&
329 (page_start < lines_.size ()) &&
330 (lines_[page_start-1].first_markup_line_))
331 penalty += breaker_->orphan_penalty ();
334 if (demerits < cur.demerits_ || page_start == line)
336 cur.demerits_ = demerits;
337 cur.force_ = space.force_;
338 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
339 cur.system_count_status_ = breaker_->line_count_status (line_count)
340 | (prev ? prev->system_count_status_ : 0);
341 cur.prev_ = page_start - 1;
342 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
347 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
350 return !isinf (cur.demerits_);