Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(59)

Unified Diff: flower/interval-set.cc

Issue 5626052: Gets vertical skylines from grob stencils (Closed)
Patch Set: Run astyle on c++ files Created 11 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: flower/interval-set.cc
diff --git a/flower/interval-set.cc b/flower/interval-set.cc
index 84bde76a9cfe2a00d9cba2879d2f74f5362249e9..f1aaea59fcc67fbc74c0fbd92e3b326c14abd898 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;
}
« no previous file with comments | « flower/include/yaffut.hh ('k') | flower/test-interval-set.cc » ('j') | lily/skyline.cc » ('J')

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b