Bullet Collision Detection & Physics Library
gim_radixsort.h
Go to the documentation of this file.
1#ifndef GIM_RADIXSORT_H_INCLUDED
2#define GIM_RADIXSORT_H_INCLUDED
8/*
9-----------------------------------------------------------------------------
10This source file is part of GIMPACT Library.
11
12For the latest info, see http://gimpact.sourceforge.net/
13
14Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
15email: projectileman@yahoo.com
16
17 This library is free software; you can redistribute it and/or
18 modify it under the terms of EITHER:
19 (1) The GNU Lesser General Public License as published by the Free
20 Software Foundation; either version 2.1 of the License, or (at
21 your option) any later version. The text of the GNU Lesser
22 General Public License is included with this library in the
23 file GIMPACT-LICENSE-LGPL.TXT.
24 (2) The BSD-style license that is included with this library in
25 the file GIMPACT-LICENSE-BSD.TXT.
26 (3) The zlib/libpng license that is included with this library in
27 the file GIMPACT-LICENSE-ZLIB.TXT.
28
29 This library is distributed in the hope that it will be useful,
30 but WITHOUT ANY WARRANTY; without even the implied warranty of
31 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
32 GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.
33
34-----------------------------------------------------------------------------
35*/
36
37#include "gim_memory.h"
38
42{
43 public:
44
45 template<class T,class Z>
46 inline int operator() ( const T& a, const Z& b )
47 {
48 return ( a<b?-1:(a>b?1:0));
49 }
50};
51
54{
55 public:
56
57 template<class T>
58 inline int operator() ( const T& a, const T& b )
59 {
60 return (int)(a-b);
61 }
62};
63
66{
67public:
68 template<class T>
69 inline GUINT operator()( const T& a)
70 {
71 return (GUINT)a;
72 }
73};
74
75
78{
79public:
80 template<class T>
81 inline void operator()(T& a,T& b)
82 {
83 a = b;
84 }
85};
86
89{
90public:
91 template<class T>
92 inline void operator()(T& a,T& b)
93 {
94 gim_simd_memcpy(&a,&b,sizeof(T));
95 }
96};
97
98
101{
105 {
106 }
108 {
109 m_key = rtoken.m_key;
110 m_value = rtoken.m_value;
111 }
112
113 inline bool operator <(const GIM_RSORT_TOKEN& other) const
114 {
115 return (m_key < other.m_key);
116 }
117
118 inline bool operator >(const GIM_RSORT_TOKEN& other) const
119 {
120 return (m_key > other.m_key);
121 }
122};
123
126{
127 public:
128
129 inline int operator()( const GIM_RSORT_TOKEN& a, const GIM_RSORT_TOKEN& b )
130 {
131 return (int)((a.m_key) - (b.m_key));
132 }
133};
134
135
136
137#define kHist 2048
138// ---- utils for accessing 11-bit quantities
139#define D11_0(x) (x & 0x7FF)
140#define D11_1(x) (x >> 11 & 0x7FF)
141#define D11_2(x) (x >> 22 )
142
143
144
147 GIM_RSORT_TOKEN * array,
148 GIM_RSORT_TOKEN * sorted, GUINT element_count)
149{
150 GUINT i;
151 GUINT b0[kHist * 3];
152 GUINT *b1 = b0 + kHist;
153 GUINT *b2 = b1 + kHist;
154 for (i = 0; i < kHist * 3; ++i)
155 {
156 b0[i] = 0;
157 }
158 GUINT fi;
159 GUINT pos;
160 for (i = 0; i < element_count; ++i)
161 {
162 fi = array[i].m_key;
163 b0[D11_0(fi)] ++;
164 b1[D11_1(fi)] ++;
165 b2[D11_2(fi)] ++;
166 }
167 {
168 GUINT sum0 = 0, sum1 = 0, sum2 = 0;
169 GUINT tsum;
170 for (i = 0; i < kHist; ++i)
171 {
172 tsum = b0[i] + sum0;
173 b0[i] = sum0 - 1;
174 sum0 = tsum;
175 tsum = b1[i] + sum1;
176 b1[i] = sum1 - 1;
177 sum1 = tsum;
178 tsum = b2[i] + sum2;
179 b2[i] = sum2 - 1;
180 sum2 = tsum;
181 }
182 }
183 for (i = 0; i < element_count; ++i)
184 {
185 fi = array[i].m_key;
186 pos = D11_0(fi);
187 pos = ++b0[pos];
188 sorted[pos].m_key = array[i].m_key;
189 sorted[pos].m_value = array[i].m_value;
190 }
191 for (i = 0; i < element_count; ++i)
192 {
193 fi = sorted[i].m_key;
194 pos = D11_1(fi);
195 pos = ++b1[pos];
196 array[pos].m_key = sorted[i].m_key;
197 array[pos].m_value = sorted[i].m_value;
198 }
199 for (i = 0; i < element_count; ++i)
200 {
201 fi = array[i].m_key;
202 pos = D11_2(fi);
203 pos = ++b2[pos];
204 sorted[pos].m_key = array[i].m_key;
205 sorted[pos].m_value = array[i].m_value;
206 }
207}
208
209
210
211
213
219template<typename T, class GETKEY_CLASS>
221 T* array ,
222 GIM_RSORT_TOKEN * sorted_tokens,
223 GUINT element_count,GETKEY_CLASS uintkey_macro)
224{
225 GIM_RSORT_TOKEN * _unsorted = (GIM_RSORT_TOKEN *) gim_alloc(sizeof(GIM_RSORT_TOKEN)*element_count);
226 for (GUINT _i=0;_i<element_count;++_i)
227 {
228 _unsorted[_i].m_key = uintkey_macro(array[_i]);
229 _unsorted[_i].m_value = _i;
230 }
231 gim_radix_sort_rtokens(_unsorted,sorted_tokens,element_count);
232 gim_free(_unsorted);
233 gim_free(_unsorted);
234}
235
237
244template<typename T, class GETKEY_CLASS, class COPY_CLASS>
246 T * array, GUINT element_count,
247 GETKEY_CLASS get_uintkey_macro, COPY_CLASS copy_elements_macro)
248{
249 GIM_RSORT_TOKEN * _sorted = (GIM_RSORT_TOKEN *) gim_alloc(sizeof(GIM_RSORT_TOKEN)*element_count);
250 gim_radix_sort_array_tokens(array,_sorted,element_count,get_uintkey_macro);
251 T * _original_array = (T *) gim_alloc(sizeof(T)*element_count);
252 gim_simd_memcpy(_original_array,array,sizeof(T)*element_count);
253 for (GUINT _i=0;_i<element_count;++_i)
254 {
255 copy_elements_macro(array[_i],_original_array[_sorted[_i].m_value]);
256 }
257 gim_free(_original_array);
258 gim_free(_sorted);
259}
260
262
272template<class T, typename KEYCLASS, typename COMP_CLASS>
274 const T* _array, GUINT _start_i,
275 GUINT _end_i,GUINT & _result_index,
276 const KEYCLASS & _search_key,
277 COMP_CLASS _comp_macro)
278{
279 GUINT _k;
280 int _comp_result;
281 GUINT _i = _start_i;
282 GUINT _j = _end_i+1;
283 while (_i < _j)
284 {
285 _k = (_j+_i-1)/2;
286 _comp_result = _comp_macro(_array[_k], _search_key);
287 if (_comp_result == 0)
288 {
289 _result_index = _k;
290 return true;
291 }
292 else if (_comp_result < 0)
293 {
294 _i = _k+1;
295 }
296 else
297 {
298 _j = _k;
299 }
300 }
301 _result_index = _i;
302 return false;
303}
304
305
306
308
317template<class T>
319 const T*_array,GUINT _start_i,
320 GUINT _end_i,const T & _search_key,
321 GUINT & _result_index)
322{
323 GUINT _i = _start_i;
324 GUINT _j = _end_i+1;
325 GUINT _k;
326 while(_i < _j)
327 {
328 _k = (_j+_i-1)/2;
329 if(_array[_k]==_search_key)
330 {
331 _result_index = _k;
332 return true;
333 }
334 else if (_array[_k]<_search_key)
335 {
336 _i = _k+1;
337 }
338 else
339 {
340 _j = _k;
341 }
342 }
343 _result_index = _i;
344 return false;
345}
346
347
348
350template <typename T, typename COMP_CLASS>
351void gim_down_heap(T *pArr, GUINT k, GUINT n,COMP_CLASS CompareFunc)
352{
353 /* PRE: a[k+1..N] is a heap */
354 /* POST: a[k..N] is a heap */
355
356 T temp = pArr[k - 1];
357 /* k has child(s) */
358 while (k <= n/2)
359 {
360 int child = 2*k;
361
362 if ((child < (int)n) && CompareFunc(pArr[child - 1] , pArr[child])<0)
363 {
364 child++;
365 }
366 /* pick larger child */
367 if (CompareFunc(temp , pArr[child - 1])<0)
368 {
369 /* move child up */
370 pArr[k - 1] = pArr[child - 1];
371 k = child;
372 }
373 else
374 {
375 break;
376 }
377 }
378 pArr[k - 1] = temp;
379} /*downHeap*/
380
381
382template <typename T, typename COMP_CLASS>
383void gim_heap_sort(T *pArr, GUINT element_count, COMP_CLASS CompareFunc)
384{
385 /* sort a[0..N-1], N.B. 0 to N-1 */
386 GUINT k;
387 GUINT n = element_count;
388 for (k = n/2; k > 0; k--)
389 {
390 gim_down_heap(pArr, k, n, CompareFunc);
391 }
392
393 /* a[1..N] is now a heap */
394 while ( n>=2 )
395 {
396 gim_swap_elements(pArr,0,n-1); /* largest of a[0..n-1] */
397 --n;
398 /* restore a[1..i-1] heap */
399 gim_down_heap(pArr, 1, n, CompareFunc);
400 }
401}
402
403
404
405
406#endif // GIM_RADIXSORT_H_INCLUDED
Prototype for comparators.
int operator()(const GIM_RSORT_TOKEN &a, const GIM_RSORT_TOKEN &b)
Prototype for copying elements.
Definition: gim_radixsort.h:78
void operator()(T &a, T &b)
Definition: gim_radixsort.h:81
Prototype for comparators.
Definition: gim_radixsort.h:54
int operator()(const T &a, const T &b)
Definition: gim_radixsort.h:58
Macros for sorting.
Definition: gim_radixsort.h:42
int operator()(const T &a, const Z &b)
Definition: gim_radixsort.h:46
Prototype for copying elements.
Definition: gim_radixsort.h:89
void operator()(T &a, T &b)
Definition: gim_radixsort.h:92
Prototype for getting the integer representation of an object.
Definition: gim_radixsort.h:66
GUINT operator()(const T &a)
Definition: gim_radixsort.h:69
#define GUINT
Definition: gim_math.h:42
void * gim_alloc(size_t size)
Standar Memory functions.
Definition: gim_memory.cpp:86
void gim_free(void *ptr)
Definition: gim_memory.cpp:119
void gim_simd_memcpy(void *dst, const void *src, size_t copysize)
Definition: gim_memory.h:130
void gim_swap_elements(T *_array, size_t _i, size_t _j)
Definition: gim_memory.h:162
bool gim_binary_search(const T *_array, GUINT _start_i, GUINT _end_i, const T &_search_key, GUINT &_result_index)
Failsafe Iterative binary search,Template version.
#define D11_1(x)
void gim_heap_sort(T *pArr, GUINT element_count, COMP_CLASS CompareFunc)
void gim_radix_sort_array_tokens(T *array, GIM_RSORT_TOKEN *sorted_tokens, GUINT element_count, GETKEY_CLASS uintkey_macro)
Get the sorted tokens from an array. For generic use. Tokens are IRR_RSORT_TOKEN.
bool gim_binary_search_ex(const T *_array, GUINT _start_i, GUINT _end_i, GUINT &_result_index, const KEYCLASS &_search_key, COMP_CLASS _comp_macro)
Failsafe Iterative binary search,.
#define kHist
#define D11_2(x)
void gim_down_heap(T *pArr, GUINT k, GUINT n, COMP_CLASS CompareFunc)
heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/
void gim_radix_sort_rtokens(GIM_RSORT_TOKEN *array, GIM_RSORT_TOKEN *sorted, GUINT element_count)
Radix sort for unsigned integer keys.
void gim_radix_sort(T *array, GUINT element_count, GETKEY_CLASS get_uintkey_macro, COPY_CLASS copy_elements_macro)
Sorts array in place. For generic use.
#define D11_0(x)
bool operator<(const GIM_RSORT_TOKEN &other) const
GIM_RSORT_TOKEN(const GIM_RSORT_TOKEN &rtoken)
bool operator>(const GIM_RSORT_TOKEN &other) const