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