#include "gim_memory.h"

Include dependency graph for gim_radixsort.h:

This graph shows which files directly or indirectly include 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.

Classes

Detailed Description

Macro Definition Documentation

Function Documentation