openshot-audio  0.1.6
juce_SparseSet.h
Go to the documentation of this file.
1 /*
2  ==============================================================================
3 
4  This file is part of the juce_core module of the JUCE library.
5  Copyright (c) 2015 - ROLI Ltd.
6 
7  Permission to use, copy, modify, and/or distribute this software for any purpose with
8  or without fee is hereby granted, provided that the above copyright notice and this
9  permission notice appear in all copies.
10 
11  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD
12  TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN
13  NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
14  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
15  IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
16  CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 
18  ------------------------------------------------------------------------------
19 
20  NOTE! This permissive ISC license applies ONLY to files within the juce_core module!
21  All other JUCE modules are covered by a dual GPL/commercial license, so if you are
22  using any other modules, be sure to check that you also comply with their license.
23 
24  For more details, visit www.juce.com
25 
26  ==============================================================================
27 */
28 
29 #ifndef JUCE_SPARSESET_H_INCLUDED
30 #define JUCE_SPARSESET_H_INCLUDED
31 
32 
33 //==============================================================================
44 template <class Type>
45 class SparseSet
46 {
47 public:
48  //==============================================================================
51  {
52  }
53 
55  SparseSet (const SparseSet<Type>& other)
56  : values (other.values)
57  {
58  }
59 
60  //==============================================================================
62  void clear()
63  {
64  values.clear();
65  }
66 
72  {
73  return values.size() == 0;
74  }
75 
82  Type size() const
83  {
84  Type total (0);
85 
86  for (int i = 0; i < values.size(); i += 2)
87  total += values.getUnchecked (i + 1) - values.getUnchecked (i);
88 
89  return total;
90  }
91 
97  Type operator[] (Type index) const
98  {
99  for (int i = 0; i < values.size(); i += 2)
100  {
101  const Type start (values.getUnchecked (i));
102  const Type len (values.getUnchecked (i + 1) - start);
103 
104  if (index < len)
105  return start + index;
106 
107  index -= len;
108  }
109 
110  return Type();
111  }
112 
114  bool contains (const Type valueToLookFor) const
115  {
116  for (int i = 0; i < values.size(); ++i)
117  if (valueToLookFor < values.getUnchecked(i))
118  return (i & 1) != 0;
119 
120  return false;
121  }
122 
123  //==============================================================================
128  {
129  return values.size() >> 1;
130  }
131 
137  const Range<Type> getRange (const int rangeIndex) const
138  {
139  if (isPositiveAndBelow (rangeIndex, getNumRanges()))
140  return Range<Type> (values.getUnchecked (rangeIndex << 1),
141  values.getUnchecked ((rangeIndex << 1) + 1));
142 
143  return Range<Type>();
144  }
145 
150  {
151  if (values.size() > 0)
152  {
153  jassert ((values.size() & 1) == 0);
154  return Range<Type> (values.getUnchecked (0),
155  values.getUnchecked (values.size() - 1));
156  }
157 
158  return Range<Type>();
159  }
160 
161  //==============================================================================
165  void addRange (const Range<Type> range)
166  {
167  jassert (range.getLength() >= 0);
168  if (range.getLength() > 0)
169  {
170  removeRange (range);
171 
172  values.addUsingDefaultSort (range.getStart());
173  values.addUsingDefaultSort (range.getEnd());
174 
175  simplify();
176  }
177  }
178 
182  void removeRange (const Range<Type> rangeToRemove)
183  {
184  jassert (rangeToRemove.getLength() >= 0);
185 
186  if (rangeToRemove.getLength() > 0
187  && values.size() > 0
188  && rangeToRemove.getStart() < values.getUnchecked (values.size() - 1)
189  && values.getUnchecked(0) < rangeToRemove.getEnd())
190  {
191  const bool onAtStart = contains (rangeToRemove.getStart() - 1);
192  const Type lastValue (jmin (rangeToRemove.getEnd(), values.getLast()));
193  const bool onAtEnd = contains (lastValue);
194 
195  for (int i = values.size(); --i >= 0;)
196  {
197  if (values.getUnchecked(i) <= lastValue)
198  {
199  while (values.getUnchecked(i) >= rangeToRemove.getStart())
200  {
201  values.remove (i);
202 
203  if (--i < 0)
204  break;
205  }
206 
207  break;
208  }
209  }
210 
211  if (onAtStart) values.addUsingDefaultSort (rangeToRemove.getStart());
212  if (onAtEnd) values.addUsingDefaultSort (lastValue);
213 
214  simplify();
215  }
216  }
217 
219  void invertRange (const Range<Type> range)
220  {
221  SparseSet newItems;
222  newItems.addRange (range);
223 
224  for (int i = getNumRanges(); --i >= 0;)
225  newItems.removeRange (getRange (i));
226 
227  removeRange (range);
228 
229  for (int i = newItems.getNumRanges(); --i >= 0;)
230  addRange (newItems.getRange(i));
231  }
232 
234  bool overlapsRange (const Range<Type> range)
235  {
236  if (range.getLength() > 0)
237  {
238  for (int i = getNumRanges(); --i >= 0;)
239  {
240  if (values.getUnchecked ((i << 1) + 1) <= range.getStart())
241  return false;
242 
243  if (values.getUnchecked (i << 1) < range.getEnd())
244  return true;
245  }
246  }
247 
248  return false;
249  }
250 
252  bool containsRange (const Range<Type> range)
253  {
254  if (range.getLength() > 0)
255  {
256  for (int i = getNumRanges(); --i >= 0;)
257  {
258  if (values.getUnchecked ((i << 1) + 1) <= range.getStart())
259  return false;
260 
261  if (values.getUnchecked (i << 1) <= range.getStart()
262  && range.getEnd() <= values.getUnchecked ((i << 1) + 1))
263  return true;
264  }
265  }
266 
267  return false;
268  }
269 
270  //==============================================================================
272  {
273  return values == other.values;
274  }
275 
277  {
278  return values != other.values;
279  }
280 
281 private:
282  //==============================================================================
283  // alternating start/end values of ranges of values that are present.
285 
286  void simplify()
287  {
288  jassert ((values.size() & 1) == 0);
289 
290  for (int i = values.size(); --i > 0;)
291  if (values.getUnchecked(i) == values.getUnchecked (i - 1))
292  values.removeRange (--i, 2);
293  }
294 };
295 
296 
297 
298 #endif // JUCE_SPARSESET_H_INCLUDED
void invertRange(const Range< Type > range)
Definition: juce_SparseSet.h:219
SparseSet()
Definition: juce_SparseSet.h:50
Type operator[](Type index) const
Definition: juce_SparseSet.h:97
bool operator!=(const SparseSet< Type > &other) noexcept
Definition: juce_SparseSet.h:276
void removeRange(const Range< Type > rangeToRemove)
Definition: juce_SparseSet.h:182
#define noexcept
Definition: juce_CompilerSupport.h:141
Type jmin(const Type a, const Type b)
Definition: juce_core.h:113
bool isPositiveAndBelow(Type valueToTest, Type upperLimit) noexcept
Definition: juce_core.h:238
Definition: juce_Range.h:44
bool isEmpty() const noexcept
Definition: juce_SparseSet.h:71
int getNumRanges() const noexcept
Definition: juce_SparseSet.h:127
const Range< Type > getRange(const int rangeIndex) const
Definition: juce_SparseSet.h:137
ValueType getLength() const noexcept
Definition: juce_Range.h:98
ElementType getLast() const
Definition: juce_Array.h:302
SparseSet(const SparseSet< Type > &other)
Definition: juce_SparseSet.h:55
void removeRange(int startIndex, int numberToRemove)
Definition: juce_Array.h:862
#define const
void addUsingDefaultSort(ParameterType newElement)
Definition: juce_Array.h:739
void addRange(const Range< Type > range)
Definition: juce_SparseSet.h:165
void clear()
Definition: juce_SparseSet.h:62
Definition: juce_SparseSet.h:45
Type size() const
Definition: juce_SparseSet.h:82
ElementType remove(const int indexToRemove)
Definition: juce_Array.h:795
bool containsRange(const Range< Type > range)
Definition: juce_SparseSet.h:252
#define jassert(a)
Definition: juce_PlatformDefs.h:146
ElementType getUnchecked(const int index) const
Definition: juce_Array.h:258
void clear()
Definition: juce_Array.h:200
ValueType getStart() const noexcept
Definition: juce_Range.h:95
bool operator==(const SparseSet< Type > &other) noexcept
Definition: juce_SparseSet.h:271
bool overlapsRange(const Range< Type > range)
Definition: juce_SparseSet.h:234
bool contains(const Type valueToLookFor) const
Definition: juce_SparseSet.h:114
int size() const noexcept
Definition: juce_Array.h:221
Range< Type > getTotalRange() const
Definition: juce_SparseSet.h:149
ValueType getEnd() const noexcept
Definition: juce_Range.h:101