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

#define D11_0

(

x

)

(x & 0x7FF)

Definition at line 139 of file gim_radixsort.h.

#define D11_1

(

x

)

(x >> 11 & 0x7FF)

Definition at line 140 of file gim_radixsort.h.

#define D11_2

(

x

)

(x >> 22 )

Definition at line 141 of file gim_radixsort.h.

#define kHist   2048

Definition at line 137 of file gim_radixsort.h.

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_i	the beginning of the array
_end_i	the ending index of the array
_search_key	Value to find
_result_index	the 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.

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_i	the beginning of the array
_end_i	the ending index of the array
_search_key	Value to find
_comp_macro	macro for comparing elements
_found	If true the value has found. Boolean
_result_index	the 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.

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.

template<typename T , typename COMP_CLASS >

void gim_heap_sort	(	T *	pArr,
		GUINT	element_count,
		COMP_CLASS	CompareFunc
	)

Definition at line 383 of file gim_radixsort.h.

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

type	Type of the array
array
element_count
get_uintkey_macro	Macro for extract the Integer value of the element. Similar to SIMPLE_GET_UINTKEY
copy_elements_macro	Macro for copy elements, similar to SIMPLE_COPY_ELEMENTS

Definition at line 245 of file gim_radixsort.h.

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

array	Array of elements to sort
sorted_tokens	Tokens of sorted elements
element_count	element count
uintkey_macro	Functor which retrieves the integer representation of an array element

Definition at line 220 of file gim_radixsort.h.

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.