X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fgrob.cc;h=13dd9c7b393c0c7a5e6a009accb5d30d2a1e06da;hb=d8fce1e1ea2aca1a82e25e47805aef0f70f511b9;hp=d8aeedd5ad2d3f53fff33bfd5761e5ff7e91953a;hpb=a066a93ee74edebb9d238a1bac93c3bc7e8e6e4a;p=lilypond.git

diff --git a/lily/grob.cc b/lily/grob.cc
index d8aeedd5ad..13dd9c7b39 100644
--- a/lily/grob.cc
+++ b/lily/grob.cc
@@ -286,7 +286,7 @@ Grob::translate_axis (Real y, Axis a)
 {
   if (isinf (y) || isnan (y))
     {
-      programming_error (_ ("Infinity or NaN encountered"));
+      programming_error ("Infinity or NaN encountered");
       return;
     }
 
@@ -483,8 +483,6 @@ Grob::pure_height (Grob *refp, int start, int end)
 Interval
 Grob::maybe_pure_extent (Grob *refp, Axis a, bool pure, int start, int end)
 {
-  if (pure && a != Y_AXIS)
-    programming_error ("tried to get pure width");
   return (pure && a == Y_AXIS) ? pure_height (refp, start, end) : extent (refp, a);
 }
 
@@ -515,15 +513,39 @@ Grob::less (Grob *g1, Grob *g2)
 Grob *
 Grob::common_refpoint (Grob const *s, Axis a) const
 {
-  /* I don't like the quadratic aspect of this code, but I see no
-     other way.  The largest chain of parents might be 10 high or so,
-     so it shouldn't be a real issue.  */
-  for (Grob const *c = this; c; c = c->dim_cache_[a].parent_)
-    for (Grob const *d = s; d; d = d->dim_cache_[a].parent_)
-      if (d == c)
-        return (Grob *) d;
 
-  return 0;
+  /* Catching the trivial cases is likely costlier than just running
+     through: one can't avoid going to the respective chain ends
+     anyway.  We might save the second run through when the chain ends
+     differ, but keeping track of the ends makes the loop more costly.
+  */
+
+  int balance = 0;
+  Grob const *c;
+  Grob const *d;
+
+  for (c = this; c; ++balance)
+    c = c->dim_cache_[a].parent_;
+
+  for (d = s; d; --balance)
+    d = d->dim_cache_[a].parent_;
+
+  /* Cut down ancestry to same size */
+
+  for (c = this; balance > 0; --balance)
+    c = c->dim_cache_[a].parent_;
+
+  for (d = s; balance < 0; ++balance)
+    d = d->dim_cache_[a].parent_;
+
+  /* Now find point where our lineages converge */
+  while (c != d)
+    {
+      c = c->dim_cache_[a].parent_;
+      d = d->dim_cache_[a].parent_;
+    }
+
+  return (Grob *) c;
 }
 
 void
@@ -572,6 +594,100 @@ Grob::fixup_refpoint ()
     }
 }
 
+/****************************************************************
+  VERTICAL ORDERING
+****************************************************************/
+
+Grob*
+get_maybe_root_vertical_alignment (Grob *g, Grob *maybe)
+{
+  if (!g)
+    return maybe;
+  if (Align_interface::has_interface (g))
+    return get_maybe_root_vertical_alignment (g->get_parent (Y_AXIS), g);
+  return get_maybe_root_vertical_alignment (g->get_parent (Y_AXIS), maybe);
+
+}
+
+Grob*
+Grob::get_root_vertical_alignment (Grob *g)
+{
+  return get_maybe_root_vertical_alignment (g, 0);
+}
+
+Grob*
+Grob::get_vertical_axis_group (Grob *g)
+{
+  if (!g)
+    return 0;
+  if (Axis_group_interface::has_interface (g)
+      && Align_interface::has_interface (g->get_parent (Y_AXIS)))
+    return g;
+  return get_vertical_axis_group (g->get_parent (Y_AXIS));
+
+}
+
+int
+Grob::get_vertical_axis_group_index (Grob *g)
+{
+  Grob *val = get_root_vertical_alignment (g);
+  if (!val)
+    return -1;
+  Grob *vax = get_vertical_axis_group (g);
+  extract_grob_set (val, "elements", elts);
+  for (vsize i = 0; i < elts.size (); i++)
+    if (elts[i] == vax)
+      return (int) i;
+  g->programming_error ("could not find this grob's vertical axis group in the vertical alignment");
+  return -1;
+}
+
+bool
+Grob::vertical_less (Grob *g1, Grob *g2)
+{
+  return internal_vertical_less (g1, g2, false);
+}
+
+bool
+Grob::pure_vertical_less (Grob *g1, Grob *g2)
+{
+  return internal_vertical_less (g1, g2, true);
+}
+
+bool
+Grob::internal_vertical_less (Grob *g1, Grob *g2, bool pure)
+{
+  Grob *vag = get_root_vertical_alignment (g1);
+  if (!vag)
+    return false;
+  if (!vag)
+    {
+      g1->programming_error ("grob does not belong to a VerticalAlignment?");
+      return false;
+    }
+  Grob *ag1 = get_vertical_axis_group (g1);
+  Grob *ag2 = get_vertical_axis_group (g2);
+
+  extract_grob_set (vag, "elements", elts);
+
+  if (ag1 == ag2 && !pure)
+    {
+      Grob *common = g1->common_refpoint (g2, Y_AXIS);
+      return g1->relative_coordinate (common, Y_AXIS) > g2->relative_coordinate (common, Y_AXIS);
+    }
+
+  for (vsize i = 0; i < elts.size (); i++)
+    {
+      if (elts[i] == ag1)
+        return true;
+      if (elts[i] == ag2)
+        return false;
+    }
+
+  g1->programming_error ("could not place this grob in its axis group");
+  return false;
+}
+
 /****************************************************************
   MESSAGES
 ****************************************************************/