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 ();
59 if (!line.tight_spacing_)
60 rod_height_ += line.title_ ? last_line_.title_padding_ : last_line_.padding_;
61 spring_len_ += line.space_;
62 inverse_spring_k_ += line.inverse_hooke_;
70 Page_spacing::prepend_system (const Line_details &line)
72 if (rod_height_ && !first_line_.tight_spacing_)
73 rod_height_ += first_line_.title_ ? line.title_padding_ : line.padding_;
77 rod_height_ -= first_line_.full_height ();
78 rod_height_ += first_line_.tallness_;
79 rod_height_ += line.full_height();
80 spring_len_ += line.space_;
81 inverse_spring_k_ += line.inverse_hooke_;
89 Page_spacing::clear ()
91 force_ = rod_height_ = spring_len_ = 0;
92 inverse_spring_k_ = 0;
96 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
99 first_page_num_ = first_page_num;
102 ragged_ = breaker->ragged ();
103 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
107 Page_spacer::solve (vsize page_count)
109 if (page_count > max_page_count_)
112 Page_spacing_result ret;
114 vsize system = lines_.size () - 1;
115 vsize extra_systems = 0;
116 vsize extra_pages = 0;
118 if (isinf (state_.at (system, page_count-1).demerits_))
120 programming_error ("tried to space systems on a bad number of pages");
121 /* Usually, this means that we tried to cram too many systems into
122 to few pages. To avoid crashing, we look for the largest number of
123 systems that we can fit properly onto the right number of pages.
124 All the systems that don't fit get tacked onto the last page.
127 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
132 extra_systems = system - i;
137 /* try chopping off pages from the end */
139 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
144 extra_pages = page_count - j;
148 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
152 ret.force_.resize (page_count);
153 ret.systems_per_page_.resize (page_count);
154 ret.penalty_ = state_.at (system, page_count-1).penalty_
155 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
158 for (vsize p = page_count; p--;)
160 assert (system != VPOS);
162 Page_spacing_node const &ps = state_.at (system, p);
163 ret.force_[p] = ps.force_;
164 ret.demerits_ += ps.force_ * ps.force_;
166 ret.systems_per_page_[p] = system + 1;
168 ret.systems_per_page_[p] = system - ps.prev_;
174 ret.systems_per_page_.back () += extra_systems;
175 ret.force_.back () = BAD_SPACING_PENALTY;
179 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
180 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
187 Page_spacer::resize (vsize page_count)
189 assert (page_count > 0);
191 if (max_page_count_ >= page_count)
194 state_.resize (lines_.size (), page_count, Page_spacing_node ());
195 for (vsize page = max_page_count_; page < page_count; page++)
196 for (vsize line = page; line < lines_.size (); line++)
197 if (!calc_subproblem (page, line))
200 max_page_count_ = page_count;
203 // Carries out one step in the dynamic programming algorithm for putting systems
204 // on a fixed number of pages. One call to this routine calculates the best
205 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
206 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
208 // This algorithm is similar to the constrained-breaking algorithm.
210 Page_spacer::calc_subproblem (vsize page, vsize line)
212 bool last = line == lines_.size () - 1;
213 Page_spacing space (breaker_->page_height (page + first_page_num_, last),
215 Page_spacing_node &cur = state_.at (line, page);
216 bool ragged = ragged_ || (ragged_last_ && last);
219 for (vsize page_start = line+1; page_start > page && page_start--;)
221 Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
223 space.prepend_system (lines_[page_start]);
225 // This 'if' statement is a little hard to parse. It won't consider this configuration
226 // if it is overfull unless the current configuration is the first one with this start
227 // point. We also make an exception (and consider this configuration) if the previous
228 // configuration we tried had fewer lines than min-systems-per-page.
229 if (!breaker_->too_few_lines (line_count)
231 && (isinf (space.force_) || (space.force_ < 0 && ragged)))
234 line_count += lines_[page_start].compressed_nontitle_lines_count_;
235 if (page > 0 || page_start == 0)
237 // If the last page is ragged, set its force to zero. This way, we will leave
238 // the last page half-empty rather than trying to balance things out
239 // (which only makes sense in non-ragged situations).
240 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
243 Real demerits = space.force_ * space.force_;
244 /* If a single line is taller than a page, we need to consider it as
245 a possible solution (but we give it a very bad score). */
246 if (isinf (space.force_) && page_start == line)
247 demerits = BAD_SPACING_PENALTY;
248 demerits += (prev ? prev->demerits_ : 0);
250 Real penalty = breaker_->line_count_penalty (line_count);
252 penalty += lines_[page_start-1].page_penalty_
253 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
255 /* Deal with widow/orphan lines */
256 /* Last line of paragraph is first line on the new page */
257 if ((page_start > 0) &&
258 (page_start < lines_.size ()) &&
259 (lines_[page_start].last_markup_line_))
260 penalty += breaker_->orphan_penalty ();
261 /* First line of paragraph is last line on the previous page */
262 if ((page_start > 0) &&
263 (page_start < lines_.size ()) &&
264 (lines_[page_start-1].first_markup_line_))
265 penalty += breaker_->orphan_penalty ();
268 if (demerits < cur.demerits_ || page_start == line)
270 cur.demerits_ = demerits;
271 cur.force_ = space.force_;
272 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
273 cur.system_count_status_ = breaker_->line_count_status (line_count)
274 | (prev ? prev->system_count_status_ : 0);
275 cur.prev_ = page_start - 1;
280 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
283 return !isinf (cur.demerits_);