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