OpenShot Library | libopenshot-audio  0.1.9
juce_SparseSet.h
1 
2 /** @weakgroup juce_core-containers
3  * @{
4  */
5 /*
6  ==============================================================================
7 
8  This file is part of the JUCE library.
9  Copyright (c) 2017 - ROLI Ltd.
10 
11  JUCE is an open source library subject to commercial or open-source
12  licensing.
13 
14  The code included in this file is provided under the terms of the ISC license
15  http://www.isc.org/downloads/software-support-policy/isc-license. Permission
16  To use, copy, modify, and/or distribute this software for any purpose with or
17  without fee is hereby granted provided that the above copyright notice and
18  this permission notice appear in all copies.
19 
20  JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
21  EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
22  DISCLAIMED.
23 
24  ==============================================================================
25 */
26 
27 namespace juce
28 {
29 
30 //==============================================================================
31 /**
32  Holds a set of primitive values, storing them as a set of ranges.
33 
34  This container acts like an array, but can efficiently hold large contiguous
35  ranges of values. It's quite a specialised class, mostly useful for things
36  like keeping the set of selected rows in a listbox.
37 
38  The type used as a template parameter must be an integer type, such as int, short,
39  int64, etc.
40 
41  @tags{Core}
42 */
43 template <class Type>
44 class SparseSet
45 {
46 public:
47  //==============================================================================
48  SparseSet() = default;
49 
50  SparseSet (const SparseSet&) = default;
51  SparseSet& operator= (const SparseSet&) = default;
52 
53  SparseSet (SparseSet&& other) noexcept : ranges (std::move (other.ranges)) {}
54  SparseSet& operator= (SparseSet&& other) noexcept { ranges = std::move (other.ranges); return *this; }
55 
56  //==============================================================================
57  /** Clears the set. */
58  void clear() { ranges.clear(); }
59 
60  /** Checks whether the set is empty.
61  This is much quicker than using (size() == 0).
62  */
63  bool isEmpty() const noexcept { return ranges.isEmpty(); }
64 
65  /** Returns the number of values in the set.
66 
67  Because of the way the data is stored, this method can take longer if there
68  are a lot of items in the set. Use isEmpty() for a quick test of whether there
69  are any items.
70  */
71  Type size() const noexcept
72  {
73  Type total = {};
74 
75  for (auto& r : ranges)
76  total += r.getLength();
77 
78  return total;
79  }
80 
81  /** Returns one of the values in the set.
82 
83  @param index the index of the value to retrieve, in the range 0 to (size() - 1).
84  @returns the value at this index, or 0 if it's out-of-range
85  */
86  Type operator[] (Type index) const noexcept
87  {
88  Type total = {};
89 
90  for (auto& r : ranges)
91  {
92  auto end = total + r.getLength();
93 
94  if (index < end)
95  return r.getStart() + (index - total);
96 
97  total = end;
98  }
99 
100  return {};
101  }
102 
103  /** Checks whether a particular value is in the set. */
104  bool contains (Type valueToLookFor) const noexcept
105  {
106  for (auto& r : ranges)
107  {
108  if (r.getStart() > valueToLookFor)
109  break;
110 
111  if (r.getEnd() > valueToLookFor)
112  return true;
113  }
114 
115  return false;
116  }
117 
118  //==============================================================================
119  /** Returns the number of contiguous blocks of values.
120  @see getRange
121  */
122  int getNumRanges() const noexcept { return ranges.size(); }
123 
124  /** Returns one of the contiguous ranges of values stored.
125  @param rangeIndex the index of the range to look up, between 0
126  and (getNumRanges() - 1)
127  @see getTotalRange
128  */
129  Range<Type> getRange (int rangeIndex) const noexcept { return ranges[rangeIndex]; }
130 
131  /** Returns the range between the lowest and highest values in the set.
132  @see getRange
133  */
134  Range<Type> getTotalRange() const noexcept
135  {
136  if (ranges.isEmpty())
137  return {};
138 
139  return { ranges.getFirst().getStart(),
140  ranges.getLast().getEnd() };
141  }
142 
143  //==============================================================================
144  /** Adds a range of contiguous values to the set.
145  e.g. addRange (Range <int> (10, 14)) will add (10, 11, 12, 13) to the set.
146  */
147  void addRange (Range<Type> range)
148  {
149  if (! range.isEmpty())
150  {
151  removeRange (range);
152  ranges.add (range);
153  std::sort (ranges.begin(), ranges.end(),
154  [] (Range<Type> a, Range<Type> b) { return a.getStart() < b.getStart(); });
155  simplify();
156  }
157  }
158 
159  /** Removes a range of values from the set.
160  e.g. removeRange (Range<int> (10, 14)) will remove (10, 11, 12, 13) from the set.
161  */
162  void removeRange (Range<Type> rangeToRemove)
163  {
164  if (getTotalRange().intersects (rangeToRemove) && ! rangeToRemove.isEmpty())
165  {
166  for (int i = ranges.size(); --i >= 0;)
167  {
168  auto& r = ranges.getReference(i);
169 
170  if (r.getEnd() <= rangeToRemove.getStart())
171  break;
172 
173  if (r.getStart() >= rangeToRemove.getEnd())
174  continue;
175 
176  if (rangeToRemove.contains (r))
177  {
178  ranges.remove (i);
179  }
180  else if (r.contains (rangeToRemove))
181  {
182  auto r1 = r.withEnd (rangeToRemove.getStart());
183  auto r2 = r.withStart (rangeToRemove.getEnd());
184 
185  // this should be covered in if (rangeToRemove.contains (r))
186  jassert (! r1.isEmpty() || ! r2.isEmpty());
187 
188  r = r1;
189 
190  if (r.isEmpty())
191  r = r2;
192 
193  if (! r1.isEmpty() && ! r2.isEmpty())
194  ranges.insert (i + 1, r2);
195  }
196  else if (rangeToRemove.getEnd() > r.getEnd())
197  {
198  r.setEnd (rangeToRemove.getStart());
199  }
200  else
201  {
202  r.setStart (rangeToRemove.getEnd());
203  }
204  }
205  }
206  }
207 
208  /** Does an XOR of the values in a given range. */
210  {
211  SparseSet newItems;
212  newItems.addRange (range);
213 
214  for (auto& r : ranges)
215  newItems.removeRange (r);
216 
217  removeRange (range);
218 
219  for (auto& r : newItems.ranges)
220  addRange (r);
221  }
222 
223  /** Checks whether any part of a given range overlaps any part of this set. */
224  bool overlapsRange (Range<Type> range) const noexcept
225  {
226  if (! range.isEmpty())
227  for (auto& r : ranges)
228  if (r.intersects (range))
229  return true;
230 
231  return false;
232  }
233 
234  /** Checks whether the whole of a given range is contained within this one. */
235  bool containsRange (Range<Type> range) const noexcept
236  {
237  if (! range.isEmpty())
238  for (auto& r : ranges)
239  if (r.contains (range))
240  return true;
241 
242  return false;
243  }
244 
245  /** Returns the set as a list of ranges, which you may want to iterate over. */
246  const Array<Range<Type>>& getRanges() const noexcept { return ranges; }
247 
248  //==============================================================================
249  bool operator== (const SparseSet& other) const noexcept { return ranges == other.ranges; }
250  bool operator!= (const SparseSet& other) const noexcept { return ranges != other.ranges; }
251 
252 private:
253  //==============================================================================
254  Array<Range<Type>> ranges;
255 
256  void simplify()
257  {
258  for (int i = ranges.size(); --i > 0;)
259  {
260  auto& r1 = ranges.getReference (i - 1);
261  auto& r2 = ranges.getReference (i);
262 
263  if (r1.getEnd() == r2.getStart())
264  {
265  r1.setEnd (r2.getEnd());
266  ranges.remove (i);
267  }
268  }
269  }
270 };
271 
272 } // namespace juce
273 
274 /** @}*/
Type operator[](Type index) const noexcept
Returns one of the values in the set.
bool contains(Type valueToLookFor) const noexcept
Checks whether a particular value is in the set.
int getNumRanges() const noexcept
Returns the number of contiguous blocks of values.
Range< Type > getRange(int rangeIndex) const noexcept
Returns one of the contiguous ranges of values stored.
JUCE_CONSTEXPR bool contains(const ValueType position) const noexcept
Returns true if the given position lies inside this range.
Definition: juce_Range.h:213
void removeRange(Range< Type > rangeToRemove)
Removes a range of values from the set.
bool containsRange(Range< Type > range) const noexcept
Checks whether the whole of a given range is contained within this one.
void addRange(Range< Type > range)
Adds a range of contiguous values to the set.
JUCE_CONSTEXPR ValueType getEnd() const noexcept
Returns the end of the range.
Definition: juce_Range.h:90
bool isEmpty() const noexcept
Checks whether the set is empty.
Holds a resizable array of primitive or copy-by-value objects.
Definition: juce_Array.h:59
int size() const noexcept
Returns the current number of elements in the array.
Definition: juce_Array.h:219
JUCE_CONSTEXPR bool isEmpty() const noexcept
Returns true if the range has a length of zero.
Definition: juce_Range.h:93
void clear()
Clears the set.
ElementType & getReference(int index) const noexcept
Returns a direct reference to one of the elements in the array, without checking the index passed in...
Definition: juce_Array.h:271
Holds a set of primitive values, storing them as a set of ranges.
Range< Type > getTotalRange() const noexcept
Returns the range between the lowest and highest values in the set.
JUCE_CONSTEXPR ValueType getStart() const noexcept
Returns the start of the range.
Definition: juce_Range.h:84
bool overlapsRange(Range< Type > range) const noexcept
Checks whether any part of a given range overlaps any part of this set.
const Array< Range< Type > > & getRanges() const noexcept
Returns the set as a list of ranges, which you may want to iterate over.
void remove(int indexToRemove)
Removes an element from the array.
Definition: juce_Array.h:724
void invertRange(Range< Type > range)
Does an XOR of the values in a given range.
Type size() const noexcept
Returns the number of values in the set.