Classes
struct	FKahnContext

struct	FMutuallyReachableVertexSetContext

struct	TLess

struct	TRangePointerType

struct	TRangePointerType< T[N]>

Typedefs
typedef int32	FKahnHandle

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

FORCEINLINE int32	HeapGetLeftChildIndex (int32 Index)

FORCEINLINE bool	HeapIsLeaf (int32 Index, int32 Count)

FORCEINLINE int32	HeapGetParentIndex (int32 Index)

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

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

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

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

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

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

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

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

template<typename RangeType , typename PredicateType >
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 RangeType , typename ValueType , typename ProjectionType >
auto	IndexOfBy (RangeType &&Range, const ValueType &Value, ProjectionType Proj)

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

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 >
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 >
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 BinaryPredicate >
SizeType	Unique (T *Array, SizeType ArraySize, 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

Definition at line 22 of file KahnTopologicalSort.h.

Function Documentation

◆ FindBy()

template<typename RangeType , typename ValueType , typename ProjectionType >

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

Definition at line 13 of file Find.h.

◆ FindByPredicate()

template<typename RangeType , typename PredicateType >

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

Definition at line 27 of file Find.h.

◆ FindLastBy()

template<typename T , typename ValueType , typename ProjectionType >

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

Definition at line 12 of file FindLast.h.

◆ FindLastByPredicate()

template<typename T , typename PredicateType >

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

Definition at line 26 of file FindLast.h.

◆ 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.

Definition at line 223 of file KahnTopologicalSort.h.

◆ FindSequence()

template<typename WhereType , typename WhatType >

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

constexpr

Definition at line 10 of file FindSequence.h.

◆ HeapGetLeftChildIndex()

FORCEINLINE int32 AlgoImpl::HeapGetLeftChildIndex ( int32 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.

Definition at line 17 of file BinaryHeap.h.

Here is the caller graph for this function:

◆ HeapGetParentIndex()

FORCEINLINE int32 AlgoImpl::HeapGetParentIndex ( int32 Index )

Gets the parent index for node at Index.

Parameters

Index node index.

Returns: Parent index.

Definition at line 39 of file BinaryHeap.h.

◆ HeapifyInternal()

template<typename RangeValueType , typename ProjectionType , typename PredicateType >

FORCEINLINE void AlgoImpl::HeapifyInternal	(	RangeValueType *	First,
		int32	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.

Definition at line 116 of file BinaryHeap.h.

◆ HeapIsLeaf()

FORCEINLINE bool AlgoImpl::HeapIsLeaf	(	int32	Index,
		int32	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.

Definition at line 28 of file BinaryHeap.h.

Here is the call graph for this function:

◆ HeapSiftDown()

template<typename RangeValueType , typename ProjectionType , typename PredicateType >

FORCEINLINE void AlgoImpl::HeapSiftDown	(	RangeValueType *	Heap,
		int32	Index,
		const int32	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.

Definition at line 54 of file BinaryHeap.h.

◆ HeapSiftUp()

template<class RangeValueType , typename ProjectionType , class PredicateType >

FORCEINLINE int32 AlgoImpl::HeapSiftUp	(	RangeValueType *	Heap,
		int32	RootIndex,
		int32	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

Definition at line 89 of file BinaryHeap.h.

◆ HeapSortInternal()

template<typename RangeValueType , typename ProjectionType , class PredicateType >

void AlgoImpl::HeapSortInternal	(	RangeValueType *	First,
		int32	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

Definition at line 133 of file BinaryHeap.h.

◆ IndexOfBy()

template<typename RangeType , typename ValueType , typename ProjectionType >

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

Definition at line 12 of file IndexOf.h.

◆ IndexOfByPredicate()

template<typename RangeType , typename PredicateType >

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

Definition at line 30 of file IndexOf.h.

◆ IntroSortInternal()

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

void AlgoImpl::IntroSortInternal	(	T *	First,
		IndexType	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

Definition at line 26 of file IntroSort.h.

◆ IsHeapInternal()

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

bool AlgoImpl::IsHeapInternal	(	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

Definition at line 25 of file IsHeap.h.

◆ IsSortedBy()

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

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

Definition at line 15 of file IsSorted.h.

◆ 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

Definition at line 165 of file KahnTopologicalSort.h.

◆ 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

Definition at line 23 of file LegacySort.h.

◆ LowerBoundInternal()

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

FORCEINLINE 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

Definition at line 23 of file BinarySearch.h.

◆ MaxElementBy()

template<typename RangeType , typename ProjectionType , typename PredicateType >

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

Definition at line 14 of file MaxElement.h.

◆ Merge()

template<typename T , typename ProjectionType , typename PredicateType >

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

Definition at line 16 of file StableSort.h.

◆ MinElementBy()

template<typename RangeType , typename ProjectionType , typename PredicateType >

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

Definition at line 14 of file MinElement.h.

◆ Reverse()

template<typename T >

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

Definition at line 11 of file Reverse.h.

◆ RotateInternal()

template<typename T >

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

Definition at line 11 of file Rotate.h.

◆ SelectRandomWeightedBy()

template<typename RangeType , typename ProjectionType >

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

Definition at line 15 of file SelectRandomWeighted.h.

◆ 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.

Definition at line 50 of file StableSort.h.

◆ Unique()

template<typename T , typename SizeType , typename BinaryPredicate >

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

Definition at line 12 of file Unique.h.

◆ UpperBoundInternal()

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

FORCEINLINE 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

Definition at line 56 of file BinarySearch.h.

Variable Documentation

◆ MinMergeSubgroupSize

constexpr int32 AlgoImpl::MinMergeSubgroupSize = 2

inlineconstexpr

Definition at line 38 of file StableSort.h.

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