lily/axis-group-interface.cc

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