lily/axis-group-interface.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2000--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   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.
  10
  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.
  15
  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/>.
  18 */
  19
  20 #include "axis-group-interface.hh"
  21
  22 #include "align-interface.hh"
  23 #include "directional-element-interface.hh"
  24 #include "grob-array.hh"
  25 #include "hara-kiri-group-spanner.hh"
  26 #include "international.hh"
  27 #include "lookup.hh"
  28 #include "paper-column.hh"
  29 #include "paper-score.hh"
  30 #include "pointer-group-interface.hh"
  31 #include "separation-item.hh"
  32 #include "skyline-pair.hh"
  33 #include "staff-grouper-interface.hh"
  34 #include "stencil.hh"
  35 #include "system.hh"
  36 #include "warn.hh"
  37 #include "unpure-pure-container.hh"
  38
  39 static bool
  40 pure_staff_priority_less (Grob *const &g1, Grob *const &g2);
  41
  42 void
  43 Axis_group_interface::add_element (Grob *me, Grob *e)
  44 {
  45   SCM axes = me->get_property ("axes");
  46   if (!scm_is_pair (axes))
  47     programming_error ("axes should be nonempty");
  48
  49   for (SCM ax = axes; scm_is_pair (ax); ax = scm_cdr (ax))
  50     {
  51       Axis a = (Axis) scm_to_int (scm_car (ax));
  52
  53       if (!e->get_parent (a))
  54         e->set_parent (me, a);
  55
  56       e->set_object ((a == X_AXIS)
  57                      ? ly_symbol2scm ("axis-group-parent-X")
  58                      : ly_symbol2scm ("axis-group-parent-Y"),
  59                      me->self_scm ());
  60     }
  61
  62   /* must be ordered, because Align_interface also uses
  63      Axis_group_interface  */
  64   Pointer_group_interface::add_grob (me, ly_symbol2scm ("elements"), e);
  65 }
  66
  67 bool
  68 Axis_group_interface::has_axis (Grob *me, Axis a)
  69 {
  70   SCM axes = me->get_property ("axes");
  71
  72   return (SCM_BOOL_F != scm_memq (scm_from_int (a), axes));
  73 }
  74
  75 Interval
  76 Axis_group_interface::relative_group_extent (vector<Grob *> const &elts,
  77                                              Grob *common, Axis a)
  78 {
  79   return relative_maybe_bound_group_extent (elts, common, a, false);
  80 }
  81
  82 Interval
  83 Axis_group_interface::relative_maybe_bound_group_extent (vector<Grob *> const &elts,
  84                                                          Grob *common, Axis a, bool bound)
  85 {
  86   Interval r;
  87   for (vsize i = 0; i < elts.size (); i++)
  88     {
  89       Grob *se = elts[i];
  90       if (!to_boolean (se->get_property ("cross-staff")))
  91         {
  92           Interval dims = (bound && has_interface (se)
  93                            ? generic_bound_extent (se, common, a)
  94                            : se->extent (common, a));
  95           if (!dims.is_empty ())
  96             r.unite (dims);
  97         }
  98     }
  99   return r;
 100 }
 101
 102 Interval
 103 Axis_group_interface::generic_bound_extent (Grob *me, Grob *common, Axis a)
 104 {
 105   /* trigger the callback to do skyline-spacing on the children */
 106   if (a == Y_AXIS)
 107     (void) me->get_property ("vertical-skylines");
 108
 109   extract_grob_set (me, "elements", elts);
 110   vector<Grob *> new_elts;
 111
 112   SCM interfaces = me->get_property ("bound-alignment-interfaces");
 113
 114   for (vsize i = 0; i < elts.size (); i++)
 115     for (SCM l = interfaces; scm_is_pair (l); l = scm_cdr (l))
 116       if (elts[i]->internal_has_interface (scm_car (l)))
 117         new_elts.push_back (elts[i]);
 118
 119   if (!new_elts.size ())
 120     return robust_relative_extent (me, common, a);
 121
 122   if (!common)
 123     common = common_refpoint_of_array (new_elts, me, a);
 124
 125   return relative_maybe_bound_group_extent (new_elts, common, a, true);
 126 }
 127
 128 Interval
 129 Axis_group_interface::sum_partial_pure_heights (Grob *me, int start, int end)
 130 {
 131   Interval iv = begin_of_line_pure_height (me, start);
 132   iv.unite (rest_of_line_pure_height (me, start, end));
 133
 134   return iv;
 135 }
 136
 137 Interval
 138 Axis_group_interface::part_of_line_pure_height (Grob *me, bool begin, int start, int end)
 139 {
 140   Spanner *sp = dynamic_cast<Spanner *> (me);
 141   SCM cache_symbol = begin
 142                      ? ly_symbol2scm ("begin-of-line-pure-height")
 143                      : ly_symbol2scm ("rest-of-line-pure-height");
 144   SCM cached = sp->get_cached_pure_property (cache_symbol, start, end);
 145   if (scm_is_pair (cached))
 146     return robust_scm2interval (cached, Interval (0, 0));
 147
 148   SCM adjacent_pure_heights = me->get_property ("adjacent-pure-heights");
 149   Interval ret;
 150
 151   if (!scm_is_pair (adjacent_pure_heights))
 152     ret = Interval (0, 0);
 153   else
 154     {
 155       SCM these_pure_heights = begin
 156                                ? scm_car (adjacent_pure_heights)
 157                                : scm_cdr (adjacent_pure_heights);
 158
 159       if (scm_is_vector (these_pure_heights))
 160         ret = combine_pure_heights (me, these_pure_heights, start, end);
 161       else
 162         ret = Interval (0, 0);
 163     }
 164
 165   sp->cache_pure_property (cache_symbol, start, end, ly_interval2scm (ret));
 166   return ret;
 167 }
 168
 169 Interval
 170 Axis_group_interface::begin_of_line_pure_height (Grob *me, int start)
 171 {
 172   return part_of_line_pure_height (me, true, start, start + 1);
 173 }
 174
 175 Interval
 176 Axis_group_interface::rest_of_line_pure_height (Grob *me, int start, int end)
 177 {
 178   return part_of_line_pure_height (me, false, start, end);
 179 }
 180
 181 Interval
 182 Axis_group_interface::combine_pure_heights (Grob *me, SCM measure_extents, int start, int end)
 183 {
 184   Paper_score *ps = get_root_system (me)->paper_score ();
 185   vector<vsize> breaks = ps->get_break_indices ();
 186   vector<Grob *> cols = ps->get_columns ();
 187
 188   Interval ext;
 189   for (vsize i = 0; i + 1 < breaks.size (); i++)
 190     {
 191       int r = Paper_column::get_rank (cols[breaks[i]]);
 192       if (r >= end)
 193         break;
 194
 195       if (r >= start)
 196         ext.unite (ly_scm2interval (scm_c_vector_ref (measure_extents, i)));
 197     }
 198
 199   return ext;
 200 }
 201
 202 // adjacent-pure-heights is a pair of vectors, each of which has one element
 203 // for every measure in the score. The first vector stores, for each measure,
 204 // the combined height of the elements that are present only when the bar
 205 // is at the beginning of a line. The second vector stores, for each measure,
 206 // the combined height of the elements that are present only when the bar
 207 // is not at the beginning of a line.
 208 MAKE_SCHEME_CALLBACK (Axis_group_interface, adjacent_pure_heights, 1)
 209 SCM
 210 Axis_group_interface::adjacent_pure_heights (SCM smob)
 211 {
 212   Grob *me = unsmob_grob (smob);
 213
 214   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 215   extract_grob_set (me, "pure-relevant-grobs", elts);
 216
 217   Paper_score *ps = get_root_system (me)->paper_score ();
 218   vector<vsize> ranks = ps->get_break_ranks ();
 219
 220   vector<Interval> begin_line_heights;
 221   vector<Interval> mid_line_heights;
 222   vector<Interval> begin_line_staff_heights;
 223   vector<Interval> mid_line_staff_heights;
 224   begin_line_heights.resize (ranks.size () - 1);
 225   mid_line_heights.resize (ranks.size () - 1);
 226
 227   for (vsize i = 0; i < elts.size (); ++i)
 228     {
 229       Grob *g = elts[i];
 230
 231       if (to_boolean (g->get_property ("cross-staff")))
 232         continue;
 233
 234       bool outside_staff = scm_is_number (g->get_property ("outside-staff-priority"));
 235       Real padding = robust_scm2double (g->get_property ("outside-staff-padding"), 0.5);
 236
 237       // When we encounter the first outside-staff grob, make a copy
 238       // of the current heights to use as an estimate for the staff heights.
 239       // Note that the outside-staff approximation that we use here doesn't
 240       // consider any collisions that might occur between outside-staff grobs,
 241       // but only the fact that outside-staff grobs may need to be raised above
 242       // the staff.
 243       if (outside_staff && begin_line_staff_heights.empty ())
 244         {
 245           begin_line_staff_heights = begin_line_heights;
 246           mid_line_staff_heights = mid_line_heights;
 247         }
 248
 249       // TODO: consider a pure version of get_grob_direction?
 250       Direction d = to_dir (g->get_property_data ("direction"));
 251       d = (d == CENTER) ? UP : d;
 252
 253       Interval_t<int> rank_span = g->spanned_rank_interval ();
 254       vsize first_break = lower_bound (ranks, (vsize)rank_span[LEFT], less<vsize> ());
 255       if (first_break > 0 && ranks[first_break] >= (vsize)rank_span[LEFT])
 256         first_break--;
 257
 258       for (vsize j = first_break; j + 1 < ranks.size () && (int)ranks[j] <= rank_span[RIGHT]; ++j)
 259         {
 260           int start = ranks[j];
 261           int end = ranks[j + 1];
 262
 263           // Take grobs that are visible with respect to a slightly longer line.
 264           // Otherwise, we will never include grobs at breakpoints which aren't
 265           // end-of-line-visible.
 266           int visibility_end = j + 2 < ranks.size () ? ranks[j + 2] : end;
 267
 268           if (g->pure_is_visible (start, visibility_end))
 269             {
 270               Interval dims = g->pure_height (common, start, end);
 271               if (!dims.is_empty ())
 272                 {
 273                   if (rank_span[LEFT] <= start)
 274                     {
 275                       if (outside_staff)
 276                         begin_line_heights[j].unite (begin_line_staff_heights[j].union_disjoint (dims, padding, d));
 277                       else
 278                         begin_line_heights[j].unite (dims);
 279                     }
 280                   if (rank_span[RIGHT] > start)
 281                     {
 282                       if (outside_staff)
 283                         mid_line_heights[j].unite (mid_line_staff_heights[j].union_disjoint (dims, padding, d));
 284                       else
 285                         mid_line_heights[j].unite (dims);
 286                     }
 287                 }
 288             }
 289         }
 290     }
 291
 292   // Convert begin_line_heights and min_line_heights to SCM.
 293   SCM begin_scm = scm_c_make_vector (ranks.size () - 1, SCM_EOL);
 294   SCM mid_scm = scm_c_make_vector (ranks.size () - 1, SCM_EOL);
 295   for (vsize i = 0; i < begin_line_heights.size (); ++i)
 296     {
 297       scm_vector_set_x (begin_scm, scm_from_int (i), ly_interval2scm (begin_line_heights[i]));
 298       scm_vector_set_x (mid_scm, scm_from_int (i), ly_interval2scm (mid_line_heights[i]));
 299     }
 300
 301   return scm_cons (begin_scm, mid_scm);
 302 }
 303
 304 Interval
 305 Axis_group_interface::relative_pure_height (Grob *me, int start, int end)
 306 {
 307   /* It saves a _lot_ of time if we assume a VerticalAxisGroup is additive
 308      (ie. height (i, k) = max (height (i, j) height (j, k)) for all i <= j <= k).
 309      Unfortunately, it isn't always true, particularly if there is a
 310      VerticalAlignment somewhere in the descendants.
 311
 312      Usually, the only VerticalAlignment comes from Score. This makes it
 313      reasonably safe to assume that if our parent is a VerticalAlignment,
 314      we can assume additivity and cache things nicely. */
 315   Grob *p = me->get_parent (Y_AXIS);
 316   if (p && Align_interface::has_interface (p))
 317     return Axis_group_interface::sum_partial_pure_heights (me, start, end);
 318
 319   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 320   extract_grob_set (me, "pure-relevant-grobs", elts);
 321
 322   Interval r;
 323   for (vsize i = 0; i < elts.size (); i++)
 324     {
 325       Grob *g = elts[i];
 326       Interval_t<int> rank_span = g->spanned_rank_interval ();
 327       if (rank_span[LEFT] <= end && rank_span[RIGHT] >= start
 328           && g->pure_is_visible (start, end)
 329           && !to_boolean (g->get_property ("cross-staff")))
 330         {
 331           Interval dims = g->pure_height (common, start, end);
 332           if (!dims.is_empty ())
 333             r.unite (dims);
 334         }
 335     }
 336   return r;
 337 }
 338
 339 MAKE_SCHEME_CALLBACK (Axis_group_interface, width, 1);
 340 SCM
 341 Axis_group_interface::width (SCM smob)
 342 {
 343   Grob *me = unsmob_grob (smob);
 344   return generic_group_extent (me, X_AXIS);
 345 }
 346
 347 MAKE_SCHEME_CALLBACK (Axis_group_interface, height, 1);
 348 SCM
 349 Axis_group_interface::height (SCM smob)
 350 {
 351   Grob *me = unsmob_grob (smob);
 352   return generic_group_extent (me, Y_AXIS);
 353 }
 354
 355 MAKE_SCHEME_CALLBACK (Axis_group_interface, pure_height, 3);
 356 SCM
 357 Axis_group_interface::pure_height (SCM smob, SCM start_scm, SCM end_scm)
 358 {
 359   int start = robust_scm2int (start_scm, 0);
 360   int end = robust_scm2int (end_scm, INT_MAX);
 361   Grob *me = unsmob_grob (smob);
 362
 363   /* Maybe we are in the second pass of a two-pass spacing run. In that
 364      case, the Y-extent of a system is already given to us */
 365   System *system = dynamic_cast<System *> (me);
 366   if (system)
 367     {
 368       SCM line_break_details = system->column (start)->get_property ("line-break-system-details");
 369       SCM system_y_extent = scm_assq (ly_symbol2scm ("system-Y-extent"), line_break_details);
 370       if (scm_is_pair (system_y_extent))
 371         return scm_cdr (system_y_extent);
 372     }
 373
 374   return ly_interval2scm (pure_group_height (me, start, end));
 375 }
 376
 377 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_skylines, 1);
 378 SCM
 379 Axis_group_interface::calc_skylines (SCM smob)
 380 {
 381   Grob *me = unsmob_grob (smob);
 382   extract_grob_set (me, "elements", elts);
 383   Skyline_pair skylines = skyline_spacing (me, elts);
 384
 385   return skylines.smobbed_copy ();
 386 }
 387
 388 /* whereas calc_skylines calculates skylines for axis-groups with a lot of
 389    visible children, combine_skylines is designed for axis-groups whose only
 390    children are other axis-groups (ie. VerticalAlignment). Rather than
 391    calculating all the skylines from scratch, we just merge the skylines
 392    of the children.
 393 */
 394 MAKE_SCHEME_CALLBACK (Axis_group_interface, combine_skylines, 1);
 395 SCM
 396 Axis_group_interface::combine_skylines (SCM smob)
 397 {
 398   Grob *me = unsmob_grob (smob);
 399   extract_grob_set (me, "elements", elements);
 400   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 401   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 402
 403   if (y_common != me)
 404     programming_error ("combining skylines that don't belong to me");
 405
 406   Skyline_pair ret;
 407   for (vsize i = 0; i < elements.size (); i++)
 408     {
 409       SCM skyline_scm = elements[i]->get_property ("vertical-skylines");
 410       if (Skyline_pair::unsmob (skyline_scm))
 411         {
 412           Real offset = elements[i]->relative_coordinate (y_common, Y_AXIS);
 413           Skyline_pair other = *Skyline_pair::unsmob (skyline_scm);
 414           other.raise (offset);
 415           other.shift (elements[i]->relative_coordinate (x_common, X_AXIS));
 416           ret.merge (other);
 417         }
 418     }
 419   return ret.smobbed_copy ();
 420 }
 421
 422 SCM
 423 Axis_group_interface::generic_group_extent (Grob *me, Axis a)
 424 {
 425   /* trigger the callback to do skyline-spacing on the children */
 426   if (a == Y_AXIS)
 427     (void) me->get_property ("vertical-skylines");
 428
 429   extract_grob_set (me, "elements", elts);
 430   Grob *common = common_refpoint_of_array (elts, me, a);
 431
 432   Real my_coord = me->relative_coordinate (common, a);
 433   Interval r (relative_group_extent (elts, common, a));
 434
 435   return ly_interval2scm (r - my_coord);
 436 }
 437
 438 /* This is like generic_group_extent, but it only counts the grobs that
 439    are children of some other axis-group. This is uncached; if it becomes
 440    commonly used, it may be necessary to cache it somehow. */
 441 Interval
 442 Axis_group_interface::staff_extent (Grob *me, Grob *refp, Axis ext_a, Grob *staff, Axis parent_a)
 443 {
 444   extract_grob_set (me, "elements", elts);
 445   vector<Grob *> new_elts;
 446
 447   for (vsize i = 0; i < elts.size (); i++)
 448     if (elts[i]->common_refpoint (staff, parent_a) == staff)
 449       new_elts.push_back (elts[i]);
 450
 451   return relative_group_extent (new_elts, refp, ext_a);
 452 }
 453
 454 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_relevant_grobs, 1);
 455 SCM
 456 Axis_group_interface::calc_pure_relevant_grobs (SCM smob)
 457 {
 458   Grob *me = unsmob_grob (smob);
 459   return internal_calc_pure_relevant_grobs (me, "elements");
 460 }
 461
 462 SCM
 463 Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, string grob_set_name)
 464 {
 465   extract_grob_set (me, grob_set_name.c_str (), elts);
 466
 467   vector<Grob *> relevant_grobs;
 468   SCM pure_relevant_p = ly_lily_module_constant ("pure-relevant?");
 469
 470   for (vsize i = 0; i < elts.size (); i++)
 471     {
 472       if (to_boolean (scm_apply_1 (pure_relevant_p, elts[i]->self_scm (), SCM_EOL)))
 473         relevant_grobs.push_back (elts[i]);
 474
 475       if (Item *it = dynamic_cast<Item *> (elts[i]))
 476         {
 477           Direction d = LEFT;
 478           do
 479             {
 480               Item *piece = it->find_prebroken_piece (d);
 481               if (piece && to_boolean (scm_apply_1 (pure_relevant_p, piece->self_scm (), SCM_EOL)))
 482                 relevant_grobs.push_back (piece);
 483             }
 484           while (flip (&d) != LEFT);
 485         }
 486     }
 487
 488   vector_sort (relevant_grobs, pure_staff_priority_less);
 489   SCM grobs_scm = Grob_array::make_array ();
 490   unsmob_grob_array (grobs_scm)->set_array (relevant_grobs);
 491
 492   return grobs_scm;
 493 }
 494
 495 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_y_common, 1);
 496 SCM
 497 Axis_group_interface::calc_pure_y_common (SCM smob)
 498 {
 499   Grob *me = unsmob_grob (smob);
 500
 501   extract_grob_set (me, "pure-relevant-grobs", elts);
 502   Grob *common = common_refpoint_of_array (elts, me, Y_AXIS);
 503   if (!common)
 504     {
 505       me->programming_error ("No common parent found in calc_pure_y_common.");
 506       return SCM_EOL;
 507     }
 508
 509   return common->self_scm ();
 510 }
 511
 512 SCM
 513 Axis_group_interface::calc_common (Grob *me, Axis axis)
 514 {
 515   extract_grob_set (me, "elements", elts);
 516   Grob *common = common_refpoint_of_array (elts, me, axis);
 517   if (!common)
 518     {
 519       me->programming_error ("No common parent found in calc_common axis.");
 520       return SCM_EOL;
 521     }
 522
 523   return common->self_scm ();
 524 }
 525
 526 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_x_common, 1);
 527 SCM
 528 Axis_group_interface::calc_x_common (SCM grob)
 529 {
 530   return calc_common (unsmob_grob (grob), X_AXIS);
 531 }
 532
 533 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_y_common, 1);
 534 SCM
 535 Axis_group_interface::calc_y_common (SCM grob)
 536 {
 537   return calc_common (unsmob_grob (grob), Y_AXIS);
 538 }
 539
 540 Interval
 541 Axis_group_interface::pure_group_height (Grob *me, int start, int end)
 542 {
 543   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 544
 545   if (!common)
 546     {
 547       programming_error ("no pure Y common refpoint");
 548       return Interval ();
 549     }
 550   Real my_coord = me->relative_coordinate (common, Y_AXIS);
 551   Interval r (relative_pure_height (me, start, end));
 552
 553   return r - my_coord;
 554 }
 555
 556 void
 557 Axis_group_interface::get_children (Grob *me, vector<Grob *> *found)
 558 {
 559   found->push_back (me);
 560
 561   if (!has_interface (me))
 562     return;
 563
 564   extract_grob_set (me, "elements", elements);
 565   for (vsize i = 0; i < elements.size (); i++)
 566     {
 567       Grob *e = elements[i];
 568       Axis_group_interface::get_children (e, found);
 569     }
 570 }
 571
 572 static bool
 573 staff_priority_less (Grob *const &g1, Grob *const &g2)
 574 {
 575   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 576   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 577
 578   if (priority_1 < priority_2)
 579     return true;
 580   else if (priority_1 > priority_2)
 581     return false;
 582
 583   /* if neither grob has an outside-staff priority, the ordering will have no
 584      effect -- we just need to choose a consistent ordering. We do this to
 585      avoid the side-effect of calculating extents. */
 586   if (isinf (priority_1))
 587     return g1 < g2;
 588
 589   /* if there is no preference in staff priority, choose the left-most one */
 590   Grob *common = g1->common_refpoint (g2, X_AXIS);
 591   Real start_1 = g1->extent (common, X_AXIS)[LEFT];
 592   Real start_2 = g2->extent (common, X_AXIS)[LEFT];
 593   return start_1 < start_2;
 594 }
 595
 596 static bool
 597 pure_staff_priority_less (Grob *const &g1, Grob *const &g2)
 598 {
 599   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 600   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 601
 602   return priority_1 < priority_2;
 603 }
 604
 605 static void
 606 add_boxes (Grob *me, Grob *x_common, Grob *y_common, vector<Box> *const boxes, Skyline_pair *skylines)
 607 {
 608   /* if a child has skylines, use them instead of the extent box */
 609   if (Skyline_pair *pair = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
 610     {
 611       Skyline_pair s = *pair;
 612       s.shift (me->relative_coordinate (x_common, X_AXIS));
 613       s.raise (me->relative_coordinate (y_common, Y_AXIS));
 614       skylines->merge (s);
 615     }
 616   else if (Grob_array *elements = unsmob_grob_array (me->get_object ("elements")))
 617     {
 618       for (vsize i = 0; i < elements->size (); i++)
 619         add_boxes (elements->grob (i), x_common, y_common, boxes, skylines);
 620     }
 621   else if (!scm_is_number (me->get_property ("outside-staff-priority"))
 622            && !to_boolean (me->get_property ("cross-staff")))
 623     {
 624       boxes->push_back (Box (me->extent (x_common, X_AXIS),
 625                              me->extent (y_common, Y_AXIS)));
 626     }
 627 }
 628
 629 /* We want to avoid situations like this:
 630            still more text
 631       more text
 632    text
 633    -------------------
 634    staff
 635    -------------------
 636
 637    The point is that "still more text" should be positioned under
 638    "more text".  In order to achieve this, we place the grobs in several
 639    passes.  We keep track of the right-most horizontal position that has been
 640    affected by the current pass so far (actually we keep track of 2
 641    positions, one for above the staff, one for below).
 642
 643    In each pass, we loop through the unplaced grobs from left to right.
 644    If the grob doesn't overlap the right-most affected position, we place it
 645    (and then update the right-most affected position to point to the right
 646    edge of the just-placed grob).  Otherwise, we skip it until the next pass.
 647 */
 648 static void
 649 add_grobs_of_one_priority (Skyline_pair *const skylines,
 650                            vector<Grob *> elements,
 651                            Grob *x_common,
 652                            Grob *y_common)
 653 {
 654   vector<Box> boxes;
 655   Drul_array<Real> last_affected_position;
 656
 657   reverse (elements);
 658   while (!elements.empty ())
 659     {
 660       last_affected_position[UP] = -infinity_f;
 661       last_affected_position[DOWN] = -infinity_f;
 662       /* do one pass */
 663       for (vsize i = elements.size (); i--;)
 664         {
 665           Direction dir = get_grob_direction (elements[i]);
 666           if (dir == CENTER)
 667             {
 668               warning (_ ("an outside-staff object should have a direction, defaulting to up"));
 669               dir = UP;
 670             }
 671
 672           Box b (elements[i]->extent (x_common, X_AXIS),
 673                  elements[i]->extent (y_common, Y_AXIS));
 674           SCM horizon_padding_scm = elements[i]->get_property ("outside-staff-horizontal-padding");
 675           Real horizon_padding = robust_scm2double (horizon_padding_scm, 0.0);
 676
 677           if (b[X_AXIS][LEFT] - 2 * horizon_padding < last_affected_position[dir])
 678             continue;
 679
 680           if (!b[X_AXIS].is_empty () && !b[Y_AXIS].is_empty ())
 681             {
 682               boxes.clear ();
 683               boxes.push_back (b);
 684               Skyline other = Skyline (boxes, horizon_padding, X_AXIS, -dir);
 685               Real padding = robust_scm2double (elements[i]->get_property ("outside-staff-padding"), 0.5);
 686               Real dist = (*skylines)[dir].distance (other) + padding;
 687
 688               if (dist > 0)
 689                 {
 690                   b.translate (Offset (0, dir * dist));
 691                   elements[i]->translate_axis (dir * dist, Y_AXIS);
 692                 }
 693               skylines->insert (b, 0, X_AXIS);
 694               elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
 695               last_affected_position[dir] = b[X_AXIS][RIGHT];
 696             }
 697
 698           /*
 699             Ugh: quadratic. --hwn
 700            */
 701           elements.erase (elements.begin () + i);
 702         }
 703     }
 704 }
 705
 706 bool
 707 Axis_group_interface::has_outside_staff_parent (Grob *me)
 708 {
 709   return (me
 710           ? (scm_is_number (me->get_property ("outside-staff-priority"))
 711              || has_outside_staff_parent (me->get_parent (Y_AXIS)))
 712           : false);
 713 }
 714
 715 // TODO: it is tricky to correctly handle skyline placement of cross-staff grobs.
 716 // For example, cross-staff beams cannot be formatted until the distance between
 717 // staves is known and therefore any grobs that depend on the beam cannot be placed
 718 // until the skylines are known. On the other hand, the distance between staves should
 719 // really depend on position of the cross-staff grobs that lie between them.
 720 // Currently, we just leave cross-staff grobs out of the
 721 // skyline altogether, but this could mean that staves are placed so close together
 722 // that there is no room for the cross-staff grob. It also means, of course, that
 723 // we don't get the benefits of skyline placement for cross-staff grobs.
 724 Skyline_pair
 725 Axis_group_interface::skyline_spacing (Grob *me, vector<Grob *> elements)
 726 {
 727   /* For grobs with an outside-staff-priority, the sorting function might
 728      call extent and cause suicide. This breaks the contract that is required
 729      for the STL sort function. To avoid this, we make sure that any suicides
 730      are triggered beforehand.
 731   */
 732   for (vsize i = 0; i < elements.size (); i++)
 733     if (scm_is_number (elements[i]->get_property ("outside-staff-priority")))
 734       elements[i]->extent (elements[i], X_AXIS);
 735
 736   vector_sort (elements, staff_priority_less);
 737   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 738   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 739
 740   assert (y_common == me);
 741
 742   vsize i = 0;
 743   vector<Box> boxes;
 744
 745   Skyline_pair skylines;
 746   for (i = 0; i < elements.size ()
 747        && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
 748     if (!(to_boolean (elements[i]->get_property ("cross-staff")) || has_outside_staff_parent (elements[i])))
 749       add_boxes (elements[i], x_common, y_common, &boxes, &skylines);
 750
 751   SCM padding_scm = me->get_property ("skyline-horizontal-padding");
 752   Real padding = robust_scm2double (padding_scm, 0.1);
 753   skylines.merge (Skyline_pair (boxes, padding, X_AXIS));
 754   for (; i < elements.size (); i++)
 755     {
 756       if (to_boolean (elements[i]->get_property ("cross-staff")))
 757         continue;
 758
 759       SCM priority = elements[i]->get_property ("outside-staff-priority");
 760       vector<Grob *> current_elts;
 761       current_elts.push_back (elements[i]);
 762       while (i + 1 < elements.size ()
 763              && scm_is_eq (elements[i + 1]->get_property ("outside-staff-priority"), priority))
 764         {
 765           if (!to_boolean (elements[i + 1]->get_property ("cross-staff")))
 766             current_elts.push_back (elements[i + 1]);
 767           ++i;
 768         }
 769
 770       add_grobs_of_one_priority (&skylines, current_elts, x_common, y_common);
 771     }
 772   skylines.shift (-me->relative_coordinate (x_common, X_AXIS));
 773   return skylines;
 774 }
 775
 776 MAKE_SCHEME_CALLBACK (Axis_group_interface, print, 1)
 777 SCM
 778 Axis_group_interface::print (SCM smob)
 779 {
 780   if (!debug_skylines)
 781     return SCM_BOOL_F;
 782
 783   Grob *me = unsmob_grob (smob);
 784   Stencil ret;
 785   if (Skyline_pair *s = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
 786     {
 787       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[UP].to_points (X_AXIS))
 788                        .in_color (255, 0, 255));
 789       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[DOWN].to_points (X_AXIS))
 790                        .in_color (0, 255, 255));
 791     }
 792   return ret.smobbed_copy ();
 793 }
 794
 795 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_staff_staff_spacing, 3)
 796 SCM
 797 Axis_group_interface::calc_pure_staff_staff_spacing (SCM smob, SCM start, SCM end)
 798 {
 799   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 800                                               true,
 801                                               scm_to_int (start),
 802                                               scm_to_int (end));
 803 }
 804
 805 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_staff_staff_spacing, 1)
 806 SCM
 807 Axis_group_interface::calc_staff_staff_spacing (SCM smob)
 808 {
 809   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 810                                               false,
 811                                               0,
 812                                               INT_MAX);
 813 }
 814
 815 SCM
 816 Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure, int start, int end)
 817 {
 818   Grob *grouper = unsmob_grob (me->get_object ("staff-grouper"));
 819
 820   if (grouper)
 821     {
 822       bool within_group = Staff_grouper_interface::maybe_pure_within_group (grouper, me, pure, start, end);
 823       if (within_group)
 824         return grouper->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
 825       else
 826         return grouper->get_maybe_pure_property ("staffgroup-staff-spacing", pure, start, end);
 827     }
 828   return me->get_maybe_pure_property ("default-staff-staff-spacing", pure, start, end);
 829 }
 830
 831 Real
 832 Axis_group_interface::minimum_distance (Grob *g1, Grob *g2, Axis a)
 833 {
 834   SCM sym = ly_symbol2scm ((a == Y_AXIS) ? "vertical-skylines" : "horizontal-skylines");
 835
 836   Skyline_pair *s1 = Skyline_pair::unsmob (g1->get_property (sym));
 837   Skyline_pair *s2 = Skyline_pair::unsmob (g2->get_property (sym));
 838   if (s1 && s2)
 839     return (*s1)[DOWN].distance ((*s2)[UP]);
 840   return 0;
 841 }
 842
 843 ADD_INTERFACE (Axis_group_interface,
 844                "An object that groups other layout objects.",
 845
 846                // TODO: some of these properties are specific to
 847                // VerticalAxisGroup. We should split off a
 848                // vertical-axis-group-interface.
 849                /* properties */
 850                "adjacent-pure-heights "
 851                "axes "
 852                "bound-alignment-interfaces "
 853                "default-staff-staff-spacing "
 854                "elements "
 855                "max-stretch "
 856                "no-alignment "
 857                "nonstaff-nonstaff-spacing "
 858                "nonstaff-relatedstaff-spacing "
 859                "nonstaff-unrelatedstaff-spacing "
 860                "pure-relevant-grobs "
 861                "pure-relevant-items "
 862                "pure-relevant-spanners "
 863                "pure-Y-common "
 864                "staff-affinity "
 865                "staff-grouper "
 866                "staff-staff-spacing "
 867                "system-Y-offset "
 868                "vertical-skylines "
 869                "X-common "
 870                "Y-common "
 871               );