Improvements in vertical skyline approximations (issue 2148).

The file stencil-integral.cc provides a suite of functions that
traverse a stencil and do linear approximations of its components.
These are then turned into boxes that are passed to the Skyline
constructor. This approximation is used for several vertical skylines
including those of VerticalAxisGroup and System. As a result of these
more accurate approximations, vertical spacing is more snug between
grobs.

Additionally, in axis-group-interface.cc, skylines of grobs are no
longer compared to a monolithic axis-group skyline but rather all
of the component skylines of the axis-group, allowing grobs to
be fit under other ones if there is space instead of always shifted over.

Two new python scripts allow to visualize the position of skylines.

All other changes provide functions that allow for better debugging
of Skylines, better approximations of grobs via skylines, and changes
to the measurement of distance between grobs via the new Skyline API.

This results in a significant time increase in score compilation for
objects with complex skylines such as all text grobs.  For orchestral
scores, the increase is not as steep.

4 files changed, 213 insertions, 51 deletions

diff --git a/flower/include/interval-set.hh b/flower/include/interval-set.hh
index b0acda6509..6ea7b43173 100644
--- a/flower/include/interval-set.hh
+++ b/flower/include/interval-set.hh
@@ -23,20 +23,20 @@
 #include "std-vector.hh"
 #include "interval.hh"
 
-/*
-  A union of intervals in the real line.
-
-  Abysmal performance (quadratic) for large N, hopefully we don't have
-  that large N. In any case, this should probably be rewritten to use
-  a balanced tree.
-*/
-struct Interval_set
+class Interval_set
 {
-  vector<Interval> allowed_regions_;
-
+public:
   Interval_set ();
-  void set_full ();
-  void remove_interval (Interval rm);
+
+  static Interval_set interval_union (vector<Interval>);
+
+  vector<Interval> const &intervals () const { return intervals_; }
+  vector<Interval>::const_iterator upper_bound (Real x) const;
+  Real nearest_point (Real x, Direction dir = CENTER) const;
+  Interval_set complement () const;
+
+private:
+  vector<Interval> intervals_;
 };
 
 #endif /* INTERVAL_SET_HH */
diff --git a/flower/include/yaffut.hh b/flower/include/yaffut.hh
index 8b10d23aa5..148d1a8801 100644
--- a/flower/include/yaffut.hh
+++ b/flower/include/yaffut.hh
@@ -21,6 +21,7 @@
 #include <memory>
 #include <sstream>
 #include <stdexcept>
+#include <unistd.h>
 
 #define YAFFUT_STRINGIZE(x) YAFFUT_STRINGIZE_(x)
 #define YAFFUT_STRINGIZE_(x) #x
diff --git a/flower/interval-set.cc b/flower/interval-set.cc
index 84bde76a9c..f1aaea59fc 100644
--- a/flower/interval-set.cc
+++ b/flower/interval-set.cc
@@ -22,55 +22,106 @@
 /*
   A union of intervals in the real line.
 
-  Abysmal performance (quadratic) for large N, hopefully we don't have
-  that large N. In any case, this should probably be rewritten to use
-  a balanced tree.
+  This class gives good performance for finding the union of
+  a collection of intervals (n log n) and for testing if a point
+  belongs to the union (log n).  It does not give an efficient way to
+  update the set (ie. by adding more intervals); to do this
+  efficiently would require a self-balancing tree, and it would not
+  be currently useful in lilypond anyway.
 */
 
 Interval_set::Interval_set ()
 {
-  set_full ();
 }
 
-void
-Interval_set::set_full ()
+Interval_set
+Interval_set::interval_union (vector<Interval> ivs)
 {
-  allowed_regions_.clear ();
-  Interval s;
-  s.set_full ();
-  allowed_regions_.push_back (s);
+  vector_sort (ivs, Interval::left_less);
+
+  Interval_set ret;
+
+  if (ivs.empty ())
+    return ret;
+
+  ret.intervals_.push_back (ivs.front ());
+
+  // Go over the intervals from left to right.  If the current interval
+  // overlaps with the last one, merge them.  Otherwise, append the
+  // current interval to the list.
+  for (vsize i = 1; i < ivs.size (); ++i)
+    {
+      Interval iv = ivs[i];
+      Interval &last = ret.intervals_.back ();
+
+      if (last[RIGHT] >= iv[LEFT])
+        // overlapping intervals: merge them
+        last[RIGHT] = max (last[RIGHT], iv[RIGHT]);
+      else if (!iv.is_empty ())
+        ret.intervals_.push_back (iv);
+    }
+
+  return ret;
+}
+
+// Returns an iterator pointing to the first interval whose left
+// endpoint is at least x.  That interval may or may not contain x.
+vector<Interval>::const_iterator
+Interval_set::upper_bound (Real x) const
+{
+  Interval xx (x, x);
+  return std::upper_bound (intervals_.begin (), intervals_.end (), xx, Interval::left_less);
 }
 
-void
-Interval_set::remove_interval (Interval rm)
+Real
+Interval_set::nearest_point (Real x, Direction d) const
 {
-  for (vsize i = 0; i < allowed_regions_.size ();)
+  Real left = -infinity_f; // The closest point to the left of x.
+  Real right = infinity_f; // The closest point to the right of x.
+
+  vector<Interval>::const_iterator i = upper_bound (x);
+  if (i != intervals_.end ())
+    right = (*i)[LEFT];
+
+  if (i != intervals_.begin ())
     {
-      Interval s = rm;
-
-      s.intersect (allowed_regions_[i]);
-
-      if (!s.is_empty ())
-        {
-          Interval before = allowed_regions_[i];
-          Interval after = allowed_regions_[i];
-
-          before[RIGHT] = s[LEFT];
-          after[LEFT] = s[RIGHT];
-
-          if (!before.is_empty () && before.length () > 0.0)
-            {
-              allowed_regions_.insert (allowed_regions_.begin () + (long)i, before);
-              i++;
-            }
-          allowed_regions_.erase (allowed_regions_.begin () + (long)i);
-          if (!after.is_empty () && after.length () > 0.0)
-            {
-              allowed_regions_.insert (allowed_regions_.begin () + (long)i, after);
-              i++;
-            }
-        }
-      else
-        i++;
+      Interval left_iv = *(i - 1);
+      // left_iv[LEFT] is guaranteed to be less than x. So if
+      // left_iv[RIGHT] >= x then left_iv contains x, which must then
+      // be the nearest point to x.
+      if (left_iv[RIGHT] >= x)
+        return x;
+
+      left = left_iv[RIGHT];
+    }
+
+  if (d == RIGHT)
+    return right;
+  if (d == LEFT)
+    return left;
+  else
+    return (right - x) < (x - left) ? right : left;
+}
+
+Interval_set
+Interval_set::complement () const
+{
+  Interval_set ret;
+
+  if (intervals_.empty ())
+    {
+      ret.intervals_.push_back (Interval (-infinity_f, infinity_f));
+      return ret;
     }
+
+  if (intervals_[0][LEFT] > -infinity_f)
+    ret.intervals_.push_back (Interval (-infinity_f, intervals_[0][LEFT]));
+
+  for (vsize i = 1; i < intervals_.size (); ++i)
+    ret.intervals_.push_back (Interval (intervals_[i - 1][RIGHT], intervals_[i][LEFT]));
+
+  if (intervals_.back ()[RIGHT] < infinity_f)
+    ret.intervals_.push_back (Interval (intervals_.back ()[RIGHT], infinity_f));
+
+  return ret;
 }
diff --git a/flower/test-interval-set.cc b/flower/test-interval-set.cc
new file mode 100644
index 0000000000..5b4d1f637e
--- /dev/null
+++ b/flower/test-interval-set.cc
@@ -0,0 +1,110 @@
+/*
+  This file is part of LilyPond, the GNU music typesetter.
+
+  Copyright (C) 2012 Joe Neeman <joeneeman@gmail.com>
+
+  LilyPond is free software: you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation, either version 3 of the License, or
+  (at your option) any later version.
+
+  LilyPond is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "interval-set.hh"
+
+#include "yaffut.hh"
+
+using namespace std;
+
+FUNC (interval_set_union)
+{
+  vector<Interval> ivs;
+
+  // Overlapping intervals.
+  ivs.push_back (Interval (-1, 1));
+  ivs.push_back (Interval (0, 3));
+  ivs.push_back (Interval (1, 2));
+  Interval_set result = Interval_set::interval_union (ivs);
+  EQUAL (result.intervals ().size (), 1);
+  // Compare intervals using to_string, since yaffut doesn't know how to compare intervals.
+  EQUAL (result.intervals ()[0].to_string (), Interval (-1, 3).to_string ());
+
+  // Non-overlapping intervals.
+  ivs.push_back (Interval (-5, -4));
+  result = Interval_set::interval_union (ivs);
+  EQUAL (result.intervals ().size (), 2);
+  EQUAL (result.intervals ()[0].to_string (), Interval (-5, -4).to_string ());
+  EQUAL (result.intervals ()[1].to_string (), Interval (-1, 3).to_string ());
+
+  // Infinite intervals.
+  ivs.push_back (Interval (-infinity_f, -4));
+  result = Interval_set::interval_union (ivs);
+  EQUAL (result.intervals ().size (), 2);
+  EQUAL (result.intervals ()[0].to_string (), Interval (-infinity_f, -4).to_string ());
+  EQUAL (result.intervals ()[1].to_string (), Interval (-1, 3).to_string ());
+
+  // Empty intervals.
+  ivs.push_back (Interval (infinity_f, -infinity_f));
+  result = Interval_set::interval_union (ivs);
+  EQUAL (result.intervals ().size (), 2);
+}
+
+FUNC (interval_set_nearest_point)
+{
+  vector<Interval> ivs;
+
+  ivs.push_back (Interval (-3, -1));
+  ivs.push_back (Interval (1, 3));
+  Interval_set set = Interval_set::interval_union (ivs);
+
+  // If the point is in the set, direction does not matter.
+  EQUAL (set.nearest_point (-2, UP), -2);
+  EQUAL (set.nearest_point (-2, DOWN), -2);
+  EQUAL (set.nearest_point (-2, CENTER), -2);
+
+  // If the point is not in the set, direction does matter.
+  EQUAL (set.nearest_point (-0.5, UP), 1);
+  EQUAL (set.nearest_point (-0.5, DOWN), -1);
+  EQUAL (set.nearest_point (-0.5, CENTER), -1);
+  EQUAL (set.nearest_point (0.5, CENTER), 1);
+
+  // The return value can be +- infinity.
+  EQUAL (set.nearest_point (5, UP), infinity_f);
+  EQUAL (set.nearest_point (5, DOWN), 3);
+  EQUAL (set.nearest_point (-5, DOWN), -infinity_f);
+  EQUAL (set.nearest_point (-5, UP), -3);
+}
+
+FUNC (interval_set_complement)
+{
+  vector<Interval> ivs;
+
+  ivs.push_back (Interval (-3, -1));
+  ivs.push_back (Interval (1, 3));
+  Interval_set set = Interval_set::interval_union (ivs).complement ();
+  EQUAL (set.intervals ().size (), 3);
+  EQUAL (set.intervals ()[0].to_string (), Interval (-infinity_f, -3).to_string ());
+  EQUAL (set.intervals ()[1].to_string (), Interval (-1, 1).to_string ());
+  EQUAL (set.intervals ()[2].to_string (), Interval (3, infinity_f).to_string ());
+
+  // Half-infinite sets are handled correctly.
+  ivs.push_back (Interval (-infinity_f, -2));
+  set = Interval_set::interval_union (ivs).complement ();
+  EQUAL (set.intervals ().size (), 2);
+  EQUAL (set.intervals ()[0].to_string (), Interval (-1, 1).to_string ());
+  EQUAL (set.intervals ()[1].to_string (), Interval (3, infinity_f).to_string ());
+
+  // Full and empty sets are handled correctly.
+  set = Interval_set ().complement ();
+  EQUAL (set.intervals ().size (), 1);
+  EQUAL (set.intervals ()[0].to_string (), Interval (-infinity_f, infinity_f).to_string ());
+  set = set.complement ();
+  EQUAL (set.intervals ().size (), 0);
+}