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 private:
 143         void coalesce () {
 144                 if (!_dirty) {
 145                         return;
 146                 }
 147
 148         restart:
 149                 for (typename List::iterator i = _list.begin(); i != _list.end(); ++i) {
 150                         for (typename List::iterator j = _list.begin(); j != _list.end(); ++j) {
 151
 152                                 if (i == j) {
 153                                         continue;
 154                                 }
 155
 156                                 if (coverage (i->from, i->to, j->from, j->to) != OverlapNone) {
 157                                         i->from = std::min (i->from, j->from);
 158                                         i->to = std::max (i->to, j->to);
 159                                         _list.erase (j);
 160                                         goto restart;
 161                                 }
 162                         }
 163                 }
 164
 165                 _dirty = false;
 166         }
 167
 168         List _list;
 169         bool _dirty;
 170 };
 171
 172 /** Type to describe the movement of a time range */
 173 template<typename T>
 174 struct RangeMove {
 175         RangeMove (T f, double l, T t) : from (f), length (l), to (t) {}
 176         T         from;   ///< start of the range
 177         double    length; ///< length of the range
 178         T         to;     ///< new start of the range
 179 };
 180
 181 template<typename T>
 182 RangeList<T> subtract (Range<T> range, RangeList<T> sub)
 183 {
 184         RangeList<T> result;
 185
 186         if (sub.empty ()) {
 187                 result.add (range);
 188                 return result;
 189         }
 190
 191         T x = range.from;
 192
 193         typename RangeList<T>::List s = sub.get ();
 194
 195         for (typename RangeList<T>::List::const_iterator i = s.begin(); i != s.end(); ++i) {
 196
 197                 if (coverage (range.from, range.to, i->from, i->to) == OverlapNone) {
 198                         continue;
 199                 }
 200
 201                 Range<T> clamped (std::max (range.from, i->from), std::min (range.to, i->to));
 202
 203                 if (clamped.from != x) {
 204                         result.add (Range<T> (x, clamped.from - 1));
 205                 }
 206
 207                 x = clamped.to;
 208         }
 209
 210         if (s.back().to < range.to) {
 211                 result.add (Range<T> (x, range.to));
 212         }
 213
 214         return result;
 215 }
 216
 217 }
 218
 219 #endif