openshot-audio  0.1.6
juce_SortedSet.h
Go to the documentation of this file.
1 /*
2  ==============================================================================
3 
4  This file is part of the juce_core module of the JUCE library.
5  Copyright (c) 2015 - ROLI Ltd.
6 
7  Permission to use, copy, modify, and/or distribute this software for any purpose with
8  or without fee is hereby granted, provided that the above copyright notice and this
9  permission notice appear in all copies.
10 
11  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD
12  TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN
13  NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
14  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
15  IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
16  CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 
18  ------------------------------------------------------------------------------
19 
20  NOTE! This permissive ISC license applies ONLY to files within the juce_core module!
21  All other JUCE modules are covered by a dual GPL/commercial license, so if you are
22  using any other modules, be sure to check that you also comply with their license.
23 
24  For more details, visit www.juce.com
25 
26  ==============================================================================
27 */
28 
29 #ifndef JUCE_SORTEDSET_H_INCLUDED
30 #define JUCE_SORTEDSET_H_INCLUDED
31 
32 #if JUCE_MSVC
33  #pragma warning (push)
34  #pragma warning (disable: 4512)
35 #endif
36 
37 //==============================================================================
59 template <class ElementType, class TypeOfCriticalSectionToUse = DummyCriticalSection>
60 class SortedSet
61 {
62 public:
63  //==============================================================================
66  {
67  }
68 
72  SortedSet (const SortedSet& other)
73  : data (other.data)
74  {
75  }
76 
79  {
80  }
81 
86  {
87  data = other.data;
88  return *this;
89  }
90 
91  //==============================================================================
96  bool operator== (const SortedSet<ElementType>& other) const noexcept
97  {
98  return data == other.data;
99  }
100 
105  bool operator!= (const SortedSet<ElementType>& other) const noexcept
106  {
107  return ! operator== (other);
108  }
109 
110  //==============================================================================
120  {
121  data.clear();
122  }
123 
128  {
129  data.clearQuick();
130  }
131 
132  //==============================================================================
134  inline int size() const noexcept
135  {
136  return data.size();
137  }
138 
150  inline ElementType operator[] (const int index) const noexcept
151  {
152  return data [index];
153  }
154 
163  inline ElementType getUnchecked (const int index) const noexcept
164  {
165  return data.getUnchecked (index);
166  }
167 
176  inline ElementType& getReference (const int index) const noexcept
177  {
178  return data.getReference (index);
179  }
180 
184  inline ElementType getFirst() const noexcept
185  {
186  return data.getFirst();
187  }
188 
192  inline ElementType getLast() const noexcept
193  {
194  return data.getLast();
195  }
196 
197  //==============================================================================
201  inline ElementType* begin() const noexcept
202  {
203  return data.begin();
204  }
205 
209  inline ElementType* end() const noexcept
210  {
211  return data.end();
212  }
213 
214  //==============================================================================
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  const int halfway = (s + e) / 2;
239 
240  if (halfway == s)
241  return -1;
242 
243  if (elementToLookFor < data.getReference (halfway))
244  e = halfway;
245  else
246  s = halfway;
247  }
248  }
249 
255  bool contains (const ElementType& elementToLookFor) const noexcept
256  {
257  return indexOf (elementToLookFor) >= 0;
258  }
259 
260  //==============================================================================
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  ElementType& elem = data.getReference (s);
282  if (newElement == elem)
283  {
284  elem = newElement; // force an update in case operator== permits differences.
285  return false;
286  }
287 
288  const int halfway = (s + e) / 2;
289  const 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 
340  {
341  const ScopedLockType lock2 (getLock());
342  jassert (this != &setToAddFrom);
343 
344  if (this != &setToAddFrom)
345  {
346  if (startIndex < 0)
347  {
348  jassertfalse;
349  startIndex = 0;
350  }
351 
352  if (numElementsToAdd < 0 || startIndex + numElementsToAdd > setToAddFrom.size())
353  numElementsToAdd = setToAddFrom.size() - startIndex;
354 
355  if (numElementsToAdd > 0)
356  addArray (&setToAddFrom.data.getReference (startIndex), numElementsToAdd);
357  }
358  }
359  }
360 
361  //==============================================================================
371  ElementType remove (const int indexToRemove) noexcept
372  {
373  return data.remove (indexToRemove);
374  }
375 
383  void removeValue (const ElementType valueToRemove) noexcept
384  {
385  const ScopedLockType lock (getLock());
386  data.remove (indexOf (valueToRemove));
387  }
388 
394  template <class OtherSetType>
395  void removeValuesIn (const OtherSetType& otherSet) noexcept
396  {
397  const typename OtherSetType::ScopedLockType lock1 (otherSet.getLock());
398  const ScopedLockType lock2 (getLock());
399 
400  if (this == &otherSet)
401  {
402  clear();
403  }
404  else if (otherSet.size() > 0)
405  {
406  for (int i = data.size(); --i >= 0;)
407  if (otherSet.contains (data.getReference (i)))
408  remove (i);
409  }
410  }
411 
419  template <class OtherSetType>
420  void removeValuesNotIn (const OtherSetType& otherSet) noexcept
421  {
422  const typename OtherSetType::ScopedLockType lock1 (otherSet.getLock());
423  const ScopedLockType lock2 (getLock());
424 
425  if (this != &otherSet)
426  {
427  if (otherSet.size() <= 0)
428  {
429  clear();
430  }
431  else
432  {
433  for (int i = data.size(); --i >= 0;)
434  if (! otherSet.contains (data.getReference (i)))
435  remove (i);
436  }
437  }
438  }
439 
445  template <class OtherSetType>
446  void swapWith (OtherSetType& otherSet) noexcept
447  {
448  data.swapWith (otherSet.data);
449  }
450 
451  //==============================================================================
459  {
461  }
462 
469  void ensureStorageAllocated (const int minNumElements)
470  {
471  data.ensureStorageAllocated (minNumElements);
472  }
473 
474  //==============================================================================
479  inline const TypeOfCriticalSectionToUse& getLock() const noexcept { return data.getLock(); }
480 
482  typedef typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType;
483 
484 
485 private:
486  //==============================================================================
488 };
489 
490 #if JUCE_MSVC
491  #pragma warning (pop)
492 #endif
493 
494 #endif // JUCE_SORTEDSET_H_INCLUDED
ElementType * begin() const noexcept
Definition: juce_core.h:329
ElementType getLast() const noexcept
Definition: juce_SortedSet.h:192
int size() const noexcept
Definition: juce_SortedSet.h:134
void minimiseStorageOverheads()
Definition: juce_core.h:1033
void swapWith(OtherArrayType &otherArray) noexcept
Definition: juce_core.h:651
#define noexcept
Definition: juce_CompilerSupport.h:141
SortedSet & operator=(const SortedSet &other) noexcept
Definition: juce_SortedSet.h:85
void clearQuick()
Definition: juce_core.h:212
void minimiseStorageOverheads() noexcept
Definition: juce_SortedSet.h:458
ElementType & getReference(const int index) const noexcept
Definition: juce_core.h:275
void ensureStorageAllocated(const int minNumElements)
Definition: juce_SortedSet.h:469
Definition: juce_SortedSet.h:60
ElementType getFirst() const
Definition: juce_core.h:286
bool operator==(const SortedSet< ElementType > &other) const noexcept
Definition: juce_SortedSet.h:96
void removeValue(const ElementType valueToRemove) noexcept
Definition: juce_SortedSet.h:383
#define jassertfalse
Definition: juce_PlatformDefs.h:141
~SortedSet() noexcept
Definition: juce_SortedSet.h:78
DummyCriticalSection ::ScopedLockType ScopedLockType
Definition: juce_SortedSet.h:482
ElementType getLast() const
Definition: juce_core.h:303
void insert(int indexToInsertAt, ParameterType newElement)
Definition: juce_core.h:426
void clearQuick() noexcept
Definition: juce_SortedSet.h:127
void removeValuesNotIn(const OtherSetType &otherSet) noexcept
Definition: juce_SortedSet.h:420
ElementType operator[](const int index) const noexcept
Definition: juce_SortedSet.h:150
bool operator!=(const SortedSet< ElementType > &other) const noexcept
Definition: juce_SortedSet.h:105
bool add(const ElementType &newElement) noexcept
Definition: juce_SortedSet.h:272
void addSet(const OtherSetType &setToAddFrom, int startIndex=0, int numElementsToAdd=-1) noexcept
Definition: juce_SortedSet.h:334
ElementType * end() const noexcept
Definition: juce_core.h:337
void swapWith(OtherSetType &otherSet) noexcept
Definition: juce_SortedSet.h:446
int indexOf(const ElementType &elementToLookFor) const noexcept
Definition: juce_SortedSet.h:223
void clear() noexcept
Definition: juce_SortedSet.h:119
void ensureStorageAllocated(const int minNumElements)
Definition: juce_core.h:1045
const TypeOfCriticalSectionToUse & getLock() const noexcept
Definition: juce_SortedSet.h:479
void clear()
Definition: juce_core.h:201
int size() const noexcept
Definition: juce_core.h:222
Definition: juce_Array.h:60
#define jassert(a)
Definition: juce_PlatformDefs.h:146
const TypeOfCriticalSectionToUse & getLock() const noexcept
Definition: juce_core.h:1093
ElementType * begin() const noexcept
Definition: juce_SortedSet.h:201
bool contains(const ElementType &elementToLookFor) const noexcept
Definition: juce_SortedSet.h:255
void removeValuesIn(const OtherSetType &otherSet) noexcept
Definition: juce_SortedSet.h:395
ElementType & getReference(const int index) const noexcept
Definition: juce_SortedSet.h:176
ElementType remove(const int indexToRemove)
Definition: juce_core.h:796
ElementType getFirst() const noexcept
Definition: juce_SortedSet.h:184
ElementType getUnchecked(const int index) const
Definition: juce_core.h:259
SortedSet(const SortedSet &other)
Definition: juce_SortedSet.h:72
void addArray(const ElementType *elementsToAdd, int numElementsToAdd) noexcept
Definition: juce_SortedSet.h:315
ElementType getUnchecked(const int index) const noexcept
Definition: juce_SortedSet.h:163
ElementType * end() const noexcept
Definition: juce_SortedSet.h:209
SortedSet() noexcept
Definition: juce_SortedSet.h:65