1/**************************************************************************/
2/* sort_array.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef SORT_ARRAY_H
32#define SORT_ARRAY_H
33
34#include "core/error/error_macros.h"
35#include "core/typedefs.h"
36
37#define ERR_BAD_COMPARE(cond) \
38 if (unlikely(cond)) { \
39 ERR_PRINT("bad comparison function; sorting will be broken"); \
40 break; \
41 }
42
43template <class T>
44struct _DefaultComparator {
45 _FORCE_INLINE_ bool operator()(const T &a, const T &b) const { return (a < b); }
46};
47
48#ifdef DEBUG_ENABLED
49#define SORT_ARRAY_VALIDATE_ENABLED true
50#else
51#define SORT_ARRAY_VALIDATE_ENABLED false
52#endif
53
54template <class T, class Comparator = _DefaultComparator<T>, bool Validate = SORT_ARRAY_VALIDATE_ENABLED>
55class SortArray {
56 enum {
57 INTROSORT_THRESHOLD = 16
58 };
59
60public:
61 Comparator compare;
62
63 inline const T &median_of_3(const T &a, const T &b, const T &c) const {
64 if (compare(a, b)) {
65 if (compare(b, c)) {
66 return b;
67 } else if (compare(a, c)) {
68 return c;
69 } else {
70 return a;
71 }
72 } else if (compare(a, c)) {
73 return a;
74 } else if (compare(b, c)) {
75 return c;
76 } else {
77 return b;
78 }
79 }
80
81 inline int bitlog(int n) const {
82 int k;
83 for (k = 0; n != 1; n >>= 1) {
84 ++k;
85 }
86 return k;
87 }
88
89 /* Heap / Heapsort functions */
90
91 inline void push_heap(int p_first, int p_hole_idx, int p_top_index, T p_value, T *p_array) const {
92 int parent = (p_hole_idx - 1) / 2;
93 while (p_hole_idx > p_top_index && compare(p_array[p_first + parent], p_value)) {
94 p_array[p_first + p_hole_idx] = p_array[p_first + parent];
95 p_hole_idx = parent;
96 parent = (p_hole_idx - 1) / 2;
97 }
98 p_array[p_first + p_hole_idx] = p_value;
99 }
100
101 inline void pop_heap(int p_first, int p_last, int p_result, T p_value, T *p_array) const {
102 p_array[p_result] = p_array[p_first];
103 adjust_heap(p_first, 0, p_last - p_first, p_value, p_array);
104 }
105 inline void pop_heap(int p_first, int p_last, T *p_array) const {
106 pop_heap(p_first, p_last - 1, p_last - 1, p_array[p_last - 1], p_array);
107 }
108
109 inline void adjust_heap(int p_first, int p_hole_idx, int p_len, T p_value, T *p_array) const {
110 int top_index = p_hole_idx;
111 int second_child = 2 * p_hole_idx + 2;
112
113 while (second_child < p_len) {
114 if (compare(p_array[p_first + second_child], p_array[p_first + (second_child - 1)])) {
115 second_child--;
116 }
117
118 p_array[p_first + p_hole_idx] = p_array[p_first + second_child];
119 p_hole_idx = second_child;
120 second_child = 2 * (second_child + 1);
121 }
122
123 if (second_child == p_len) {
124 p_array[p_first + p_hole_idx] = p_array[p_first + (second_child - 1)];
125 p_hole_idx = second_child - 1;
126 }
127 push_heap(p_first, p_hole_idx, top_index, p_value, p_array);
128 }
129
130 inline void sort_heap(int p_first, int p_last, T *p_array) const {
131 while (p_last - p_first > 1) {
132 pop_heap(p_first, p_last--, p_array);
133 }
134 }
135
136 inline void make_heap(int p_first, int p_last, T *p_array) const {
137 if (p_last - p_first < 2) {
138 return;
139 }
140 int len = p_last - p_first;
141 int parent = (len - 2) / 2;
142
143 while (true) {
144 adjust_heap(p_first, parent, len, p_array[p_first + parent], p_array);
145 if (parent == 0) {
146 return;
147 }
148 parent--;
149 }
150 }
151
152 inline void partial_sort(int p_first, int p_last, int p_middle, T *p_array) const {
153 make_heap(p_first, p_middle, p_array);
154 for (int i = p_middle; i < p_last; i++) {
155 if (compare(p_array[i], p_array[p_first])) {
156 pop_heap(p_first, p_middle, i, p_array[i], p_array);
157 }
158 }
159 sort_heap(p_first, p_middle, p_array);
160 }
161
162 inline void partial_select(int p_first, int p_last, int p_middle, T *p_array) const {
163 make_heap(p_first, p_middle, p_array);
164 for (int i = p_middle; i < p_last; i++) {
165 if (compare(p_array[i], p_array[p_first])) {
166 pop_heap(p_first, p_middle, i, p_array[i], p_array);
167 }
168 }
169 }
170
171 inline int partitioner(int p_first, int p_last, T p_pivot, T *p_array) const {
172 const int unmodified_first = p_first;
173 const int unmodified_last = p_last;
174
175 while (true) {
176 while (compare(p_array[p_first], p_pivot)) {
177 if (Validate) {
178 ERR_BAD_COMPARE(p_first == unmodified_last - 1);
179 }
180 p_first++;
181 }
182 p_last--;
183 while (compare(p_pivot, p_array[p_last])) {
184 if (Validate) {
185 ERR_BAD_COMPARE(p_last == unmodified_first);
186 }
187 p_last--;
188 }
189
190 if (!(p_first < p_last)) {
191 return p_first;
192 }
193
194 SWAP(p_array[p_first], p_array[p_last]);
195 p_first++;
196 }
197 }
198
199 inline void introsort(int p_first, int p_last, T *p_array, int p_max_depth) const {
200 while (p_last - p_first > INTROSORT_THRESHOLD) {
201 if (p_max_depth == 0) {
202 partial_sort(p_first, p_last, p_last, p_array);
203 return;
204 }
205
206 p_max_depth--;
207
208 int cut = partitioner(
209 p_first,
210 p_last,
211 median_of_3(
212 p_array[p_first],
213 p_array[p_first + (p_last - p_first) / 2],
214 p_array[p_last - 1]),
215 p_array);
216
217 introsort(cut, p_last, p_array, p_max_depth);
218 p_last = cut;
219 }
220 }
221
222 inline void introselect(int p_first, int p_nth, int p_last, T *p_array, int p_max_depth) const {
223 while (p_last - p_first > 3) {
224 if (p_max_depth == 0) {
225 partial_select(p_first, p_nth + 1, p_last, p_array);
226 SWAP(p_first, p_nth);
227 return;
228 }
229
230 p_max_depth--;
231
232 int cut = partitioner(
233 p_first,
234 p_last,
235 median_of_3(
236 p_array[p_first],
237 p_array[p_first + (p_last - p_first) / 2],
238 p_array[p_last - 1]),
239 p_array);
240
241 if (cut <= p_nth) {
242 p_first = cut;
243 } else {
244 p_last = cut;
245 }
246 }
247
248 insertion_sort(p_first, p_last, p_array);
249 }
250
251 inline void unguarded_linear_insert(int p_last, T p_value, T *p_array) const {
252 int next = p_last - 1;
253 while (compare(p_value, p_array[next])) {
254 if (Validate) {
255 ERR_BAD_COMPARE(next == 0);
256 }
257 p_array[p_last] = p_array[next];
258 p_last = next;
259 next--;
260 }
261 p_array[p_last] = p_value;
262 }
263
264 inline void linear_insert(int p_first, int p_last, T *p_array) const {
265 T val = p_array[p_last];
266 if (compare(val, p_array[p_first])) {
267 for (int i = p_last; i > p_first; i--) {
268 p_array[i] = p_array[i - 1];
269 }
270
271 p_array[p_first] = val;
272 } else {
273 unguarded_linear_insert(p_last, val, p_array);
274 }
275 }
276
277 inline void insertion_sort(int p_first, int p_last, T *p_array) const {
278 if (p_first == p_last) {
279 return;
280 }
281 for (int i = p_first + 1; i != p_last; i++) {
282 linear_insert(p_first, i, p_array);
283 }
284 }
285
286 inline void unguarded_insertion_sort(int p_first, int p_last, T *p_array) const {
287 for (int i = p_first; i != p_last; i++) {
288 unguarded_linear_insert(i, p_array[i], p_array);
289 }
290 }
291
292 inline void final_insertion_sort(int p_first, int p_last, T *p_array) const {
293 if (p_last - p_first > INTROSORT_THRESHOLD) {
294 insertion_sort(p_first, p_first + INTROSORT_THRESHOLD, p_array);
295 unguarded_insertion_sort(p_first + INTROSORT_THRESHOLD, p_last, p_array);
296 } else {
297 insertion_sort(p_first, p_last, p_array);
298 }
299 }
300
301 inline void sort_range(int p_first, int p_last, T *p_array) const {
302 if (p_first != p_last) {
303 introsort(p_first, p_last, p_array, bitlog(p_last - p_first) * 2);
304 final_insertion_sort(p_first, p_last, p_array);
305 }
306 }
307
308 inline void sort(T *p_array, int p_len) const {
309 sort_range(0, p_len, p_array);
310 }
311
312 inline void nth_element(int p_first, int p_last, int p_nth, T *p_array) const {
313 if (p_first == p_last || p_nth == p_last) {
314 return;
315 }
316 introselect(p_first, p_nth, p_last, p_array, bitlog(p_last - p_first) * 2);
317 }
318};
319
320#endif // SORT_ARRAY_H
321