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. In that case,
251 // the algorithm may not be optimal: if our page has a very large header then perhaps
252 // we need to look ahead a few systems in order to find the best solution. But
253 // we won't, because we stop once we overfill the page with the large header.
254 vsize page_num = page == VPOS ? 0 : page;
255 Real paper_height = breaker_->paper_height ();
256 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
258 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
259 bool ragged = ragged_ || (ragged_last_ && last);
262 for (vsize page_start = line+1; page_start > page_num && page_start--;)
264 Page_spacing_node const *prev = 0;
270 prev = &simple_state_[page_start-1];
271 space.resize (breaker_->page_height (prev->page_ + 1, last));
274 space.resize (breaker_->page_height (first_page_num_, last));
277 prev = &state_.at (page_start-1, page-1);
279 space.prepend_system (lines_[page_start]);
281 bool overfull = (space.rod_height_ > paper_height
283 && (space.rod_height_ + space.spring_len_ > paper_height)));
284 // This 'if' statement is a little hard to parse. It won't consider this configuration
285 // if it is overfull unless the current configuration is the first one with this start
286 // point. We also make an exception (and consider this configuration) if the previous
287 // configuration we tried had fewer lines than min-systems-per-page.
288 if (!breaker_->too_few_lines (line_count)
293 line_count += lines_[page_start].compressed_nontitle_lines_count_;
294 if (page > 0 || page_start == 0)
296 // If the last page is ragged, set its force to zero. This way, we will leave
297 // the last page half-empty rather than trying to balance things out
298 // (which only makes sense in non-ragged situations).
299 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
302 Real demerits = space.force_ * space.force_;
303 /* If a single line is taller than a page, we need to consider it as
304 a possible solution (but we give it a very bad score). */
305 if (isinf (space.force_) && page_start == line)
306 demerits = BAD_SPACING_PENALTY;
307 demerits += (prev ? prev->demerits_ : 0);
309 Real penalty = breaker_->line_count_penalty (line_count);
311 penalty += lines_[page_start-1].page_penalty_
312 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
314 /* Deal with widow/orphan lines */
315 /* Last line of paragraph is first line on the new page */
316 if ((page_start > 0) &&
317 (page_start < lines_.size ()) &&
318 (lines_[page_start].last_markup_line_))
319 penalty += breaker_->orphan_penalty ();
320 /* First line of paragraph is last line on the previous page */
321 if ((page_start > 0) &&
322 (page_start < lines_.size ()) &&
323 (lines_[page_start-1].first_markup_line_))
324 penalty += breaker_->orphan_penalty ();
327 if (demerits < cur.demerits_ || page_start == line)
329 cur.demerits_ = demerits;
330 cur.force_ = space.force_;
331 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
332 cur.system_count_status_ = breaker_->line_count_status (line_count)
333 | (prev ? prev->system_count_status_ : 0);
334 cur.prev_ = page_start - 1;
335 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
340 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
343 return !isinf (cur.demerits_);