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 
27 namespace 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 */
59 template <class ElementType, class TypeOfCriticalSectionToUse = DummyCriticalSection>
60 class SortedSet
61 {
62 public:
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  */
462  void minimiseStorageOverheads() noexcept
463  {
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 
489 private:
490  //==============================================================================
492 };
493 
494 #if JUCE_MSVC
495  #pragma warning (pop)
496 #endif
497 
498 } // namespace juce
499 
500 /** @}*/
ElementType operator[](const int index) const noexcept
Returns one of the elements in the set.
int size() const noexcept
Returns the current number of elements in the set.
ElementType & getReference(const int index) noexcept
Returns a direct reference to one of the elements in the set, without checking the index passed in...
ElementType * end() noexcept
Returns a pointer to the element which follows the last element in the array.
Definition: juce_Array.h:348
void minimiseStorageOverheads()
Reduces the amount of storage being used by the array.
Definition: juce_Array.h:1054
void swapWith(OtherArrayType &otherArray) noexcept
This swaps the contents of this array with those of another array.
Definition: juce_Array.h:625
void clearQuick()
Removes all elements from the array without freeing the array&#39;s allocated storage.
Definition: juce_Array.h:202
~SortedSet()=default
Destructor.
void ensureStorageAllocated(int minNumElements)
Increases the array&#39;s internal storage to hold a minimum number of elements.
Definition: juce_Array.h:1066
bool add(const ElementType &newElement) noexcept
Adds a new element to the set, (as long as it&#39;s not already in there).
bool operator!=(const SortedSet< ElementType > &other) const noexcept
Compares this set to another one.
ElementType getLast() const noexcept
Returns the last element in the array, or a default value if the array is empty.
Definition: juce_Array.h:304
ElementType * data() noexcept
Returns a pointer to the first element in the array.
Definition: juce_Array.h:364
const TypeOfCriticalSectionToUse & getLock() const noexcept
Returns the CriticalSection that locks this array.
void removeValuesNotIn(const OtherSetType &otherSet) noexcept
Removes any elements which are not found in another set.
void addSet(const OtherSetType &setToAddFrom, int startIndex=0, int numElementsToAdd=-1) noexcept
Adds elements from another set to this one.
void removeValuesIn(const OtherSetType &otherSet) noexcept
Removes any elements which are also in another set.
void insert(int indexToInsertAt, ParameterType newElement)
Inserts a new element into the array at a given position.
Definition: juce_Array.h:466
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 contains(const ElementType &elementToLookFor) const noexcept
Returns true if the set contains at least one occurrence of an object.
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 * begin() noexcept
Returns a pointer to the first element in the array.
Definition: juce_Array.h:332
const ElementType * end() const noexcept
Returns a pointer to the element which follows the last element in the set.
void clearQuick() noexcept
Removes all elements from the set without freeing the array&#39;s allocated storage.
const ElementType * begin() const noexcept
Returns a pointer to the first element in the set.
SortedSet & operator=(const SortedSet &)=default
Makes a copy of another set.
void minimiseStorageOverheads() noexcept
Reduces the amount of storage being used by the set.
Holds a set of unique primitive objects, such as ints or doubles.
ElementType getUnchecked(const int index) const noexcept
Returns one of the elements in the set, without checking the index passed in.
void clear()
Removes all elements from the array.
Definition: juce_Array.h:192
int size() const noexcept
Returns the current number of elements in the array.
Definition: juce_Array.h:219
ElementType getFirst() const noexcept
Returns the first element in the set, or 0 if the set is empty.
void clear() noexcept
Removes all elements from the set.
ElementType removeAndReturn(int indexToRemove)
Removes an element from the array.
Definition: juce_Array.h:789
const TypeOfCriticalSectionToUse & getLock() const noexcept
Returns the CriticalSection that locks this array.
Definition: juce_Array.h:1124
bool isEmpty() const noexcept
Returns true if the set is empty, false otherwise.
ElementType getFirst() const noexcept
Returns the first element in the array, or a default value if the array is empty. ...
Definition: juce_Array.h:294
void ensureStorageAllocated(const int minNumElements)
Increases the set&#39;s internal storage to hold a minimum number of elements.
ElementType & getReference(int index) 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 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 addArray(const ElementType *elementsToAdd, int numElementsToAdd) noexcept
Adds elements from an array to this set.
int indexOf(const ElementType &elementToLookFor) const noexcept
Finds the index of the first element which matches the value passed in.
void removeValue(const ElementType valueToRemove) noexcept
Removes an item from the set.
SortedSet()=default
Creates an empty set.
void remove(int indexToRemove)
Removes an element from the array.
Definition: juce_Array.h:771
typename DummyCriticalSection ::ScopedLockType ScopedLockType
Returns the type of scoped lock to use for locking this array.
ElementType getLast() const noexcept
Returns the last element in the set, or 0 if the set is empty.