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--2007 Joe Neeman <joeneeman@gmail.com>
10 #include "page-spacing.hh"
16 A much simplified rods-and-springs problem.
24 Real inverse_spring_k_;
26 Line_details last_line_;
28 Page_spacing (Real page_height)
30 page_height_ = page_height;
36 void append_system (const Line_details &line);
37 void prepend_system (const Line_details &line);
41 /* In order to prevent possible division by zero, we require every line
42 to have a spring of non-zero length. */
44 line_space (const Line_details &line)
46 return max (0.1, line.space_);
50 Page_spacing::calc_force ()
52 if (rod_height_ + last_line_.bottom_padding_ >= page_height_ || !inverse_spring_k_)
55 force_ = (page_height_ - rod_height_ - last_line_.bottom_padding_ - spring_len_) / inverse_spring_k_;
59 Page_spacing::append_system (const Line_details &line)
61 rod_height_ += last_line_.padding_;
63 rod_height_ += line.extent_.length ();
64 spring_len_ += line_space (line);
65 inverse_spring_k_ += max (0.1, line.inverse_hooke_);
73 Page_spacing::prepend_system (const Line_details &line)
76 rod_height_ += line.padding_;
80 rod_height_ += line.extent_.length ();
81 spring_len_ += line_space (line);
82 inverse_spring_k_ += max (0.1, line.inverse_hooke_);
88 Page_spacing::clear ()
90 force_ = rod_height_ = spring_len_ = 0;
91 inverse_spring_k_ = 0;
94 /* for each forbidden page break, merge the systems around it into one system. */
95 static vector<Line_details>
96 compress_lines (const vector<Line_details> &orig)
98 vector<Line_details> ret;
100 for (vsize i = 0; i < orig.size (); i++)
102 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
104 Line_details const &old = ret.back ();
105 Line_details compressed = orig[i];
106 compressed.extent_[DOWN] = old.extent_[DOWN];
107 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
108 compressed.space_ += old.space_;
109 compressed.inverse_hooke_ += old.inverse_hooke_;
111 /* we don't need the force_ field for the vertical spacing,
112 so we use force_ = n to signal that the line was compressed,
113 reducing the number of lines by n (and force_ = 0 otherwise).
114 This makes uncompression much easier. */
115 compressed.force_ = old.force_ + 1;
116 ret.back () = compressed;
120 ret.push_back (orig[i]);
121 ret.back ().force_ = 0;
127 /* translate the number of systems-per-page into something meaningful for
128 the uncompressed lines.
131 uncompress_solution (vector<vsize> const &systems_per_page,
132 vector<Line_details> const &compressed)
137 for (vsize i = 0; i < systems_per_page.size (); i++)
139 int compressed_count = 0;
140 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
141 compressed_count += (int)compressed[j].force_;
143 ret.push_back (systems_per_page[i] + compressed_count);
144 start_sys += systems_per_page[i];
149 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
150 are by far the most common cases, we have special functions for them */
151 static Spacing_result
152 space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
154 Page_spacing space (page_height);
157 for (vsize i = 0; i < lines.size (); i++)
158 space.append_system (lines[i]);
160 ret.systems_per_page_.push_back (lines.size ());
161 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
162 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
163 ret.demerits_ = ret.force_.back () * ret.force_.back () + ret.penalty_;
168 static Spacing_result
169 space_systems_on_2_pages (vector<Line_details> const &lines,
174 /* if there is a forced break, this reduces to 2 1-page problems */
175 for (vsize i = 0; i + 1 < lines.size (); i++)
176 if (lines[i].page_permission_ == ly_symbol2scm ("force"))
178 vector<Line_details> lines1 (lines.begin (), lines.begin () + i + 1);
179 vector<Line_details> lines2 (lines.begin () + i + 1, lines.end ());
180 Spacing_result p1 = space_systems_on_1_page (lines1, page_height, ragged);
181 Spacing_result p2 = space_systems_on_1_page (lines2, page_height, ragged || ragged_last);
183 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
184 p1.force_.push_back (p2.force_[0]);
185 p1.penalty_ += p2.penalty_ - lines[i].turn_penalty_;
186 p1.demerits_ += p2.demerits_ - lines[i].turn_penalty_;
190 vector<Real> page1_force;
191 vector<Real> page2_force;
192 Page_spacing page1 (page_height);
193 Page_spacing page2 (page_height);
195 page1_force.resize (lines.size () - 1, infinity_f);
196 page2_force.resize (lines.size () - 1, infinity_f);
198 for (vsize i = 0; i < page1_force.size (); i++)
200 page1.append_system (lines[i]);
201 page2.prepend_system (lines[lines.size () - 1 - i]);
202 page1_force[i] = (ragged && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
204 if (ragged || ragged_last)
205 page2_force[page2_force.size () - 1 - i] =
206 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
208 page2_force[page2_force.size () - 1 - i] = page2.force_;
211 vsize best_sys_count = 1;
212 Real best_demerits = infinity_f;
213 for (vsize i = 0; i < page1_force.size (); i++)
215 Real dem = page1_force[i] * page1_force[i]
216 + page2_force[i] * page2_force[i]
217 + lines[i+1].page_penalty_
218 + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
219 if (dem < best_demerits)
222 best_sys_count = i+1;
227 ret.systems_per_page_.push_back (best_sys_count);
228 ret.systems_per_page_.push_back (lines.size () - best_sys_count);
229 ret.force_.push_back (page1_force[best_sys_count-1]);
230 ret.force_.push_back (page2_force[best_sys_count-1]);
231 ret.penalty_ = lines[best_sys_count-1].page_penalty_
232 + lines.back ().page_penalty_
233 + lines.back ().turn_penalty_;
234 ret.demerits_ = best_demerits;
239 Page_spacer::Page_spacer (vector<Line_details> const &lines, Real page_height, bool ragged, bool ragged_last)
242 page_height_ = page_height;
245 ragged_last_ = ragged_last;
249 Page_spacer::solve (vsize page_count)
251 if (page_count > max_page_count_)
255 ret.force_.resize (page_count);
256 ret.systems_per_page_.resize (page_count);
258 vsize system = lines_.size () - 1;
259 vsize tack_onto_the_end = 0;
261 if (isinf (state_.at (system, page_count-1).demerits_))
263 programming_error ("tried to space systems on a bad number of pages");
264 /* Usually, this means that we tried to cram too many systems into
265 to few pages. To avoid crashing, we look for the largest number of
266 systems that we can fit properly onto the right number of pages.
267 All the systems that don't fit get tacked onto the last page.
270 for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i--; )
275 tack_onto_the_end = system - i;
279 return Spacing_result (); /* couldn't salvage it -- probably going to crash */
282 ret.penalty_ = state_.at (system, page_count-1).penalty_
283 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
286 for (vsize p = page_count; p--;)
288 assert (system != VPOS);
290 Page_spacing_node const &ps = state_.at (system, p);
291 ret.force_[p] = ps.force_;
292 ret.demerits_ += ps.force_ * ps.force_;
294 ret.systems_per_page_[p] = system + 1;
296 ret.systems_per_page_[p] = system - ps.prev_ + tack_onto_the_end;
299 ret.demerits_ += ret.penalty_;
304 Page_spacer::resize (vsize page_count)
306 assert (page_count > 0);
308 if (max_page_count_ >= page_count)
311 state_.resize (lines_.size (), page_count, Page_spacing_node ());
312 for (vsize page = max_page_count_; page < page_count; page++)
313 for (vsize line = page; line < lines_.size (); line++)
314 if (!calc_subproblem (page, line))
317 max_page_count_ = page_count;
321 Page_spacer::calc_subproblem (vsize page, vsize line)
323 Page_spacing space (page_height_);
324 Page_spacing_node &cur = state_.at (line, page);
325 bool ragged = ragged_ || (ragged_last_ && line == lines_.size () - 1);
327 for (vsize page_start = line+1; page_start > page && page_start--;)
329 Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
331 space.prepend_system (lines_[page_start]);
332 if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
335 if (page > 0 || page_start == 0)
337 if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0)
340 /* we may have to deal with single lines that are taller than a page */
341 if (isinf (space.force_) && page_start == line)
342 space.force_ = -200000;
344 Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
347 penalty = lines_[page_start-1].page_penalty_
348 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
351 if (dem < cur.demerits_ || page_start == line)
354 cur.force_ = space.force_;
355 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
356 cur.prev_ = page_start - 1;
361 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
364 return !isinf (cur.demerits_);
368 min_page_count (vector<Line_details> const &uncompressed_lines,
369 Real page_height, bool ragged, bool ragged_last)
372 Real cur_rod_height = 0;
373 vector<Line_details> lines = compress_lines (uncompressed_lines);
375 assert (lines.size ());
376 for (vsize i = lines.size (); i--;)
378 bool rag = ragged || (ragged_last && ret == 1);
379 Real ext_len = lines[i].extent_.length ();
380 Real next_height = cur_rod_height + ext_len
381 + (rag ? line_space (lines[i]) : 0)
382 + ((cur_rod_height > 0) ? lines[i].padding_: 0);
384 if ((next_height > page_height && cur_rod_height > 0)
385 || (i + 1 < lines.size () && lines[i].page_permission_ == ly_symbol2scm ("force")))
388 cur_rod_height = ext_len + (rag ? line_space (lines[i]) : 0);
391 cur_rod_height = next_height;
398 space_systems_on_n_pages (vector<Line_details> const &lines,
404 vector<Line_details> compressed_lines = compress_lines (lines);
406 assert (n >= min_page_count (lines, page_height, ragged, ragged_last));
408 if (n > compressed_lines.size ())
409 return Spacing_result ();
411 ret = space_systems_on_1_page (compressed_lines, page_height, ragged || ragged_last);
413 ret = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last);
415 Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
418 ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines);
423 space_systems_on_n_or_one_more_pages (vector<Line_details> const &lines,
426 Real odd_pages_penalty,
430 Spacing_result n_res = space_systems_on_n_pages (lines, n, page_height, ragged, ragged_last);
431 Spacing_result m_res = space_systems_on_n_pages (lines, n+1, page_height, ragged, ragged_last);
432 n_res.demerits_ += odd_pages_penalty;
433 n_res.force_.back () += odd_pages_penalty;
435 if (n_res.demerits_ < m_res.demerits_)
441 space_systems_on_best_pages (vector<Line_details> const &lines,
443 Real odd_pages_penalty,
447 vector<Line_details> compressed_lines = compress_lines (lines);
448 vsize min_p_count = min_page_count (compressed_lines, page_height, ragged, ragged_last);
450 Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
451 Spacing_result best = ps.solve (min_p_count);
452 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
453 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
455 for (vsize i = min_p_count+1; i <= compressed_lines.size (); i++)
457 Spacing_result cur = ps.solve (i);
458 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
459 if (cur.demerits_ < best.demerits_)
463 best.systems_per_page_ = uncompress_solution (best.systems_per_page_, compressed_lines);