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 spring_len_ += max (0.0, line.space_ - refpoint_dist);
67 inverse_spring_k_ += line.inverse_hooke_;
75 Page_spacing::prepend_system (const Line_details &line)
80 rod_height_ -= first_line_.full_height ();
81 rod_height_ += first_line_.tallness_;
82 rod_height_ += line.full_height();
84 Real refpoint_dist = line.tallness_
85 + line.refpoint_extent_[DOWN]
86 - first_line_.refpoint_extent_[UP];
87 spring_len_ += max (0.0, line.space_ - refpoint_dist);
88 inverse_spring_k_ += line.inverse_hooke_;
96 Page_spacing::clear ()
98 force_ = rod_height_ = spring_len_ = 0;
99 inverse_spring_k_ = 0;
103 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
106 first_page_num_ = first_page_num;
109 ragged_ = breaker->ragged ();
110 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
114 Page_spacer::solve ()
116 if (simple_state_.empty ())
118 simple_state_.resize (lines_.size ());
119 for (vsize i = 0; i < lines_.size (); ++i)
120 calc_subproblem (VPOS, i);
123 Page_spacing_result ret;
124 ret.penalty_ = simple_state_.back ().penalty_
125 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
126 ret.system_count_status_ = simple_state_.back ().system_count_status_;
128 vsize system = lines_.size () - 1;
129 while (system != VPOS)
131 Page_spacing_node const& cur = simple_state_[system];
132 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
134 ret.force_.push_back (cur.force_);
135 ret.systems_per_page_.push_back (system_count);
136 ret.demerits_ += cur.force_ * cur.force_;
140 reverse (ret.force_);
141 reverse (ret.systems_per_page_);
146 Page_spacer::solve (vsize page_count)
148 if (page_count > max_page_count_)
151 Page_spacing_result ret;
153 vsize system = lines_.size () - 1;
154 vsize extra_systems = 0;
155 vsize extra_pages = 0;
157 if (isinf (state_.at (system, page_count-1).demerits_))
159 programming_error ("tried to space systems on a bad number of pages");
160 /* Usually, this means that we tried to cram too many systems into
161 to few pages. To avoid crashing, we look for the largest number of
162 systems that we can fit properly onto the right number of pages.
163 All the systems that don't fit get tacked onto the last page.
166 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
171 extra_systems = system - i;
176 /* try chopping off pages from the end */
178 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
183 extra_pages = page_count - j;
187 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
191 ret.force_.resize (page_count);
192 ret.systems_per_page_.resize (page_count);
193 ret.system_count_status_ = state_.at (system, page_count-1).system_count_status_;
194 ret.penalty_ = state_.at (system, page_count-1).penalty_
195 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
198 for (vsize p = page_count; p--;)
200 assert (system != VPOS);
202 Page_spacing_node const &ps = state_.at (system, p);
203 ret.force_[p] = ps.force_;
204 ret.demerits_ += ps.force_ * ps.force_;
206 ret.systems_per_page_[p] = system + 1;
208 ret.systems_per_page_[p] = system - ps.prev_;
214 ret.systems_per_page_.back () += extra_systems;
215 ret.force_.back () = BAD_SPACING_PENALTY;
219 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
220 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
227 Page_spacer::resize (vsize page_count)
229 assert (page_count > 0);
231 if (max_page_count_ >= page_count)
234 state_.resize (lines_.size (), page_count, Page_spacing_node ());
235 for (vsize page = max_page_count_; page < page_count; page++)
236 for (vsize line = page; line < lines_.size (); line++)
237 if (!calc_subproblem (page, line))
240 max_page_count_ = page_count;
243 // Carries out one step in the dynamic programming algorithm for putting systems
244 // on a fixed number of pages. One call to this routine calculates the best
245 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
246 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
248 // This algorithm is similar to the constrained-breaking algorithm.
250 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
251 // we don't want to constrain the number of pages that the solution has. In this
252 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
253 // the subproblems look similar for both, so we reuse this method.
255 Page_spacer::calc_subproblem (vsize page, vsize line)
257 bool last = line == lines_.size () - 1;
259 // Note: if page == VPOS then we don't actually know yet which page number we're
260 // working on, so we have to recalculate the page height in the loop. Therefore
261 // our early-exit condition from the loop depends on paper_height rather than
262 // page_height (ie. we break only if we would overfill a page without margins
263 // or headers/footers). Otherwise, the algorithm would not be optimal:
264 // if our page has a very large header then perhaps
265 // we should look ahead a few systems in order to find the best solution. A
266 // good example of this is input/regression/page-spacing-tall-headfoot.ly
267 vsize page_num = page == VPOS ? 0 : page;
268 Real paper_height = breaker_->paper_height ();
269 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
271 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
272 bool ragged = ragged_ || (ragged_last_ && last);
275 for (vsize page_start = line+1; page_start > page_num && page_start--;)
277 Page_spacing_node const *prev = 0;
283 prev = &simple_state_[page_start-1];
284 space.resize (breaker_->page_height (prev->page_ + 1, last));
287 space.resize (breaker_->page_height (first_page_num_, last));
290 prev = &state_.at (page_start-1, page-1);
292 space.prepend_system (lines_[page_start]);
294 bool overfull = (space.rod_height_ > paper_height
296 && (space.rod_height_ + space.spring_len_ > paper_height)));
297 // This 'if' statement is a little hard to parse. It won't consider this configuration
298 // if it is overfull unless the current configuration is the first one with this start
299 // point. We also make an exception (and consider this configuration) if the previous
300 // configuration we tried had fewer lines than min-systems-per-page.
301 if (!breaker_->too_few_lines (line_count)
306 line_count += lines_[page_start].compressed_nontitle_lines_count_;
307 if (page > 0 || page_start == 0)
309 // If the last page is ragged, set its force to zero. This way, we will leave
310 // the last page half-empty rather than trying to balance things out
311 // (which only makes sense in non-ragged situations).
312 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
315 Real demerits = space.force_ * space.force_;
317 // Clamp the demerits at BAD_SPACING_PENALTY, even if the page
318 // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes
319 // precedence over overfull pages.
320 demerits = min (demerits, BAD_SPACING_PENALTY);
321 demerits += (prev ? prev->demerits_ : 0);
323 Real penalty = breaker_->line_count_penalty (line_count);
325 penalty += lines_[page_start-1].page_penalty_
326 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
328 /* Deal with widow/orphan lines */
329 /* Last line of paragraph is first line on the new page */
330 if ((page_start > 0) &&
331 (page_start < lines_.size ()) &&
332 (lines_[page_start].last_markup_line_))
333 penalty += breaker_->orphan_penalty ();
334 /* First line of paragraph is last line on the previous page */
335 if ((page_start > 0) &&
336 (page_start < lines_.size ()) &&
337 (lines_[page_start-1].first_markup_line_))
338 penalty += breaker_->orphan_penalty ();
341 if (demerits < cur.demerits_ || page_start == line)
343 cur.demerits_ = demerits;
344 cur.force_ = space.force_;
345 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
346 cur.system_count_status_ = breaker_->line_count_status (line_count)
347 | (prev ? prev->system_count_status_ : 0);
348 cur.prev_ = page_start - 1;
349 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
354 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
357 return !isinf (cur.demerits_);