2 page-layout-problem.cc -- space systems nicely on a page. If systems can
3 be stretched, do that too.
5 source file of the GNU LilyPond music typesetter
7 (c) 2009 Joe Neeman <joeneeman@gmail.com>
10 #include "page-layout-problem.hh"
12 #include "align-interface.hh"
13 #include "international.hh"
15 #include "output-def.hh"
16 #include "paper-book.hh"
17 #include "pointer-group-interface.hh"
19 #include "skyline-pair.hh"
22 Page_layout_problem::Page_layout_problem (Paper_book *pb, SCM page_scm, SCM systems)
23 : bottom_skyline_ (DOWN)
25 Prob *page = unsmob_prob (page_scm);
32 Stencil *head = unsmob_stencil (page->get_property ("head-stencil"));
33 Stencil *foot = unsmob_stencil (page->get_property ("foot-stencil"));
35 header_height_ = head ? head->extent (Y_AXIS).length () : 0;
36 footer_height_ = foot ? foot->extent (Y_AXIS).length () : 0;
37 page_height_ = robust_scm2double (page->get_property ("paper-height"), 100);
40 // Initially, bottom_skyline_ represents the top of the page. Make
41 // it solid, so that the top of the first system will be forced
42 // below the top of the printable area.
43 bottom_skyline_.set_minimum_height (-header_height_);
45 SCM between_system_spacing = SCM_EOL;
46 SCM after_title_spacing = SCM_EOL;
47 SCM before_title_spacing = SCM_EOL;
48 SCM between_title_spacing = SCM_EOL;
50 // first_system_spacing controls the spring from the top of the printable
51 // area to the first staff. It allows the user to control the offset of
52 // the first staff (as opposed to the top of the first system) from the
53 // top of the page. Similarly for last_system_spacing.
54 SCM first_system_spacing = SCM_EOL;
55 SCM last_system_spacing = SCM_EOL;
58 Output_def *paper = pb->paper_;
59 between_system_spacing = paper->c_variable ("between-system-spacing");
60 after_title_spacing = paper->c_variable ("after-title-spacing");
61 before_title_spacing = paper->c_variable ("before-title-spacing");
62 between_title_spacing = paper->c_variable ("between-title-spacing");
63 last_system_spacing = paper->c_variable ("last-system-spacing");
64 first_system_spacing = paper->c_variable ("first-system-spacing");
65 if (scm_is_pair (systems) && unsmob_prob (scm_car (systems)))
66 first_system_spacing = paper->c_variable ("first-system-title-spacing");
68 // Note: the page height here does _not_ reserve space for headers and
69 // footers. This is because we want to anchor the first-system-spacing
70 // spring at the _top_ of the header.
71 page_height_ -= robust_scm2double (paper->c_variable ("top-margin"), 0)
72 + robust_scm2double (paper->c_variable ("bottom-margin"), 0);
74 bool last_system_was_title = false;
77 for (SCM s = systems; scm_is_pair (s); s = scm_cdr (s))
79 bool first = (s == systems);
81 if (Grob *g = unsmob_grob (scm_car (s)))
83 System *sys = dynamic_cast<System*> (g);
86 programming_error ("got a grob for vertical spacing that wasn't a System");
90 SCM spec = first ? first_system_spacing
91 : (last_system_was_title ? after_title_spacing : between_system_spacing);
92 Spring spring (first ? 0 : 1, 0.0);
94 alter_spring_from_spacing_spec (spec, &spring);
95 read_spacing_spec (spec, &padding, ly_symbol2scm ("padding"));
97 append_system (sys, spring, padding);
98 last_system_was_title = false;
100 else if (Prob *p = unsmob_prob (scm_car (s)))
102 SCM spec = first ? first_system_spacing
103 : (last_system_was_title ? between_title_spacing : before_title_spacing);
104 Spring spring (first ? 0 : 1, 0.0);
106 alter_spring_from_spacing_spec (spec, &spring);
107 read_spacing_spec (spec, &padding, ly_symbol2scm ("padding"));
109 append_prob (p, spring, padding);
110 last_system_was_title = true;
113 programming_error ("got a system that was neither a Grob nor a Prob");
116 Spring last_spring (0, 0);
117 Real last_padding = 0;
118 alter_spring_from_spacing_spec (last_system_spacing, &last_spring);
119 read_spacing_spec (last_system_spacing, &last_padding, ly_symbol2scm ("padding"));
120 last_spring.ensure_min_distance (last_padding - bottom_skyline_.max_height () + footer_height_);
121 springs_.push_back (last_spring);
125 Page_layout_problem::set_header_height (Real height)
127 header_height_ = height;
131 Page_layout_problem::set_footer_height (Real height)
133 footer_height_ = height;
137 Page_layout_problem::find_vertical_alignment (System *sys)
139 extract_grob_set (sys, "elements", elts);
140 for (vsize i = 0; i < elts.size (); ++i)
141 if (Align_interface::has_interface (elts[i]))
148 Page_layout_problem::append_system (System *sys, Spring const& spring, Real padding)
150 Grob *align = find_vertical_alignment (sys);
153 sys->programming_error ("no VerticalAlignment in system: can't do vertical spacing");
157 align->set_property ("positioning-done", SCM_BOOL_T);
159 extract_grob_set (align, "elements", elts);
160 vector<Real> minimum_offsets = Align_interface::get_minimum_translations (align, elts, Y_AXIS,
163 Skyline up_skyline (UP);
164 Skyline down_skyline (DOWN);
165 build_system_skyline (elts, minimum_offsets, &up_skyline, &down_skyline);
167 Real minimum_distance = up_skyline.distance (bottom_skyline_) + padding;
169 Spring spring_copy = spring;
170 spring_copy.ensure_min_distance (minimum_distance);
171 springs_.push_back (spring_copy);
173 bottom_skyline_ = down_skyline;
174 elements_.push_back (Element (elts, minimum_offsets));
176 // Add the springs for the VerticalAxisGroups in this system.
178 // If the user has specified the offsets of the individual staves, fix the
179 // springs at the given distances. Otherwise, use stretchable springs.
180 SCM details = get_details (elements_.back ());
181 SCM manual_dists = ly_assoc_get (ly_symbol2scm ("alignment-distances"), details, SCM_EOL);
182 vsize last_spaceable_staff = 0;
183 bool first_live_element = true;
184 for (vsize i = 0; i < elts.size (); ++i)
186 if (elts[i]->is_live () && is_spaceable (elts[i]))
188 // We don't add a spring for the first live element, since
189 // we are only adding springs _between_ staves here.
190 if (first_live_element)
193 add_loose_lines_as_spaceable_lines (elts, minimum_offsets, 0, i-1);
195 first_live_element = false;
196 last_spaceable_staff = i;
200 Spring spring (0.5, 0.0);
201 SCM spec = elts[last_spaceable_staff]->get_property ("next-staff-spacing");
202 alter_spring_from_spacing_spec (spec, &spring);
204 springs_.push_back (spring);
205 Real min_distance = minimum_offsets[last_spaceable_staff] - minimum_offsets[i];
206 springs_.back ().ensure_min_distance (min_distance);
208 if (scm_is_pair (manual_dists))
210 if (scm_is_number (scm_car (manual_dists)))
212 Real dy = scm_to_double (scm_car (manual_dists));
214 springs_.back ().set_distance (dy);
215 springs_.back ().set_min_distance (dy);
216 springs_.back ().set_inverse_stretch_strength (0);
218 manual_dists = scm_cdr (manual_dists);
220 last_spaceable_staff = i;
223 // Any loose lines hanging off the end are treated as spaceable
224 // lines. This might give slightly weird results if the hanging
225 // systems have staff-affinity != UP. It's not quite clear what
226 // should happen in that case, though.
227 if (last_spaceable_staff + 1 < elts.size ())
228 add_loose_lines_as_spaceable_lines (elts, minimum_offsets,
229 first_live_element ? 0 : last_spaceable_staff + 1,
234 Page_layout_problem::add_loose_lines_as_spaceable_lines (vector<Grob*> const& elts,
235 vector<Real> const& minimum_offsets,
236 vsize first, vsize last)
238 Direction last_affinity = UP;
239 SCM last_spec = SCM_EOL;
240 bool found_live_line = false;
241 for (vsize i = first; i <= last; ++i)
243 if (elts[i]->is_live ())
245 Direction affinity = robust_scm2dir (elts[i]->get_property ("staff-affinity"), CENTER);
246 if (affinity > last_affinity)
248 warning (_ ("staff-affinities should only decrease"));
249 affinity = last_affinity;
252 SCM spec = elts[i]->get_property ("inter-staff-spacing");
253 if ((affinity != DOWN && found_live_line)
254 || (affinity == DOWN && i != last)) // FIXME: we want to know if we are the last _live_ line.
255 spec = elts[i]->get_property ("inter-loose-line-spacing");
257 Spring spring (1.0, 0.0);
258 // When affinity == DOWN, the spacing spec specifies the
259 // spacing to the staff below.
260 if (affinity == DOWN)
261 alter_spring_from_spacing_spec (last_spec, &spring);
263 alter_spring_from_spacing_spec (spec, &spring);
265 Real min_distance = (i > 0 ? minimum_offsets[i-1] : 0) - minimum_offsets[i];
266 spring.ensure_min_distance (min_distance);
268 // The first line in a system doesn't get a spring.
269 if (first > 0 || found_live_line)
270 springs_.push_back (spring);
272 mark_as_spaceable (elts[i]);
274 last_affinity = affinity;
275 found_live_line = true;
279 if (found_live_line && last + 1 < elts.size ())
281 Spring spring (1.0, 0.0);
282 if (last_affinity == UP)
283 warning (_ ("a system with staff-affinity UP is stranded above the system"));
284 alter_spring_from_spacing_spec (last_spec, &spring);
286 Real min_distance = minimum_offsets[last] - minimum_offsets[last+1];
287 spring.ensure_min_distance (min_distance);
288 springs_.push_back (spring);
293 Page_layout_problem::append_prob (Prob *prob, Spring const& spring, Real padding)
295 Skyline_pair *sky = Skyline_pair::unsmob (prob->get_property ("vertical-skylines"));
296 Real minimum_distance = 0;
299 minimum_distance = (*sky)[UP].distance (bottom_skyline_);
300 bottom_skyline_ = (*sky)[DOWN];
302 else if (Stencil *sten = unsmob_stencil (prob->get_property ("stencil")))
304 Interval iv = sten->extent (Y_AXIS);
305 minimum_distance = iv[UP] - bottom_skyline_.max_height ();
307 bottom_skyline_.clear ();
308 bottom_skyline_.set_minimum_height (iv[DOWN]);
310 minimum_distance += padding;
312 Spring spring_copy = spring;
313 spring_copy.ensure_min_distance (minimum_distance);
314 springs_.push_back (spring_copy);
315 elements_.push_back (Element (prob));
319 Page_layout_problem::solve_rod_spring_problem (bool ragged)
321 Simple_spacer spacer;
323 for (vsize i = 0; i < springs_.size (); ++i)
324 spacer.add_spring (springs_[i]);
326 Real bottom_padding = 0;
327 Interval first_staff_iv (0, 0);
328 Interval last_staff_iv (0, 0);
329 if (elements_.size ())
331 first_staff_iv = first_staff_extent (elements_[0]);
332 last_staff_iv = last_staff_extent (elements_.back ());
334 // TODO: junk bottom-space now that we have last-spring-spacing?
335 // bottom-space has the flexibility that one can do it per-system.
336 // NOTE: bottom-space is misnamed since it is not stretchable space.
337 if (Prob *p = elements_.back ().prob)
338 bottom_padding = robust_scm2double (p->get_property ("bottom-space"), 0);
339 else if (elements_.back ().staves.size ())
341 SCM details = get_details (elements_.back ());
342 bottom_padding = robust_scm2double (ly_assoc_get (ly_symbol2scm ("bottom-space"),
349 spacer.solve (page_height_ - bottom_padding, ragged);
350 solution_ = spacer.spring_positions ();
353 // The solution_ vector stores the position of every live VerticalAxisGroup
354 // and every title. From that information,
355 // 1) within each system, stretch the staves so they land at the right position
356 // 2) find the offset of each system (relative to the printable area of the page).
357 // TODO: this function is getting too long, maybe split it up?
359 Page_layout_problem::find_system_offsets ()
361 SCM system_offsets = SCM_EOL;
362 SCM *tail = &system_offsets;
364 // spring_idx 0 is the top of the page. Interesting values start from 1.
365 vsize spring_idx = 1;
366 for (vsize i = 0; i < elements_.size (); ++i)
368 if (elements_[i].prob)
370 *tail = scm_cons (scm_from_double (solution_[spring_idx]), SCM_EOL);
371 tail = SCM_CDRLOC (*tail);
376 // Getting this signs right here is a little tricky. The configuration
377 // we return has zero at the top of the page and positive numbers further
378 // down, as does the solution_ vector. Within a staff, however, positive
380 // TODO: perhaps change the way the page 'configuration variable works so
381 // that it is consistent with the usual up/down sign conventions in
382 // Lilypond. Then this would be less confusing.
384 // These two positions are relative to the page (with positive numbers being
386 Real first_staff_position = solution_[spring_idx];
387 Real first_staff_min_translation = elements_[i].min_offsets.size () ? elements_[i].min_offsets[0] : 0;
388 Real system_position = first_staff_position + first_staff_min_translation;
390 // Position the staves within this system.
391 Real translation = 0;
392 bool found_live_staff = false;
393 vector<Grob*> loose_lines;
394 vector<Real> const& min_offsets = elements_[i].min_offsets;
395 vector<Real> loose_line_min_distances;
396 Grob *last_spaceable_line = 0;
397 Real last_spaceable_line_translation = 0;
398 vsize last_live_staff = 0;
399 for (vsize staff_idx = 0; staff_idx < elements_[i].staves.size (); ++staff_idx)
401 Grob *staff = elements_[i].staves[staff_idx];
403 // Dead VerticalAxisGroups didn't participate in the
404 // rod-and-spring problem, but they still need to be
405 // translated. We translate them by the same amount as
406 // the VerticalAxisGroup directly before. (but we don't
407 // increment spring_idx!)
408 if (is_spaceable (staff) || !staff->is_live ())
410 if (staff->is_live ())
412 // this is relative to the system: negative numbers are down.
413 translation = system_position - solution_[spring_idx];
414 found_live_staff = true;
417 // Lay out any non-spaceable lines between this line and
419 if (loose_lines.size ())
421 loose_line_min_distances.push_back (min_offsets[last_live_staff] - min_offsets[staff_idx]);
422 distribute_loose_lines (last_spaceable_line, last_spaceable_line_translation,
423 loose_lines, loose_line_min_distances,
425 loose_lines.clear ();
426 loose_line_min_distances.clear ();
428 last_spaceable_line = staff;
429 last_spaceable_line_translation = translation;
430 last_live_staff = staff_idx;
433 staff->translate_axis (translation, Y_AXIS);
435 // We only need to deal with loose lines if we've
436 // already found a live staff (because any loose lines
437 // that occur before our first live staff are treated as
438 // spaced lines anyway).
439 else if (found_live_staff)
441 loose_lines.push_back (staff);
442 loose_line_min_distances.push_back (min_offsets[last_live_staff] - min_offsets[staff_idx]);
443 last_live_staff = staff_idx;
447 // Corner case: even if a system has no live staves, it still takes up
448 // one spring (a system with one live staff also takes up one spring),
449 // which we need to increment past.
450 if (!found_live_staff)
453 *tail = scm_cons (scm_from_double (system_position), SCM_EOL);
454 tail = SCM_CDRLOC (*tail);
458 assert (spring_idx == solution_.size () - 1);
459 return system_offsets;
462 // Given two lines that are already spaced (line_before and line_after), distribute
463 // some unspaced lines between them. If line_before is null, the unspaced lines
464 // will be packed as closely as possible to line_after. If line_after is null, the
465 // unspaced lines will be packed as closely as possible to line_before. If both are
466 // null, the first loose_line will be translated to before_offset and the rest
467 // of the loose_lines will be packed as closely as possible to it.
469 // min_distances has one more element than loose_lines; the first element of
470 // min_distances contains the minimum skyline distance between line_before
471 // and loose_lines[0].
473 Page_layout_problem::distribute_loose_lines (Grob *line_before, Real before_offset,
474 vector<Grob*> const &loose_lines,
475 vector<Real> const &min_distances,
476 Grob *line_after, Real after_offset)
478 vector<Real> offsets;
479 assert (line_before && line_after);
481 Simple_spacer spacer;
482 Direction last_affinity = UP;
483 for (vsize i = 0; i < loose_lines.size (); ++i)
485 Direction affinity = robust_scm2dir (loose_lines[i]->get_property ("staff-affinity"), CENTER);
486 if (affinity > last_affinity)
488 warning (_ ("staff-affinities should only decrease"));
489 affinity = last_affinity;
492 SCM staff_spec = loose_lines[i]->get_property ("inter-staff-spacing");
493 SCM loose_spec = loose_lines[i]->get_property ("inter-loose-line-spacing");
494 SCM spec = loose_spec;
495 if ((i == 0 && affinity == UP)
496 || (i + 1 == loose_lines.size () && affinity != UP))
499 Spring spring (1.0, 0.0);
500 alter_spring_from_spacing_spec (spec, &spring);
502 if (affinity != last_affinity)
504 if (affinity == CENTER)
506 Spring up_spring (1.0, 0.0);
507 SCM up_spec = (i == 0) ? staff_spec : loose_spec;
508 alter_spring_from_spacing_spec (up_spec, &up_spring);
509 up_spring.ensure_min_distance (min_distances[i]);
511 spacer.add_spring (up_spring);
513 else if (affinity == DOWN && last_affinity == UP)
515 // Insert a very flexible spring, so it doesn't mess things up too much.
516 Spring extra_spr (1.0, min_distances[i]);
517 extra_spr.set_inverse_stretch_strength (100000);
518 extra_spr.set_inverse_compress_strength (100000);
519 spacer.add_spring (extra_spr);
523 spring.ensure_min_distance (min_distances[i]);
525 spring.ensure_min_distance (min_distances[i+1]);
527 spacer.add_spring (spring);
528 last_affinity = affinity;
531 if (last_affinity == UP)
533 Spring extra_spr (1.0, min_distances.back ());
534 extra_spr.set_inverse_stretch_strength (100000);
535 extra_spr.set_inverse_compress_strength (100000);
536 spacer.add_spring (extra_spr);
539 // Remember: offsets are decreasing, since we're going from UP to DOWN!
540 spacer.solve (before_offset - after_offset, false);
542 vector<Real> solution = spacer.spring_positions ();
543 for (vsize i = 1; i + 1 < solution.size (); ++i)
544 offsets.push_back (before_offset - solution[i]);
546 assert (offsets.size () == loose_lines.size ());
547 for (vsize i = 0; i < offsets.size (); ++i)
548 loose_lines[i]->translate_axis (offsets[i], Y_AXIS);
552 Page_layout_problem::solution (bool ragged)
554 solve_rod_spring_problem (ragged);
555 return find_system_offsets ();
558 // Build upper and lower skylines for a system. We don't yet know the positions
559 // of the staves within the system, so we make the skyline as conservative as
560 // possible. That is, for the upper skyline, we pretend that all of the staves
561 // in the system are packed together close to the top system; for the lower
562 // skyline, we pretend that all of the staves are packed together close to
563 // the bottom system.
565 // The upper skyline is relative to the top staff; the lower skyline is relative to
568 Page_layout_problem::build_system_skyline (vector<Grob*> const& staves,
569 vector<Real> const& minimum_translations,
573 if (minimum_translations.empty ())
576 assert (staves.size () == minimum_translations.size ());
577 Real first_translation = minimum_translations[0];
580 for (vsize i = 0; i < staves.size (); ++i)
582 Real dy = minimum_translations[i] - first_translation;
584 Skyline_pair *sky = Skyline_pair::unsmob (g->get_property ("vertical-skylines"));
588 up->merge ((*sky)[UP]);
592 down->merge ((*sky)[DOWN]);
599 // Leave the down skyline at a position
600 // relative to the bottom staff.
601 down->raise (-last_dy);
605 Page_layout_problem::prob_extent (Prob *p)
607 Stencil *sten = unsmob_stencil (p->get_property ("stencil"));
608 return sten ? sten->extent (Y_AXIS) : Interval (0, 0);
612 Page_layout_problem::first_staff_extent (Element const& e)
615 return prob_extent (e.prob);
616 else if (e.staves.size ())
617 return e.staves[0]->extent (e.staves[0], Y_AXIS);
619 return Interval (0, 0);
623 Page_layout_problem::last_staff_extent (Element const& e)
626 return prob_extent (e.prob);
627 else if (e.staves.size ())
628 return e.staves.back ()->extent (e.staves.back (), Y_AXIS);
630 return Interval (0, 0);
634 Page_layout_problem::get_details (Element const& elt)
636 if (elt.staves.empty ())
639 return get_details (elt.staves.back ()->get_system ());
643 Page_layout_problem::get_details (Grob *g)
645 Grob *left_bound = dynamic_cast<Spanner*> (g)->get_bound (LEFT);
646 return left_bound->get_property ("line-break-system-details");
650 Page_layout_problem::is_spaceable (Grob *g)
652 return !scm_is_number (g->get_property ("staff-affinity"));
656 Page_layout_problem::mark_as_spaceable (Grob *g)
658 g->set_property ("staff-affinity", SCM_BOOL_F);
662 Page_layout_problem::read_spacing_spec (SCM spec, Real* dest, SCM sym)
664 SCM pair = scm_sloppy_assq (sym, spec);
665 if (scm_is_pair (pair) && scm_is_number (scm_cdr (pair)))
667 *dest = scm_to_double (scm_cdr (pair));
674 Page_layout_problem::alter_spring_from_spacing_spec (SCM spec, Spring* spring)
679 if (read_spacing_spec (spec, &space, ly_symbol2scm ("space")))
680 spring->set_distance (space);
681 if (read_spacing_spec (spec, &min_dist, ly_symbol2scm ("minimum-distance")))
682 spring->set_min_distance (min_dist);
683 spring->set_default_strength ();
685 if (read_spacing_spec (spec, &stretch, ly_symbol2scm ("stretchability")))
687 spring->set_inverse_stretch_strength (stretch);
688 spring->set_inverse_compress_strength (stretch);