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 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);
42 Page_spacing::calc_force ()
44 if (rod_height_ + last_line_.bottom_padding_ >= page_height_ || !inverse_spring_k_)
47 force_ = (page_height_ - rod_height_ - last_line_.bottom_padding_ - spring_len_) / inverse_spring_k_;
51 Page_spacing::append_system (const Line_details &line)
53 rod_height_ += last_line_.padding_;
55 rod_height_ += line.extent_.length ();
56 spring_len_ += line.space_;
57 inverse_spring_k_ += line.inverse_hooke_;
65 Page_spacing::prepend_system (const Line_details &line)
68 rod_height_ += line.padding_;
72 rod_height_ += line.extent_.length ();
73 spring_len_ += line.space_;
74 inverse_spring_k_ += line.inverse_hooke_;
80 Page_spacing::clear ()
82 force_ = rod_height_ = spring_len_ = 0;
83 inverse_spring_k_ = 0;
86 /* for each forbidden page break, merge the systems around it into one system. */
87 static vector<Line_details>
88 compress_lines (const vector<Line_details> &orig)
90 vector<Line_details> ret;
92 for (vsize i = 0; i < orig.size (); i++)
94 if (i < orig.size () - 1 && orig[i].page_permission_ == SCM_EOL)
96 Line_details compressed = orig[i+1];
97 compressed.extent_[DOWN] = orig[i].extent_[DOWN];
98 compressed.extent_[UP] = orig[i].extent_[UP] + orig[i+1].extent_.length () + orig[i].padding_;
99 compressed.space_ += orig[i].space_;
100 compressed.inverse_hooke_ += orig[i].inverse_hooke_;
102 /* we don't need the force_ field for the vertical spacing,
103 so we use force_ = -1 to signal that the line was compressed
104 (and force_ = +1 otherwise).
105 This makes uncompression much easier. */
106 compressed.force_ = -1;
107 ret.push_back (compressed);
112 ret.push_back (orig[i]);
113 ret.back ().force_ = 1;
119 /* translate the number of systems-per-page into something meaningful for
120 the uncompressed lines.
123 uncompress_solution (vector<vsize> const &systems_per_page,
124 vector<Line_details> const &compressed)
129 for (vsize i = 0; i < systems_per_page.size (); i++)
131 int compressed_count = 0;
132 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
133 if (compressed[j].force_ < 0)
136 ret.push_back (systems_per_page[i] + compressed_count);
137 start_sys += systems_per_page[i];
142 /* the cases for page_count = 1 or 2 can be done in O(n) time. Since they
143 are by far the most common cases, we have special functions for them */
144 static Spacing_result
145 space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
147 Page_spacing space (page_height);
150 for (vsize i = 0; i < lines.size (); i++)
151 space.append_system (lines[i]);
153 ret.systems_per_page_.push_back (lines.size ());
154 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
155 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
156 ret.demerits_ = ret.force_.back () * ret.force_.back () + ret.penalty_;
161 static Spacing_result
162 space_systems_on_2_pages (vector<Line_details> const &lines,
167 /* if there is a forced break, this reduces to 2 1-page problems */
168 for (vsize i = 0; i < lines.size () - 1; i++)
169 if (lines[i].page_permission_ == ly_symbol2scm ("force"))
171 vector<Line_details> lines1 (lines.begin (), lines.begin () + i + 1);
172 vector<Line_details> lines2 (lines.begin () + i + 1, lines.end ());
173 Spacing_result p1 = space_systems_on_1_page (lines1, page_height, ragged);
174 Spacing_result p2 = space_systems_on_1_page (lines2, page_height, ragged || ragged_last);
176 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
177 p1.force_.push_back (p2.force_[0]);
178 p1.penalty_ += p2.penalty_ - lines[i].turn_penalty_;
179 p1.demerits_ += p2.demerits_ - lines[i].turn_penalty_;
183 vector<Real> page1_force;
184 vector<Real> page2_force;
185 Page_spacing page1 (page_height);
186 Page_spacing page2 (page_height);
188 page1_force.resize (lines.size () - 1, infinity_f);
189 page2_force.resize (lines.size () - 1, infinity_f);
191 for (vsize i = 0; i < page1_force.size (); i++)
193 page1.append_system (lines[i]);
194 page2.prepend_system (lines[lines.size () - 1 - i]);
195 page1_force[i] = (ragged && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
197 if (ragged || ragged_last)
198 page2_force[page2_force.size () - 1 - i] =
199 (page2.force_ < 0 && i < page1_force.size () - 1) ? infinity_f : 0;
201 page2_force[page2_force.size () - 1 - i] = page2.force_;
204 vsize best_sys_count = 1;
205 Real best_demerits = infinity_f;
206 for (vsize i = 0; i < page1_force.size (); i++)
208 Real dem = page1_force[i] * page1_force[i]
209 + page2_force[i] * page2_force[i]
210 + lines[i+1].page_penalty_
211 + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
212 if (dem < best_demerits)
215 best_sys_count = i+1;
220 ret.systems_per_page_.push_back (best_sys_count);
221 ret.systems_per_page_.push_back (lines.size () - best_sys_count);
222 ret.force_.push_back (page1_force[best_sys_count-1]);
223 ret.force_.push_back (page2_force[best_sys_count-1]);
224 ret.penalty_ = lines[best_sys_count-1].page_penalty_
225 + lines.back ().page_penalty_
226 + lines.back ().turn_penalty_;
227 ret.demerits_ = best_demerits;
232 Page_spacer::Page_spacer (vector<Line_details> const &lines, Real page_height, bool ragged, bool ragged_last)
235 page_height_ = page_height;
238 ragged_last_ = ragged_last;
242 Page_spacer::solve (vsize page_count)
244 if (page_count > max_page_count_)
248 ret.force_.resize (page_count);
249 ret.systems_per_page_.resize (page_count);
251 vsize system = lines_.size () - 1;
253 if (isinf (state_.at (system, page_count-1).demerits_))
255 programming_error ("tried to space systems on a bad number of pages");
256 return Spacing_result (); /* bad number of pages */
259 ret.penalty_ = state_.at (system, page_count-1).penalty_
260 + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
263 for (vsize p = page_count; p--;)
265 assert (system != VPOS);
267 Page_spacing_node const &ps = state_.at (system, p);
268 ret.force_[p] = ps.force_;
269 ret.demerits_ += ps.force_ * ps.force_;
271 ret.systems_per_page_[p] = system + 1;
273 ret.systems_per_page_[p] = system - ps.prev_;
276 ret.demerits_ += ret.penalty_;
281 Page_spacer::resize (vsize page_count)
283 assert (page_count > 0);
285 if (max_page_count_ >= page_count)
288 state_.resize (lines_.size (), page_count, Page_spacing_node ());
289 for (vsize page = max_page_count_; page < page_count; page++)
290 for (vsize line = page; line < lines_.size (); line++)
291 if (!calc_subproblem (page, line))
294 max_page_count_ = page_count;
298 Page_spacer::calc_subproblem (vsize page, vsize line)
300 Page_spacing space (page_height_);
301 Page_spacing_node &cur = state_.at (line, page);
302 bool ragged = ragged_ || (ragged_last_ && line == lines_.size () - 1);
304 for (vsize page_start = line+1; page_start > page && page_start--;)
306 Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
308 space.prepend_system (lines_[page_start]);
309 if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
312 if (page > 0 || page_start == 0)
314 if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0)
317 /* we may have to deal with single lines that are taller than a page */
318 if (isinf (space.force_) && page_start == line)
319 space.force_ = -200000;
321 Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
324 penalty = lines_[page_start-1].page_penalty_
325 + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
328 if (dem < cur.demerits_ || page_start == line)
331 cur.force_ = space.force_;
332 cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
333 cur.prev_ = page_start - 1;
338 && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force"))
341 return !isinf (cur.demerits_);
345 min_page_count (vector<Line_details> const &uncompressed_lines,
346 Real page_height, bool ragged, bool ragged_last)
349 Real cur_rod_height = 0;
350 vector<Line_details> lines = compress_lines (uncompressed_lines);
352 assert (lines.size ());
353 for (vsize i = lines.size (); i--;)
355 bool rag = ragged || (ragged_last && ret == 1);
356 Real ext_len = lines[i].extent_.length ();
357 Real next_height = cur_rod_height + ext_len
358 + (rag ? lines[i].space_ : 0)
359 + ((cur_rod_height > 0) ? lines[i].padding_: 0);
361 if ((next_height > page_height && cur_rod_height > 0)
362 || (i < lines.size () - 1 && lines[i].page_permission_ == ly_symbol2scm ("force")))
365 cur_rod_height = ext_len + (rag ? lines[i].space_ : 0);
368 cur_rod_height = next_height;
375 space_systems_on_n_pages (vector<Line_details> const &lines,
381 vector<Line_details> compressed_lines = compress_lines (lines);
383 assert (n >= min_page_count (lines, page_height, ragged, ragged_last));
385 if (n > compressed_lines.size ())
386 return Spacing_result ();
388 ret = space_systems_on_1_page (compressed_lines, page_height, ragged || ragged_last);
390 ret = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last);
392 Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
395 ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines);
400 space_systems_on_n_or_one_more_pages (vector<Line_details> const &lines,
403 Real odd_pages_penalty,
407 Spacing_result n_res = space_systems_on_n_pages (lines, n, page_height, ragged, ragged_last);
408 Spacing_result m_res = space_systems_on_n_pages (lines, n+1, page_height, ragged, ragged_last);
409 n_res.demerits_ += odd_pages_penalty;
410 n_res.force_.back () += odd_pages_penalty;
412 if (n_res.demerits_ < m_res.demerits_)
418 space_systems_on_best_pages (vector<Line_details> const &lines,
420 Real odd_pages_penalty,
424 vector<Line_details> compressed_lines = compress_lines (lines);
425 vsize min_p_count = min_page_count (compressed_lines, page_height, ragged, ragged_last);
427 Page_spacer ps (compressed_lines, page_height, ragged, ragged_last);
428 Spacing_result best = ps.solve (min_p_count);
429 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
430 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
432 for (vsize i = min_p_count+1; i <= compressed_lines.size (); i++)
434 Spacing_result cur = ps.solve (i);
435 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
436 if (cur.demerits_ < best.demerits_)
440 best.systems_per_page_ = uncompress_solution (best.systems_per_page_, compressed_lines);