Sorting.h File Reference

#include "CoreTypes.h"
#include "Algo/BinarySearch.h"
#include "Algo/Sort.h"
#include "HAL/PlatformMath.h"
#include "Templates/Less.h"

Go to the source code of this file.

Classes
struct	TDereferenceWrapper< T, PREDICATE_CLASS >
struct	TDereferenceWrapper< T *, PREDICATE_CLASS >
struct	TArrayRange< T >
struct	TIsContiguousContainer< TArrayRange< T > >
class	FEuclidDivisionGCD
class	TJugglingRotation< TGCDPolicy >
class	TRotationInPlaceMerge< TRotationPolicy >
class	TMergeSort< TMergePolicy, MinMergeSubgroupSize >
struct	TRadixSortKeyCastUint32< T >
struct	FRadixSortKeyFloat
struct	TRadixSortKeyCastUint64< T >

Enumerations
enum class	ERadixSortBufferState { IsInitialized , IsUninitialized }

Functions
template<class T , class PREDICATE_CLASS >
void	Sort (T *First, const int32 Num, const PREDICATE_CLASS &Predicate)
template<class T , class PREDICATE_CLASS >
void	Sort (T **First, const int32 Num, const PREDICATE_CLASS &Predicate)
template<class T >
void	Sort (T *First, const int32 Num)
template<class T >
void	Sort (T **First, const int32 Num)
template<class T , class PREDICATE_CLASS >
void	Merge (T *Out, T *In, const int32 Mid, const int32 Num, const PREDICATE_CLASS &Predicate)
template<class T , class PREDICATE_CLASS >
void	StableSortInternal (T *First, const int32 Num, const PREDICATE_CLASS &Predicate)
template<class T , class PREDICATE_CLASS >
void	StableSort (T *First, const int32 Num, const PREDICATE_CLASS &Predicate)
template<class T , class PREDICATE_CLASS >
void	StableSort (T **First, const int32 Num, const PREDICATE_CLASS &Predicate)
template<class T >
void	StableSort (T *First, const int32 Num)
template<class T >
void	StableSort (T **First, const int32 Num)
template<typename ValueType , typename CountType , class SortKeyClass >
void	RadixSort32 (ValueType *RESTRICT Dst, ValueType *RESTRICT Src, CountType Num, const SortKeyClass &SortKey)
template<typename ValueType , typename CountType >
void	RadixSort32 (ValueType *RESTRICT Dst, ValueType *RESTRICT Src, CountType Num)
template<typename CountType >
void	RadixSort32 (float *RESTRICT Dst, float *RESTRICT Src, CountType Num)
template<ERadixSortBufferState BufferState, typename ValueType , typename CountType , class SortKeyClass >
void	RadixSort64 (ValueType *RESTRICT Array, ValueType *RESTRICT Buffer, CountType Num, const SortKeyClass &SortKey)
template<ERadixSortBufferState BufferState, typename ValueType , typename CountType >
void	RadixSort64 (ValueType *RESTRICT Array, ValueType *RESTRICT Buffer, CountType Num)
template<typename ValueType , typename CountType , class SortKeyClass >
void	RadixSort64 (ValueType *RESTRICT Array, CountType Num, const SortKeyClass &SortKey)
template<typename ValueType , typename CountType >
void	RadixSort64 (ValueType *RESTRICT Array, CountType Num)

Enumeration Type Documentation

ERadixSortBufferState

enum class ERadixSortBufferState

strong

Enumerator
IsInitialized
IsUninitialized

Function Documentation

Merge()

template<class T , class PREDICATE_CLASS >

void Merge	(	T *	Out,
		T *	In,
		const int32	Mid,
		const int32	Num,
		const PREDICATE_CLASS &	Predicate
	)

Stable merge to perform sort below. Stable sort is slower than non-stable algorithm.

Parameters

Out	Pointer to the first element of output array.
In	Pointer to the first element to sort.
Mid	Middle point of the table, i.e. merge separator.
Num	Number of elements in the whole table.
Predicate	Predicate class.

RadixSort32() [1/3]

template<typename CountType >

void RadixSort32	(	float *RESTRICT	Dst,
		float *RESTRICT	Src,
		CountType	Num
	)

RadixSort32() [2/3]

template<typename ValueType , typename CountType >

void RadixSort32	(	ValueType *RESTRICT	Dst,
		ValueType *RESTRICT	Src,
		CountType	Num
	)

RadixSort32() [3/3]

template<typename ValueType , typename CountType , class SortKeyClass >

void RadixSort32	(	ValueType *RESTRICT	Dst,
		ValueType *RESTRICT	Src,
		CountType	Num,
		const SortKeyClass &	SortKey
	)

Very fast 32bit radix sort. SortKeyClass defines operator() that takes ValueType and returns a uint32. Sorting based on key. No comparisons. Is stable. Use a smaller CountType for smaller histograms.

RadixSort64() [1/4]

template<typename ValueType , typename CountType >

void RadixSort64	(	ValueType *RESTRICT	Array,
		CountType	Num
	)

RadixSort64() [2/4]

template<typename ValueType , typename CountType , class SortKeyClass >

void RadixSort64	(	ValueType *RESTRICT	Array,
		CountType	Num,
		const SortKeyClass &	SortKey
	)

RadixSort64() [3/4]

template<ERadixSortBufferState BufferState, typename ValueType , typename CountType >

void RadixSort64	(	ValueType *RESTRICT	Array,
		ValueType *RESTRICT	Buffer,
		CountType	Num
	)

RadixSort64() [4/4]

template<ERadixSortBufferState BufferState, typename ValueType , typename CountType , class SortKeyClass >

void RadixSort64	(	ValueType *RESTRICT	Array,
		ValueType *RESTRICT	Buffer,
		CountType	Num,
		const SortKeyClass &	SortKey
	)

Very fast 64bit radix sort. SortKeyClass defines operator() that takes ValueType and returns a uint32. Sorting based on key. No comparisons. Is stable. The default takes up 40k of stack space. Use a smaller CountType for smaller histograms and less stack space. Buffer needs to be able to hold at least Num elements.

Sort() [1/4]

template<class T >

void Sort	(	T **	First,
		const int32	Num
	)

Specialized version of the above Sort function for pointers to elements.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort

Sort() [2/4]

template<class T , class PREDICATE_CLASS >

void Sort	(	T **	First,
		const int32	Num,
		const PREDICATE_CLASS &	Predicate
	)

Specialized version of the above Sort function for pointers to elements.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort
Predicate	predicate class

Sort() [3/4]

template<class T >

void Sort	(	T *	First,
		const int32	Num
	)

Sort elements. The sort is unstable, meaning that the ordering of equal items is not necessarily preserved. Assumes < operator is defined for the template type.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort

Sort() [4/4]

template<class T , class PREDICATE_CLASS >

void Sort	(	T *	First,
		const int32	Num,
		const PREDICATE_CLASS &	Predicate
	)

Sort elements using user defined predicate class. The sort is unstable, meaning that the ordering of equal items is not necessarily preserved.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort
Predicate	predicate class

StableSort() [1/4]

template<class T >

void StableSort	(	T **	First,
		const int32	Num
	)

Specialized version of the above StableSort function for pointers to elements. Stable sort is slower than non-stable algorithm.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort

StableSort() [2/4]

template<class T , class PREDICATE_CLASS >

void StableSort	(	T **	First,
		const int32	Num,
		const PREDICATE_CLASS &	Predicate
	)

Specialized version of the above StableSort function for pointers to elements. Stable sort is slower than non-stable algorithm.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort
Predicate	predicate class

StableSort() [3/4]

template<class T >

void StableSort	(	T *	First,
		const int32	Num
	)

Stable sort elements. The sort is stable, meaning that the ordering of equal items is preserved, but it's slower than non-stable algorithm.

Assumes < operator is defined for the template type.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort

StableSort() [4/4]

template<class T , class PREDICATE_CLASS >

void StableSort	(	T *	First,
		const int32	Num,
		const PREDICATE_CLASS &	Predicate
	)

Stable sort elements using user defined predicate class. The sort is stable, meaning that the ordering of equal items is preserved, but it's slower than non-stable algorithm.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort
Predicate	predicate class

StableSortInternal()

template<class T , class PREDICATE_CLASS >

void StableSortInternal	(	T *	First,
		const int32	Num,
		const PREDICATE_CLASS &	Predicate
	)

Stable sort elements using user defined predicate class. The sort is stable, meaning that the ordering of equal items is preserved, but it's slower than non-stable algorithm.

This is the internal sorting function used by StableSort overrides.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort
Predicate	predicate class