2 page-spacing.cc - implement routines for spacing
3 systems vertically on pages
5 source file of the GNU LilyPond music typesetter
7 (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
10 #include "page-spacing.hh"
13 #include "page-breaking.hh"
17 Page_spacing::calc_force ()
19 /* If the first system contains a title, we add back in the page-top-space. */
20 bool starts_with_title = first_line_.compressed_nontitle_lines_count_ < first_line_.compressed_lines_count_;
21 Real height = starts_with_title ? page_height_ + page_top_space_ : page_height_;
23 if (rod_height_ + last_line_.bottom_padding_ >= height)
26 force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
27 / max (0.1, inverse_spring_k_);
31 Page_spacing::resize (Real new_height)
33 page_height_ = new_height;
38 Page_spacing::append_system (const Line_details &line)
43 rod_height_ += last_line_.padding_;
45 rod_height_ += line.extent_.length ();
46 spring_len_ += line.space_;
47 inverse_spring_k_ += line.inverse_hooke_;
55 Page_spacing::prepend_system (const Line_details &line)
58 rod_height_ += line.padding_;
62 rod_height_ += line.extent_.length ();
63 spring_len_ += line.space_;
64 inverse_spring_k_ += line.inverse_hooke_;
72 Page_spacing::clear ()
74 force_ = rod_height_ = spring_len_ = 0;
75 inverse_spring_k_ = 0;
79 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
82 first_page_num_ = first_page_num;
85 ragged_ = breaker->ragged ();
86 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
90 Page_spacer::solve (vsize page_count)
92 if (page_count > max_page_count_)
95 Page_spacing_result ret;
97 vsize system = lines_.size () - 1;
98 vsize extra_systems = 0;
99 vsize extra_pages = 0;
101 if (isinf (state_.at (system, page_count-1).demerits_))
103 programming_error ("tried to space systems on a bad number of pages");
104 /* Usually, this means that we tried to cram too many systems into
105 to few pages. To avoid crashing, we look for the largest number of
106 systems that we can fit properly onto the right number of pages.
107 All the systems that don't fit get tacked onto the last page.
110 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
115 extra_systems = system - i;
120 /* try chopping off pages from the end */
122 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
127 extra_pages = page_count - j;
131 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
135 ret.force_.resize (page_count);
136 ret.systems_per_page_.resize (page_count);
137 ret.penalty_ = state_.at (system, page_count-1).penalty_
138 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
141 for (vsize p = page_count; p--;)
143 assert (system != VPOS);
145 Page_spacing_node const &ps = state_.at (system, p);
146 ret.force_[p] = ps.force_;
147 ret.demerits_ += ps.force_ * ps.force_;
149 ret.systems_per_page_[p] = system + 1;
151 ret.systems_per_page_[p] = system - ps.prev_;
157 ret.systems_per_page_.back () += extra_systems;
158 ret.demerits_ += BAD_SPACING_PENALTY;
162 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
163 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
164 ret.demerits_ += BAD_SPACING_PENALTY;
168 ret.demerits_ += ret.penalty_;
173 Page_spacer::resize (vsize page_count)
175 assert (page_count > 0);
177 if (max_page_count_ >= page_count)
180 state_.resize (lines_.size (), page_count, Page_spacing_node ());
181 for (vsize page = max_page_count_; page < page_count; page++)
182 for (vsize line = page; line < lines_.size (); line++)
183 if (!calc_subproblem (page, line))
186 max_page_count_ = page_count;
189 // Carries out one step in the dynamic programming algorithm for putting systems
190 // on a fixed number of pages. One call to this routine calculates the best
191 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
192 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
194 // This algorithm is similar to the constrained-breaking algorithm.
196 Page_spacer::calc_subproblem (vsize page, vsize line)
198 bool last = line == lines_.size () - 1;
199 Page_spacing space (breaker_->page_height (page + first_page_num_, last),
200 breaker_->page_top_space ());
201 Page_spacing_node &cur = state_.at (line, page);
202 bool ragged = ragged_ || (ragged_last_ && last);
205 for (vsize page_start = line+1; page_start > page && page_start--;)
207 Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
209 space.prepend_system (lines_[page_start]);
211 // This 'if' statement is a little hard to parse. It won't consider this configuration
212 // if it is overfull unless the current configuration is the first one with this start
213 // point. We also make an exception (and consider this configuration) if the previous
214 // configuration we tried had fewer lines than min-systems-per-page.
215 if (!breaker_->too_few_lines (line_count)
217 && (isinf (space.force_) || (space.force_ < 0 && ragged)))
220 line_count += lines_[page_start].compressed_nontitle_lines_count_;
221 if (page > 0 || page_start == 0)
223 // If the last page is ragged, set its force to zero. This way, we will leave
224 // the last page half-empty rather than trying to balance things out
225 // (which only makes sense in non-ragged situations).
226 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
229 Real demerits = space.force_ * space.force_;
230 /* If a single line is taller than a page, we need to consider it as
231 a possible solution (but we give it a very bad score). */
232 if (isinf (space.force_) && page_start == line)
233 demerits = BAD_SPACING_PENALTY;
234 demerits += (prev ? prev->demerits_ : 0);
236 Real penalty = breaker_->line_count_penalty (line_count);
238 penalty += lines_[page_start-1].page_penalty_
239 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
242 if (demerits < cur.demerits_ || page_start == line)
244 cur.demerits_ = demerits;
245 cur.force_ = space.force_;
246 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
247 cur.system_count_status_ = breaker_->line_count_status (line_count)
248 | (prev ? prev->system_count_status_ : 0);
249 cur.prev_ = page_start - 1;
254 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
257 return !isinf (cur.demerits_);