OpenShot Library | OpenShotAudio  0.2.2
juce_ElementComparator.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 #ifndef DOXYGEN
31 
32 /** This is an internal helper class which converts a juce ElementComparator style
33  class (using a "compareElements" method) into a class that's compatible with
34  std::sort (i.e. using an operator() to compare the elements)
35 
36  @tags{Core}
37 */
38 template <typename ElementComparator>
39 struct SortFunctionConverter
40 {
41  SortFunctionConverter (ElementComparator& e) : comparator (e) {}
42 
43  template <typename Type>
44  bool operator() (Type a, Type b) { return comparator.compareElements (a, b) < 0; }
45 
46 private:
47  ElementComparator& comparator;
48  SortFunctionConverter& operator= (const SortFunctionConverter&) = delete;
49 };
50 
51 #endif
52 
53 
54 //==============================================================================
55 /**
56  Sorts a range of elements in an array.
57 
58  The comparator object that is passed-in must define a public method with the following
59  signature:
60  @code
61  int compareElements (ElementType first, ElementType second);
62  @endcode
63 
64  ..and this method must return:
65  - a value of < 0 if the first comes before the second
66  - a value of 0 if the two objects are equivalent
67  - a value of > 0 if the second comes before the first
68 
69  To improve performance, the compareElements() method can be declared as static or const.
70 
71  @param comparator an object which defines a compareElements() method
72  @param array the array to sort
73  @param firstElement the index of the first element of the range to be sorted
74  @param lastElement the index of the last element in the range that needs
75  sorting (this is inclusive)
76  @param retainOrderOfEquivalentItems if true, the order of items that the
77  comparator deems the same will be maintained - this will be
78  a slower algorithm than if they are allowed to be moved around.
79 
80  @see sortArrayRetainingOrder
81 */
82 template <class ElementType, class ElementComparator>
83 static void sortArray (ElementComparator& comparator,
84  ElementType* const array,
85  int firstElement,
86  int lastElement,
87  const bool retainOrderOfEquivalentItems)
88 {
89  jassert (firstElement >= 0);
90 
91  if (lastElement > firstElement)
92  {
93  SortFunctionConverter<ElementComparator> converter (comparator);
94 
95  if (retainOrderOfEquivalentItems)
96  std::stable_sort (array + firstElement, array + lastElement + 1, converter);
97  else
98  std::sort (array + firstElement, array + lastElement + 1, converter);
99  }
100 }
101 
102 
103 //==============================================================================
104 /**
105  Searches a sorted array of elements, looking for the index at which a specified value
106  should be inserted for it to be in the correct order.
107 
108  The comparator object that is passed-in must define a public method with the following
109  signature:
110  @code
111  int compareElements (ElementType first, ElementType second);
112  @endcode
113 
114  ..and this method must return:
115  - a value of < 0 if the first comes before the second
116  - a value of 0 if the two objects are equivalent
117  - a value of > 0 if the second comes before the first
118 
119  To improve performance, the compareElements() method can be declared as static or const.
120 
121  @param comparator an object which defines a compareElements() method
122  @param array the array to search
123  @param newElement the value that is going to be inserted
124  @param firstElement the index of the first element to search
125  @param lastElement the index of the last element in the range (this is non-inclusive)
126 */
127 template <class ElementType, class ElementComparator>
128 static int findInsertIndexInSortedArray (ElementComparator& comparator,
129  ElementType* const array,
130  const ElementType newElement,
131  int firstElement,
132  int lastElement)
133 {
134  jassert (firstElement <= lastElement);
135 
136  ignoreUnused (comparator); // if you pass in an object with a static compareElements() method, this
137  // avoids getting warning messages about the parameter being unused
138 
139  while (firstElement < lastElement)
140  {
141  if (comparator.compareElements (newElement, array [firstElement]) == 0)
142  {
143  ++firstElement;
144  break;
145  }
146  else
147  {
148  const int halfway = (firstElement + lastElement) >> 1;
149 
150  if (halfway == firstElement)
151  {
152  if (comparator.compareElements (newElement, array [halfway]) >= 0)
153  ++firstElement;
154 
155  break;
156  }
157  else if (comparator.compareElements (newElement, array [halfway]) >= 0)
158  {
159  firstElement = halfway;
160  }
161  else
162  {
163  lastElement = halfway;
164  }
165  }
166  }
167 
168  return firstElement;
169 }
170 
171 //==============================================================================
172 /**
173  A simple ElementComparator class that can be used to sort an array of
174  objects that support the '<' operator.
175 
176  This will work for primitive types and objects that implement operator<().
177 
178  Example: @code
179  Array<int> myArray;
180  DefaultElementComparator<int> sorter;
181  myArray.sort (sorter);
182  @endcode
183 
184  @see ElementComparator
185 
186  @tags{Core}
187 */
188 template <class ElementType>
190 {
191 private:
192  using ParameterType = typename TypeHelpers::ParameterType<ElementType>::type;
193 
194 public:
195  static int compareElements (ParameterType first, ParameterType second)
196  {
197  return (first < second) ? -1 : ((second < first) ? 1 : 0);
198  }
199 };
200 
201 } // namespace juce
202 
203 /** @}*/
A simple ElementComparator class that can be used to sort an array of objects that support the &#39;<&#39; op...