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