libs/evoral/evoral/Range.hpp

   1 /* This file is part of Evoral.
   2  * Copyright (C) 2008 David Robillard <http://drobilla.net>
   3  * Copyright (C) 2000-2008 Paul Davis
   4  *
   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
   8  * version.
   9  *
  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.
  13  *
  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
  17  */
  18
  19 #ifndef EVORAL_RANGE_HPP
  20 #define EVORAL_RANGE_HPP
  21
  22 #include <list>
  23 #include <assert.h>
  24 #include <iostream>
  25 #include "evoral/visibility.h"
  26
  27
  28
  29 /*
  30
  31 a:   |---|
  32 b starts before:
  33   |-|
  34   |--|
  35   |----|
  36   |------|
  37   |--------|
  38 a:   |---|
  39 b starts equal:
  40      |-|
  41      |---|
  42      |----|
  43 a:   |---|
  44 b starts inside:
  45       |-|
  46       |--|
  47       |---|
  48 a:   |---|
  49 b starts at end:
  50          |--|
  51 a:   |---|
  52 b starts after:
  53           |-|
  54 */
  55
  56 namespace Evoral {
  57
  58 enum /*LIBEVORAL_API*/ OverlapType {
  59         OverlapNone,      // no overlap
  60         OverlapInternal,  // the overlap is 100% with the object
  61         OverlapStart,     // overlap covers start, but ends within
  62         OverlapEnd,       // overlap begins within and covers end
  63         OverlapExternal   // overlap extends to (at least) begin+end
  64 };
  65
  66 template<typename T>
  67 /*LIBEVORAL_API*/ OverlapType coverage (T sa, T ea, T sb, T eb) {
  68         /* OverlapType returned reflects how the second (B)
  69            range overlaps the first (A).
  70
  71            The diagrams show various relative placements
  72            of A and B for each OverlapType.
  73
  74            Notes:
  75               Internal: the start and end points cannot coincide
  76               External: the start and end points can coincide
  77               Start: end points can coincide
  78               End: start points can coincide
  79
  80            Internal disallows start and end point equality, and thus implies
  81            that there are two disjoint portions of A which do not overlap B.
  82         */
  83
  84         // assert(sa <= ea); // seems we are sometimes called with 0-length ranges
  85         if (sa > ea) {
  86                 std::cerr << "a - start after end: " << sa << ", " << ea << std::endl;
  87                 return OverlapNone;
  88         }
  89
  90         // assert(sb <= eb);
  91         if (sb > eb) {
  92                 std::cerr << "b - start after end: " << sb << ", " << eb << std::endl;
  93                 return OverlapNone;
  94         }
  95
  96         if (sb < sa) {
  97                 if (eb < sa) {
  98                         return OverlapNone;
  99                 } else if (eb == sa) {
 100                         return OverlapStart;
 101                 } else {
 102                         if (eb < ea) {
 103                                 return OverlapStart;
 104                         } else if (eb == ea) {
 105                                 return OverlapExternal;
 106                         } else {
 107                                 return OverlapExternal;
 108                         }
 109                 }
 110         } else if (sb == sa) {
 111                 if (eb < ea) {
 112                         return OverlapStart;
 113                 } else if (eb == ea) {
 114                         return OverlapExternal;
 115                 } else { // eb > ea
 116                         return OverlapExternal;
 117                 }
 118         } else { // sb > sa
 119                 if (eb < ea) {
 120                         return OverlapInternal;
 121                 } else if (eb == ea) {
 122                         return OverlapEnd;
 123                 } else { // eb > ea
 124                         if (sb < ea) {
 125                                 return OverlapEnd;
 126                         } else if (sb == ea) {
 127                                 return OverlapEnd;
 128                         } else {
 129                                 return OverlapNone;
 130                         }
 131                 }
 132         }
 133
 134
 135         std::cerr << "unknown overlap type!" << sa << ", " << ea << "; " << sb << ", " << eb << std::endl;
 136         // assert(!"unknown overlap type!");
 137         return OverlapNone;
 138
 139 #if 0
 140         /*
 141              |--------------------|   A
 142                   |------|            B
 143                 |-----------------|   B
 144
 145              "B is internal to A"
 146         */
 147
 148         if ((sb > sa) && (eb < ea)) {
 149                 return OverlapInternal;
 150         }
 151
 152         /*
 153              |--------------------|    A
 154            --------------------------  B
 155              |-----------------------  B
 156             ----------------------|    B
 157              |--------------------|    B
 158
 159            "B overlaps all of A"
 160         */
 161         if ((sb <= sa) && (eb >= ea)) {
 162                 return OverlapExternal;
 163         }
 164
 165         /*
 166              |--------------------|   A
 167            ----|                      B
 168            -----------------------|   B
 169            --|                        B
 170
 171              "B overlaps the start of A"
 172         */
 173
 174         if ((sb <= sa) && (eb >= sa) && (eb <= ea)) {
 175                 return OverlapStart;
 176         }
 177         /*
 178              |---------------------|  A
 179                    |----------------- B
 180              |----------------------- B
 181                                    |- B
 182
 183             "B overlaps the end of A"
 184         */
 185         if ((sb > sa) && (sb < ea) && (eb >= ea)) {
 186                 return OverlapEnd;
 187         }
 188
 189         // assert(eb < sa || sb > ea);
 190         return OverlapNone;
 191 #endif
 192 }
 193
 194 /** Type to describe a time range */
 195 template<typename T>
 196 struct /*LIBEVORAL_API*/ Range {
 197         Range (T f, T t) : from (f), to (t) {}
 198         T from; ///< start of the range
 199         T to;   ///< end of the range
 200 };
 201
 202 template<typename T>
 203 bool operator== (Range<T> a, Range<T> b) {
 204         return a.from == b.from && a.to == b.to;
 205 }
 206
 207 template<typename T>
 208 class /*LIBEVORAL_API*/ RangeList {
 209 public:
 210         RangeList () : _dirty (false) {}
 211
 212         typedef std::list<Range<T> > List;
 213
 214         List const & get () {
 215                 coalesce ();
 216                 return _list;
 217         }
 218
 219         void add (Range<T> const & range) {
 220                 _dirty = true;
 221                 _list.push_back (range);
 222         }
 223
 224         bool empty () const {
 225                 return _list.empty ();
 226         }
 227
 228         void coalesce () {
 229                 if (!_dirty) {
 230                         return;
 231                 }
 232
 233         restart:
 234                 for (typename List::iterator i = _list.begin(); i != _list.end(); ++i) {
 235                         for (typename List::iterator j = _list.begin(); j != _list.end(); ++j) {
 236
 237                                 if (i == j) {
 238                                         continue;
 239                                 }
 240
 241                                 if (coverage (i->from, i->to, j->from, j->to) != OverlapNone) {
 242                                         i->from = std::min (i->from, j->from);
 243                                         i->to = std::max (i->to, j->to);
 244                                         _list.erase (j);
 245                                         goto restart;
 246                                 }
 247                         }
 248                 }
 249
 250                 _dirty = false;
 251         }
 252
 253 private:
 254
 255         List _list;
 256         bool _dirty;
 257 };
 258
 259 /** Type to describe the movement of a time range */
 260 template<typename T>
 261 struct /*LIBEVORAL_API*/ RangeMove {
 262         RangeMove (T f, double l, T t) : from (f), length (l), to (t) {}
 263         T         from;   ///< start of the range
 264         double    length; ///< length of the range
 265         T         to;     ///< new start of the range
 266 };
 267
 268 /** Subtract the ranges in `sub' from that in `range',
 269  *  returning the result.
 270  */
 271 template<typename T>
 272 RangeList<T> subtract (Range<T> range, RangeList<T> sub)
 273 {
 274         /* Start with the input range */
 275         RangeList<T> result;
 276         result.add (range);
 277
 278         if (sub.empty ()) {
 279                 return result;
 280         }
 281
 282         typename RangeList<T>::List s = sub.get ();
 283
 284         /* The basic idea here is to keep a list of the result ranges, and subtract
 285            the bits of `sub' from them one by one.
 286         */
 287
 288         for (typename RangeList<T>::List::const_iterator i = s.begin(); i != s.end(); ++i) {
 289
 290                 /* Here's where we'll put the new current result after subtracting *i from it */
 291                 RangeList<T> new_result;
 292
 293                 typename RangeList<T>::List r = result.get ();
 294
 295                 /* Work on all parts of the current result using this range *i */
 296                 for (typename RangeList<T>::List::const_iterator j = r.begin(); j != r.end(); ++j) {
 297
 298                         switch (coverage (j->from, j->to, i->from, i->to)) {
 299                         case OverlapNone:
 300                                 /* The thing we're subtracting does not overlap this bit of the result,
 301                                    so pass it through.
 302                                 */
 303                                 new_result.add (*j);
 304                                 break;
 305                         case OverlapInternal:
 306                                 /* Internal overlap of the thing we're subtracting from this bit of the result,
 307                                    so we might end up with two bits left over.
 308                                 */
 309                                 if (j->from < (i->from - 1)) {
 310                                         new_result.add (Range<T> (j->from, i->from - 1));
 311                                 }
 312                                 if (j->to != i->to) {
 313                                         new_result.add (Range<T> (i->to, j->to));
 314                                 }
 315                                 break;
 316                         case OverlapStart:
 317                                 /* The bit we're subtracting overlaps the start of the bit of the result */
 318                                 new_result.add (Range<T> (i->to, j->to - 1));
 319                                 break;
 320                         case OverlapEnd:
 321                                 /* The bit we're subtracting overlaps the end of the bit of the result */
 322                                 new_result.add (Range<T> (j->from, i->from - 1));
 323                                 break;
 324                         case OverlapExternal:
 325                                 /* total overlap of the bit we're subtracting with the result bit, so the
 326                                    result bit is completely removed; do nothing */
 327                                 break;
 328                         }
 329                 }
 330
 331                 new_result.coalesce ();
 332                 result = new_result;
 333         }
 334
 335         return result;
 336 }
 337
 338 }
 339
 340 #endif