Functions
template<typename RangeValueType , typename SizeType , typename PredicateValueType , typename ProjectionType , typename SortPredicateType >
ULANG_FORCEINLINE SizeType	LowerBoundInternal (RangeValueType *First, const SizeType Num, const PredicateValueType &Value, ProjectionType Projection, SortPredicateType SortPredicate)

template<typename RangeValueType , typename SizeType , typename PredicateValueType , typename ProjectionType , typename SortPredicateType >
ULANG_FORCEINLINE SizeType	UpperBoundInternal (RangeValueType *First, const SizeType Num, const PredicateValueType &Value, ProjectionType Projection, SortPredicateType SortPredicate)

ULANG_FORCEINLINE int32_t	HeapGetLeftChildIndex (int32_t Index)

ULANG_FORCEINLINE bool	HeapIsLeaf (int32_t Index, int32_t Count)

ULANG_FORCEINLINE int32_t	HeapGetParentIndex (int32_t Index)

template<typename RangeValueType , typename ProjectionType , typename PredicateType >
ULANG_FORCEINLINE void	HeapSiftDown (RangeValueType *Heap, int32_t Index, const int32_t Count, const ProjectionType &Projection, const PredicateType &Predicate)

template<class RangeValueType , typename ProjectionType , class PredicateType >
ULANG_FORCEINLINE int32_t	HeapSiftUp (RangeValueType *Heap, int32_t RootIndex, int32_t NodeIndex, const ProjectionType &Projection, const PredicateType &Predicate)

template<typename RangeValueType , typename ProjectionType , typename PredicateType >
ULANG_FORCEINLINE void	HeapifyInternal (RangeValueType *First, int32_t Num, ProjectionType Projection, PredicateType Predicate)

template<typename RangeValueType , typename ProjectionType , class PredicateType >
void	HeapSortInternal (RangeValueType *First, int32_t Num, ProjectionType Projection, PredicateType Predicate)

template<typename T , typename ProjectionType , typename PredicateType >
void	IntroSortInternal (T *First, size_t Num, ProjectionType Projection, PredicateType Predicate)

template<typename T >
size_t	RotateInternal (T *First, size_t Num, size_t Count)

template<typename T , typename ProjectionType , typename PredicateType >
void	Merge (T *First, size_t Mid, size_t Num, ProjectionType Projection, PredicateType Predicate)

template<typename T , typename ProjectionType , typename PredicateType >
void	StableSortInternal (T *First, size_t Num, ProjectionType Projection, PredicateType Predicate)

Variables
constexpr size_t	MinMergeSubgroupSize = 2

Function Documentation

◆ HeapGetLeftChildIndex()

ULANG_FORCEINLINE int32_t uLang::AlgoImpl::HeapGetLeftChildIndex ( int32_t Index )

Gets the index of the left child of node at Index.

Parameters

Index Node for which the left child index is to be returned.

Returns: Index of the left child.

◆ HeapGetParentIndex()

ULANG_FORCEINLINE int32_t uLang::AlgoImpl::HeapGetParentIndex ( int32_t Index )

Gets the parent index for node at Index.

Parameters

Index node index.

Returns: Parent index.

◆ HeapifyInternal()

template<typename RangeValueType , typename ProjectionType , typename PredicateType >

ULANG_FORCEINLINE void uLang::AlgoImpl::HeapifyInternal	(	RangeValueType *	First,
		int32_t	Num,
		ProjectionType	Projection,
		PredicateType	Predicate
	)

Builds an implicit min-heap from a range of elements. This is the internal function used by Heapify overrides.

Parameters

First	pointer to the first element to heapify
Num	the number of items to heapify
Projection	The projection to apply to the elements.
Predicate	A binary predicate object used to specify if one element should precede another.

◆ HeapIsLeaf()

ULANG_FORCEINLINE bool uLang::AlgoImpl::HeapIsLeaf	(	int32_t	Index,
		int32_t	Count
	)

Checks if node located at Index is a leaf or not.

Parameters

Index Node index.

Returns: true if node is a leaf, false otherwise.

◆ HeapSiftDown()

template<typename RangeValueType , typename ProjectionType , typename PredicateType >

ULANG_FORCEINLINE void uLang::AlgoImpl::HeapSiftDown	(	RangeValueType *	Heap,
		int32_t	Index,
		const int32_t	Count,
		const ProjectionType &	Projection,
		const PredicateType &	Predicate
	)

Fixes a possible violation of order property between node at Index and a child.

Parameters

Heap	Pointer to the first element of a binary heap.
Index	Node index.
Count	Size of the heap.
Projection	The projection to apply to the elements.
Predicate	A binary predicate object used to specify if one element should precede another.

◆ HeapSiftUp()

template<class RangeValueType , typename ProjectionType , class PredicateType >

ULANG_FORCEINLINE int32_t uLang::AlgoImpl::HeapSiftUp	(	RangeValueType *	Heap,
		int32_t	RootIndex,
		int32_t	NodeIndex,
		const ProjectionType &	Projection,
		const PredicateType &	Predicate
	)

Fixes a possible violation of order property between node at NodeIndex and a parent.

Parameters

Heap	Pointer to the first element of a binary heap.
RootIndex	How far to go up?
NodeIndex	Node index.
Projection	The projection to apply to the elements.
Predicate	A binary predicate object used to specify if one element should precede another.

Returns: The new index of the node that was at NodeIndex

◆ HeapSortInternal()

template<typename RangeValueType , typename ProjectionType , class PredicateType >

void uLang::AlgoImpl::HeapSortInternal	(	RangeValueType *	First,
		int32_t	Num,
		ProjectionType	Projection,
		PredicateType	Predicate
	)

Performs heap sort on the elements. This is the internal sorting function used by HeapSort overrides.

Parameters

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

◆ IntroSortInternal()

template<typename T , typename ProjectionType , typename PredicateType >

void uLang::AlgoImpl::IntroSortInternal	(	T *	First,
		size_t	Num,
		ProjectionType	Projection,
		PredicateType	Predicate
	)

Implementation of an introspective sort. Starts with quick sort and switches to heap sort when the iteration depth is too big. The sort is unstable, meaning that the ordering of equal items is not necessarily preserved. This is the internal sorting function used by IntroSort overrides.

Parameters

First	pointer to the first element to sort
Num	the number of items to sort
Projection	The projection to sort by when applied to the element.
Predicate	predicate class

◆ LowerBoundInternal()

template<typename RangeValueType , typename SizeType , typename PredicateValueType , typename ProjectionType , typename SortPredicateType >

ULANG_FORCEINLINE SizeType uLang::AlgoImpl::LowerBoundInternal	(	RangeValueType *	First,
		const SizeType	Num,
		const PredicateValueType &	Value,
		ProjectionType	Projection,
		SortPredicateType	SortPredicate
	)

Performs binary search, resulting in position of the first element >= Value

Parameters

First	Pointer to array
Num	Number of elements in array
Value	Value to look for
Projection	Called on values in array to get type that can be compared to Value
SortPredicate	Predicate for sort comparison

Returns: Position of the first element >= Value, may be == Num

◆ Merge()

template<typename T , typename ProjectionType , typename PredicateType >

void uLang::AlgoImpl::Merge	(	T *	First,
		size_t	Mid,
		size_t	Num,
		ProjectionType	Projection,
		PredicateType	Predicate
	)

◆ RotateInternal()

template<typename T >

size_t uLang::AlgoImpl::RotateInternal	(	T *	First,
		size_t	Num,
		size_t	Count
	)

◆ StableSortInternal()

template<typename T , typename ProjectionType , typename PredicateType >

void uLang::AlgoImpl::StableSortInternal	(	T *	First,
		size_t	Num,
		ProjectionType	Projection,
		PredicateType	Predicate
	)

Sort elements using user defined projection and predicate classes. The sort is stable, meaning that the ordering of equal items is preserved. This is the internal sorting function used by the Algo::Sort overloads.

Parameters

First	Pointer to the first element to sort.
Num	The number of items to sort.
Projection	A projection to apply to each element to get the value to sort by.
Predicate	A predicate class which compares two projected elements and returns whether one occurs before the other.

◆ UpperBoundInternal()

template<typename RangeValueType , typename SizeType , typename PredicateValueType , typename ProjectionType , typename SortPredicateType >

ULANG_FORCEINLINE SizeType uLang::AlgoImpl::UpperBoundInternal	(	RangeValueType *	First,
		const SizeType	Num,
		const PredicateValueType &	Value,
		ProjectionType	Projection,
		SortPredicateType	SortPredicate
	)

Performs binary search, resulting in position of the first element that is larger than the given value

Parameters

First	Pointer to array
Num	Number of elements in array
Value	Value to look for
SortPredicate	Predicate for sort comparison

Returns: Position of the first element > Value, may be == Num

Variable Documentation

◆ MinMergeSubgroupSize

constexpr size_t uLang::AlgoImpl::MinMergeSubgroupSize = 2

inlineconstexpr

Functions

Variables

Function Documentation

◆ HeapGetLeftChildIndex()

◆ HeapGetParentIndex()

◆ HeapifyInternal()

◆ HeapIsLeaf()

◆ HeapSiftDown()

◆ HeapSiftUp()

◆ HeapSortInternal()

◆ IntroSortInternal()

◆ LowerBoundInternal()

◆ Merge()

◆ RotateInternal()

◆ StableSortInternal()

◆ UpperBoundInternal()

Variable Documentation

◆ MinMergeSubgroupSize