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