X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finterval-set.cc;h=da857f277c8e3e892effff8438351425138ed420;hb=97a0169312a260933246ab224e4f8b0969871dd5;hp=89e518883085e1bf7051cba084a0f654f8035e00;hpb=58bcc84c9480dae1b21bc24d8396b91fe19e0131;p=lilypond.git

diff --git a/flower/interval-set.cc b/flower/interval-set.cc
index 89e5188830..da857f277c 100644
--- a/flower/interval-set.cc
+++ b/flower/interval-set.cc
@@ -1,9 +1,20 @@
 /*
-  interval-set.hh -- implement Interval_set
+  This file is part of LilyPond, the GNU music typesetter.
 
-  source file of the GNU LilyPond music typesetter
+  Copyright (C) 2004--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
 
-  (c) 2004 Han-Wen Nienhuys <hanwen@xs4all.nl>
+  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"
@@ -11,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)
+{
+  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
 {
-  allowed_regions_.clear ();
-  Interval s;
-  s.set_full ();
-  allowed_regions_.push (s);
+  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 (int 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 (before, i);
-	      i++;
-	    }
-	  allowed_regions_.del (i);
-	  if (!after.is_empty () && after.length () > 0.0)
-	    {
-	      allowed_regions_.insert (after, i);
-	      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;
 }