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           for (LEFT_and_RIGHT (d))
 480             {
 481               Item *piece = it->find_prebroken_piece (d);
 482               if (piece && to_boolean (scm_apply_1 (pure_relevant_p, piece->self_scm (), SCM_EOL)))
 483                 relevant_grobs.push_back (piece);
 484             }
 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               );