1 /*
2 * Copyright (C) 2012 Carl Hetherington <carl@carlh.net>
3 * Copyright (C) 2013-2016 Paul Davis <paul@linuxaudiosystems.com>
4 * Copyright (C) 2014 Colin Fletcher <colin.m.fletcher@googlemail.com>
5 *
6 * This program 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 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program 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.
15 *
16 * You should have received a copy of the GNU General Public License along
17 * with this program; if not, write to the Free Software Foundation, Inc.,
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19 */
20
21 #ifndef EVORAL_RANGE_HPP
22 #define EVORAL_RANGE_HPP
23
24 #include <list>
25 #include <assert.h>
26 #include <iostream>
27 #include "evoral/visibility.h"
28
29
30
31 namespace Evoral {
32
33 enum /*LIBEVORAL_API*/ OverlapType {
34 OverlapNone, // no overlap
35 OverlapInternal, // the overlap is 100% within the object
36 OverlapStart, // overlap covers start, but ends within
37 OverlapEnd, // overlap begins within and covers end
38 OverlapExternal // overlap extends to (at least) begin+end
39 };
40
41 template<typename T>
coverage(T sa,T ea,T sb,T eb)42 /*LIBEVORAL_API*/ OverlapType coverage (T sa, T ea, T sb, T eb) {
43 /* OverlapType returned reflects how the second (B)
44 * range overlaps the first (A).
45 *
46 * The diagram shows the OverlapType of each possible relative
47 * placement of A and B.
48 *
49 * Notes:
50 * Internal: the start and end points cannot coincide
51 * External: the start and end points can coincide
52 * Start: end points can coincide
53 * End: start points can coincide
54 *
55 * Internal disallows start and end point equality, and thus implies
56 * that there are two disjoint portions of A which do not overlap B.
57 *
58 * A: |---|
59 * B starts before A
60 * B: |-| None
61 * B: |--| Start
62 * B: |----| Start
63 * B: |------| External
64 * B: |--------| External
65 * B starts equal to A
66 * B: |-| Start
67 * B: |---| External
68 * B: |----| External
69 * B starts inside A
70 * B: |-| Internal
71 * B: |--| End
72 * B: |---| End
73 * B starts at end of A
74 * B: |--| End
75 * B starts after A
76 * B: |-| None
77 * A: |---|
78 */
79
80
81 if (sa > ea) {
82 // seems we are sometimes called with negative length ranges
83 return OverlapNone;
84 }
85
86 if (sb > eb) {
87 // seems we are sometimes called with negative length ranges
88 return OverlapNone;
89 }
90
91 if (sb < sa) { // B starts before A
92 if (eb < sa) {
93 return OverlapNone;
94 } else if (eb == sa) {
95 return OverlapStart;
96 } else { // eb > sa
97 if (eb < ea) {
98 return OverlapStart;
99 } else if (eb == ea) {
100 return OverlapExternal;
101 } else {
102 return OverlapExternal;
103 }
104 }
105 } else if (sb == sa) { // B starts equal to A
106 if (eb < ea) {
107 return OverlapStart;
108 } else if (eb == ea) {
109 return OverlapExternal;
110 } else { // eb > ea
111 return OverlapExternal;
112 }
113 } else { // sb > sa
114 if (eb < ea) {
115 return OverlapInternal;
116 } else if (eb == ea) {
117 return OverlapEnd;
118 } else { // eb > ea
119 if (sb < ea) { // B starts inside A
120 return OverlapEnd;
121 } else if (sb == ea) { // B starts at end of A
122 return OverlapEnd;
123 } else { // sb > ea, B starts after A
124 return OverlapNone;
125 }
126 }
127 }
128
129 std::cerr << "unknown overlap type!" << sa << ", " << ea << "; " << sb << ", " << eb << std::endl;
130 assert(!"unknown overlap type!");
131 return OverlapNone;
132 }
133
134 /** Type to describe a time range */
135 template<typename T>
136 struct /*LIBEVORAL_API*/ Range {
RangeRange137 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)
emptyRange140 bool empty() const { return from == to; }
lengthRange141 T length() const { return to - from + 1; }
142
143 /** for a T, return a mapping of it into the range (used for
144 * looping). If the argument is earlier than or equal to the end of
145 * this range, do nothing.
146 */
squishRange147 T squish (T t) const {
148 if (t > to) {
149 t = (from + ((t - from) % length()));
150 }
151 return t;
152 }
153 };
154
155 template<typename T>
156 bool operator== (Range<T> a, Range<T> b) {
157 return a.from == b.from && a.to == b.to;
158 }
159
160 template<typename T>
161 class /*LIBEVORAL_API*/ RangeList {
162 public:
RangeList()163 RangeList () : _dirty (false) {}
164
165 typedef std::list<Range<T> > List;
166
get()167 List const & get () {
168 coalesce ();
169 return _list;
170 }
171
add(Range<T> const & range)172 void add (Range<T> const & range) {
173 _dirty = true;
174 _list.push_back (range);
175 }
176
empty()177 bool empty () const {
178 return _list.empty ();
179 }
180
coalesce()181 void coalesce () {
182 if (!_dirty) {
183 return;
184 }
185
186 restart:
187 for (typename List::iterator i = _list.begin(); i != _list.end(); ++i) {
188 for (typename List::iterator j = _list.begin(); j != _list.end(); ++j) {
189
190 if (i == j) {
191 continue;
192 }
193
194 if (coverage (i->from, i->to, j->from, j->to) != OverlapNone) {
195 i->from = std::min (i->from, j->from);
196 i->to = std::max (i->to, j->to);
197 _list.erase (j);
198 goto restart;
199 }
200 }
201 }
202
203 _dirty = false;
204 }
205
206 private:
207
208 List _list;
209 bool _dirty;
210 };
211
212 /** Type to describe the movement of a time range */
213 template<typename T>
214 struct /*LIBEVORAL_API*/ RangeMove {
RangeMoveRangeMove215 RangeMove (T f, double l, T t) : from (f), length (l), to (t) {}
216 T from; ///< start of the range
217 double length; ///< length of the range
218 T to; ///< new start of the range
219 };
220
221 /** Subtract the ranges in `sub' from that in `range',
222 * returning the result.
223 */
224 template<typename T>
subtract(Range<T> range,RangeList<T> sub)225 RangeList<T> subtract (Range<T> range, RangeList<T> sub)
226 {
227 /* Start with the input range */
228 RangeList<T> result;
229 result.add (range);
230
231 if (sub.empty () || range.empty()) {
232 return result;
233 }
234
235 typename RangeList<T>::List s = sub.get ();
236
237 /* The basic idea here is to keep a list of the result ranges, and subtract
238 the bits of `sub' from them one by one.
239 */
240
241 for (typename RangeList<T>::List::const_iterator i = s.begin(); i != s.end(); ++i) {
242
243 /* Here's where we'll put the new current result after subtracting *i from it */
244 RangeList<T> new_result;
245
246 typename RangeList<T>::List r = result.get ();
247
248 /* Work on all parts of the current result using this range *i */
249 for (typename RangeList<T>::List::const_iterator j = r.begin(); j != r.end(); ++j) {
250
251 switch (coverage (j->from, j->to, i->from, i->to)) {
252 case OverlapNone:
253 /* The thing we're subtracting (*i) does not overlap this bit of the result (*j),
254 so pass it through.
255 */
256 new_result.add (*j);
257 break;
258 case OverlapInternal:
259 /* Internal overlap of the thing we're subtracting (*i) from this bit of the result,
260 so we should end up with two bits of (*j) left over, from the start of (*j) to
261 the start of (*i), and from the end of (*i) to the end of (*j).
262 */
263 assert (j->from < i->from);
264 assert (j->to > i->to);
265 new_result.add (Range<T> (j->from, i->from - 1));
266 new_result.add (Range<T> (i->to + 1, j->to));
267 break;
268 case OverlapStart:
269 /* The bit we're subtracting (*i) overlaps the start of the bit of the result (*j),
270 * so we keep only the part of of (*j) from after the end of (*i)
271 */
272 assert (i->to < j->to);
273 new_result.add (Range<T> (i->to + 1, j->to));
274 break;
275 case OverlapEnd:
276 /* The bit we're subtracting (*i) overlaps the end of the bit of the result (*j),
277 * so we keep only the part of of (*j) from before the start of (*i)
278 */
279 assert (j->from < i->from);
280 new_result.add (Range<T> (j->from, i->from - 1));
281 break;
282 case OverlapExternal:
283 /* total overlap of the bit we're subtracting with the result bit, so the
284 result bit is completely removed; do nothing */
285 break;
286 }
287 }
288
289 new_result.coalesce ();
290 result = new_result;
291 }
292
293 return result;
294 }
295
296 }
297
298 #endif
299