2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2004--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
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.
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.
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/>.
20 #include "interval-set.hh"
25 A union of intervals in the real line.
27 This class gives good performance for finding the union of
28 a collection of intervals (n log n) and for testing if a point
29 belongs to the union (log n). It does not give an efficient way to
30 update the set (ie. by adding more intervals); to do this
31 efficiently would require a self-balancing tree, and it would not
32 be currently useful in lilypond anyway.
35 Interval_set::Interval_set ()
40 Interval_set::interval_union (vector<Interval> ivs)
42 vector_sort (ivs, Interval::left_less);
49 ret.intervals_.push_back (ivs.front ());
51 // Go over the intervals from left to right. If the current interval
52 // overlaps with the last one, merge them. Otherwise, append the
53 // current interval to the list.
54 for (vsize i = 1; i < ivs.size (); ++i)
57 Interval &last = ret.intervals_.back ();
59 if (last[RIGHT] >= iv[LEFT])
60 // overlapping intervals: merge them
61 last[RIGHT] = std::max (last[RIGHT], iv[RIGHT]);
62 else if (!iv.is_empty ())
63 ret.intervals_.push_back (iv);
69 // Returns an iterator pointing to the first interval whose left
70 // endpoint is at least x. That interval may or may not contain x.
71 vector<Interval>::const_iterator
72 Interval_set::upper_bound (Real x) const
75 return std::upper_bound (intervals_.begin (), intervals_.end (), xx, Interval::left_less);
79 Interval_set::nearest_point (Real x, Direction d) const
81 Real left = -infinity_f; // The closest point to the left of x.
82 Real right = infinity_f; // The closest point to the right of x.
84 vector<Interval>::const_iterator i = upper_bound (x);
85 if (i != intervals_.end ())
88 if (i != intervals_.begin ())
90 Interval left_iv = *(i - 1);
91 // left_iv[LEFT] is guaranteed to be less than x. So if
92 // left_iv[RIGHT] >= x then left_iv contains x, which must then
93 // be the nearest point to x.
94 if (left_iv[RIGHT] >= x)
97 left = left_iv[RIGHT];
105 return (right - x) < (x - left) ? right : left;
109 Interval_set::complement () const
113 if (intervals_.empty ())
115 ret.intervals_.push_back (Interval (-infinity_f, infinity_f));
119 if (intervals_[0][LEFT] > -infinity_f)
120 ret.intervals_.push_back (Interval (-infinity_f, intervals_[0][LEFT]));
122 for (vsize i = 1; i < intervals_.size (); ++i)
123 ret.intervals_.push_back (Interval (intervals_[i - 1][RIGHT], intervals_[i][LEFT]));
125 if (intervals_.back ()[RIGHT] < infinity_f)
126 ret.intervals_.push_back (Interval (intervals_.back ()[RIGHT], infinity_f));