Classes
struct	FKahnContext

struct	FMutuallyReachableVertexSetContext

struct	TLess

struct	TRangePointerType

struct	TRangePointerType< T[N]>

Typedefs
typedef int32	FKahnHandle

Functions
template<typename RangeValueType , typename SizeType , typename PredicateValueType , typename ProjectionType , typename SortPredicateType >
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 >
SizeType	UpperBoundInternal (RangeValueType *First, const SizeType Num, const PredicateValueType &Value, ProjectionType Projection, SortPredicateType SortPredicate)

template<typename RangeType , typename ValueType , typename ProjectionType >
constexpr TRangePointerType< typenameTRemoveReference< RangeType >::Type >::Type	FindBy (RangeType &&Range, const ValueType &Value, ProjectionType Proj)

template<typename RangeType , typename PredicateType >
constexpr TRangePointerType< typenameTRemoveReference< RangeType >::Type >::Type	FindByPredicate (RangeType &&Range, PredicateType Pred)

template<typename T , typename ValueType , typename ProjectionType >
T *	FindLastBy (T *First, SIZE_T Num, const ValueType &Value, ProjectionType Proj)

template<typename T , typename PredicateType >
T *	FindLastByPredicate (T *First, SIZE_T Num, PredicateType Pred)

template<typename WhereType , typename WhatType >
constexpr WhereType *	FindSequence (WhereType First, WhereType Last, WhatType WhatFirst, WhatType WhatLast)

template<typename IndexType >
FORCEINLINE IndexType	HeapGetLeftChildIndex (IndexType Index)

template<typename IndexType >
FORCEINLINE bool	HeapIsLeaf (IndexType Index, IndexType Count)

template<typename IndexType >
FORCEINLINE IndexType	HeapGetParentIndex (IndexType Index)

template<typename RangeValueType , typename IndexType , typename ProjectionType , typename PredicateType >
void	HeapSiftDown (RangeValueType *Heap, IndexType Index, const IndexType Count, const ProjectionType &InProj, const PredicateType &Predicate)

template<class RangeValueType , typename IndexType , typename ProjectionType , class PredicateType >
IndexType	HeapSiftUp (RangeValueType *Heap, IndexType RootIndex, IndexType NodeIndex, const ProjectionType &InProj, const PredicateType &Predicate)

template<typename RangeValueType , typename IndexType , typename ProjectionType , typename PredicateType >
void	HeapifyInternal (RangeValueType *First, IndexType Num, ProjectionType Proj, PredicateType Predicate)

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

template<typename RangeType , typename ValueType , typename ProjectionType >
auto	IndexOfBy (const RangeType &Range, const ValueType &Value, ProjectionType Proj)

template<typename RangeType , typename PredicateType >
auto	IndexOfByPredicate (const RangeType &Range, PredicateType Pred)

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

template<typename RangeValueType , typename IndexType , typename ProjectionType , typename PredicateType >
bool	IsHeapInternal (const RangeValueType *Heap, IndexType Num, ProjectionType Projection, PredicateType Predicate)

template<typename T , typename IndexType , typename ProjectionType , typename PredType >
bool	IsSortedBy (const T *Range, IndexType RangeSize, ProjectionType Proj, PredType Pred)

template<typename RangeType , typename GetElementDependenciesType >
void	KahnTopologicalSort_CreateWorkingGraph (FKahnContext &Context, RangeType &UniqueRange, GetElementDependenciesType GetElementDependencies, TSet< FKahnHandle > &OutInitialIndependents)

const TSet< FKahnHandle > &	FindMostIndependentMutuallyReachableVertexSet (FKahnContext &Context)

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

template<typename RangeType , typename ProjectionType , typename PredicateType >
constexpr TRangePointerType< RangeType >::Type	MaxElementBy (RangeType &Range, ProjectionType Proj, PredicateType Pred)

template<typename RangeType , typename ProjectionType , typename PredicateType >
TRangePointerType< RangeType >::Type	MinElementBy (RangeType &Range, ProjectionType Proj, PredicateType Pred)

template<typename T >
void	Reverse (T *Array, int32 ArraySize)

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

template<typename RangeType , typename ProjectionType >
TRangePointerType< typenameTRemoveReference< RangeType >::Type >::Type	SelectRandomWeightedBy (RangeType &&Range, ProjectionType Proj)

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

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

template<typename T , typename SizeType , typename ProjectionType , typename BinaryPredicate >
SizeType	Unique (T *Array, SizeType ArraySize, ProjectionType Proj, BinaryPredicate Predicate)

Variables
constexpr int32	MinMergeSubgroupSize = 2

Typedef Documentation

◆ FKahnHandle

typedef int32 AlgoImpl::FKahnHandle

KahnTopologicalSort converts vertices and edges from ElementType to indexes of the vertex in the original UniqueRange of ElementType. FKahnHandle is how vertices are represented during the graph algorithm

Function Documentation

◆ FindBy()

template<typename RangeType , typename ValueType , typename ProjectionType >

constexpr TRangePointerType< typenameTRemoveReference< RangeType >::Type >::Type AlgoImpl::FindBy	(	RangeType &&	Range,
		const ValueType &	Value,
		ProjectionType	Proj
	)

constexpr

◆ FindByPredicate()

template<typename RangeType , typename PredicateType >

constexpr TRangePointerType< typenameTRemoveReference< RangeType >::Type >::Type AlgoImpl::FindByPredicate	(	RangeType &&	Range,
		PredicateType	Pred
	)

constexpr

◆ FindLastBy()

template<typename T , typename ValueType , typename ProjectionType >

T * AlgoImpl::FindLastBy	(	T *	First,
		SIZE_T	Num,
		const ValueType &	Value,
		ProjectionType	Proj
	)

◆ FindLastByPredicate()

template<typename T , typename PredicateType >

T * AlgoImpl::FindLastByPredicate	(	T *	First,
		SIZE_T	Num,
		PredicateType	Pred
	)

◆ FindMostIndependentMutuallyReachableVertexSet()

const TSet< FKahnHandle > & AlgoImpl::FindMostIndependentMutuallyReachableVertexSet ( FKahnContext & Context )

inline

Called when there is a MutuallyReachableVertexSet (aka no vertices are independent). It returns the most-independent maximal MutuallyReachableVertexSet.

◆ FindSequence()

template<typename WhereType , typename WhatType >

constexpr WhereType * AlgoImpl::FindSequence	(	WhereType *	First,
		WhereType *	Last,
		WhatType *	WhatFirst,
		WhatType *	WhatLast
	)

constexpr

◆ HeapGetLeftChildIndex()

template<typename IndexType >

FORCEINLINE IndexType AlgoImpl::HeapGetLeftChildIndex ( IndexType 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()

template<typename IndexType >

FORCEINLINE IndexType AlgoImpl::HeapGetParentIndex ( IndexType Index )

Gets the parent index for node at Index.

Parameters

Index node index.

Returns: Parent index.

◆ HeapifyInternal()

template<typename RangeValueType , typename IndexType , typename ProjectionType , typename PredicateType >

void AlgoImpl::HeapifyInternal	(	RangeValueType *	First,
		IndexType	Num,
		ProjectionType	Proj,
		PredicateType	Predicate
	)

inline

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
Proj	The projection to apply to the elements.
Predicate	A binary predicate object used to specify if one element should precede another.

◆ HeapIsLeaf()

template<typename IndexType >

FORCEINLINE bool AlgoImpl::HeapIsLeaf	(	IndexType	Index,
		IndexType	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 IndexType , typename ProjectionType , typename PredicateType >

void AlgoImpl::HeapSiftDown	(	RangeValueType *	Heap,
		IndexType	Index,
		const IndexType	Count,
		const ProjectionType &	InProj,
		const PredicateType &	Predicate
	)

inline

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.
InProj	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 IndexType , typename ProjectionType , class PredicateType >

IndexType AlgoImpl::HeapSiftUp	(	RangeValueType *	Heap,
		IndexType	RootIndex,
		IndexType	NodeIndex,
		const ProjectionType &	InProj,
		const PredicateType &	Predicate
	)

inline

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.
InProj	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 IndexType , typename ProjectionType , class PredicateType >

void AlgoImpl::HeapSortInternal	(	RangeValueType *	First,
		IndexType	Num,
		ProjectionType	Proj,
		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
Proj	The projection to apply to the elements.
Predicate	A binary predicate object used to specify if one element should precede another.

◆ IndexOfBy()

template<typename RangeType , typename ValueType , typename ProjectionType >

auto AlgoImpl::IndexOfBy	(	const RangeType &	Range,
		const ValueType &	Value,
		ProjectionType	Proj
	)

◆ IndexOfByPredicate()

template<typename RangeType , typename PredicateType >

auto AlgoImpl::IndexOfByPredicate	(	const RangeType &	Range,
		PredicateType	Pred
	)

◆ IntroSortInternal()

template<typename T , typename IndexType , typename ProjectionType , typename PredicateType >

void AlgoImpl::IntroSortInternal	(	T *	First,
		IndexType	Num,
		ProjectionType	Proj,
		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
Proj	The projection to sort by when applied to the element.
Predicate	predicate class

◆ IsHeapInternal()

template<typename RangeValueType , typename IndexType , typename ProjectionType , typename PredicateType >

bool AlgoImpl::IsHeapInternal	(	const RangeValueType *	Heap,
		IndexType	Num,
		ProjectionType	Projection,
		PredicateType	Predicate
	)

Verifies that the range is a min-heap (parent <= child) This is the internal function used by IsHeap overrides.

Parameters

Heap	Pointer to the first element of a binary heap.
Num	the number of items in the heap.
Projection	The projection to apply to the elements.
Predicate	A binary predicate object used to specify if one element should precede another.

Returns: returns true if the range is a min-heap

◆ IsSortedBy()

template<typename T , typename IndexType , typename ProjectionType , typename PredType >

bool AlgoImpl::IsSortedBy	(	const T *	Range,
		IndexType	RangeSize,
		ProjectionType	Proj,
		PredType	Pred
	)

◆ KahnTopologicalSort_CreateWorkingGraph()

template<typename RangeType , typename GetElementDependenciesType >

void AlgoImpl::KahnTopologicalSort_CreateWorkingGraph	(	FKahnContext &	Context,
		RangeType &	UniqueRange,
		GetElementDependenciesType	GetElementDependencies,
		TSet< FKahnHandle > &	OutInitialIndependents
	)

inline

Convert UniqueRange and GetElementDependencies into handles, dependency count, dependencies, and referencers

◆ LegacySortInternal()

template<typename T , typename ProjectionType , typename PredicateType >

void AlgoImpl::LegacySortInternal	(	T *	First,
		int32	Num,
		ProjectionType	Projection,
		PredicateType	Predicate
	)

Sort elements using user defined predicate class. The sort is unstable, meaning that the ordering of equal items is not necessarily preserved. This is the internal sorting function used by Sort overrides. This used to be Algo::Sort and is now considered legacy.

Parameters

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

◆ LowerBoundInternal()

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

SizeType 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

◆ MaxElementBy()

template<typename RangeType , typename ProjectionType , typename PredicateType >

constexpr TRangePointerType< RangeType >::Type AlgoImpl::MaxElementBy	(	RangeType &	Range,
		ProjectionType	Proj,
		PredicateType	Pred
	)

constexpr

◆ Merge()

template<typename T , typename ProjectionType , typename PredicateType >

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

◆ MinElementBy()

template<typename RangeType , typename ProjectionType , typename PredicateType >

TRangePointerType< RangeType >::Type AlgoImpl::MinElementBy	(	RangeType &	Range,
		ProjectionType	Proj,
		PredicateType	Pred
	)

◆ Reverse()

template<typename T >

void AlgoImpl::Reverse	(	T *	Array,
		int32	ArraySize
	)

◆ RotateInternal()

template<typename T >

int32 AlgoImpl::RotateInternal	(	T *	First,
		int32	Num,
		int32	Count
	)

◆ SelectRandomWeightedBy()

template<typename RangeType , typename ProjectionType >

TRangePointerType< typenameTRemoveReference< RangeType >::Type >::Type AlgoImpl::SelectRandomWeightedBy	(	RangeType &&	Range,
		ProjectionType	Proj
	)

◆ StableSortInternal()

template<typename T , typename ProjectionType , typename PredicateType >

void AlgoImpl::StableSortInternal	(	T *	First,
		int32	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.

◆ Unique()

template<typename T , typename SizeType , typename ProjectionType , typename BinaryPredicate >

SizeType AlgoImpl::Unique	(	T *	Array,
		SizeType	ArraySize,
		ProjectionType	Proj,
		BinaryPredicate	Predicate
	)

◆ UpperBoundInternal()

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

SizeType 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 int32 AlgoImpl::MinMergeSubgroupSize = 2

inlineconstexpr

Classes

Typedefs

Functions

Variables

Typedef Documentation

◆ FKahnHandle

Function Documentation

◆ FindBy()

◆ FindByPredicate()

◆ FindLastBy()

◆ FindLastByPredicate()

◆ FindMostIndependentMutuallyReachableVertexSet()

◆ FindSequence()

◆ HeapGetLeftChildIndex()

◆ HeapGetParentIndex()

◆ HeapifyInternal()

◆ HeapIsLeaf()

◆ HeapSiftDown()

◆ HeapSiftUp()

◆ HeapSortInternal()

◆ IndexOfBy()

◆ IndexOfByPredicate()

◆ IntroSortInternal()

◆ IsHeapInternal()

◆ IsSortedBy()

◆ KahnTopologicalSort_CreateWorkingGraph()

◆ LegacySortInternal()

◆ LowerBoundInternal()

◆ MaxElementBy()

◆ Merge()

◆ MinElementBy()

◆ Reverse()

◆ RotateInternal()

◆ SelectRandomWeightedBy()

◆ StableSortInternal()

◆ Unique()

◆ UpperBoundInternal()

Variable Documentation

◆ MinMergeSubgroupSize