OpenShot Audio Library | OpenShotAudio  0.3.0
juce_SortedSet.h
1 /*
2  ==============================================================================
3 
4  This file is part of the JUCE library.
5  Copyright (c) 2017 - ROLI Ltd.
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 
23 namespace juce
24 {
25 
26 #if JUCE_MSVC
27  #pragma warning (push)
28  #pragma warning (disable: 4512)
29 #endif
30 
31 //==============================================================================
55 template <class ElementType, class TypeOfCriticalSectionToUse = DummyCriticalSection>
56 class SortedSet
57 {
58 public:
59  //==============================================================================
61  SortedSet() = default;
62 
64  SortedSet (const SortedSet&) = default;
65 
67  SortedSet (SortedSet&&) noexcept = default;
68 
70  SortedSet& operator= (const SortedSet&) = default;
71 
73  SortedSet& operator= (SortedSet&&) noexcept = default;
74 
76  ~SortedSet() = default;
77 
78  //==============================================================================
83  bool operator== (const SortedSet<ElementType>& other) const noexcept
84  {
85  return data == other.data;
86  }
87 
92  bool operator!= (const SortedSet<ElementType>& other) const noexcept
93  {
94  return ! operator== (other);
95  }
96 
97  //==============================================================================
106  void clear() noexcept
107  {
108  data.clear();
109  }
110 
114  void clearQuick() noexcept
115  {
116  data.clearQuick();
117  }
118 
119  //==============================================================================
121  inline int size() const noexcept
122  {
123  return data.size();
124  }
125 
127  inline bool isEmpty() const noexcept
128  {
129  return size() == 0;
130  }
131 
143  inline ElementType operator[] (const int index) const noexcept
144  {
145  return data [index];
146  }
147 
156  inline ElementType getUnchecked (const int index) const noexcept
157  {
158  return data.getUnchecked (index);
159  }
160 
169  inline ElementType& getReference (const int index) noexcept
170  {
171  return data.getReference (index);
172  }
173 
178  inline const ElementType& getReference (const int index) const noexcept
179  {
180  return data.getReference (index);
181  }
182 
186  inline ElementType getFirst() const noexcept
187  {
188  return data.getFirst();
189  }
190 
194  inline ElementType getLast() const noexcept
195  {
196  return data.getLast();
197  }
198 
199  //==============================================================================
203  inline const ElementType* begin() const noexcept
204  {
205  return data.begin();
206  }
207 
211  inline const ElementType* end() const noexcept
212  {
213  return data.end();
214  }
215 
216  //==============================================================================
225  int indexOf (const ElementType& elementToLookFor) const noexcept
226  {
227  const ScopedLockType lock (data.getLock());
228 
229  int s = 0;
230  int e = data.size();
231 
232  for (;;)
233  {
234  if (s >= e)
235  return -1;
236 
237  if (elementToLookFor == data.getReference (s))
238  return s;
239 
240  auto halfway = (s + e) / 2;
241 
242  if (halfway == s)
243  return -1;
244 
245  if (elementToLookFor < data.getReference (halfway))
246  e = halfway;
247  else
248  s = halfway;
249  }
250  }
251 
257  bool contains (const ElementType& elementToLookFor) const noexcept
258  {
259  return indexOf (elementToLookFor) >= 0;
260  }
261 
262  //==============================================================================
274  bool add (const ElementType& newElement) noexcept
275  {
276  const ScopedLockType lock (getLock());
277 
278  int s = 0;
279  int e = data.size();
280 
281  while (s < e)
282  {
283  auto& elem = data.getReference (s);
284 
285  if (newElement == elem)
286  {
287  elem = newElement; // force an update in case operator== permits differences.
288  return false;
289  }
290 
291  auto halfway = (s + e) / 2;
292  bool isBeforeHalfway = (newElement < data.getReference (halfway));
293 
294  if (halfway == s)
295  {
296  if (! isBeforeHalfway)
297  ++s;
298 
299  break;
300  }
301 
302  if (isBeforeHalfway)
303  e = halfway;
304  else
305  s = halfway;
306  }
307 
308  data.insert (s, newElement);
309  return true;
310  }
311 
318  void addArray (const ElementType* elementsToAdd,
319  int numElementsToAdd) noexcept
320  {
321  const ScopedLockType lock (getLock());
322 
323  while (--numElementsToAdd >= 0)
324  add (*elementsToAdd++);
325  }
326 
336  template <class OtherSetType>
337  void addSet (const OtherSetType& setToAddFrom,
338  int startIndex = 0,
339  int numElementsToAdd = -1) noexcept
340  {
341  const typename OtherSetType::ScopedLockType lock1 (setToAddFrom.getLock());
342  const ScopedLockType lock2 (getLock());
343  jassert (this != &setToAddFrom);
344 
345  if (this != &setToAddFrom)
346  {
347  if (startIndex < 0)
348  {
349  jassertfalse;
350  startIndex = 0;
351  }
352 
353  if (numElementsToAdd < 0 || startIndex + numElementsToAdd > setToAddFrom.size())
354  numElementsToAdd = setToAddFrom.size() - startIndex;
355 
356  if (numElementsToAdd > 0)
357  addArray (&setToAddFrom.data.getReference (startIndex), numElementsToAdd);
358  }
359  }
360 
361  //==============================================================================
371  ElementType remove (const int indexToRemove) noexcept
372  {
373  return data.removeAndReturn (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.isEmpty())
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.isEmpty())
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  //==============================================================================
458  void minimiseStorageOverheads() noexcept
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  using ScopedLockType = typename TypeOfCriticalSectionToUse::ScopedLockType;
483 
484 
485 private:
486  //==============================================================================
488 };
489 
490 #if JUCE_MSVC
491  #pragma warning (pop)
492 #endif
493 
494 } // namespace juce
ElementType operator[](const int index) const noexcept
int size() const noexcept
ElementType & getReference(const int index) noexcept
ElementType * end() noexcept
Definition: juce_Array.h:344
void minimiseStorageOverheads()
Definition: juce_Array.h:1050
void swapWith(OtherArrayType &otherArray) noexcept
Definition: juce_Array.h:621
void clearQuick()
Definition: juce_Array.h:198
~SortedSet()=default
void ensureStorageAllocated(int minNumElements)
Definition: juce_Array.h:1062
bool add(const ElementType &newElement) noexcept
bool operator!=(const SortedSet< ElementType > &other) const noexcept
ElementType getLast() const noexcept
Definition: juce_Array.h:300
ElementType * data() noexcept
Definition: juce_Array.h:360
const TypeOfCriticalSectionToUse & getLock() const noexcept
void removeValuesNotIn(const OtherSetType &otherSet) noexcept
void addSet(const OtherSetType &setToAddFrom, int startIndex=0, int numElementsToAdd=-1) noexcept
void removeValuesIn(const OtherSetType &otherSet) noexcept
void insert(int indexToInsertAt, ParameterType newElement)
Definition: juce_Array.h:462
ElementType getUnchecked(int index) const
Definition: juce_Array.h:252
bool contains(const ElementType &elementToLookFor) const noexcept
const ElementType & getReference(const int index) const noexcept
ElementType * begin() noexcept
Definition: juce_Array.h:328
const ElementType * end() const noexcept
void clearQuick() noexcept
const ElementType * begin() const noexcept
SortedSet & operator=(const SortedSet &)=default
void minimiseStorageOverheads() noexcept
ElementType getUnchecked(const int index) const noexcept
void clear()
Definition: juce_Array.h:188
int size() const noexcept
Definition: juce_Array.h:215
ElementType getFirst() const noexcept
void clear() noexcept
ElementType removeAndReturn(int indexToRemove)
Definition: juce_Array.h:785
const TypeOfCriticalSectionToUse & getLock() const noexcept
Definition: juce_Array.h:1120
bool isEmpty() const noexcept
ElementType getFirst() const noexcept
Definition: juce_Array.h:290
void ensureStorageAllocated(const int minNumElements)
ElementType & getReference(int index) noexcept
Definition: juce_Array.h:267
bool operator==(const SortedSet< ElementType > &other) const noexcept
void swapWith(OtherSetType &otherSet) noexcept
void addArray(const ElementType *elementsToAdd, int numElementsToAdd) noexcept
int indexOf(const ElementType &elementToLookFor) const noexcept
void removeValue(const ElementType valueToRemove) noexcept
SortedSet()=default
void remove(int indexToRemove)
Definition: juce_Array.h:767
typename DummyCriticalSection ::ScopedLockType ScopedLockType
ElementType getLast() const noexcept