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 (vsize page_count)
106 if (page_count > max_page_count_)
109 Page_spacing_result ret;
111 vsize system = lines_.size () - 1;
112 vsize extra_systems = 0;
113 vsize extra_pages = 0;
115 if (isinf (state_.at (system, page_count-1).demerits_))
117 programming_error ("tried to space systems on a bad number of pages");
118 /* Usually, this means that we tried to cram too many systems into
119 to few pages. To avoid crashing, we look for the largest number of
120 systems that we can fit properly onto the right number of pages.
121 All the systems that don't fit get tacked onto the last page.
124 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
129 extra_systems = system - i;
134 /* try chopping off pages from the end */
136 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
141 extra_pages = page_count - j;
145 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
149 ret.force_.resize (page_count);
150 ret.systems_per_page_.resize (page_count);
151 ret.penalty_ = state_.at (system, page_count-1).penalty_
152 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
155 for (vsize p = page_count; p--;)
157 assert (system != VPOS);
159 Page_spacing_node const &ps = state_.at (system, p);
160 ret.force_[p] = ps.force_;
161 ret.demerits_ += ps.force_ * ps.force_;
163 ret.systems_per_page_[p] = system + 1;
165 ret.systems_per_page_[p] = system - ps.prev_;
171 ret.systems_per_page_.back () += extra_systems;
172 ret.force_.back () = BAD_SPACING_PENALTY;
176 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
177 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
184 Page_spacer::resize (vsize page_count)
186 assert (page_count > 0);
188 if (max_page_count_ >= page_count)
191 state_.resize (lines_.size (), page_count, Page_spacing_node ());
192 for (vsize page = max_page_count_; page < page_count; page++)
193 for (vsize line = page; line < lines_.size (); line++)
194 if (!calc_subproblem (page, line))
197 max_page_count_ = page_count;
200 // Carries out one step in the dynamic programming algorithm for putting systems
201 // on a fixed number of pages. One call to this routine calculates the best
202 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
203 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
205 // This algorithm is similar to the constrained-breaking algorithm.
207 Page_spacer::calc_subproblem (vsize page, vsize line)
209 bool last = line == lines_.size () - 1;
210 Page_spacing space (breaker_->page_height (page + first_page_num_, last),
212 Page_spacing_node &cur = state_.at (line, page);
213 bool ragged = ragged_ || (ragged_last_ && last);
216 for (vsize page_start = line+1; page_start > page && page_start--;)
218 Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
220 space.prepend_system (lines_[page_start]);
222 // This 'if' statement is a little hard to parse. It won't consider this configuration
223 // if it is overfull unless the current configuration is the first one with this start
224 // point. We also make an exception (and consider this configuration) if the previous
225 // configuration we tried had fewer lines than min-systems-per-page.
226 if (!breaker_->too_few_lines (line_count)
228 && (isinf (space.force_) || (space.force_ < 0 && ragged)))
231 line_count += lines_[page_start].compressed_nontitle_lines_count_;
232 if (page > 0 || page_start == 0)
234 // If the last page is ragged, set its force to zero. This way, we will leave
235 // the last page half-empty rather than trying to balance things out
236 // (which only makes sense in non-ragged situations).
237 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
240 Real demerits = space.force_ * space.force_;
241 /* If a single line is taller than a page, we need to consider it as
242 a possible solution (but we give it a very bad score). */
243 if (isinf (space.force_) && page_start == line)
244 demerits = BAD_SPACING_PENALTY;
245 demerits += (prev ? prev->demerits_ : 0);
247 Real penalty = breaker_->line_count_penalty (line_count);
249 penalty += lines_[page_start-1].page_penalty_
250 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
252 /* Deal with widow/orphan lines */
253 /* Last line of paragraph is first line on the new page */
254 if ((page_start > 0) &&
255 (page_start < lines_.size ()) &&
256 (lines_[page_start].last_markup_line_))
257 penalty += breaker_->orphan_penalty ();
258 /* First line of paragraph is last line on the previous page */
259 if ((page_start > 0) &&
260 (page_start < lines_.size ()) &&
261 (lines_[page_start-1].first_markup_line_))
262 penalty += breaker_->orphan_penalty ();
265 if (demerits < cur.demerits_ || page_start == line)
267 cur.demerits_ = demerits;
268 cur.force_ = space.force_;
269 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
270 cur.system_count_status_ = breaker_->line_count_status (line_count)
271 | (prev ? prev->system_count_status_ : 0);
272 cur.prev_ = page_start - 1;
277 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
280 return !isinf (cur.demerits_);