OpenShot Audio Library | OpenShotAudio  0.3.1
juce_SparseSet.h
1 /*
2  ==============================================================================
3 
4  This file is part of the JUCE library.
5  Copyright (c) 2017 - ROLI Ltd.
6 
7  JUCE is an open source library subject to commercial or open-source
8  licensing.
9 
10  The code included in this file is provided under the terms of the ISC license
11  http://www.isc.org/downloads/software-support-policy/isc-license. Permission
12  To use, copy, modify, and/or distribute this software for any purpose with or
13  without fee is hereby granted provided that the above copyright notice and
14  this permission notice appear in all copies.
15 
16  JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
17  EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
18  DISCLAIMED.
19 
20  ==============================================================================
21 */
22 
23 namespace juce
24 {
25 
26 //==============================================================================
39 template <class Type>
40 class SparseSet
41 {
42 public:
43  //==============================================================================
44  SparseSet() = default;
45 
46  SparseSet (const SparseSet&) = default;
47  SparseSet& operator= (const SparseSet&) = default;
48 
49  SparseSet (SparseSet&& other) noexcept : ranges (std::move (other.ranges)) {}
50  SparseSet& operator= (SparseSet&& other) noexcept { ranges = std::move (other.ranges); return *this; }
51 
52  //==============================================================================
54  void clear() { ranges.clear(); }
55 
59  bool isEmpty() const noexcept { return ranges.isEmpty(); }
60 
67  Type size() const noexcept
68  {
69  Type total = {};
70 
71  for (auto& r : ranges)
72  total += r.getLength();
73 
74  return total;
75  }
76 
82  Type operator[] (Type index) const noexcept
83  {
84  Type total = {};
85 
86  for (auto& r : ranges)
87  {
88  auto end = total + r.getLength();
89 
90  if (index < end)
91  return r.getStart() + (index - total);
92 
93  total = end;
94  }
95 
96  return {};
97  }
98 
100  bool contains (Type valueToLookFor) const noexcept
101  {
102  for (auto& r : ranges)
103  {
104  if (r.getStart() > valueToLookFor)
105  break;
106 
107  if (r.getEnd() > valueToLookFor)
108  return true;
109  }
110 
111  return false;
112  }
113 
114  //==============================================================================
118  int getNumRanges() const noexcept { return ranges.size(); }
119 
125  Range<Type> getRange (int rangeIndex) const noexcept { return ranges[rangeIndex]; }
126 
130  Range<Type> getTotalRange() const noexcept
131  {
132  if (ranges.isEmpty())
133  return {};
134 
135  return { ranges.getFirst().getStart(),
136  ranges.getLast().getEnd() };
137  }
138 
139  //==============================================================================
143  void addRange (Range<Type> range)
144  {
145  if (! range.isEmpty())
146  {
147  removeRange (range);
148  ranges.add (range);
149  std::sort (ranges.begin(), ranges.end(),
150  [] (Range<Type> a, Range<Type> b) { return a.getStart() < b.getStart(); });
151  simplify();
152  }
153  }
154 
158  void removeRange (Range<Type> rangeToRemove)
159  {
160  if (getTotalRange().intersects (rangeToRemove) && ! rangeToRemove.isEmpty())
161  {
162  for (int i = ranges.size(); --i >= 0;)
163  {
164  auto& r = ranges.getReference(i);
165 
166  if (r.getEnd() <= rangeToRemove.getStart())
167  break;
168 
169  if (r.getStart() >= rangeToRemove.getEnd())
170  continue;
171 
172  if (rangeToRemove.contains (r))
173  {
174  ranges.remove (i);
175  }
176  else if (r.contains (rangeToRemove))
177  {
178  auto r1 = r.withEnd (rangeToRemove.getStart());
179  auto r2 = r.withStart (rangeToRemove.getEnd());
180 
181  // this should be covered in if (rangeToRemove.contains (r))
182  jassert (! r1.isEmpty() || ! r2.isEmpty());
183 
184  r = r1;
185 
186  if (r.isEmpty())
187  r = r2;
188 
189  if (! r1.isEmpty() && ! r2.isEmpty())
190  ranges.insert (i + 1, r2);
191  }
192  else if (rangeToRemove.getEnd() > r.getEnd())
193  {
194  r.setEnd (rangeToRemove.getStart());
195  }
196  else
197  {
198  r.setStart (rangeToRemove.getEnd());
199  }
200  }
201  }
202  }
203 
206  {
207  SparseSet newItems;
208  newItems.addRange (range);
209 
210  for (auto& r : ranges)
211  newItems.removeRange (r);
212 
213  removeRange (range);
214 
215  for (auto& r : newItems.ranges)
216  addRange (r);
217  }
218 
220  bool overlapsRange (Range<Type> range) const noexcept
221  {
222  if (! range.isEmpty())
223  for (auto& r : ranges)
224  if (r.intersects (range))
225  return true;
226 
227  return false;
228  }
229 
231  bool containsRange (Range<Type> range) const noexcept
232  {
233  if (! range.isEmpty())
234  for (auto& r : ranges)
235  if (r.contains (range))
236  return true;
237 
238  return false;
239  }
240 
242  const Array<Range<Type>>& getRanges() const noexcept { return ranges; }
243 
244  //==============================================================================
245  bool operator== (const SparseSet& other) const noexcept { return ranges == other.ranges; }
246  bool operator!= (const SparseSet& other) const noexcept { return ranges != other.ranges; }
247 
248 private:
249  //==============================================================================
250  Array<Range<Type>> ranges;
251 
252  void simplify()
253  {
254  for (int i = ranges.size(); --i > 0;)
255  {
256  auto& r1 = ranges.getReference (i - 1);
257  auto& r2 = ranges.getReference (i);
258 
259  if (r1.getEnd() == r2.getStart())
260  {
261  r1.setEnd (r2.getEnd());
262  ranges.remove (i);
263  }
264  }
265  }
266 };
267 
268 } // namespace juce
JUCE_CONSTEXPR ValueType getStart() const noexcept
Definition: juce_Range.h:80
JUCE_CONSTEXPR bool contains(const ValueType position) const noexcept
Definition: juce_Range.h:209
JUCE_CONSTEXPR bool isEmpty() const noexcept
Definition: juce_Range.h:89
JUCE_CONSTEXPR ValueType getEnd() const noexcept
Definition: juce_Range.h:86
Range< Type > getRange(int rangeIndex) const noexcept
void invertRange(Range< Type > range)
bool overlapsRange(Range< Type > range) const noexcept
Range< Type > getTotalRange() const noexcept
Type size() const noexcept
void addRange(Range< Type > range)
bool isEmpty() const noexcept
Type operator[](Type index) const noexcept
bool contains(Type valueToLookFor) const noexcept
int getNumRanges() const noexcept
const Array< Range< Type > > & getRanges() const noexcept
bool containsRange(Range< Type > range) const noexcept
void removeRange(Range< Type > rangeToRemove)