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 Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
252 Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page);
253 bool ragged = ragged_ || (ragged_last_ && last);
256 for (vsize page_start = line+1; page_start > page_num && page_start--;)
258 Page_spacing_node const *prev = 0;
264 prev = &simple_state_[page_start-1];
265 space.resize (breaker_->page_height (prev->page_ + 1, last));
268 space.resize (breaker_->page_height (first_page_num_, last));
271 prev = &state_.at (page_start-1, page-1);
273 space.prepend_system (lines_[page_start]);
275 // This 'if' statement is a little hard to parse. It won't consider this configuration
276 // if it is overfull unless the current configuration is the first one with this start
277 // point. We also make an exception (and consider this configuration) if the previous
278 // configuration we tried had fewer lines than min-systems-per-page.
279 if (!breaker_->too_few_lines (line_count)
281 && (isinf (space.force_) || (space.force_ < 0 && ragged)))
284 line_count += lines_[page_start].compressed_nontitle_lines_count_;
285 if (page > 0 || page_start == 0)
287 // If the last page is ragged, set its force to zero. This way, we will leave
288 // the last page half-empty rather than trying to balance things out
289 // (which only makes sense in non-ragged situations).
290 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
293 Real demerits = space.force_ * space.force_;
294 /* If a single line is taller than a page, we need to consider it as
295 a possible solution (but we give it a very bad score). */
296 if (isinf (space.force_) && page_start == line)
297 demerits = BAD_SPACING_PENALTY;
298 demerits += (prev ? prev->demerits_ : 0);
300 Real penalty = breaker_->line_count_penalty (line_count);
302 penalty += lines_[page_start-1].page_penalty_
303 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
305 /* Deal with widow/orphan lines */
306 /* Last line of paragraph is first line on the new page */
307 if ((page_start > 0) &&
308 (page_start < lines_.size ()) &&
309 (lines_[page_start].last_markup_line_))
310 penalty += breaker_->orphan_penalty ();
311 /* First line of paragraph is last line on the previous page */
312 if ((page_start > 0) &&
313 (page_start < lines_.size ()) &&
314 (lines_[page_start-1].first_markup_line_))
315 penalty += breaker_->orphan_penalty ();
318 if (demerits < cur.demerits_ || page_start == line)
320 cur.demerits_ = demerits;
321 cur.force_ = space.force_;
322 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
323 cur.system_count_status_ = breaker_->line_count_status (line_count)
324 | (prev ? prev->system_count_status_ : 0);
325 cur.prev_ = page_start - 1;
326 cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
331 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
334 return !isinf (cur.demerits_);