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
3 
8 /*
9 -----------------------------------------------------------------------------
10 This source file is part of GIMPACT Library.
11 
12 For the latest info, see http://gimpact.sourceforge.net/
13 
14 Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
15 email: 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 {
67 public:
68  template<class T>
69  inline GUINT operator()( const T& a)
70  {
71  return (GUINT)a;
72  }
73 };
74 
75 
78 {
79 public:
80  template<class T>
81  inline void operator()(T& a,T& b)
82  {
83  a = b;
84  }
85 };
86 
89 {
90 public:
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 
219 template<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 
244 template<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 
272 template<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 
317 template<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 
350 template <typename T, typename COMP_CLASS>
351 void 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 
382 template <typename T, typename COMP_CLASS>
383 void 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
void gim_simd_memcpy(void *dst, const void *src, size_t copysize)
Definition: gim_memory.h:130
Prototype for copying elements.
Definition: gim_radixsort.h:88
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/
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.
void operator()(T &a, T &b)
Definition: gim_radixsort.h:92
Prototype for comparators.
Definition: gim_radixsort.h:53
void gim_heap_sort(T *pArr, GUINT element_count, COMP_CLASS CompareFunc)
#define D11_0(x)
void gim_free(void *ptr)
Definition: gim_memory.cpp:119
int operator()(const GIM_RSORT_TOKEN &a, const GIM_RSORT_TOKEN &b)
void operator()(T &a, T &b)
Definition: gim_radixsort.h:81
GIM_RSORT_TOKEN(const GIM_RSORT_TOKEN &rtoken)
void gim_radix_sort_rtokens(GIM_RSORT_TOKEN *array, GIM_RSORT_TOKEN *sorted, GUINT element_count)
Radix sort for unsigned integer keys.
Prototype for getting the integer representation of an object.
Definition: gim_radixsort.h:65
#define D11_2(x)
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,.
Prototype for comparators.
void gim_swap_elements(T *_array, size_t _i, size_t _j)
Definition: gim_memory.h:162
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.
void * gim_alloc(size_t size)
Standar Memory functions.
Definition: gim_memory.cpp:86
#define kHist
GUINT operator()(const T &a)
Definition: gim_radixsort.h:69
#define GUINT
Definition: gim_math.h:42
int operator()(const T &a, const Z &b)
Definition: gim_radixsort.h:46
#define D11_1(x)
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. ...
Prototype for copying elements.
Definition: gim_radixsort.h:77
Macros for sorting.
Definition: gim_radixsort.h:41