Blender V2.61 - r43446
Classes

gim_radixsort.h File Reference

#include "gim_memory.h"

Go to the source code of this file.

Classes

class  less_comparator
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
 Radix sort for unsigned integer keys.
#define D11_0(x)   (x & 0x7FF)
 Radix sort for unsigned integer keys.
#define D11_1(x)   (x >> 11 & 0x7FF)
 Radix sort for unsigned integer keys.
#define D11_2(x)   (x >> 22 )
 Radix sort for unsigned integer keys.
void gim_radix_sort_rtokens (GIM_RSORT_TOKEN *array, GIM_RSORT_TOKEN *sorted, GUINT element_count)
 Radix sort for unsigned integer keys.
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.
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.
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,.
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.
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/
template<typename T , typename COMP_CLASS >
void gim_heap_sort (T *pArr, GUINT element_count, COMP_CLASS CompareFunc)
 Radix sort for unsigned integer keys.

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.

Define Documentation

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

Radix sort for unsigned integer keys.

Definition at line 139 of file gim_radixsort.h.

Referenced by gim_radix_sort_rtokens().

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

Radix sort for unsigned integer keys.

Definition at line 140 of file gim_radixsort.h.

Referenced by gim_radix_sort_rtokens().

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

Radix sort for unsigned integer keys.

Definition at line 141 of file gim_radixsort.h.

Referenced by gim_radix_sort_rtokens().

#define kHist   2048

Radix sort for unsigned integer keys.

Definition at line 137 of file gim_radixsort.h.

Referenced by gim_radix_sort_rtokens().

Function Documentation

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 318 of file gim_radixsort.h.

References GUINT.

Referenced by gim_next_prime().

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 273 of file gim_radixsort.h.

References GUINT.

Referenced by gim_hash_table< T >::_insert_sorted(), gim_hash_table< T >::_insert_sorted_replace(), and gim_hash_table< T >::find().

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/

Definition at line 351 of file gim_radixsort.h.

References T.

Referenced by gim_heap_sort().

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

Radix sort for unsigned integer keys.

Definition at line 383 of file gim_radixsort.h.

References gim_down_heap(), gim_swap_elements(), and GUINT.

Referenced by gim_sort_hash_node_array(), and gim_contact_array::merge_contacts().

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 245 of file gim_radixsort.h.

References gim_alloc(), gim_free(), gim_radix_sort_array_tokens(), gim_simd_memcpy(), GUINT, and T.

Referenced by gim_sort_hash_node_array().

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 220 of file gim_radixsort.h.

References gim_alloc(), gim_free(), gim_radix_sort_rtokens(), GUINT, GIM_RSORT_TOKEN::m_key, and GIM_RSORT_TOKEN::m_value.

Referenced by gim_radix_sort().

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 146 of file gim_radixsort.h.

References D11_0, D11_1, D11_2, GUINT, i, kHist, GIM_RSORT_TOKEN::m_key, and GIM_RSORT_TOKEN::m_value.

Referenced by gim_radix_sort_array_tokens().

Generated on Tue Jan 17 2012 14:38:07 for Blender by  doxygen 1.7.3