lily/axis-group-interface.cc

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