OpenShot Audio Library | OpenShotAudio 0.4.0
juce_SortedSet.h
1/*
2 ==============================================================================
3
4 This file is part of the JUCE library.
5 Copyright (c) 2022 - Raw Material Software Limited
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
23namespace juce
24{
25
26JUCE_BEGIN_IGNORE_WARNINGS_MSVC (4512)
27
28//==============================================================================
52template <class ElementType, class TypeOfCriticalSectionToUse = DummyCriticalSection>
54{
55public:
56 //==============================================================================
58 SortedSet() = default;
59
61 SortedSet (const SortedSet&) = default;
62
64 SortedSet (SortedSet&&) noexcept = default;
65
67 SortedSet& operator= (const SortedSet&) = default;
68
70 SortedSet& operator= (SortedSet&&) noexcept = default;
71
73 ~SortedSet() = default;
74
75 //==============================================================================
80 bool operator== (const SortedSet<ElementType>& other) const noexcept
81 {
82 return data == other.data;
83 }
84
89 bool operator!= (const SortedSet<ElementType>& other) const noexcept
90 {
91 return ! operator== (other);
92 }
93
94 //==============================================================================
103 void clear() noexcept
104 {
105 data.clear();
106 }
107
111 void clearQuick() noexcept
112 {
113 data.clearQuick();
114 }
115
116 //==============================================================================
118 inline int size() const noexcept
119 {
120 return data.size();
121 }
122
124 inline bool isEmpty() const noexcept
125 {
126 return size() == 0;
127 }
128
140 inline ElementType operator[] (const int index) const noexcept
141 {
142 return data [index];
143 }
144
153 inline ElementType getUnchecked (const int index) const noexcept
154 {
155 return data.getUnchecked (index);
156 }
157
166 inline ElementType& getReference (const int index) noexcept
167 {
168 return data.getReference (index);
169 }
170
175 inline const ElementType& getReference (const int index) const noexcept
176 {
177 return data.getReference (index);
178 }
179
183 inline ElementType getFirst() const noexcept
184 {
185 return data.getFirst();
186 }
187
191 inline ElementType getLast() const noexcept
192 {
193 return data.getLast();
194 }
195
196 //==============================================================================
200 inline const ElementType* begin() const noexcept
201 {
202 return data.begin();
203 }
204
208 inline const ElementType* end() const noexcept
209 {
210 return data.end();
211 }
212
213 //==============================================================================
222 int indexOf (const ElementType& elementToLookFor) const noexcept
223 {
224 const ScopedLockType lock (data.getLock());
225
226 int s = 0;
227 int e = data.size();
228
229 for (;;)
230 {
231 if (s >= e)
232 return -1;
233
234 if (elementToLookFor == data.getReference (s))
235 return s;
236
237 auto halfway = (s + e) / 2;
238
239 if (halfway == s)
240 return -1;
241
242 if (elementToLookFor < data.getReference (halfway))
243 e = halfway;
244 else
245 s = halfway;
246 }
247 }
248
254 bool contains (const ElementType& elementToLookFor) const noexcept
255 {
256 return indexOf (elementToLookFor) >= 0;
257 }
258
259 //==============================================================================
271 bool add (const ElementType& newElement) noexcept
272 {
273 const ScopedLockType lock (getLock());
274
275 int s = 0;
276 int e = data.size();
277
278 while (s < e)
279 {
280 auto& elem = data.getReference (s);
281
282 if (newElement == elem)
283 {
284 elem = newElement; // force an update in case operator== permits differences.
285 return false;
286 }
287
288 auto halfway = (s + e) / 2;
289 bool isBeforeHalfway = (newElement < data.getReference (halfway));
290
291 if (halfway == s)
292 {
293 if (! isBeforeHalfway)
294 ++s;
295
296 break;
297 }
298
299 if (isBeforeHalfway)
300 e = halfway;
301 else
302 s = halfway;
303 }
304
305 data.insert (s, newElement);
306 return true;
307 }
308
315 void addArray (const ElementType* elementsToAdd,
316 int numElementsToAdd) noexcept
317 {
318 const ScopedLockType lock (getLock());
319
320 while (--numElementsToAdd >= 0)
321 add (*elementsToAdd++);
322 }
323
333 template <class OtherSetType>
334 void addSet (const OtherSetType& setToAddFrom,
335 int startIndex = 0,
336 int numElementsToAdd = -1) noexcept
337 {
338 const typename OtherSetType::ScopedLockType lock1 (setToAddFrom.getLock());
339 const ScopedLockType lock2 (getLock());
340 jassert (this != &setToAddFrom);
341
342 if (this != &setToAddFrom)
343 {
344 if (startIndex < 0)
345 {
346 jassertfalse;
347 startIndex = 0;
348 }
349
350 if (numElementsToAdd < 0 || startIndex + numElementsToAdd > setToAddFrom.size())
351 numElementsToAdd = setToAddFrom.size() - startIndex;
352
353 if (numElementsToAdd > 0)
354 addArray (&setToAddFrom.data.getReference (startIndex), numElementsToAdd);
355 }
356 }
357
358 //==============================================================================
368 ElementType remove (const int indexToRemove) noexcept
369 {
370 return data.removeAndReturn (indexToRemove);
371 }
372
380 void removeValue (const ElementType& valueToRemove) noexcept
381 {
382 const ScopedLockType lock (getLock());
383 data.remove (indexOf (valueToRemove));
384 }
385
391 template <class OtherSetType>
392 void removeValuesIn (const OtherSetType& otherSet) noexcept
393 {
394 const typename OtherSetType::ScopedLockType lock1 (otherSet.getLock());
395 const ScopedLockType lock2 (getLock());
396
397 if (this == &otherSet)
398 {
399 clear();
400 }
401 else if (! otherSet.isEmpty())
402 {
403 for (int i = data.size(); --i >= 0;)
404 if (otherSet.contains (data.getReference (i)))
405 remove (i);
406 }
407 }
408
416 template <class OtherSetType>
417 void removeValuesNotIn (const OtherSetType& otherSet) noexcept
418 {
419 const typename OtherSetType::ScopedLockType lock1 (otherSet.getLock());
420 const ScopedLockType lock2 (getLock());
421
422 if (this != &otherSet)
423 {
424 if (otherSet.isEmpty())
425 {
426 clear();
427 }
428 else
429 {
430 for (int i = data.size(); --i >= 0;)
431 if (! otherSet.contains (data.getReference (i)))
432 remove (i);
433 }
434 }
435 }
436
442 template <class OtherSetType>
443 void swapWith (OtherSetType& otherSet) noexcept
444 {
445 data.swapWith (otherSet.data);
446 }
447
448 //==============================================================================
456 {
457 data.minimiseStorageOverheads();
458 }
459
466 void ensureStorageAllocated (const int minNumElements)
467 {
468 data.ensureStorageAllocated (minNumElements);
469 }
470
471 //==============================================================================
476 inline const TypeOfCriticalSectionToUse& getLock() const noexcept { return data.getLock(); }
477
479 using ScopedLockType = typename TypeOfCriticalSectionToUse::ScopedLockType;
480
481
482private:
483 //==============================================================================
485};
486
487JUCE_END_IGNORE_WARNINGS_MSVC
488
489} // namespace juce
int size() const noexcept
ElementType remove(const int indexToRemove) noexcept
bool isEmpty() const noexcept
int indexOf(const ElementType &elementToLookFor) const noexcept
void addSet(const OtherSetType &setToAddFrom, int startIndex=0, int numElementsToAdd=-1) noexcept
SortedSet()=default
void addArray(const ElementType *elementsToAdd, int numElementsToAdd) noexcept
const ElementType & getReference(const int index) const noexcept
ElementType getFirst() const noexcept
void removeValuesIn(const OtherSetType &otherSet) noexcept
bool add(const ElementType &newElement) noexcept
void clearQuick() noexcept
ElementType getUnchecked(const int index) const noexcept
const TypeOfCriticalSectionToUse & getLock() const noexcept
SortedSet(SortedSet &&) noexcept=default
SortedSet(const SortedSet &)=default
void swapWith(OtherSetType &otherSet) noexcept
void minimiseStorageOverheads() noexcept
ElementType getLast() const noexcept
void ensureStorageAllocated(const int minNumElements)
ElementType & getReference(const int index) noexcept
const ElementType * end() const noexcept
void removeValue(const ElementType &valueToRemove) noexcept
void clear() noexcept
bool contains(const ElementType &elementToLookFor) const noexcept
const ElementType * begin() const noexcept
void removeValuesNotIn(const OtherSetType &otherSet) noexcept
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType