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