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 is a title, we add back in the page-top-space. */
20 Real height = first_line_.title_ ? page_height_ + page_top_space_ : page_height_;
22 if (rod_height_ + last_line_.bottom_padding_ >= height)
25 force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
26 / max (0.1, inverse_spring_k_);
30 Page_spacing::resize (Real new_height)
32 page_height_ = new_height;
37 Page_spacing::append_system (const Line_details &line)
42 rod_height_ += last_line_.padding_;
44 rod_height_ += line.extent_.length ();
45 spring_len_ += line.space_;
46 inverse_spring_k_ += line.inverse_hooke_;
54 Page_spacing::prepend_system (const Line_details &line)
57 rod_height_ += line.padding_;
61 rod_height_ += line.extent_.length ();
62 spring_len_ += line.space_;
63 inverse_spring_k_ += line.inverse_hooke_;
71 Page_spacing::clear ()
73 force_ = rod_height_ = spring_len_ = 0;
74 inverse_spring_k_ = 0;
78 Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const *breaker)
81 first_page_num_ = first_page_num;
84 ragged_ = breaker->ragged ();
85 ragged_last_ = breaker->is_last () && breaker->ragged_last ();
89 Page_spacer::solve (vsize page_count)
91 if (page_count > max_page_count_)
94 Page_spacing_result ret;
96 vsize system = lines_.size () - 1;
97 vsize extra_systems = 0;
98 vsize extra_pages = 0;
100 if (isinf (state_.at (system, page_count-1).demerits_))
102 programming_error ("tried to space systems on a bad number of pages");
103 /* Usually, this means that we tried to cram too many systems into
104 to few pages. To avoid crashing, we look for the largest number of
105 systems that we can fit properly onto the right number of pages.
106 All the systems that don't fit get tacked onto the last page.
109 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i; i--)
114 extra_systems = system - i;
119 /* try chopping off pages from the end */
121 for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
126 extra_pages = page_count - j;
130 return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
134 ret.force_.resize (page_count);
135 ret.systems_per_page_.resize (page_count);
136 ret.penalty_ = state_.at (system, page_count-1).penalty_
137 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
140 for (vsize p = page_count; p--;)
142 assert (system != VPOS);
144 Page_spacing_node const &ps = state_.at (system, p);
145 ret.force_[p] = ps.force_;
146 ret.demerits_ += ps.force_ * ps.force_;
148 ret.systems_per_page_[p] = system + 1;
150 ret.systems_per_page_[p] = system - ps.prev_;
156 ret.systems_per_page_.back () += extra_systems;
157 ret.demerits_ += BAD_SPACING_PENALTY;
161 ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
162 ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
163 ret.demerits_ += BAD_SPACING_PENALTY;
167 ret.demerits_ += ret.penalty_;
172 Page_spacer::resize (vsize page_count)
174 assert (page_count > 0);
176 if (max_page_count_ >= page_count)
179 state_.resize (lines_.size (), page_count, Page_spacing_node ());
180 for (vsize page = max_page_count_; page < page_count; page++)
181 for (vsize line = page; line < lines_.size (); line++)
182 if (!calc_subproblem (page, line))
185 max_page_count_ = page_count;
188 // Carries out one step in the dynamic programming algorithm for putting systems
189 // on a fixed number of pages. One call to this routine calculates the best
190 // configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
191 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
193 // This algorithm is similar to the constrained-breaking algorithm.
195 Page_spacer::calc_subproblem (vsize page, vsize line)
197 bool last = line == lines_.size () - 1;
198 Page_spacing space (breaker_->page_height (page + first_page_num_, last),
199 breaker_->page_top_space ());
200 Page_spacing_node &cur = state_.at (line, page);
201 bool ragged = ragged_ || (ragged_last_ && last);
204 for (vsize page_start = line+1; page_start > page && page_start--;)
206 Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
208 space.prepend_system (lines_[page_start]);
210 // This 'if' statement is a little hard to parse. It won't consider this configuration
211 // if it is overfull unless the current configuration is the first one with this start
212 // point. We also make an exception (and consider this configuration) if the previous
213 // configuration we tried had fewer lines than min-systems-per-page.
214 if (!breaker_->too_few_lines (line_count)
216 && (isinf (space.force_) || (space.force_ < 0 && ragged)))
219 line_count += lines_[page_start].compressed_nontitle_lines_count_;
220 if (page > 0 || page_start == 0)
222 // If the last page is ragged, set its force to zero. This way, we will leave
223 // the last page half-empty rather than trying to balance things out
224 // (which only makes sense in non-ragged situations).
225 if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
228 Real demerits = space.force_ * space.force_;
229 /* If a single line is taller than a page, we need to consider it as
230 a possible solution (but we give it a very bad score). */
231 if (isinf (space.force_) && page_start == line)
232 demerits = BAD_SPACING_PENALTY;
233 demerits += (prev ? prev->demerits_ : 0);
235 Real penalty = breaker_->line_count_penalty (line_count);
237 penalty += lines_[page_start-1].page_penalty_
238 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
241 if (demerits < cur.demerits_ || page_start == line)
243 cur.demerits_ = demerits;
244 cur.force_ = space.force_;
245 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
246 cur.system_count_status_ = breaker_->line_count_status (line_count)
247 | (prev ? prev->system_count_status_ : 0);
248 cur.prev_ = page_start - 1;
253 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
256 return !isinf (cur.demerits_);