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
  24 #include "evoral/visibility.h"
  25
  26 namespace Evoral {
  27
  28 enum /*LIBEVORAL_API*/ OverlapType {
  29         OverlapNone,      // no overlap
  30         OverlapInternal,  // the overlap is 100% with the object
  31         OverlapStart,     // overlap covers start, but ends within
  32         OverlapEnd,       // overlap begins within and covers end
  33         OverlapExternal   // overlap extends to (at least) begin+end
  34 };
  35
  36 template<typename T>
  37 /*LIBEVORAL_API*/ OverlapType coverage (T sa, T ea, T sb, T eb) {
  38         /* OverlapType returned reflects how the second (B)
  39            range overlaps the first (A).
  40
  41            The diagrams show various relative placements
  42            of A and B for each OverlapType.
  43
  44            Notes:
  45               Internal: the start points cannot coincide
  46               External: the start and end points can coincide
  47               Start: end points can coincide
  48               End: start points can coincide
  49
  50            XXX Logically, Internal should disallow end
  51            point equality.
  52         */
  53
  54         /*
  55              |--------------------|   A
  56                   |------|            B
  57                 |-----------------|   B
  58
  59
  60              "B is internal to A"
  61
  62         */
  63
  64         if ((sb > sa) && (eb <= ea)) {
  65                 return OverlapInternal;
  66         }
  67
  68         /*
  69              |--------------------|   A
  70            ----|                      B
  71            -----------------------|   B
  72            --|                        B
  73
  74              "B overlaps the start of A"
  75
  76         */
  77
  78         if ((eb >= sa) && (eb <= ea)) {
  79                 return OverlapStart;
  80         }
  81         /*
  82              |---------------------|  A
  83                    |----------------- B
  84              |----------------------- B
  85                                    |- B
  86
  87             "B overlaps the end of A"
  88
  89         */
  90         if ((sb > sa) && (sb <= ea)) {
  91                 return OverlapEnd;
  92         }
  93         /*
  94              |--------------------|     A
  95            --------------------------  B
  96              |-----------------------  B
  97             ----------------------|    B
  98              |--------------------|    B
  99
 100
 101            "B overlaps all of A"
 102         */
 103         if ((sa >= sb) && (sa <= eb) && (ea <= eb)) {
 104                 return OverlapExternal;
 105         }
 106
 107         return OverlapNone;
 108 }
 109
 110 /** Type to describe a time range */
 111 template<typename T>
 112 struct /*LIBEVORAL_API*/ Range {
 113         Range (T f, T t) : from (f), to (t) {}
 114         T from; ///< start of the range
 115         T to;   ///< end of the range
 116 };
 117
 118 template<typename T>
 119 bool operator== (Range<T> a, Range<T> b) {
 120         return a.from == b.from && a.to == b.to;
 121 }
 122
 123 template<typename T>
 124 class /*LIBEVORAL_API*/ RangeList {
 125 public:
 126         RangeList () : _dirty (false) {}
 127
 128         typedef std::list<Range<T> > List;
 129
 130         List const & get () {
 131                 coalesce ();
 132                 return _list;
 133         }
 134
 135         void add (Range<T> const & range) {
 136                 _dirty = true;
 137                 _list.push_back (range);
 138         }
 139
 140         bool empty () const {
 141                 return _list.empty ();
 142         }
 143
 144         void coalesce () {
 145                 if (!_dirty) {
 146                         return;
 147                 }
 148
 149         restart:
 150                 for (typename List::iterator i = _list.begin(); i != _list.end(); ++i) {
 151                         for (typename List::iterator j = _list.begin(); j != _list.end(); ++j) {
 152
 153                                 if (i == j) {
 154                                         continue;
 155                                 }
 156
 157                                 if (coverage (i->from, i->to, j->from, j->to) != OverlapNone) {
 158                                         i->from = std::min (i->from, j->from);
 159                                         i->to = std::max (i->to, j->to);
 160                                         _list.erase (j);
 161                                         goto restart;
 162                                 }
 163                         }
 164                 }
 165
 166                 _dirty = false;
 167         }
 168
 169 private:
 170
 171         List _list;
 172         bool _dirty;
 173 };
 174
 175 /** Type to describe the movement of a time range */
 176 template<typename T>
 177 struct /*LIBEVORAL_API*/ RangeMove {
 178         RangeMove (T f, double l, T t) : from (f), length (l), to (t) {}
 179         T         from;   ///< start of the range
 180         double    length; ///< length of the range
 181         T         to;     ///< new start of the range
 182 };
 183
 184 /** Subtract the ranges in `sub' from that in `range',
 185  *  returning the result.
 186  */
 187 template<typename T>
 188 RangeList<T> subtract (Range<T> range, RangeList<T> sub)
 189 {
 190         /* Start with the input range */
 191         RangeList<T> result;
 192         result.add (range);
 193
 194         if (sub.empty ()) {
 195                 return result;
 196         }
 197
 198         typename RangeList<T>::List s = sub.get ();
 199
 200         /* The basic idea here is to keep a list of the result ranges, and subtract
 201            the bits of `sub' from them one by one.
 202         */
 203
 204         for (typename RangeList<T>::List::const_iterator i = s.begin(); i != s.end(); ++i) {
 205
 206                 /* Here's where we'll put the new current result after subtracting *i from it */
 207                 RangeList<T> new_result;
 208
 209                 typename RangeList<T>::List r = result.get ();
 210
 211                 /* Work on all parts of the current result using this range *i */
 212                 for (typename RangeList<T>::List::const_iterator j = r.begin(); j != r.end(); ++j) {
 213
 214                         switch (coverage (j->from, j->to, i->from, i->to)) {
 215                         case OverlapNone:
 216                                 /* The thing we're subtracting does not overlap this bit of the result,
 217                                    so pass it through.
 218                                 */
 219                                 new_result.add (*j);
 220                                 break;
 221                         case OverlapInternal:
 222                                 /* Internal overlap of the thing we're subtracting from this bit of the result,
 223                                    so we might end up with two bits left over.
 224                                 */
 225                                 if (j->from < (i->from - 1)) {
 226                                         new_result.add (Range<T> (j->from, i->from - 1));
 227                                 }
 228                                 if (j->to != i->to) {
 229                                         new_result.add (Range<T> (i->to, j->to));
 230                                 }
 231                                 break;
 232                         case OverlapStart:
 233                                 /* The bit we're subtracting overlaps the start of the bit of the result */
 234                                 new_result.add (Range<T> (i->to, j->to - 1));
 235                                 break;
 236                         case OverlapEnd:
 237                                 /* The bit we're subtracting overlaps the end of the bit of the result */
 238                                 new_result.add (Range<T> (j->from, i->from - 1));
 239                                 break;
 240                         case OverlapExternal:
 241                                 /* total overlap of the bit we're subtracting with the result bit, so the
 242                                    result bit is completely removed; do nothing */
 243                                 break;
 244                         }
 245                 }
 246
 247                 new_result.coalesce ();
 248                 result = new_result;
 249         }
 250
 251         return result;
 252 }
 253
 254 }
 255
 256 #endif