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       (void) elts[i]->get_property ("vertical-skylines");
 460
 461   Grob *common = common_refpoint_of_array (elts, me, a);
 462
 463   Real my_coord = me->relative_coordinate (common, a);
 464   Interval r (relative_group_extent (elts, common, a));
 465
 466   return ly_interval2scm (r - my_coord);
 467 }
 468
 469 /* This is like generic_group_extent, but it only counts the grobs that
 470    are children of some other axis-group. This is uncached; if it becomes
 471    commonly used, it may be necessary to cache it somehow. */
 472 Interval
 473 Axis_group_interface::staff_extent (Grob *me, Grob *refp, Axis ext_a, Grob *staff, Axis parent_a)
 474 {
 475   extract_grob_set (me, "elements", elts);
 476   vector<Grob *> new_elts;
 477
 478   for (vsize i = 0; i < elts.size (); i++)
 479     if (elts[i]->common_refpoint (staff, parent_a) == staff)
 480       new_elts.push_back (elts[i]);
 481
 482   return relative_group_extent (new_elts, refp, ext_a);
 483 }
 484
 485 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_relevant_grobs, 1);
 486 SCM
 487 Axis_group_interface::calc_pure_relevant_grobs (SCM smob)
 488 {
 489   Grob *me = unsmob_grob (smob);
 490   return internal_calc_pure_relevant_grobs (me, "elements");
 491 }
 492
 493 SCM
 494 Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, string grob_set_name)
 495 {
 496   extract_grob_set (me, grob_set_name.c_str (), elts);
 497
 498   vector<Grob *> relevant_grobs;
 499
 500   for (vsize i = 0; i < elts.size (); i++)
 501     {
 502       if (elts[i] && elts[i]->is_live ())
 503         {
 504           relevant_grobs.push_back (elts[i]);
 505           if (Item *it = dynamic_cast<Item *> (elts[i]))
 506             {
 507               for (LEFT_and_RIGHT (d))
 508                 {
 509                   Item *piece = it->find_prebroken_piece (d);
 510                   if (piece && piece->is_live ())
 511                     relevant_grobs.push_back (piece);
 512                 }
 513             }
 514         }
 515     }
 516
 517   vector_sort (relevant_grobs, pure_staff_priority_less);
 518   SCM grobs_scm = Grob_array::make_array ();
 519   unsmob_grob_array (grobs_scm)->set_array (relevant_grobs);
 520
 521   return grobs_scm;
 522 }
 523
 524 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_y_common, 1);
 525 SCM
 526 Axis_group_interface::calc_pure_y_common (SCM smob)
 527 {
 528   Grob *me = unsmob_grob (smob);
 529
 530   extract_grob_set (me, "pure-relevant-grobs", elts);
 531   Grob *common = common_refpoint_of_array (elts, me, Y_AXIS);
 532   if (!common)
 533     {
 534       me->programming_error ("No common parent found in calc_pure_y_common.");
 535       return SCM_EOL;
 536     }
 537
 538   return common->self_scm ();
 539 }
 540
 541 SCM
 542 Axis_group_interface::calc_common (Grob *me, Axis axis)
 543 {
 544   extract_grob_set (me, "elements", elts);
 545   Grob *common = common_refpoint_of_array (elts, me, axis);
 546   if (!common)
 547     {
 548       me->programming_error ("No common parent found in calc_common axis.");
 549       return SCM_EOL;
 550     }
 551
 552   return common->self_scm ();
 553 }
 554
 555 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_x_common, 1);
 556 SCM
 557 Axis_group_interface::calc_x_common (SCM grob)
 558 {
 559   return calc_common (unsmob_grob (grob), X_AXIS);
 560 }
 561
 562 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_y_common, 1);
 563 SCM
 564 Axis_group_interface::calc_y_common (SCM grob)
 565 {
 566   return calc_common (unsmob_grob (grob), Y_AXIS);
 567 }
 568
 569 Interval
 570 Axis_group_interface::pure_group_height (Grob *me, int start, int end)
 571 {
 572   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 573
 574   if (!common)
 575     {
 576       programming_error ("no pure Y common refpoint");
 577       return Interval ();
 578     }
 579   Real my_coord = me->pure_relative_y_coordinate (common, start, end);
 580   Interval r (relative_pure_height (me, start, end));
 581
 582   return r - my_coord;
 583 }
 584
 585 void
 586 Axis_group_interface::get_children (Grob *me, vector<Grob *> *found)
 587 {
 588   found->push_back (me);
 589
 590   if (!has_interface (me))
 591     return;
 592
 593   extract_grob_set (me, "elements", elements);
 594   for (vsize i = 0; i < elements.size (); i++)
 595     {
 596       Grob *e = elements[i];
 597       Axis_group_interface::get_children (e, found);
 598     }
 599 }
 600
 601 static bool
 602 staff_priority_less (Grob *const &g1, Grob *const &g2)
 603 {
 604   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 605   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 606
 607   if (priority_1 < priority_2)
 608     return true;
 609   else if (priority_1 > priority_2)
 610     return false;
 611
 612   /* if neither grob has an outside-staff priority, the ordering will have no
 613      effect -- we just need to choose a consistent ordering. We do this to
 614      avoid the side-effect of calculating extents. */
 615   if (isinf (priority_1))
 616     return g1 < g2;
 617
 618   /* if there is no preference in staff priority, choose the left-most one */
 619   Grob *common = g1->common_refpoint (g2, X_AXIS);
 620   Real start_1 = g1->extent (common, X_AXIS)[LEFT];
 621   Real start_2 = g2->extent (common, X_AXIS)[LEFT];
 622   return start_1 < start_2;
 623 }
 624
 625 static bool
 626 pure_staff_priority_less (Grob *const &g1, Grob *const &g2)
 627 {
 628   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 629   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 630
 631   return priority_1 < priority_2;
 632 }
 633
 634 static void
 635 add_interior_skylines (Grob *me, Grob *x_common, Grob *y_common, vector<Skyline_pair> *skylines)
 636 {
 637   if (Grob_array *elements = unsmob_grob_array (me->get_object ("elements")))
 638     {
 639       for (vsize i = 0; i < elements->size (); i++)
 640         add_interior_skylines (elements->grob (i), x_common, y_common, skylines);
 641     }
 642   else if (!scm_is_number (me->get_property ("outside-staff-priority"))
 643            && !to_boolean (me->get_property ("cross-staff")))
 644     {
 645       Skyline_pair *maybe_pair = Skyline_pair::unsmob (me->get_property ("vertical-skylines"));
 646       if (!maybe_pair)
 647         return;
 648       if (maybe_pair->is_empty ())
 649         return;
 650       skylines->push_back (Skyline_pair (*maybe_pair));
 651       skylines->back ().shift (me->relative_coordinate (x_common, X_AXIS));
 652       skylines->back ().raise (me->relative_coordinate (y_common, Y_AXIS));
 653     }
 654 }
 655
 656 // Raises the grob elt (whose skylines are given by h_skyline
 657 // and v_skyline) so that it doesn't intersect with staff_skyline,
 658 // or with anything in other_h_skylines and other_v_skylines.
 659 void
 660 avoid_outside_staff_collisions (Grob *elt,
 661                                 Skyline_pair *v_skyline,
 662                                 Real padding,
 663                                 Real horizon_padding,
 664                                 vector<Skyline_pair> const &other_v_skylines,
 665                                 vector<Real> const &other_padding,
 666                                 vector<Real> const &other_horizon_padding,
 667                                 Direction const dir)
 668 {
 669   assert (other_v_skylines.size () == other_padding.size ());
 670   assert (other_v_skylines.size () == other_horizon_padding.size ());
 671   vector<Interval> forbidden_intervals;
 672   for (vsize j = 0; j < other_v_skylines.size (); j++)
 673     {
 674       Skyline_pair const &v_other = other_v_skylines[j];
 675       Real pad = (padding + other_padding[j]);
 676       Real horizon_pad = (horizon_padding + other_horizon_padding[j]);
 677
 678       // We need to push elt up by at least this much to be above v_other.
 679       Real up = (*v_skyline)[DOWN].distance (v_other[UP], horizon_pad) + pad;
 680       // We need to push elt down by at least this much to be below v_other.
 681       Real down = (*v_skyline)[UP].distance (v_other[DOWN], horizon_pad) + pad;
 682
 683       forbidden_intervals.push_back (Interval (-down, up));
 684     }
 685
 686   Interval_set allowed_shifts
 687     = Interval_set::interval_union (forbidden_intervals).complement ();
 688   Real move = allowed_shifts.nearest_point (0, dir);
 689   v_skyline->raise (move);
 690   elt->translate_axis (move, Y_AXIS);
 691 }
 692
 693 SCM
 694 valid_outside_staff_placement_directive (Grob *me)
 695 {
 696   SCM directive = me->get_property ("outside-staff-placement-directive");
 697
 698   if ((directive == ly_symbol2scm ("left-to-right-greedy"))
 699       || (directive == ly_symbol2scm ("left-to-right-polite"))
 700       || (directive == ly_symbol2scm ("right-to-left-greedy"))
 701       || (directive == ly_symbol2scm ("right-to-left-polite")))
 702     return directive;
 703
 704   me->warning (_f ("\"%s\" is not a valid outside-staff-placement-directive",
 705                    robust_symbol2string (directive, "").c_str ()));
 706
 707   return ly_symbol2scm ("left-to-right-polite");
 708 }
 709
 710 // Shifts the grobs in elements to ensure that they (and any
 711 // connected riders) don't collide with the staff skylines
 712 // or anything in all_X_skylines.  Afterwards, the skylines
 713 // of the grobs in elements will be added to all_v_skylines.
 714 static void
 715 add_grobs_of_one_priority (Grob *me,
 716                            Drul_array<vector<Skyline_pair> > *all_v_skylines,
 717                            Drul_array<vector<Real> > *all_paddings,
 718                            Drul_array<vector<Real> > *all_horizon_paddings,
 719                            vector<Grob *> elements,
 720                            Grob *x_common,
 721                            Grob *y_common,
 722                            multimap<Grob *, Grob *> const &riders)
 723 {
 724
 725   SCM directive
 726     = valid_outside_staff_placement_directive (me);
 727
 728   bool l2r = ((directive == ly_symbol2scm ("left-to-right-greedy"))
 729               || (directive == ly_symbol2scm ("left-to-right-polite")));
 730
 731   bool polite = ((directive == ly_symbol2scm ("left-to-right-polite"))
 732                  || (directive == ly_symbol2scm ("right-to-left-polite")));
 733
 734   vector<Box> boxes;
 735   vector<Skyline_pair> skylines_to_merge;
 736
 737   // We want to avoid situations like this:
 738   //           still more text
 739   //      more text
 740   //   text
 741   //   -------------------
 742   //   staff
 743   //   -------------------
 744
 745   // The point is that "still more text" should be positioned under
 746   // "more text".  In order to achieve this, we place the grobs in several
 747   // passes.  We keep track of the right-most horizontal position that has been
 748   // affected by the current pass so far (actually we keep track of 2
 749   // positions, one for above the staff, one for below).
 750
 751   // In each pass, we loop through the unplaced grobs from left to right.
 752   // If the grob doesn't overlap the right-most affected position, we place it
 753   // (and then update the right-most affected position to point to the right
 754   // edge of the just-placed grob).  Otherwise, we skip it until the next pass.
 755   while (!elements.empty ())
 756     {
 757       Drul_array<Real> last_end (-infinity_f, -infinity_f);
 758       vector<Grob *> skipped_elements;
 759       for (vsize i = l2r ? 0 : elements.size ();
 760            l2r ? i < elements.size () : i--;
 761            l2r ? i++ : 0)
 762         {
 763           Grob *elt = elements[i];
 764           Real padding
 765             = robust_scm2double (elt->get_property ("outside-staff-padding"), 0.25);
 766           Real horizon_padding
 767             = robust_scm2double (elt->get_property ("outside-staff-horizontal-padding"), 0.0);
 768           Interval x_extent = elt->extent (x_common, X_AXIS);
 769           x_extent.widen (horizon_padding);
 770
 771           Direction dir = get_grob_direction (elt);
 772           if (dir == CENTER)
 773             {
 774               warning (_ ("an outside-staff object should have a direction, defaulting to up"));
 775               dir = UP;
 776             }
 777
 778           if (x_extent[LEFT] <= last_end[dir] && polite)
 779             {
 780               skipped_elements.push_back (elt);
 781               continue;
 782             }
 783           last_end[dir] = x_extent[RIGHT];
 784
 785           Skyline_pair *v_orig = Skyline_pair::unsmob (elt->get_property ("vertical-skylines"));
 786           if (v_orig->is_empty ())
 787             continue;
 788
 789           // Find the riders associated with this grob, and merge their
 790           // skylines with elt's skyline.
 791           typedef multimap<Grob *, Grob *>::const_iterator GrobMapIterator;
 792           pair<GrobMapIterator, GrobMapIterator> range = riders.equal_range (elt);
 793           vector<Skyline_pair> rider_v_skylines;
 794           for (GrobMapIterator j = range.first; j != range.second; j++)
 795             {
 796               Grob *rider = j->second;
 797               Skyline_pair *v_rider = Skyline_pair::unsmob (rider->get_property ("vertical-skylines"));
 798               if (v_rider)
 799                 {
 800                   Skyline_pair copy (*v_rider);
 801                   copy.shift (rider->relative_coordinate (x_common, X_AXIS));
 802                   copy.raise (rider->relative_coordinate (y_common, Y_AXIS));
 803                   rider_v_skylines.push_back (copy);
 804                 }
 805             }
 806           Skyline_pair v_skylines (*v_orig);
 807           v_skylines.shift (elt->relative_coordinate (x_common, X_AXIS));
 808           v_skylines.raise (elt->relative_coordinate (y_common, Y_AXIS));
 809           v_skylines.merge (Skyline_pair (rider_v_skylines));
 810
 811           avoid_outside_staff_collisions (elt,
 812                                           &v_skylines,
 813                                           padding,
 814                                           horizon_padding,
 815                                           (*all_v_skylines)[dir],
 816                                           (*all_paddings)[dir],
 817                                           (*all_horizon_paddings)[dir],
 818                                           dir);
 819
 820           elt->set_property ("outside-staff-priority", SCM_BOOL_F);
 821           (*all_v_skylines)[dir].push_back (v_skylines);
 822           (*all_paddings)[dir].push_back (padding);
 823           (*all_horizon_paddings)[dir].push_back (horizon_padding);
 824         }
 825       swap (elements, skipped_elements);
 826       skipped_elements.clear ();
 827     }
 828 }
 829
 830 // If the Grob has a Y-ancestor with outside-staff-priority, return it.
 831 // Otherwise, return 0.
 832 Grob *
 833 Axis_group_interface::outside_staff_ancestor (Grob *me)
 834 {
 835   Grob *parent = me->get_parent (Y_AXIS);
 836   if (!parent)
 837     return 0;
 838
 839   if (scm_is_number (parent->get_property ("outside-staff-priority")))
 840     return parent;
 841
 842   return outside_staff_ancestor (parent);
 843 }
 844
 845 // It is tricky to correctly handle skyline placement of cross-staff grobs.
 846 // For example, cross-staff beams cannot be formatted until the distance between
 847 // staves is known and therefore any grobs that depend on the beam cannot be placed
 848 // until the skylines are known. On the other hand, the distance between staves should
 849 // really depend on position of the cross-staff grobs that lie between them.
 850 // Currently, we just leave cross-staff grobs out of the
 851 // skyline altogether, but this could mean that staves are placed so close together
 852 // that there is no room for the cross-staff grob. It also means, of course, that
 853 // we don't get the benefits of skyline placement for cross-staff grobs.
 854 Skyline_pair
 855 Axis_group_interface::skyline_spacing (Grob *me)
 856 {
 857   extract_grob_set (me, Grob_array::unsmob (me->get_object ("vertical-skyline-elements")) ? "vertical-skyline-elements" : "elements", fakeelements);
 858   vector<Grob *> elements (fakeelements);
 859   for (vsize i = 0; i < elements.size (); i++)
 860     /*
 861       As a sanity check, we make sure that no grob with an outside staff priority
 862       has a Y-parent that also has an outside staff priority, which would result
 863       in two movings.
 864     */
 865     if (scm_is_number (elements[i]->get_property ("outside-staff-priority"))
 866         && outside_staff_ancestor (elements[i]))
 867       {
 868         elements[i]->warning ("Cannot set outside-staff-priority for element and elements' Y parent.");
 869         elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
 870       }
 871
 872   /* For grobs with an outside-staff-priority, the sorting function might
 873      call extent and cause suicide. This breaks the contract that is required
 874      for the STL sort function. To avoid this, we make sure that any suicides
 875      are triggered beforehand.
 876   */
 877   for (vsize i = 0; i < elements.size (); i++)
 878     if (scm_is_number (elements[i]->get_property ("outside-staff-priority")))
 879       elements[i]->extent (elements[i], X_AXIS);
 880
 881   vector_sort (elements, staff_priority_less);
 882   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 883   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 884
 885   assert (y_common == me);
 886
 887   // A rider is a grob that is not outside-staff, but has an outside-staff
 888   // ancestor.  In that case, the rider gets moved along with its ancestor.
 889   multimap<Grob *, Grob *> riders;
 890
 891   vsize i = 0;
 892   vector<Skyline_pair> inside_staff_skylines;
 893
 894   for (i = 0; i < elements.size ()
 895        && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
 896     {
 897       Grob *elt = elements[i];
 898       Grob *ancestor = outside_staff_ancestor (elt);
 899       if (!ancestor)
 900         add_interior_skylines (elt, x_common, y_common, &inside_staff_skylines);
 901       if (ancestor)
 902         riders.insert (pair<Grob *, Grob *> (ancestor, elt));
 903     }
 904
 905   Skyline_pair skylines (inside_staff_skylines);
 906
 907   // These are the skylines of all outside-staff grobs
 908   // that have already been processed.  We keep them around in order to
 909   // check them for collisions with the currently active outside-staff grob.
 910   Drul_array<vector<Skyline_pair> > all_v_skylines;
 911   Drul_array<vector<Real> > all_paddings;
 912   Drul_array<vector<Real> > all_horizon_paddings;
 913   for (UP_and_DOWN (d))
 914     {
 915       all_v_skylines[d].push_back (skylines);
 916       all_paddings[d].push_back (0);
 917       all_horizon_paddings[d].push_back (0);
 918     }
 919
 920   for (; i < elements.size (); i++)
 921     {
 922       if (to_boolean (elements[i]->get_property ("cross-staff")))
 923         continue;
 924
 925       // Collect all the outside-staff grobs that have a particular priority.
 926       SCM priority = elements[i]->get_property ("outside-staff-priority");
 927       vector<Grob *> current_elts;
 928       current_elts.push_back (elements[i]);
 929       while (i + 1 < elements.size ()
 930              && scm_is_eq (elements[i + 1]->get_property ("outside-staff-priority"), priority))
 931         {
 932           if (!to_boolean (elements[i + 1]->get_property ("cross-staff")))
 933             current_elts.push_back (elements[i + 1]);
 934           ++i;
 935         }
 936
 937       add_grobs_of_one_priority (me,
 938                                  &all_v_skylines,
 939                                  &all_paddings,
 940                                  &all_horizon_paddings,
 941                                  current_elts,
 942                                  x_common,
 943                                  y_common,
 944                                  riders);
 945     }
 946
 947   // Now everything in all_v_skylines has been shifted appropriately; merge
 948   // them all into skylines to get the complete outline.
 949   Skyline_pair other_skylines (all_v_skylines[UP]);
 950   other_skylines.merge (Skyline_pair (all_v_skylines[DOWN]));
 951   skylines.merge (other_skylines);
 952
 953   // We began by shifting my skyline to be relative to the common refpoint; now
 954   // shift it back.
 955   skylines.shift (-me->relative_coordinate (x_common, X_AXIS));
 956
 957   return skylines;
 958 }
 959
 960 MAKE_SCHEME_CALLBACK (Axis_group_interface, print, 1)
 961 SCM
 962 Axis_group_interface::print (SCM smob)
 963 {
 964   if (!debug_skylines)
 965     return SCM_BOOL_F;
 966
 967   Grob *me = unsmob_grob (smob);
 968   Stencil ret;
 969   if (Skyline_pair *s = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
 970     {
 971       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[UP].to_points (X_AXIS))
 972                        .in_color (255, 0, 255));
 973       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[DOWN].to_points (X_AXIS))
 974                        .in_color (0, 255, 255));
 975     }
 976   return ret.smobbed_copy ();
 977 }
 978
 979 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_staff_staff_spacing, 3)
 980 SCM
 981 Axis_group_interface::calc_pure_staff_staff_spacing (SCM smob, SCM start, SCM end)
 982 {
 983   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 984                                               true,
 985                                               scm_to_int (start),
 986                                               scm_to_int (end));
 987 }
 988
 989 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_staff_staff_spacing, 1)
 990 SCM
 991 Axis_group_interface::calc_staff_staff_spacing (SCM smob)
 992 {
 993   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 994                                               false,
 995                                               0,
 996                                               INT_MAX);
 997 }
 998
 999 SCM
1000 Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure, int start, int end)
1001 {
1002   Grob *grouper = unsmob_grob (me->get_object ("staff-grouper"));
1003
1004   if (grouper)
1005     {
1006       bool within_group = Staff_grouper_interface::maybe_pure_within_group (grouper, me, pure, start, end);
1007       if (within_group)
1008         return grouper->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
1009       else
1010         return grouper->get_maybe_pure_property ("staffgroup-staff-spacing", pure, start, end);
1011     }
1012   return me->get_maybe_pure_property ("default-staff-staff-spacing", pure, start, end);
1013 }
1014
1015 ADD_INTERFACE (Axis_group_interface,
1016                "An object that groups other layout objects.",
1017
1018                // TODO: some of these properties are specific to
1019                // VerticalAxisGroup. We should split off a
1020                // vertical-axis-group-interface.
1021                /* properties */
1022                "adjacent-pure-heights "
1023                "axes "
1024                "bound-alignment-interfaces "
1025                "default-staff-staff-spacing "
1026                "elements "
1027                "max-stretch "
1028                "no-alignment "
1029                "nonstaff-nonstaff-spacing "
1030                "nonstaff-relatedstaff-spacing "
1031                "nonstaff-unrelatedstaff-spacing "
1032                "outside-staff-placement-directive "
1033                "pure-relevant-grobs "
1034                "pure-relevant-items "
1035                "pure-relevant-spanners "
1036                "pure-Y-common "
1037                "staff-affinity "
1038                "staff-grouper "
1039                "staff-staff-spacing "
1040                "system-Y-offset "
1041                "vertical-skyline-elements "
1042                "X-common "
1043                "Y-common "
1044               );