2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2009 Joe Neeman <joeneeman@gmail.com>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
20 #include "page-layout-problem.hh"
22 #include "align-interface.hh"
23 #include "axis-group-interface.hh"
24 #include "hara-kiri-group-spanner.hh"
25 #include "international.hh"
27 #include "output-def.hh"
28 #include "paper-book.hh"
29 #include "paper-column.hh"
30 #include "pointer-group-interface.hh"
32 #include "skyline-pair.hh"
35 Page_layout_problem::Page_layout_problem (Paper_book *pb, SCM page_scm, SCM systems)
36 : bottom_skyline_ (DOWN)
38 Prob *page = unsmob_prob (page_scm);
47 Stencil *head = unsmob_stencil (page->get_property ("head-stencil"));
48 Stencil *foot = unsmob_stencil (page->get_property ("foot-stencil"));
50 header_height_ = head ? head->extent (Y_AXIS).length () : 0;
51 footer_height_ = foot ? foot->extent (Y_AXIS).length () : 0;
52 page_height_ = robust_scm2double (page->get_property ("paper-height"), 100);
55 // Initially, bottom_skyline_ represents the top of the page. Make
56 // it solid, so that the top of the first system will be forced
57 // below the top of the printable area.
58 bottom_skyline_.set_minimum_height (-header_height_);
60 SCM between_system_spacing = SCM_EOL;
61 SCM between_scores_system_spacing = SCM_EOL;
62 SCM after_title_spacing = SCM_EOL;
63 SCM before_title_spacing = SCM_EOL;
64 SCM between_title_spacing = SCM_EOL;
66 // top_system_spacing controls the spring from the top of the printable
67 // area to the first staff. It allows the user to control the offset of
68 // the first staff (as opposed to the top of the first system) from the
69 // top of the page. Similarly for bottom_system_spacing.
70 SCM top_system_spacing = SCM_EOL;
71 SCM bottom_system_spacing = SCM_EOL;
74 Output_def *paper = pb->paper_;
75 between_system_spacing = paper->c_variable ("between-system-spacing");
76 between_scores_system_spacing = paper->c_variable ("between-scores-system-spacing");
77 after_title_spacing = paper->c_variable ("after-title-spacing");
78 before_title_spacing = paper->c_variable ("before-title-spacing");
79 between_title_spacing = paper->c_variable ("between-title-spacing");
80 bottom_system_spacing = paper->c_variable ("bottom-system-spacing");
81 top_system_spacing = paper->c_variable ("top-system-spacing");
82 if (scm_is_pair (systems) && unsmob_prob (scm_car (systems)))
83 top_system_spacing = paper->c_variable ("top-title-spacing");
85 // Note: the page height here does _not_ reserve space for headers and
86 // footers. This is because we want to anchor the top-system-spacing
87 // spring at the _top_ of the header.
88 page_height_ -= robust_scm2double (paper->c_variable ("top-margin"), 0)
89 + robust_scm2double (paper->c_variable ("bottom-margin"), 0);
91 read_spacing_spec (top_system_spacing, &header_padding_, ly_symbol2scm ("padding"));
92 read_spacing_spec (bottom_system_spacing, &footer_padding_, ly_symbol2scm ("padding"));
94 bool last_system_was_title = false;
97 for (SCM s = systems; scm_is_pair (s); s = scm_cdr (s))
99 bool first = (s == systems);
101 if (Grob *g = unsmob_grob (scm_car (s)))
103 System *sys = dynamic_cast<System*> (g);
106 programming_error ("got a grob for vertical spacing that wasn't a System");
110 SCM spec = between_system_spacing;
112 spec = top_system_spacing;
113 else if (last_system_was_title)
114 spec = after_title_spacing;
115 else if (0 == Paper_column::get_rank (sys->get_bound (LEFT)))
116 spec = between_scores_system_spacing;
118 Spring spring (0, 0);
120 alter_spring_from_spacing_spec (spec, &spring);
121 read_spacing_spec (spec, &padding, ly_symbol2scm ("padding"));
123 append_system (sys, spring, padding);
124 last_system_was_title = false;
126 else if (Prob *p = unsmob_prob (scm_car (s)))
128 SCM spec = first ? top_system_spacing
129 : (last_system_was_title ? between_title_spacing : before_title_spacing);
130 Spring spring (0, 0);
132 alter_spring_from_spacing_spec (spec, &spring);
133 read_spacing_spec (spec, &padding, ly_symbol2scm ("padding"));
135 append_prob (p, spring, padding);
136 last_system_was_title = true;
139 programming_error ("got a system that was neither a Grob nor a Prob");
142 Spring last_spring (0, 0);
143 Real last_padding = 0;
144 alter_spring_from_spacing_spec (bottom_system_spacing, &last_spring);
145 read_spacing_spec (bottom_system_spacing, &last_padding, ly_symbol2scm ("padding"));
146 last_spring.ensure_min_distance (last_padding - bottom_skyline_.max_height () + footer_height_);
147 springs_.push_back (last_spring);
149 if (elements_.size ())
151 Real bottom_padding = 0;
153 // TODO: junk bottom-space now that we have bottom-system-spacing?
154 // bottom-space has the flexibility that one can do it per-system.
155 // NOTE: bottom-space is misnamed since it is not stretchable space.
156 if (Prob *p = elements_.back ().prob)
157 bottom_padding = robust_scm2double (p->get_property ("bottom-space"), 0);
158 else if (elements_.back ().staves.size ())
160 SCM details = get_details (elements_.back ());
161 bottom_padding = robust_scm2double (ly_assoc_get (ly_symbol2scm ("bottom-space"),
166 page_height_ -= bottom_padding;
171 Page_layout_problem::set_header_height (Real height)
173 header_height_ = height;
177 Page_layout_problem::set_footer_height (Real height)
179 footer_height_ = height;
183 Page_layout_problem::append_system (System *sys, Spring const& spring, Real padding)
185 Grob *align = sys->get_vertical_alignment ();
189 align->set_property ("positioning-done", SCM_BOOL_T);
191 extract_grob_set (align, "elements", all_elts);
192 vector<Grob*> elts = filter_dead_elements (all_elts);
193 vector<Real> minimum_offsets = Align_interface::get_minimum_translations (align, elts, Y_AXIS,
196 Skyline up_skyline (UP);
197 Skyline down_skyline (DOWN);
198 build_system_skyline (elts, minimum_offsets, &up_skyline, &down_skyline);
200 Real minimum_distance = up_skyline.distance (bottom_skyline_) + padding;
202 Spring spring_copy = spring;
203 spring_copy.ensure_min_distance (minimum_distance);
204 springs_.push_back (spring_copy);
206 bottom_skyline_ = down_skyline;
207 elements_.push_back (Element (elts, minimum_offsets));
209 // Add the springs for the VerticalAxisGroups in this system.
211 // If the user has specified the offsets of the individual staves, fix the
212 // springs at the given distances. Otherwise, use stretchable springs.
213 SCM details = get_details (elements_.back ());
214 SCM manual_dists = ly_assoc_get (ly_symbol2scm ("alignment-distances"), details, SCM_EOL);
215 vsize last_spaceable_staff = 0;
216 bool found_spaceable_staff = false;
217 for (vsize i = 0; i < elts.size (); ++i)
219 if (is_spaceable (elts[i]))
221 // We don't add a spring for the first staff, since
222 // we are only adding springs _between_ staves here.
223 if (!found_spaceable_staff)
225 found_spaceable_staff = true;
226 last_spaceable_staff = i;
230 Spring spring (0.5, 0.0);
231 SCM spec = elts[last_spaceable_staff]->get_property ("next-staff-spacing");
232 alter_spring_from_spacing_spec (spec, &spring);
234 springs_.push_back (spring);
235 Real min_distance = (found_spaceable_staff ? minimum_offsets[last_spaceable_staff] : 0) - minimum_offsets[i];
236 springs_.back ().ensure_min_distance (min_distance);
238 if (scm_is_pair (manual_dists))
240 if (scm_is_number (scm_car (manual_dists)))
242 Real dy = scm_to_double (scm_car (manual_dists));
244 springs_.back ().set_distance (dy);
245 springs_.back ().set_min_distance (dy);
246 springs_.back ().set_inverse_stretch_strength (0);
248 manual_dists = scm_cdr (manual_dists);
250 last_spaceable_staff = i;
254 // Corner case: there was only one staff, and it wasn't spaceable.
255 // Mark it spaceable, because we do not allow non-spaceable staves
256 // to be at the top or bottom of a system.
257 if (!found_spaceable_staff && elts.size ())
258 mark_as_spaceable (elts[0]);
262 Page_layout_problem::append_prob (Prob *prob, Spring const& spring, Real padding)
264 Skyline_pair *sky = Skyline_pair::unsmob (prob->get_property ("vertical-skylines"));
265 Real minimum_distance = 0;
266 bool tight_spacing = to_boolean (prob->get_property ("tight-spacing"));
270 minimum_distance = (*sky)[UP].distance (bottom_skyline_);
271 bottom_skyline_ = (*sky)[DOWN];
273 else if (Stencil *sten = unsmob_stencil (prob->get_property ("stencil")))
275 Interval iv = sten->extent (Y_AXIS);
276 minimum_distance = iv[UP] - bottom_skyline_.max_height ();
278 bottom_skyline_.clear ();
279 bottom_skyline_.set_minimum_height (iv[DOWN]);
282 Spring spring_copy = spring;
285 spring_copy.set_min_distance (minimum_distance);
286 spring_copy.set_inverse_stretch_strength (0.0);
287 spring_copy.set_distance (0.0);
290 spring_copy.ensure_min_distance (minimum_distance + padding);
292 springs_.push_back (spring_copy);
293 elements_.push_back (Element (prob));
297 Page_layout_problem::solve_rod_spring_problem (bool ragged)
299 Simple_spacer spacer;
301 for (vsize i = 0; i < springs_.size (); ++i)
302 spacer.add_spring (springs_[i]);
304 spacer.solve (page_height_, ragged);
305 solution_ = spacer.spring_positions ();
308 // The solution_ vector stores the position of every live VerticalAxisGroup
309 // and every title. From that information,
310 // 1) within each system, stretch the staves so they land at the right position
311 // 2) find the offset of each system (relative to the printable area of the page).
312 // TODO: this function is getting too long, maybe split it up?
314 Page_layout_problem::find_system_offsets ()
316 SCM system_offsets = SCM_EOL;
317 SCM *tail = &system_offsets;
319 // spring_idx 0 is the top of the page. Interesting values start from 1.
320 vsize spring_idx = 1;
321 vector<Grob*> loose_lines;
322 vector<Real> loose_line_min_distances;
323 Grob *last_spaceable_line = 0;
324 Real last_spaceable_line_translation = 0;
325 for (vsize i = 0; i < elements_.size (); ++i)
327 if (elements_[i].prob)
329 *tail = scm_cons (scm_from_double (solution_[spring_idx]), SCM_EOL);
330 tail = SCM_CDRLOC (*tail);
332 // Lay out any non-spaceable lines between this line and
334 if (loose_lines.size ())
336 Interval loose_extent = loose_lines.back ()->extent (loose_lines.back (), Y_AXIS);
337 Interval prob_extent = unsmob_stencil (elements_[i].prob->get_property ("stencil"))->extent (Y_AXIS);
338 Real min_distance = -loose_extent[DOWN] + prob_extent[UP]; // TODO: include padding/minimum-distance
340 loose_line_min_distances.push_back (min_distance);
341 loose_lines.push_back (0);
343 distribute_loose_lines (loose_lines, loose_line_min_distances,
344 last_spaceable_line_translation, -solution_[spring_idx]);
345 loose_lines.clear ();
346 loose_line_min_distances.clear ();
349 last_spaceable_line = 0;
350 last_spaceable_line_translation = -solution_[spring_idx];
355 // Getting this signs right here is a little tricky. The configuration
356 // we return has zero at the top of the page and positive numbers further
357 // down, as does the solution_ vector. Within a staff, however, positive
359 // TODO: perhaps change the way the page 'configuration variable works so
360 // that it is consistent with the usual up/down sign conventions in
361 // Lilypond. Then this would be less confusing.
363 // These two positions are relative to the page (with positive numbers being
365 Real first_staff_position = solution_[spring_idx];
366 Real first_staff_min_translation = elements_[i].min_offsets.size () ? elements_[i].min_offsets[0] : 0;
367 Real system_position = first_staff_position + first_staff_min_translation;
369 // Position the staves within this system.
370 Real translation = 0;
371 vector<Real> const& min_offsets = elements_[i].min_offsets;
372 bool found_spaceable_staff = false;
373 for (vsize staff_idx = 0; staff_idx < elements_[i].staves.size (); ++staff_idx)
375 Grob *staff = elements_[i].staves[staff_idx];
376 staff->set_property ("system-Y-offset", scm_from_double (-system_position));
378 if (is_spaceable (staff))
380 // this is relative to the system: negative numbers are down.
381 translation = system_position - solution_[spring_idx];
384 // Lay out any non-spaceable lines between this line and
386 if (loose_lines.size ())
388 loose_line_min_distances.push_back (min_offsets[staff_idx-1] - min_offsets[staff_idx]);
389 loose_lines.push_back (staff);
391 distribute_loose_lines (loose_lines, loose_line_min_distances,
392 last_spaceable_line_translation, translation - system_position);
393 loose_lines.clear ();
394 loose_line_min_distances.clear ();
396 last_spaceable_line = staff;
397 // Negative is down but the translation is relative to the whole page.
398 last_spaceable_line_translation = -system_position + translation;
400 staff->translate_axis (translation, Y_AXIS);
401 found_spaceable_staff = true;
405 if (loose_lines.empty ())
406 loose_lines.push_back (last_spaceable_line);
409 loose_line_min_distances.push_back (min_offsets[staff_idx-1] - min_offsets[staff_idx]);
413 if (loose_lines.back ())
414 min_dist = Axis_group_interface::minimum_distance (loose_lines.back (),
417 else // distance to the top margin
418 min_dist = header_padding_ + header_height_ + staff->extent (staff, Y_AXIS)[UP];
420 loose_line_min_distances.push_back (min_dist);
422 loose_lines.push_back (staff);
426 // Corner case: even if a system has no live staves, it still takes up
427 // one spring (a system with one live staff also takes up one spring),
428 // which we need to increment past.
429 if (!found_spaceable_staff)
432 *tail = scm_cons (scm_from_double (system_position), SCM_EOL);
433 tail = SCM_CDRLOC (*tail);
437 if (loose_lines.size ())
439 Grob *last = loose_lines.back ();
440 Interval last_ext = last->extent (last, Y_AXIS);
441 loose_line_min_distances.push_back (-last_ext[DOWN] + footer_height_ + footer_padding_);
442 loose_lines.push_back (0);
444 distribute_loose_lines (loose_lines, loose_line_min_distances,
445 last_spaceable_line_translation, -page_height_);
449 assert (spring_idx == solution_.size () - 1);
450 return system_offsets;
453 // Given two lines that are already spaced (the first and last
454 // elements of loose_lines), distribute some unspaced lines between
457 Page_layout_problem::distribute_loose_lines (vector<Grob*> const &loose_lines,
458 vector<Real> const &min_distances,
459 Real first_translation, Real last_translation)
461 Simple_spacer spacer;
462 for (vsize i = 0; i + 1 < loose_lines.size (); ++i)
464 SCM spec = get_spacing_spec (loose_lines[i], loose_lines[i+1]);
465 Spring spring (1.0, 0.0);
466 alter_spring_from_spacing_spec (spec, &spring);
467 spring.ensure_min_distance (min_distances[i]);
468 spacer.add_spring (spring);
471 // Remember: offsets are decreasing, since we're going from UP to DOWN!
472 spacer.solve (first_translation - last_translation, false);
474 vector<Real> solution = spacer.spring_positions ();
475 for (vsize i = 1; i + 1 < solution.size (); ++i)
477 Real system_offset = scm_to_double (loose_lines[i]->get_property ("system-Y-offset"));
478 loose_lines[i]->translate_axis (first_translation - solution[i] - system_offset, Y_AXIS);
483 Page_layout_problem::solution (bool ragged)
485 solve_rod_spring_problem (ragged);
486 return find_system_offsets ();
489 // Build upper and lower skylines for a system. We don't yet know the positions
490 // of the staves within the system, so we make the skyline as conservative as
491 // possible. That is, for the upper skyline, we pretend that all of the staves
492 // in the system are packed together close to the top system; for the lower
493 // skyline, we pretend that all of the staves are packed together close to
494 // the bottom system.
496 // The upper skyline is relative to the top staff; the lower skyline is relative to
499 Page_layout_problem::build_system_skyline (vector<Grob*> const& staves,
500 vector<Real> const& minimum_translations,
504 if (minimum_translations.empty ())
507 assert (staves.size () == minimum_translations.size ());
508 Real first_translation = minimum_translations[0];
509 Real last_spaceable_dy = 0;
510 Real first_spaceable_dy = 0;
511 bool found_spaceable_staff = false;
513 for (vsize i = 0; i < staves.size (); ++i)
515 Real dy = minimum_translations[i] - first_translation;
517 Skyline_pair *sky = Skyline_pair::unsmob (g->get_property ("vertical-skylines"));
521 up->merge ((*sky)[UP]);
525 down->merge ((*sky)[DOWN]);
528 if (is_spaceable (staves[i]))
530 if (!found_spaceable_staff)
532 found_spaceable_staff = true;
533 first_spaceable_dy = dy;
535 last_spaceable_dy = dy;
539 // Leave the up skyline at a position relative
540 // to the top spaceable staff.
541 up->raise (-first_spaceable_dy);
543 // Leave the down skyline at a position
544 // relative to the bottom spaceable staff.
545 down->raise (-last_spaceable_dy);
549 Page_layout_problem::prob_extent (Prob *p)
551 Stencil *sten = unsmob_stencil (p->get_property ("stencil"));
552 return sten ? sten->extent (Y_AXIS) : Interval (0, 0);
556 Page_layout_problem::first_staff_extent (Element const& e)
559 return prob_extent (e.prob);
560 else if (e.staves.size ())
561 return e.staves[0]->extent (e.staves[0], Y_AXIS);
563 return Interval (0, 0);
567 Page_layout_problem::last_staff_extent (Element const& e)
570 return prob_extent (e.prob);
571 else if (e.staves.size ())
572 return e.staves.back ()->extent (e.staves.back (), Y_AXIS);
574 return Interval (0, 0);
578 Page_layout_problem::get_details (Element const& elt)
580 if (elt.staves.empty ())
583 return get_details (elt.staves.back ()->get_system ());
587 Page_layout_problem::get_details (Grob *g)
589 Grob *left_bound = dynamic_cast<Spanner*> (g)->get_bound (LEFT);
590 return left_bound->get_property ("line-break-system-details");
594 Page_layout_problem::is_spaceable (Grob *g)
596 return !scm_is_number (g->get_property ("staff-affinity"));
600 Page_layout_problem::mark_as_spaceable (Grob *g)
602 g->set_property ("staff-affinity", SCM_BOOL_F);
606 Page_layout_problem::read_spacing_spec (SCM spec, Real* dest, SCM sym)
608 SCM pair = scm_sloppy_assq (sym, spec);
609 if (scm_is_pair (pair) && scm_is_number (scm_cdr (pair)))
611 *dest = scm_to_double (scm_cdr (pair));
618 add_stretchability (SCM alist, Real stretch)
620 if (!scm_is_pair (scm_sloppy_assq (ly_symbol2scm ("stretchability"), alist)))
621 return scm_acons (ly_symbol2scm ("stretchability"), scm_from_double (stretch), alist);
626 // We want to put a large stretch between a non-spaceable line and its
627 // non-affinity staff. We want to put an even larger stretch between
628 // a non-spaceable line and the top/bottom of the page. That way,
629 // a spacing-affinity UP line at the bottom of the page will still be
630 // placed close to its staff.
631 const double LARGE_STRETCH = 10e5;
632 const double HUGE_STRETCH = 10e7;
634 // Returns the spacing spec connecting BEFORE to AFTER.
636 Page_layout_problem::get_spacing_spec (Grob *before, Grob *after)
638 // If there are no spacing wishes, return a very flexible spring.
639 // This will occur, for example, if there are lyrics at the bottom of
640 // the page, in which case we don't want the spring from the lyrics to
641 // the bottom of the page to have much effect.
642 if (!before || !after)
643 return add_stretchability (SCM_EOL, HUGE_STRETCH);
645 if (is_spaceable (before))
647 if (is_spaceable (after))
648 return before->get_property ("next-staff-spacing");
651 Direction affinity = to_dir (after->get_property ("staff-affinity"));
652 return (affinity == DOWN)
653 ? add_stretchability (after->get_property ("non-affinity-spacing"), LARGE_STRETCH)
654 : after->get_property ("inter-staff-spacing");
659 if (is_spaceable (after))
661 Direction affinity = to_dir (before->get_property ("staff-affinity"));
662 return (affinity == UP)
663 ? add_stretchability (before->get_property ("non-affinity-spacing"), LARGE_STRETCH)
664 : before->get_property ("inter-staff-spacing");
668 Direction before_affinity = to_dir (before->get_property ("staff-affinity"));
669 Direction after_affinity = to_dir (after->get_property ("staff-affinity"));
670 if (after_affinity > before_affinity)
672 warning (_ ("staff-affinities should only decrease"));
673 after_affinity = before_affinity;
675 if (before_affinity != UP)
676 return before->get_property ("inter-loose-line-spacing");
677 else if (after_affinity != DOWN)
678 return before->get_property ("inter-loose-line-spacing");
679 return add_stretchability (before->get_property ("non-affinity-spacing"), LARGE_STRETCH);
688 Page_layout_problem::alter_spring_from_spacing_spec (SCM spec, Spring* spring)
693 if (read_spacing_spec (spec, &space, ly_symbol2scm ("space")))
694 spring->set_distance (space);
695 if (read_spacing_spec (spec, &min_dist, ly_symbol2scm ("minimum-distance")))
696 spring->set_min_distance (min_dist);
697 spring->set_default_strength ();
699 if (read_spacing_spec (spec, &stretch, ly_symbol2scm ("stretchability")))
701 spring->set_inverse_stretch_strength (stretch);
702 spring->set_inverse_compress_strength (stretch);
707 Page_layout_problem::filter_dead_elements (vector<Grob*> const& input)
709 vector<Grob*> output;
710 for (vsize i = 0; i < input.size (); ++i)
712 if (Hara_kiri_group_spanner::has_interface (input[i]))
713 Hara_kiri_group_spanner::consider_suicide (input[i]);
715 if (input[i]->is_live ())
716 output.push_back (input[i]);