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 horizon_pad = (horizon_padding + other_horizon_padding[j]);
 676
 677       Interval collision;
 678       // We need to push elt by at least this much to be outside v_other.
 679       collision[dir] = ((*v_skyline)[-dir].distance (v_other[dir], horizon_pad)
 680                         + padding) * dir;
 681       // We need to pull elt by at least this much to be inside v_other.
 682       collision[-dir] = ((*v_skyline)[dir].distance (v_other[-dir], horizon_pad)
 683                          + other_padding[j]) * -dir;
 684
 685       forbidden_intervals.push_back (collision);
 686     }
 687
 688   Interval_set allowed_shifts
 689     = Interval_set::interval_union (forbidden_intervals).complement ();
 690   Real move = allowed_shifts.nearest_point (0, dir);
 691   v_skyline->raise (move);
 692   elt->translate_axis (move, Y_AXIS);
 693 }
 694
 695 SCM
 696 valid_outside_staff_placement_directive (Grob *me)
 697 {
 698   SCM directive = me->get_property ("outside-staff-placement-directive");
 699
 700   if ((directive == ly_symbol2scm ("left-to-right-greedy"))
 701       || (directive == ly_symbol2scm ("left-to-right-polite"))
 702       || (directive == ly_symbol2scm ("right-to-left-greedy"))
 703       || (directive == ly_symbol2scm ("right-to-left-polite")))
 704     return directive;
 705
 706   me->warning (_f ("\"%s\" is not a valid outside-staff-placement-directive",
 707                    robust_symbol2string (directive, "").c_str ()));
 708
 709   return ly_symbol2scm ("left-to-right-polite");
 710 }
 711
 712 // Shifts the grobs in elements to ensure that they (and any
 713 // connected riders) don't collide with the staff skylines
 714 // or anything in all_X_skylines.  Afterwards, the skylines
 715 // of the grobs in elements will be added to all_v_skylines.
 716 static void
 717 add_grobs_of_one_priority (Grob *me,
 718                            Drul_array<vector<Skyline_pair> > *all_v_skylines,
 719                            Drul_array<vector<Real> > *all_paddings,
 720                            Drul_array<vector<Real> > *all_horizon_paddings,
 721                            vector<Grob *> elements,
 722                            Grob *x_common,
 723                            Grob *y_common,
 724                            multimap<Grob *, Grob *> const &riders)
 725 {
 726
 727   SCM directive
 728     = valid_outside_staff_placement_directive (me);
 729
 730   bool l2r = ((directive == ly_symbol2scm ("left-to-right-greedy"))
 731               || (directive == ly_symbol2scm ("left-to-right-polite")));
 732
 733   bool polite = ((directive == ly_symbol2scm ("left-to-right-polite"))
 734                  || (directive == ly_symbol2scm ("right-to-left-polite")));
 735
 736   vector<Box> boxes;
 737   vector<Skyline_pair> skylines_to_merge;
 738
 739   // We want to avoid situations like this:
 740   //           still more text
 741   //      more text
 742   //   text
 743   //   -------------------
 744   //   staff
 745   //   -------------------
 746
 747   // The point is that "still more text" should be positioned under
 748   // "more text".  In order to achieve this, we place the grobs in several
 749   // passes.  We keep track of the right-most horizontal position that has been
 750   // affected by the current pass so far (actually we keep track of 2
 751   // positions, one for above the staff, one for below).
 752
 753   // In each pass, we loop through the unplaced grobs from left to right.
 754   // If the grob doesn't overlap the right-most affected position, we place it
 755   // (and then update the right-most affected position to point to the right
 756   // edge of the just-placed grob).  Otherwise, we skip it until the next pass.
 757   while (!elements.empty ())
 758     {
 759       Drul_array<Real> last_end (-infinity_f, -infinity_f);
 760       vector<Grob *> skipped_elements;
 761       for (vsize i = l2r ? 0 : elements.size ();
 762            l2r ? i < elements.size () : i--;
 763            l2r ? i++ : 0)
 764         {
 765           Grob *elt = elements[i];
 766           Real padding
 767             = robust_scm2double (elt->get_property ("outside-staff-padding"),
 768                                  Axis_group_interface::get_default_outside_staff_padding ());
 769           Real horizon_padding
 770             = robust_scm2double (elt->get_property ("outside-staff-horizontal-padding"), 0.0);
 771           Interval x_extent = elt->extent (x_common, X_AXIS);
 772           x_extent.widen (horizon_padding);
 773
 774           Direction dir = get_grob_direction (elt);
 775           if (dir == CENTER)
 776             {
 777               warning (_ ("an outside-staff object should have a direction, defaulting to up"));
 778               dir = UP;
 779             }
 780
 781           if (x_extent[LEFT] <= last_end[dir] && polite)
 782             {
 783               skipped_elements.push_back (elt);
 784               continue;
 785             }
 786           last_end[dir] = x_extent[RIGHT];
 787
 788           Skyline_pair *v_orig = Skyline_pair::unsmob (elt->get_property ("vertical-skylines"));
 789           if (v_orig->is_empty ())
 790             continue;
 791
 792           // Find the riders associated with this grob, and merge their
 793           // skylines with elt's skyline.
 794           typedef multimap<Grob *, Grob *>::const_iterator GrobMapIterator;
 795           pair<GrobMapIterator, GrobMapIterator> range = riders.equal_range (elt);
 796           vector<Skyline_pair> rider_v_skylines;
 797           for (GrobMapIterator j = range.first; j != range.second; j++)
 798             {
 799               Grob *rider = j->second;
 800               Skyline_pair *v_rider = Skyline_pair::unsmob (rider->get_property ("vertical-skylines"));
 801               if (v_rider)
 802                 {
 803                   Skyline_pair copy (*v_rider);
 804                   copy.shift (rider->relative_coordinate (x_common, X_AXIS));
 805                   copy.raise (rider->relative_coordinate (y_common, Y_AXIS));
 806                   rider_v_skylines.push_back (copy);
 807                 }
 808             }
 809           Skyline_pair v_skylines (*v_orig);
 810           v_skylines.shift (elt->relative_coordinate (x_common, X_AXIS));
 811           v_skylines.raise (elt->relative_coordinate (y_common, Y_AXIS));
 812           v_skylines.merge (Skyline_pair (rider_v_skylines));
 813
 814           avoid_outside_staff_collisions (elt,
 815                                           &v_skylines,
 816                                           padding,
 817                                           horizon_padding,
 818                                           (*all_v_skylines)[dir],
 819                                           (*all_paddings)[dir],
 820                                           (*all_horizon_paddings)[dir],
 821                                           dir);
 822
 823           elt->set_property ("outside-staff-priority", SCM_BOOL_F);
 824           (*all_v_skylines)[dir].push_back (v_skylines);
 825           (*all_paddings)[dir].push_back (padding);
 826           (*all_horizon_paddings)[dir].push_back (horizon_padding);
 827         }
 828       swap (elements, skipped_elements);
 829       skipped_elements.clear ();
 830     }
 831 }
 832
 833 // If the Grob has a Y-ancestor with outside-staff-priority, return it.
 834 // Otherwise, return 0.
 835 Grob *
 836 Axis_group_interface::outside_staff_ancestor (Grob *me)
 837 {
 838   Grob *parent = me->get_parent (Y_AXIS);
 839   if (!parent)
 840     return 0;
 841
 842   if (scm_is_number (parent->get_property ("outside-staff-priority")))
 843     return parent;
 844
 845   return outside_staff_ancestor (parent);
 846 }
 847
 848 // It is tricky to correctly handle skyline placement of cross-staff grobs.
 849 // For example, cross-staff beams cannot be formatted until the distance between
 850 // staves is known and therefore any grobs that depend on the beam cannot be placed
 851 // until the skylines are known. On the other hand, the distance between staves should
 852 // really depend on position of the cross-staff grobs that lie between them.
 853 // Currently, we just leave cross-staff grobs out of the
 854 // skyline altogether, but this could mean that staves are placed so close together
 855 // that there is no room for the cross-staff grob. It also means, of course, that
 856 // we don't get the benefits of skyline placement for cross-staff grobs.
 857 Skyline_pair
 858 Axis_group_interface::skyline_spacing (Grob *me)
 859 {
 860   extract_grob_set (me, Grob_array::unsmob (me->get_object ("vertical-skyline-elements")) ? "vertical-skyline-elements" : "elements", fakeelements);
 861   vector<Grob *> elements (fakeelements);
 862   for (vsize i = 0; i < elements.size (); i++)
 863     /*
 864       As a sanity check, we make sure that no grob with an outside staff priority
 865       has a Y-parent that also has an outside staff priority, which would result
 866       in two movings.
 867     */
 868     if (scm_is_number (elements[i]->get_property ("outside-staff-priority"))
 869         && outside_staff_ancestor (elements[i]))
 870       {
 871         elements[i]->warning ("Cannot set outside-staff-priority for element and elements' Y parent.");
 872         elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
 873       }
 874
 875   /* For grobs with an outside-staff-priority, the sorting function might
 876      call extent and cause suicide. This breaks the contract that is required
 877      for the STL sort function. To avoid this, we make sure that any suicides
 878      are triggered beforehand.
 879   */
 880   for (vsize i = 0; i < elements.size (); i++)
 881     if (scm_is_number (elements[i]->get_property ("outside-staff-priority")))
 882       elements[i]->extent (elements[i], X_AXIS);
 883
 884   vector_sort (elements, staff_priority_less);
 885   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 886   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 887
 888   assert (y_common == me);
 889
 890   // A rider is a grob that is not outside-staff, but has an outside-staff
 891   // ancestor.  In that case, the rider gets moved along with its ancestor.
 892   multimap<Grob *, Grob *> riders;
 893
 894   vsize i = 0;
 895   vector<Skyline_pair> inside_staff_skylines;
 896
 897   for (i = 0; i < elements.size ()
 898        && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
 899     {
 900       Grob *elt = elements[i];
 901       Grob *ancestor = outside_staff_ancestor (elt);
 902       if (!ancestor)
 903         add_interior_skylines (elt, x_common, y_common, &inside_staff_skylines);
 904       if (ancestor)
 905         riders.insert (pair<Grob *, Grob *> (ancestor, elt));
 906     }
 907
 908   Skyline_pair skylines (inside_staff_skylines);
 909
 910   // These are the skylines of all outside-staff grobs
 911   // that have already been processed.  We keep them around in order to
 912   // check them for collisions with the currently active outside-staff grob.
 913   Drul_array<vector<Skyline_pair> > all_v_skylines;
 914   Drul_array<vector<Real> > all_paddings;
 915   Drul_array<vector<Real> > all_horizon_paddings;
 916   for (UP_and_DOWN (d))
 917     {
 918       all_v_skylines[d].push_back (skylines);
 919       all_paddings[d].push_back (0);
 920       all_horizon_paddings[d].push_back (0);
 921     }
 922
 923   for (; i < elements.size (); i++)
 924     {
 925       if (to_boolean (elements[i]->get_property ("cross-staff")))
 926         continue;
 927
 928       // Collect all the outside-staff grobs that have a particular priority.
 929       SCM priority = elements[i]->get_property ("outside-staff-priority");
 930       vector<Grob *> current_elts;
 931       current_elts.push_back (elements[i]);
 932       while (i + 1 < elements.size ()
 933              && scm_is_eq (elements[i + 1]->get_property ("outside-staff-priority"), priority))
 934         {
 935           if (!to_boolean (elements[i + 1]->get_property ("cross-staff")))
 936             current_elts.push_back (elements[i + 1]);
 937           ++i;
 938         }
 939
 940       add_grobs_of_one_priority (me,
 941                                  &all_v_skylines,
 942                                  &all_paddings,
 943                                  &all_horizon_paddings,
 944                                  current_elts,
 945                                  x_common,
 946                                  y_common,
 947                                  riders);
 948     }
 949
 950   // Now everything in all_v_skylines has been shifted appropriately; merge
 951   // them all into skylines to get the complete outline.
 952   Skyline_pair other_skylines (all_v_skylines[UP]);
 953   other_skylines.merge (Skyline_pair (all_v_skylines[DOWN]));
 954   skylines.merge (other_skylines);
 955
 956   // We began by shifting my skyline to be relative to the common refpoint; now
 957   // shift it back.
 958   skylines.shift (-me->relative_coordinate (x_common, X_AXIS));
 959
 960   return skylines;
 961 }
 962
 963 MAKE_SCHEME_CALLBACK (Axis_group_interface, print, 1)
 964 SCM
 965 Axis_group_interface::print (SCM smob)
 966 {
 967   if (!debug_skylines)
 968     return SCM_BOOL_F;
 969
 970   Grob *me = unsmob_grob (smob);
 971   Stencil ret;
 972   if (Skyline_pair *s = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
 973     {
 974       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[UP].to_points (X_AXIS))
 975                        .in_color (255, 0, 255));
 976       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[DOWN].to_points (X_AXIS))
 977                        .in_color (0, 255, 255));
 978     }
 979   return ret.smobbed_copy ();
 980 }
 981
 982 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_staff_staff_spacing, 3)
 983 SCM
 984 Axis_group_interface::calc_pure_staff_staff_spacing (SCM smob, SCM start, SCM end)
 985 {
 986   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 987                                               true,
 988                                               scm_to_int (start),
 989                                               scm_to_int (end));
 990 }
 991
 992 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_staff_staff_spacing, 1)
 993 SCM
 994 Axis_group_interface::calc_staff_staff_spacing (SCM smob)
 995 {
 996   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 997                                               false,
 998                                               0,
 999                                               INT_MAX);
1000 }
1001
1002 SCM
1003 Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure, int start, int end)
1004 {
1005   Grob *grouper = unsmob_grob (me->get_object ("staff-grouper"));
1006
1007   if (grouper)
1008     {
1009       bool within_group = Staff_grouper_interface::maybe_pure_within_group (grouper, me, pure, start, end);
1010       if (within_group)
1011         return grouper->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
1012       else
1013         return grouper->get_maybe_pure_property ("staffgroup-staff-spacing", pure, start, end);
1014     }
1015   return me->get_maybe_pure_property ("default-staff-staff-spacing", pure, start, end);
1016 }
1017
1018 ADD_INTERFACE (Axis_group_interface,
1019                "An object that groups other layout objects.",
1020
1021                // TODO: some of these properties are specific to
1022                // VerticalAxisGroup. We should split off a
1023                // vertical-axis-group-interface.
1024                /* properties */
1025                "adjacent-pure-heights "
1026                "axes "
1027                "bound-alignment-interfaces "
1028                "default-staff-staff-spacing "
1029                "elements "
1030                "max-stretch "
1031                "no-alignment "
1032                "nonstaff-nonstaff-spacing "
1033                "nonstaff-relatedstaff-spacing "
1034                "nonstaff-unrelatedstaff-spacing "
1035                "outside-staff-placement-directive "
1036                "pure-relevant-grobs "
1037                "pure-relevant-items "
1038                "pure-relevant-spanners "
1039                "pure-Y-common "
1040                "staff-affinity "
1041                "staff-grouper "
1042                "staff-staff-spacing "
1043                "system-Y-offset "
1044                "vertical-skyline-elements "
1045                "X-common "
1046                "Y-common "
1047               );