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 vsize system = lines_.size () - 1;
115 while (system != VPOS)
117 Page_spacing_node const& cur = simple_state_[system];
118 vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
120 ret.force_.push_back (cur.force_);
121 ret.systems_per_page_.push_back (system_count);
122 ret.demerits_ += cur.force_ * cur.force_;
126 reverse (ret.force_);
127 reverse (ret.systems_per_page_);
132 Page_spacer::solve (vsize page_count)
134 if (page_count > max_page_count_)
137 Page_spacing_result ret;
139 vsize system = lines_.size () - 1;
140 vsize extra_systems = 0;
141 vsize extra_pages = 0;
143 if (isinf (state_.at (system, page_count-1).demerits_))
145 programming_error ("tried to space systems on a bad number of pages");
146 /* Usually, this means that we tried to cram too many systems into
147 to few pages. To avoid crashing, we look for the largest number of
148 systems that we can fit properly onto the right number of pages.
149 All the systems that don't fit get tacked onto the last page.
152 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
157 extra_systems = system - i;
162 /* try chopping off pages from the end */
164 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
169 extra_pages = page_count - j;
173 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
177 ret.force_.resize (page_count);
178 ret.systems_per_page_.resize (page_count);
179 ret.penalty_ = state_.at (system, page_count-1).penalty_
180 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
183 for (vsize p = page_count; p--;)
185 assert (system != VPOS);
187 Page_spacing_node const &ps = state_.at (system, p);
188 ret.force_[p] = ps.force_;
189 ret.demerits_ += ps.force_ * ps.force_;
191 ret.systems_per_page_[p] = system + 1;
193 ret.systems_per_page_[p] = system - ps.prev_;
199 ret.systems_per_page_.back () += extra_systems;
200 ret.force_.back () = BAD_SPACING_PENALTY;
204 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
205 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
212 Page_spacer::resize (vsize page_count)
214 assert (page_count > 0);
216 if (max_page_count_ >= page_count)
219 state_.resize (lines_.size (), page_count, Page_spacing_node ());
220 for (vsize page = max_page_count_; page < page_count; page++)
221 for (vsize line = page; line < lines_.size (); line++)
222 if (!calc_subproblem (page, line))
225 max_page_count_ = page_count;
228 // Carries out one step in the dynamic programming algorithm for putting systems
229 // on a fixed number of pages. One call to this routine calculates the best
230 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
231 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
233 // This algorithm is similar to the constrained-breaking algorithm.
235 // If page == VPOS, we act on simple_state_ instead of state_. This is useful if
236 // we don't want to constrain the number of pages that the solution has. In this
237 // case, the algorithm looks more like the page-turn-page-breaking algorithm. But
238 // the subproblems look similar for both, so we reuse this method.
240 Page_spacer::calc_subproblem (vsize page, vsize line)
242 bool last = line == lines_.size () - 1;
244 // Note: if page == VPOS then we don't actually know yet which page number we're
245 // working on, so we have to recalculate the page height in the loop. In that case,
246 // the algorithm may not be optimal: if our page has a very large header then perhaps
247 // we need to look ahead a few systems in order to find the best solution. But
248 // we won't, because we stop once we overfill the page with the large header.
249 vsize page_num = page == VPOS ? 0 : page;
250 Real paper_height = breaker_->paper_height ();
251 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
253 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
254 bool ragged = ragged_ || (ragged_last_ && last);
257 for (vsize page_start = line+1; page_start > page_num && page_start--;)
259 Page_spacing_node const *prev = 0;
265 prev = &simple_state_[page_start-1];
266 space.resize (breaker_->page_height (prev->page_ + 1, last));
269 space.resize (breaker_->page_height (first_page_num_, last));
272 prev = &state_.at (page_start-1, page-1);
274 space.prepend_system (lines_[page_start]);
276 bool overfull = (space.rod_height_ > paper_height
278 && (space.rod_height_ + space.spring_len_ > paper_height)));
279 // This 'if' statement is a little hard to parse. It won't consider this configuration
280 // if it is overfull unless the current configuration is the first one with this start
281 // point. We also make an exception (and consider this configuration) if the previous
282 // configuration we tried had fewer lines than min-systems-per-page.
283 if (!breaker_->too_few_lines (line_count)
288 line_count += lines_[page_start].compressed_nontitle_lines_count_;
289 if (page > 0 || page_start == 0)
291 // If the last page is ragged, set its force to zero. This way, we will leave
292 // the last page half-empty rather than trying to balance things out
293 // (which only makes sense in non-ragged situations).
294 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
297 Real demerits = space.force_ * space.force_;
298 /* If a single line is taller than a page, we need to consider it as
299 a possible solution (but we give it a very bad score). */
300 if (isinf (space.force_) && page_start == line)
301 demerits = BAD_SPACING_PENALTY;
302 demerits += (prev ? prev->demerits_ : 0);
304 Real penalty = breaker_->line_count_penalty (line_count);
306 penalty += lines_[page_start-1].page_penalty_
307 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
309 /* Deal with widow/orphan lines */
310 /* Last line of paragraph is first line on the new page */
311 if ((page_start > 0) &&
312 (page_start < lines_.size ()) &&
313 (lines_[page_start].last_markup_line_))
314 penalty += breaker_->orphan_penalty ();
315 /* First line of paragraph is last line on the previous page */
316 if ((page_start > 0) &&
317 (page_start < lines_.size ()) &&
318 (lines_[page_start-1].first_markup_line_))
319 penalty += breaker_->orphan_penalty ();
322 if (demerits < cur.demerits_ || page_start == line)
324 cur.demerits_ = demerits;
325 cur.force_ = space.force_;
326 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
327 cur.system_count_status_ = breaker_->line_count_status (line_count)
328 | (prev ? prev->system_count_status_ : 0);
329 cur.prev_ = page_start - 1;
330 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
335 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
338 return !isinf (cur.demerits_);