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