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