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