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
27namespace 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*/
38template <typename ElementComparator>
39struct 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
46private:
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*/
82template <class ElementType, class ElementComparator>
83static 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*/
127template <class ElementType, class ElementComparator>
128static 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*/
188template <class ElementType>
190{
191private:
192 using ParameterType = typename TypeHelpers::ParameterType<ElementType>::type;
193
194public:
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 '<' op...