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 namespace Evoral {
  30
  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
  37 };
  38
  39 template<typename T>
  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).
  43          *
  44          * The diagram shows the OverlapType of each possible relative
  45          * placement of A and B.
  46          *
  47          * Notes:
  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
  52          *
  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.
  55          *
  56          * A:    |---|
  57          * B starts before A
  58          * B: |-|          None
  59          * B: |--|         Start
  60          * B: |----|       Start
  61          * B: |------|     External
  62          * B: |--------|   External
  63          * B starts equal to A
  64          * B:    |-|       Start
  65          * B:    |---|     External
  66          * B:    |----|    External
  67          * B starts inside A
  68          * B:     |-|      Internal
  69          * B:     |--|     End
  70          * B:     |---|    End
  71          * B starts at end of A
  72          * B:        |--|  End
  73          * B starts after A
  74          * B:         |-|  None
  75          * A:    |---|
  76          */
  77
  78
  79         if (sa > ea) {
  80                 // seems we are sometimes called with negative length ranges
  81                 std::cerr << "a - start after end: " << sa << ", " << ea << std::endl;
  82                 return OverlapNone;
  83         }
  84
  85         if (sb > eb) {
  86                 // seems we are sometimes called with negative length ranges
  87                 std::cerr << "b - start after end: " << sb << ", " << eb << std::endl;
  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 {
 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)
 140         bool empty() const { return from == to; }
 141 };
 142
 143 template<typename T>
 144 bool operator== (Range<T> a, Range<T> b) {
 145         return a.from == b.from && a.to == b.to;
 146 }
 147
 148 template<typename T>
 149 class /*LIBEVORAL_API*/ RangeList {
 150 public:
 151         RangeList () : _dirty (false) {}
 152
 153         typedef std::list<Range<T> > List;
 154
 155         List const & get () {
 156                 coalesce ();
 157                 return _list;
 158         }
 159
 160         void add (Range<T> const & range) {
 161                 _dirty = true;
 162                 _list.push_back (range);
 163         }
 164
 165         bool empty () const {
 166                 return _list.empty ();
 167         }
 168
 169         void coalesce () {
 170                 if (!_dirty) {
 171                         return;
 172                 }
 173
 174         restart:
 175                 for (typename List::iterator i = _list.begin(); i != _list.end(); ++i) {
 176                         for (typename List::iterator j = _list.begin(); j != _list.end(); ++j) {
 177
 178                                 if (i == j) {
 179                                         continue;
 180                                 }
 181
 182                                 if (coverage (i->from, i->to, j->from, j->to) != OverlapNone) {
 183                                         i->from = std::min (i->from, j->from);
 184                                         i->to = std::max (i->to, j->to);
 185                                         _list.erase (j);
 186                                         goto restart;
 187                                 }
 188                         }
 189                 }
 190
 191                 _dirty = false;
 192         }
 193
 194 private:
 195
 196         List _list;
 197         bool _dirty;
 198 };
 199
 200 /** Type to describe the movement of a time range */
 201 template<typename T>
 202 struct /*LIBEVORAL_API*/ RangeMove {
 203         RangeMove (T f, double l, T t) : from (f), length (l), to (t) {}
 204         T         from;   ///< start of the range
 205         double    length; ///< length of the range
 206         T         to;     ///< new start of the range
 207 };
 208
 209 /** Subtract the ranges in `sub' from that in `range',
 210  *  returning the result.
 211  */
 212 template<typename T>
 213 RangeList<T> subtract (Range<T> range, RangeList<T> sub)
 214 {
 215         /* Start with the input range */
 216         RangeList<T> result;
 217         result.add (range);
 218
 219         if (sub.empty () || range.empty()) {
 220                 return result;
 221         }
 222
 223         typename RangeList<T>::List s = sub.get ();
 224
 225         /* The basic idea here is to keep a list of the result ranges, and subtract
 226            the bits of `sub' from them one by one.
 227         */
 228
 229         for (typename RangeList<T>::List::const_iterator i = s.begin(); i != s.end(); ++i) {
 230
 231                 /* Here's where we'll put the new current result after subtracting *i from it */
 232                 RangeList<T> new_result;
 233
 234                 typename RangeList<T>::List r = result.get ();
 235
 236                 /* Work on all parts of the current result using this range *i */
 237                 for (typename RangeList<T>::List::const_iterator j = r.begin(); j != r.end(); ++j) {
 238
 239                         switch (coverage (j->from, j->to, i->from, i->to)) {
 240                         case OverlapNone:
 241                                 /* The thing we're subtracting (*i) does not overlap this bit of the result (*j),
 242                                    so pass it through.
 243                                 */
 244                                 new_result.add (*j);
 245                                 break;
 246                         case OverlapInternal:
 247                                 /* Internal overlap of the thing we're subtracting (*i) from this bit of the result,
 248                                    so we should end up with two bits of (*j) left over, from the start of (*j) to
 249                                    the start of (*i), and from the end of (*i) to the end of (*j).
 250                                 */
 251                                 assert (j->from < i->from);
 252                                 assert (j->to > i->to);
 253                                 new_result.add (Range<T> (j->from, i->from - 1));
 254                                 new_result.add (Range<T> (i->to + 1, j->to));
 255                                 break;
 256                         case OverlapStart:
 257                                 /* The bit we're subtracting (*i) overlaps the start of the bit of the result (*j),
 258                                  * so we keep only the part of of (*j) from after the end of (*i)
 259                                  */
 260                                 assert (i->to < j->to);
 261                                 new_result.add (Range<T> (i->to + 1, j->to));
 262                                 break;
 263                         case OverlapEnd:
 264                                 /* The bit we're subtracting (*i) overlaps the end of the bit of the result (*j),
 265                                  * so we keep only the part of of (*j) from before the start of (*i)
 266                                  */
 267                                 assert (j->from < i->from);
 268                                 new_result.add (Range<T> (j->from, i->from - 1));
 269                                 break;
 270                         case OverlapExternal:
 271                                 /* total overlap of the bit we're subtracting with the result bit, so the
 272                                    result bit is completely removed; do nothing */
 273                                 break;
 274                         }
 275                 }
 276
 277                 new_result.coalesce ();
 278                 result = new_result;
 279         }
 280
 281         return result;
 282 }
 283
 284 }
 285
 286 #endif