Bullet Collision Detection & Physics Library
Classes
gim_radixsort.h File Reference
#include "gim_memory.h"
Include dependency graph for gim_radixsort.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  less_comparator
 Macros for sorting. More...
 
class  integer_comparator
 Prototype for comparators. More...
 
class  uint_key_func
 Prototype for getting the integer representation of an object. More...
 
class  copy_elements_func
 Prototype for copying elements. More...
 
class  memcopy_elements_func
 Prototype for copying elements. More...
 
struct  GIM_RSORT_TOKEN
 
class  GIM_RSORT_TOKEN_COMPARATOR
 Prototype for comparators. More...
 
#define kHist   2048
 
#define D11_0(x)   (x & 0x7FF)
 
#define D11_1(x)   (x >> 11 & 0x7FF)
 
#define D11_2(x)   (x >> 22)
 
void gim_radix_sort_rtokens (GIM_RSORT_TOKEN *array, GIM_RSORT_TOKEN *sorted, GUINT element_count)
 Radix sort for unsigned integer keys. More...
 
template<typename T , class GETKEY_CLASS >
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. More...
 
template<typename T , class GETKEY_CLASS , class COPY_CLASS >
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. More...
 
template<class T , typename KEYCLASS , typename COMP_CLASS >
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,. More...
 
template<class T >
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. More...
 
template<typename T , typename COMP_CLASS >
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/ More...
 
template<typename T , typename COMP_CLASS >
void gim_heap_sort (T *pArr, GUINT element_count, COMP_CLASS CompareFunc)
 

Detailed Description

Author
Francisco Leon Najera. Based on the work of Michael Herf : "fast floating-point radix sort" Avaliable on http://www.stereopsis.com/radix.html

Definition in file gim_radixsort.h.

Macro Definition Documentation

◆ D11_0

#define D11_0 (   x)    (x & 0x7FF)

Definition at line 132 of file gim_radixsort.h.

◆ D11_1

#define D11_1 (   x)    (x >> 11 & 0x7FF)

Definition at line 133 of file gim_radixsort.h.

◆ D11_2

#define D11_2 (   x)    (x >> 22)

Definition at line 134 of file gim_radixsort.h.

◆ kHist

#define kHist   2048

Definition at line 130 of file gim_radixsort.h.

Function Documentation

◆ gim_binary_search()

template<class T >
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.

If the element is not found, it returns the nearest upper element position, may be the further position after the last element.

Parameters
_array
_start_ithe beginning of the array
_end_ithe ending index of the array
_search_keyValue to find
_result_indexthe index of the found element, or if not found then it will get the index of the closest bigger value
Returns
true if found, else false

Definition at line 304 of file gim_radixsort.h.

◆ gim_binary_search_ex()

template<class T , typename KEYCLASS , typename COMP_CLASS >
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,.

If the element is not found, it returns the nearest upper element position, may be the further position after the last element.

Parameters
_array
_start_ithe beginning of the array
_end_ithe ending index of the array
_search_keyValue to find
_comp_macromacro for comparing elements
_foundIf true the value has found. Boolean
_result_indexthe index of the found element, or if not found then it will get the index of the closest bigger value

Definition at line 261 of file gim_radixsort.h.

◆ gim_down_heap()

template<typename T , typename COMP_CLASS >
void gim_down_heap ( T *  pArr,
GUINT  k,
GUINT  n,
COMP_CLASS  CompareFunc 
)

◆ gim_heap_sort()

template<typename T , typename COMP_CLASS >
void gim_heap_sort ( T *  pArr,
GUINT  element_count,
COMP_CLASS  CompareFunc 
)

Definition at line 366 of file gim_radixsort.h.

◆ gim_radix_sort()

template<typename T , class GETKEY_CLASS , class COPY_CLASS >
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.

Parameters
typeType of the array
array
element_count
get_uintkey_macroMacro for extract the Integer value of the element. Similar to SIMPLE_GET_UINTKEY
copy_elements_macroMacro for copy elements, similar to SIMPLE_COPY_ELEMENTS

Definition at line 233 of file gim_radixsort.h.

◆ gim_radix_sort_array_tokens()

template<typename T , class GETKEY_CLASS >
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.

Parameters
arrayArray of elements to sort
sorted_tokensTokens of sorted elements
element_countelement count
uintkey_macroFunctor which retrieves the integer representation of an array element

Definition at line 208 of file gim_radixsort.h.

◆ gim_radix_sort_rtokens()

void gim_radix_sort_rtokens ( GIM_RSORT_TOKEN array,
GIM_RSORT_TOKEN sorted,
GUINT  element_count 
)
inline

Radix sort for unsigned integer keys.

Definition at line 137 of file gim_radixsort.h.