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                 return OverlapNone;
  82         }
  83
  84         if (sb > eb) {
  85                 // seems we are sometimes called with negative length ranges
  86                 return OverlapNone;
  87         }
  88
  89         if (sb < sa) {  // B starts before A
  90                 if (eb < sa) {
  91                         return OverlapNone;
  92                 } else if (eb == sa) {
  93                         return OverlapStart;
  94                 } else { // eb > sa
  95                         if (eb < ea) {
  96                                 return OverlapStart;
  97                         } else if (eb == ea) {
  98                                 return OverlapExternal;
  99                         } else {
 100                                 return OverlapExternal;
 101                         }
 102                 }
 103         } else if (sb == sa) { // B starts equal to A
 104                 if (eb < ea) {
 105                         return OverlapStart;
 106                 } else if (eb == ea) {
 107                         return OverlapExternal;
 108                 } else { // eb > ea
 109                         return OverlapExternal;
 110                 }
 111         } else { // sb > sa
 112                 if (eb < ea) {
 113                         return OverlapInternal;
 114                 } else if (eb == ea) {
 115                         return OverlapEnd;
 116                 } else { // eb > ea
 117                         if (sb < ea) { // B starts inside A
 118                                 return OverlapEnd;
 119                         } else if (sb == ea) { // B starts at end of A
 120                                 return OverlapEnd;
 121                         } else { // sb > ea, B starts after A
 122                                 return OverlapNone;
 123                         }
 124                 }
 125         }
 126
 127         std::cerr << "unknown overlap type!" << sa << ", " << ea << "; " << sb << ", " << eb << std::endl;
 128         assert(!"unknown overlap type!");
 129         return OverlapNone;
 130 }
 131
 132 /** Type to describe a time range */
 133 template<typename T>
 134 struct /*LIBEVORAL_API*/ Range {
 135         Range (T f, T t) : from (f), to (t) {}
 136         T from; ///< start of the range
 137         T to;   ///< end of the range (inclusive: to lies inside the range)
 138         bool empty() const { return from == to; }
 139         T length() const { return to - from + 1; }
 140
 141         /** for a T, return a mapping of it into the range (used for
 142          * looping). If the argument is earlier than or equal to the end of
 143          * this range, do nothing.
 144          */
 145         T squish (T t) const {
 146                 if (t > to) {
 147                         t = (from + ((t - from) % length()));
 148                 }
 149                 return t;
 150         }
 151 };
 152
 153 template<typename T>
 154 bool operator== (Range<T> a, Range<T> b) {
 155         return a.from == b.from && a.to == b.to;
 156 }
 157
 158 template<typename T>
 159 class /*LIBEVORAL_API*/ RangeList {
 160 public:
 161         RangeList () : _dirty (false) {}
 162
 163         typedef std::list<Range<T> > List;
 164
 165         List const & get () {
 166                 coalesce ();
 167                 return _list;
 168         }
 169
 170         void add (Range<T> const & range) {
 171                 _dirty = true;
 172                 _list.push_back (range);
 173         }
 174
 175         bool empty () const {
 176                 return _list.empty ();
 177         }
 178
 179         void coalesce () {
 180                 if (!_dirty) {
 181                         return;
 182                 }
 183
 184         restart:
 185                 for (typename List::iterator i = _list.begin(); i != _list.end(); ++i) {
 186                         for (typename List::iterator j = _list.begin(); j != _list.end(); ++j) {
 187
 188                                 if (i == j) {
 189                                         continue;
 190                                 }
 191
 192                                 if (coverage (i->from, i->to, j->from, j->to) != OverlapNone) {
 193                                         i->from = std::min (i->from, j->from);
 194                                         i->to = std::max (i->to, j->to);
 195                                         _list.erase (j);
 196                                         goto restart;
 197                                 }
 198                         }
 199                 }
 200
 201                 _dirty = false;
 202         }
 203
 204 private:
 205
 206         List _list;
 207         bool _dirty;
 208 };
 209
 210 /** Type to describe the movement of a time range */
 211 template<typename T>
 212 struct /*LIBEVORAL_API*/ RangeMove {
 213         RangeMove (T f, double l, T t) : from (f), length (l), to (t) {}
 214         T         from;   ///< start of the range
 215         double    length; ///< length of the range
 216         T         to;     ///< new start of the range
 217 };
 218
 219 /** Subtract the ranges in `sub' from that in `range',
 220  *  returning the result.
 221  */
 222 template<typename T>
 223 RangeList<T> subtract (Range<T> range, RangeList<T> sub)
 224 {
 225         /* Start with the input range */
 226         RangeList<T> result;
 227         result.add (range);
 228
 229         if (sub.empty () || range.empty()) {
 230                 return result;
 231         }
 232
 233         typename RangeList<T>::List s = sub.get ();
 234
 235         /* The basic idea here is to keep a list of the result ranges, and subtract
 236            the bits of `sub' from them one by one.
 237         */
 238
 239         for (typename RangeList<T>::List::const_iterator i = s.begin(); i != s.end(); ++i) {
 240
 241                 /* Here's where we'll put the new current result after subtracting *i from it */
 242                 RangeList<T> new_result;
 243
 244                 typename RangeList<T>::List r = result.get ();
 245
 246                 /* Work on all parts of the current result using this range *i */
 247                 for (typename RangeList<T>::List::const_iterator j = r.begin(); j != r.end(); ++j) {
 248
 249                         switch (coverage (j->from, j->to, i->from, i->to)) {
 250                         case OverlapNone:
 251                                 /* The thing we're subtracting (*i) does not overlap this bit of the result (*j),
 252                                    so pass it through.
 253                                 */
 254                                 new_result.add (*j);
 255                                 break;
 256                         case OverlapInternal:
 257                                 /* Internal overlap of the thing we're subtracting (*i) from this bit of the result,
 258                                    so we should end up with two bits of (*j) left over, from the start of (*j) to
 259                                    the start of (*i), and from the end of (*i) to the end of (*j).
 260                                 */
 261                                 assert (j->from < i->from);
 262                                 assert (j->to > i->to);
 263                                 new_result.add (Range<T> (j->from, i->from - 1));
 264                                 new_result.add (Range<T> (i->to + 1, j->to));
 265                                 break;
 266                         case OverlapStart:
 267                                 /* The bit we're subtracting (*i) overlaps the start of the bit of the result (*j),
 268                                  * so we keep only the part of of (*j) from after the end of (*i)
 269                                  */
 270                                 assert (i->to < j->to);
 271                                 new_result.add (Range<T> (i->to + 1, j->to));
 272                                 break;
 273                         case OverlapEnd:
 274                                 /* The bit we're subtracting (*i) overlaps the end of the bit of the result (*j),
 275                                  * so we keep only the part of of (*j) from before the start of (*i)
 276                                  */
 277                                 assert (j->from < i->from);
 278                                 new_result.add (Range<T> (j->from, i->from - 1));
 279                                 break;
 280                         case OverlapExternal:
 281                                 /* total overlap of the bit we're subtracting with the result bit, so the
 282                                    result bit is completely removed; do nothing */
 283                                 break;
 284                         }
 285                 }
 286
 287                 new_result.coalesce ();
 288                 result = new_result;
 289         }
 290
 291         return result;
 292 }
 293
 294 }
 295
 296 #endif