OpenShot Library | libopenshot-audio 0.2.0
juce_SortedSet.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
27namespace juce
28{
29
30#if JUCE_MSVC
31 #pragma warning (push)
32 #pragma warning (disable: 4512)
33#endif
34
35//==============================================================================
36/**
37 Holds a set of unique primitive objects, such as ints or doubles.
38
39 A set can only hold one item with a given value, so if for example it's a
40 set of integers, attempting to add the same integer twice will do nothing
41 the second time.
42
43 Internally, the list of items is kept sorted (which means that whatever
44 kind of primitive type is used must support the ==, <, >, <= and >= operators
45 to determine the order), and searching the set for known values is very fast
46 because it uses a binary-chop method.
47
48 Note that if you're using a class or struct as the element type, it must be
49 capable of being copied or moved with a straightforward memcpy, rather than
50 needing construction and destruction code.
51
52 To make all the set's methods thread-safe, pass in "CriticalSection" as the templated
53 TypeOfCriticalSectionToUse parameter, instead of the default DummyCriticalSection.
54
55 @see Array, OwnedArray, ReferenceCountedArray, StringArray, CriticalSection
56
57 @tags{Core}
58*/
59template <class ElementType, class TypeOfCriticalSectionToUse = DummyCriticalSection>
61{
62public:
63 //==============================================================================
64 /** Creates an empty set. */
65 // VS2013 doesn't allow defaulted noexcept constructors.
66 SortedSet() = default;
67
68 /** Creates a copy of another set. */
69 SortedSet (const SortedSet&) = default;
70
71 /** Creates a copy of another set. */
72 // VS2013 doesn't allow defaulted noexcept constructors.
73 SortedSet (SortedSet&& other) noexcept : data (std::move (other.data)) {}
74
75 /** Makes a copy of another set. */
76 SortedSet& operator= (const SortedSet&) = default;
77
78 /** Makes a copy of another set. */
79 // VS2013 doesn't allow defaulted noexcept constructors.
80 SortedSet& operator= (SortedSet&& other) noexcept { data = std::move (other.data); return *this; }
81
82 /** Destructor. */
83 ~SortedSet() = default;
84
85 //==============================================================================
86 /** Compares this set to another one.
87 Two sets are considered equal if they both contain the same set of elements.
88 @param other the other set to compare with
89 */
90 bool operator== (const SortedSet<ElementType>& other) const noexcept
91 {
92 return data == other.data;
93 }
94
95 /** Compares this set to another one.
96 Two sets are considered equal if they both contain the same set of elements.
97 @param other the other set to compare with
98 */
99 bool operator!= (const SortedSet<ElementType>& other) const noexcept
100 {
101 return ! operator== (other);
102 }
103
104 //==============================================================================
105 /** Removes all elements from the set.
106
107 This will remove all the elements, and free any storage that the set is
108 using. To clear it without freeing the storage, use the clearQuick()
109 method instead.
110
111 @see clearQuick
112 */
114 {
115 data.clear();
116 }
117
118 /** Removes all elements from the set without freeing the array's allocated storage.
119 @see clear
120 */
122 {
123 data.clearQuick();
124 }
125
126 //==============================================================================
127 /** Returns the current number of elements in the set. */
128 inline int size() const noexcept
129 {
130 return data.size();
131 }
132
133 /** Returns true if the set is empty, false otherwise. */
134 inline bool isEmpty() const noexcept
135 {
136 return size() == 0;
137 }
138
139 /** Returns one of the elements in the set.
140
141 If the index passed in is beyond the range of valid elements, this
142 will return zero.
143
144 If you're certain that the index will always be a valid element, you
145 can call getUnchecked() instead, which is faster.
146
147 @param index the index of the element being requested (0 is the first element in the set)
148 @see getUnchecked, getFirst, getLast
149 */
150 inline ElementType operator[] (const int index) const noexcept
151 {
152 return data [index];
153 }
154
155 /** Returns one of the elements in the set, without checking the index passed in.
156 Unlike the operator[] method, this will try to return an element without
157 checking that the index is within the bounds of the set, so should only
158 be used when you're confident that it will always be a valid index.
159
160 @param index the index of the element being requested (0 is the first element in the set)
161 @see operator[], getFirst, getLast
162 */
163 inline ElementType getUnchecked (const int index) const noexcept
164 {
165 return data.getUnchecked (index);
166 }
167
168 /** Returns a direct reference to one of the elements in the set, without checking the index passed in.
169
170 This is like getUnchecked, but returns a direct reference to the element, so that
171 you can alter it directly. Obviously this can be dangerous, so only use it when
172 absolutely necessary.
173
174 @param index the index of the element being requested (0 is the first element in the array)
175 */
176 inline ElementType& getReference (const int index) const noexcept
177 {
178 return data.getReference (index);
179 }
180
181 /** Returns the first element in the set, or 0 if the set is empty.
182 @see operator[], getUnchecked, getLast
183 */
185 {
186 return data.getFirst();
187 }
188
189 /** Returns the last element in the set, or 0 if the set is empty.
190 @see operator[], getUnchecked, getFirst
191 */
193 {
194 return data.getLast();
195 }
196
197 //==============================================================================
198 /** Returns a pointer to the first element in the set.
199 This method is provided for compatibility with standard C++ iteration mechanisms.
200 */
202 {
203 return data.begin();
204 }
205
206 /** Returns a pointer to the element which follows the last element in the set.
207 This method is provided for compatibility with standard C++ iteration mechanisms.
208 */
210 {
211 return data.end();
212 }
213
214 //==============================================================================
215 /** Finds the index of the first element which matches the value passed in.
216
217 This will search the set for the given object, and return the index
218 of its first occurrence. If the object isn't found, the method will return -1.
219
220 @param elementToLookFor the value or object to look for
221 @returns the index of the object, or -1 if it's not found
222 */
223 int indexOf (const ElementType& elementToLookFor) const noexcept
224 {
225 const ScopedLockType lock (data.getLock());
226
227 int s = 0;
228 int e = data.size();
229
230 for (;;)
231 {
232 if (s >= e)
233 return -1;
234
235 if (elementToLookFor == data.getReference (s))
236 return s;
237
238 auto halfway = (s + e) / 2;
239
240 if (halfway == s)
241 return -1;
242
244 e = halfway;
245 else
246 s = halfway;
247 }
248 }
249
250 /** Returns true if the set contains at least one occurrence of an object.
251
252 @param elementToLookFor the value or object to look for
253 @returns true if the item is found
254 */
255 bool contains (const ElementType& elementToLookFor) const noexcept
256 {
257 return indexOf (elementToLookFor) >= 0;
258 }
259
260 //==============================================================================
261 /** Adds a new element to the set, (as long as it's not already in there).
262
263 Note that if a matching element already exists, the new value will be assigned
264 to the existing one using operator=, so that if there are any differences between
265 the objects which were not recognised by the object's operator==, then the
266 set will always contain a copy of the most recently added one.
267
268 @param newElement the new object to add to the set
269 @returns true if the value was added, or false if it already existed
270 @see set, insert, addIfNotAlreadyThere, addSorted, addSet, addArray
271 */
272 bool add (const ElementType& newElement) noexcept
273 {
274 const ScopedLockType lock (getLock());
275
276 int s = 0;
277 int e = data.size();
278
279 while (s < e)
280 {
281 auto& elem = data.getReference (s);
282
283 if (newElement == elem)
284 {
285 elem = newElement; // force an update in case operator== permits differences.
286 return false;
287 }
288
289 auto halfway = (s + e) / 2;
291
292 if (halfway == s)
293 {
294 if (! isBeforeHalfway)
295 ++s;
296
297 break;
298 }
299
300 if (isBeforeHalfway)
301 e = halfway;
302 else
303 s = halfway;
304 }
305
306 data.insert (s, newElement);
307 return true;
308 }
309
310 /** Adds elements from an array to this set.
311
312 @param elementsToAdd the array of elements to add
313 @param numElementsToAdd how many elements are in this other array
314 @see add
315 */
317 int numElementsToAdd) noexcept
318 {
319 const ScopedLockType lock (getLock());
320
321 while (--numElementsToAdd >= 0)
322 add (*elementsToAdd++);
323 }
324
325 /** Adds elements from another set to this one.
326
327 @param setToAddFrom the set from which to copy the elements
328 @param startIndex the first element of the other set to start copying from
329 @param numElementsToAdd how many elements to add from the other set. If this
330 value is negative or greater than the number of available elements,
331 all available elements will be copied.
332 @see add
333 */
334 template <class OtherSetType>
336 int startIndex = 0,
337 int numElementsToAdd = -1) noexcept
338 {
339 const typename OtherSetType::ScopedLockType lock1 (setToAddFrom.getLock());
340 const ScopedLockType lock2 (getLock());
341 jassert (this != &setToAddFrom);
342
343 if (this != &setToAddFrom)
344 {
345 if (startIndex < 0)
346 {
347 jassertfalse;
348 startIndex = 0;
349 }
350
352 numElementsToAdd = setToAddFrom.size() - startIndex;
353
354 if (numElementsToAdd > 0)
356 }
357 }
358
359 //==============================================================================
360 /** Removes an element from the set.
361
362 This will remove the element at a given index.
363 If the index passed in is out-of-range, nothing will happen.
364
365 @param indexToRemove the index of the element to remove
366 @returns the element that has been removed
367 @see removeValue, removeRange
368 */
369 ElementType remove (const int indexToRemove) noexcept
370 {
371 return data.removeAndReturn (indexToRemove);
372 }
373
374 /** Removes an item from the set.
375
376 This will remove the given element from the set, if it's there.
377
378 @param valueToRemove the object to try to remove
379 @see remove, removeRange
380 */
382 {
383 const ScopedLockType lock (getLock());
385 }
386
387 /** Removes any elements which are also in another set.
388
389 @param otherSet the other set in which to look for elements to remove
390 @see removeValuesNotIn, remove, removeValue, removeRange
391 */
392 template <class OtherSetType>
393 void removeValuesIn (const OtherSetType& otherSet) noexcept
394 {
395 const typename OtherSetType::ScopedLockType lock1 (otherSet.getLock());
396 const ScopedLockType lock2 (getLock());
397
398 if (this == &otherSet)
399 {
400 clear();
401 }
402 else if (! otherSet.isEmpty())
403 {
404 for (int i = data.size(); --i >= 0;)
405 if (otherSet.contains (data.getReference (i)))
406 remove (i);
407 }
408 }
409
410 /** Removes any elements which are not found in another set.
411
412 Only elements which occur in this other set will be retained.
413
414 @param otherSet the set in which to look for elements NOT to remove
415 @see removeValuesIn, remove, removeValue, removeRange
416 */
417 template <class OtherSetType>
419 {
420 const typename OtherSetType::ScopedLockType lock1 (otherSet.getLock());
421 const ScopedLockType lock2 (getLock());
422
423 if (this != &otherSet)
424 {
425 if (otherSet.isEmpty())
426 {
427 clear();
428 }
429 else
430 {
431 for (int i = data.size(); --i >= 0;)
432 if (! otherSet.contains (data.getReference (i)))
433 remove (i);
434 }
435 }
436 }
437
438 /** This swaps the contents of this array with those of another array.
439
440 If you need to exchange two arrays, this is vastly quicker than using copy-by-value
441 because it just swaps their internal pointers.
442 */
443 template <class OtherSetType>
445 {
446 data.swapWith (otherSet.data);
447 }
448
449 //==============================================================================
450 /** Reduces the amount of storage being used by the set.
451
452 Sets typically allocate slightly more storage than they need, and after
453 removing elements, they may have quite a lot of unused space allocated.
454 This method will reduce the amount of allocated storage to a minimum.
455 */
460
461 /** Increases the set's internal storage to hold a minimum number of elements.
462
463 Calling this before adding a large known number of elements means that
464 the set won't have to keep dynamically resizing itself as the elements
465 are added, and it'll therefore be more efficient.
466 */
471
472 //==============================================================================
473 /** Returns the CriticalSection that locks this array.
474 To lock, you can call getLock().enter() and getLock().exit(), or preferably use
475 an object of ScopedLockType as an RAII lock for it.
476 */
477 inline const TypeOfCriticalSectionToUse& getLock() const noexcept { return data.getLock(); }
478
479 /** Returns the type of scoped lock to use for locking this array */
480 using ScopedLockType = typename TypeOfCriticalSectionToUse::ScopedLockType;
481
482
483private:
484 //==============================================================================
486};
487
488#if JUCE_MSVC
489 #pragma warning (pop)
490#endif
491
492} // namespace juce
493
494/** @}*/
Holds a resizable array of primitive or copy-by-value objects.
Definition juce_Array.h:60
void swapWith(OtherArrayType &otherArray) noexcept
This swaps the contents of this array with those of another array.
Definition juce_Array.h:578
ElementType getUnchecked(int index) const
Returns one of the elements in the array, without checking the index passed in.
Definition juce_Array.h:256
bool isEmpty() const noexcept
Returns true if the array is empty, false otherwise.
Definition juce_Array.h:226
void ensureStorageAllocated(int minNumElements)
Increases the array's internal storage to hold a minimum number of elements.
const TypeOfCriticalSectionToUse & getLock() const noexcept
Returns the CriticalSection that locks this array.
void clearQuick()
Removes all elements from the array without freeing the array's allocated storage.
Definition juce_Array.h:202
int size() const noexcept
Returns the current number of elements in the array.
Definition juce_Array.h:219
ElementType * begin() const noexcept
Returns a pointer to the first element in the array.
Definition juce_Array.h:309
void remove(int indexToRemove)
Removes an element from the array.
Definition juce_Array.h:724
void insert(int indexToInsertAt, ParameterType newElement)
Inserts a new element into the array at a given position.
Definition juce_Array.h:419
ElementType getFirst() const noexcept
Returns the first element in the array, or a default value if the array is empty.
Definition juce_Array.h:280
ElementType removeAndReturn(int indexToRemove)
Removes an element from the array.
Definition juce_Array.h:742
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
bool contains(ParameterType elementToLookFor) const
Returns true if the array contains at least one occurrence of an object.
Definition juce_Array.h:357
void clear()
Removes all elements from the array.
Definition juce_Array.h:192
ElementType * data() const noexcept
Returns a pointer to the first element in the array.
Definition juce_Array.h:325
void minimiseStorageOverheads()
Reduces the amount of storage being used by the array.
ElementType getLast() const noexcept
Returns the last element in the array, or a default value if the array is empty.
Definition juce_Array.h:290
ElementType * end() const noexcept
Returns a pointer to the element which follows the last element in the array.
Definition juce_Array.h:317
Holds a set of unique primitive objects, such as ints or doubles.
int size() const noexcept
Returns the current number of elements in the set.
ElementType remove(const int indexToRemove) noexcept
Removes an element from the set.
ElementType * begin() const noexcept
Returns a pointer to the first element in the set.
bool isEmpty() const noexcept
Returns true if the set is empty, false otherwise.
int indexOf(const ElementType &elementToLookFor) const noexcept
Finds the index of the first element which matches the value passed in.
ElementType operator[](const int index) const noexcept
Returns one of the elements in the set.
void removeValue(const ElementType valueToRemove) noexcept
Removes an item from the set.
void addSet(const OtherSetType &setToAddFrom, int startIndex=0, int numElementsToAdd=-1) noexcept
Adds elements from another set to this one.
SortedSet()=default
Creates an empty set.
void addArray(const ElementType *elementsToAdd, int numElementsToAdd) noexcept
Adds elements from an array to this set.
ElementType getFirst() const noexcept
Returns the first element in the set, or 0 if the set is empty.
~SortedSet()=default
Destructor.
void removeValuesIn(const OtherSetType &otherSet) noexcept
Removes any elements which are also in another set.
bool add(const ElementType &newElement) noexcept
Adds a new element to the set, (as long as it's not already in there).
ElementType & getReference(const int index) const noexcept
Returns a direct reference to one of the elements in the set, without checking the index passed in.
void clearQuick() noexcept
Removes all elements from the set without freeing the array's allocated storage.
ElementType getUnchecked(const int index) const noexcept
Returns one of the elements in the set, without checking the index passed in.
SortedSet & operator=(const SortedSet &)=default
Makes a copy of another set.
const TypeOfCriticalSectionToUse & getLock() const noexcept
Returns the CriticalSection that locks this array.
SortedSet(const SortedSet &)=default
Creates a copy of another set.
bool operator!=(const SortedSet< ElementType > &other) const noexcept
Compares this set to another one.
void swapWith(OtherSetType &otherSet) noexcept
This swaps the contents of this array with those of another array.
void minimiseStorageOverheads() noexcept
Reduces the amount of storage being used by the set.
ElementType getLast() const noexcept
Returns the last element in the set, or 0 if the set is empty.
void ensureStorageAllocated(const int minNumElements)
Increases the set's internal storage to hold a minimum number of elements.
SortedSet(SortedSet &&other) noexcept
Creates a copy of another set.
bool operator==(const SortedSet< ElementType > &other) const noexcept
Compares this set to another one.
void clear() noexcept
Removes all elements from the set.
bool contains(const ElementType &elementToLookFor) const noexcept
Returns true if the set contains at least one occurrence of an object.
ElementType * end() const noexcept
Returns a pointer to the element which follows the last element in the set.
void removeValuesNotIn(const OtherSetType &otherSet) noexcept
Removes any elements which are not found in another set.
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Returns the type of scoped lock to use for locking this array.