1 /* This file is part of Evoral.
2 * Copyright (C) 2008 David Robillard <http://drobilla.net>
3 * Copyright (C) 2000-2008 Paul Davis
5 * Evoral is free software; you can redistribute it and/or modify it under the
6 * terms of the GNU General Public License as published by the Free Software
7 * Foundation; either version 2 of the License, or (at your option) any later
10 * Evoral is distributed in the hope that it will be useful, but WITHOUT ANY
11 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details.
14 * You should have received a copy of the GNU General Public License along
15 * with this program; if not, write to the Free Software Foundation, Inc.,
16 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 #ifndef EVORAL_RANGE_HPP
20 #define EVORAL_RANGE_HPP
25 #include "evoral/visibility.h"
31 enum /*LIBEVORAL_API*/ OverlapType {
32 OverlapNone, // no overlap
33 OverlapInternal, // the overlap is 100% within the object
34 OverlapStart, // overlap covers start, but ends within
35 OverlapEnd, // overlap begins within and covers end
36 OverlapExternal // overlap extends to (at least) begin+end
40 /*LIBEVORAL_API*/ OverlapType coverage (T sa, T ea, T sb, T eb) {
41 /* OverlapType returned reflects how the second (B)
42 * range overlaps the first (A).
44 * The diagram shows the OverlapType of each possible relative
45 * placement of A and B.
48 * Internal: the start and end points cannot coincide
49 * External: the start and end points can coincide
50 * Start: end points can coincide
51 * End: start points can coincide
53 * Internal disallows start and end point equality, and thus implies
54 * that there are two disjoint portions of A which do not overlap B.
61 * B: |------| External
62 * B: |--------| External
71 * B starts at end of A
80 // seems we are sometimes called with negative length ranges
81 std::cerr << "a - start after end: " << sa << ", " << ea << std::endl;
86 // seems we are sometimes called with negative length ranges
87 std::cerr << "b - start after end: " << sb << ", " << eb << std::endl;
91 if (sb < sa) { // B starts before A
94 } else if (eb == sa) {
99 } else if (eb == ea) {
100 return OverlapExternal;
102 return OverlapExternal;
105 } else if (sb == sa) { // B starts equal to A
108 } else if (eb == ea) {
109 return OverlapExternal;
111 return OverlapExternal;
115 return OverlapInternal;
116 } else if (eb == ea) {
119 if (sb < ea) { // B starts inside A
121 } else if (sb == ea) { // B starts at end of A
123 } else { // sb > ea, B starts after A
129 std::cerr << "unknown overlap type!" << sa << ", " << ea << "; " << sb << ", " << eb << std::endl;
130 assert(!"unknown overlap type!");
134 /** Type to describe a time range */
136 struct /*LIBEVORAL_API*/ Range {
137 Range (T f, T t) : from (f), to (t) {}
138 T from; ///< start of the range
139 T to; ///< end of the range (inclusive: to lies inside the range)
143 bool operator== (Range<T> a, Range<T> b) {
144 return a.from == b.from && a.to == b.to;
148 class /*LIBEVORAL_API*/ RangeList {
150 RangeList () : _dirty (false) {}
152 typedef std::list<Range<T> > List;
154 List const & get () {
159 void add (Range<T> const & range) {
161 _list.push_back (range);
164 bool empty () const {
165 return _list.empty ();
174 for (typename List::iterator i = _list.begin(); i != _list.end(); ++i) {
175 for (typename List::iterator j = _list.begin(); j != _list.end(); ++j) {
181 if (coverage (i->from, i->to, j->from, j->to) != OverlapNone) {
182 i->from = std::min (i->from, j->from);
183 i->to = std::max (i->to, j->to);
199 /** Type to describe the movement of a time range */
201 struct /*LIBEVORAL_API*/ RangeMove {
202 RangeMove (T f, double l, T t) : from (f), length (l), to (t) {}
203 T from; ///< start of the range
204 double length; ///< length of the range
205 T to; ///< new start of the range
208 /** Subtract the ranges in `sub' from that in `range',
209 * returning the result.
212 RangeList<T> subtract (Range<T> range, RangeList<T> sub)
214 /* Start with the input range */
222 typename RangeList<T>::List s = sub.get ();
224 /* The basic idea here is to keep a list of the result ranges, and subtract
225 the bits of `sub' from them one by one.
228 for (typename RangeList<T>::List::const_iterator i = s.begin(); i != s.end(); ++i) {
230 /* Here's where we'll put the new current result after subtracting *i from it */
231 RangeList<T> new_result;
233 typename RangeList<T>::List r = result.get ();
235 /* Work on all parts of the current result using this range *i */
236 for (typename RangeList<T>::List::const_iterator j = r.begin(); j != r.end(); ++j) {
238 switch (coverage (j->from, j->to, i->from, i->to)) {
240 /* The thing we're subtracting (*i) does not overlap this bit of the result (*j),
245 case OverlapInternal:
246 /* Internal overlap of the thing we're subtracting (*i) from this bit of the result,
247 so we should end up with two bits of (*j) left over, from the start of (*j) to
248 the start of (*i), and from the end of (*i) to the end of (*j).
250 assert (j->from < i->from);
251 assert (j->to > i->to);
252 new_result.add (Range<T> (j->from, i->from - 1));
253 new_result.add (Range<T> (i->to + 1, j->to));
256 /* The bit we're subtracting (*i) overlaps the start of the bit of the result (*j),
257 * so we keep only the part of of (*j) from after the end of (*i)
259 assert (i->to < j->to);
260 new_result.add (Range<T> (i->to + 1, j->to));
263 /* The bit we're subtracting (*i) overlaps the end of the bit of the result (*j),
264 * so we keep only the part of of (*j) from before the start of (*i)
266 assert (j->from < i->from);
267 new_result.add (Range<T> (j->from, i->from - 1));
269 case OverlapExternal:
270 /* total overlap of the bit we're subtracting with the result bit, so the
271 result bit is completely removed; do nothing */
276 new_result.coalesce ();