pbat::common Namespace Reference

Common functionality. More...

Classes
class	BinaryRadixTree
	Binary radix tree implementation. More...
class	BruteSet
	Fixed-size brute-force set implementation. More...
class	Heap
	Fixed-size max heap. More...
struct	Overloaded
	C++20 feature to allow multiple inheritance of operator() for lambdas. More...
class	Queue
	Fixed-size queue implementation. More...
class	Stack
	Fixed-size stack implementation. More...

Concepts
concept	CArithmetic
	Concept for arithmetic types.
concept	CIndex
	Concept for integral types.
concept	CFloatingPoint
	Concept for floating-point types.
concept	CIndexRange
	Range of integer types.
concept	CContiguousIndexRange
	Contiguous range of integer types.
concept	CArithmeticRange
	Range of arithmetic types.
concept	CContiguousArithmeticRange
	Contiguous range of arithmetic types.
concept	CContiguousArithmeticMatrixRange
	Range of Eigen fixed-size matrix types.

Functions
template<std::integral TIndex, class FLess>
auto	ArgSort (TIndex n, FLess less) -> Eigen::Vector< TIndex, Eigen::Dynamic >
	Computes the indices that would sort an array.
template<class... Ts, class F>
constexpr void	ForTypes (F &&f)
	Compile-time for loop over types.
template<auto... Xs, class F>
constexpr void	ForValues (F &&f)
	Compile-time for loop over values.
template<auto Begin, auto End, typename F>
constexpr void	ForRange (F &&f)
	Compile-time for loop over a range of values.
template<std::random_access_iterator TWorkBegin, std::random_access_iterator TWorkEnd, std::random_access_iterator TValuesBegin, std::random_access_iterator TValuesEnd, class FKey, class T = typename std::iterator_traits<TValuesBegin>::value_type, class TKey = typename std::invoke_result_t<FKey, T>>
void	CountingSort (TWorkBegin wb, TWorkEnd we, TValuesBegin vb, TValuesEnd ve, TKey keyMin=std::numeric_limits< TKey >::max(), FKey fKey=[](T const &key) { return key;})
	Counting sort.
template<std::random_access_iterator TValuesBegin, std::random_access_iterator TValuesEnd, std::random_access_iterator TWorkBegin, class FKey>
void	PrefixSumFromSortedKeys (TValuesBegin vb, TValuesEnd ve, TWorkBegin wb, FKey fKey)
template<CContiguousArithmeticRange R>
auto	ToEigen (R &&r) -> Eigen::Map< Eigen::Vector< std::ranges::range_value_t< R >, Eigen::Dynamic > const >
	Map a range of scalars to an eigen vector of such scalars.
template<std::ranges::random_access_range R>
auto	Slice (R &&r)
	Slice view over a range for Eigen advanced indexing.
template<typename T>
void	HashCombineAccumulate (std::size_t &seed, T const &val)
	Incrementally combine hash values of multiple arguments.
template<typename... Types>
std::size_t	HashCombine (Types const &... args)
	Combine hash values of multiple arguments.
template<CIndexRange R, std::integral TIndex = std::ranges::range_value_t<R>>
auto	CumSum (R &&sizes) -> Eigen::Vector< TIndex, Eigen::Dynamic >
	Cumulative sum of a range of integers.
template<std::integral TIndex>
auto	Counts (auto begin, auto end, TIndex ncounts) -> Eigen::Vector< TIndex, Eigen::Dynamic >
	Counts the number of occurrences of each integer in a contiguous range.
template<std::integral TIndex>
auto	Shuffle (TIndex begin, TIndex end) -> Eigen::Vector< TIndex, Eigen::Dynamic >
	Randomly shuffle a range of integers.
template<std::integral TIndexB, std::integral TIndexE, class Func, class TIndex = std::common_type_t<TIndexB, TIndexE>>
auto	Filter (TIndexB begin, TIndexE end, Func &&f) -> Eigen::Vector< TIndex, Eigen::Dynamic >
	Filters a range of integers based on a predicate function.
template<class TDerivedX, class TDerivedR, class TScalar = typename TDerivedX::Scalar, std::integral TIndex = typename TDerivedR::Scalar>
auto	Repeat (Eigen::DenseBase< TDerivedX > const &x, Eigen::DenseBase< TDerivedR > const &r) -> Eigen::Vector< TScalar, Eigen::Dynamic >
	Repeats elements of a vector according to a repetition vector.
auto	Modulo (auto a, auto b)
template<class FVisit, class FChild, class TIndex = Index, auto N = 2, auto kStackDepth = 64>
PBAT_HOST_DEVICE void	TraverseNAryTreePseudoPreOrder (FVisit fVisit, FChild fChild, TIndex root=0)
	Pre-order traversal over an n-ary tree starting from root.
template<class FVisit, class FChild, class TIndex = Index, auto N = 2, auto kStackDepth = 64>
PBAT_HOST_DEVICE void	TraverseNAryTreePseudoPostOrder (FVisit fVisit, FChild fChild, TIndex root=0)
	Post-order traversal over an n-ary tree starting from root.
template<std::random_access_iterator TValuesBegin, std::random_access_iterator TValuesEnd, std::random_access_iterator TPermutationBegin>
void	Permute (TValuesBegin vb, TValuesEnd ve, TPermutationBegin pb)
	Permute the values in-place according to the permutation.

Detailed Description

Common functionality.

Function Documentation

ArgSort()

template<std::integral TIndex, class FLess>

auto pbat::common::ArgSort	(	TIndex	n,
		FLess	less ) -> Eigen::Vector<TIndex, Eigen::Dynamic>

Computes the indices that would sort an array.

Template Parameters

TIndex	Coefficient type of returned vector
FLess	Callable with signature bool(TIndex, TIndex)

Parameters

n	Number of elements
less	Less-than comparison function object

Returns

|n| array of indices that would sort the input array

CountingSort()

template<std::random_access_iterator TWorkBegin, std::random_access_iterator TWorkEnd, std::random_access_iterator TValuesBegin, std::random_access_iterator TValuesEnd, class FKey, class T = typename std::iterator_traits<TValuesBegin>::value_type, class TKey = typename std::invoke_result_t<FKey, T>>

void pbat::common::CountingSort	(	TWorkBegin	wb,
		TWorkEnd	we,
		TValuesBegin	vb,
		TValuesEnd	ve,
		TKey	keyMin = std::numeric_limits<TKey>::max(),
		FKey	fKey = [](T const& key) { return key; } )

Counting sort.

Template Parameters

TWorkBegin	Iterator type to the beginning of the work array
TWorkEnd	Iterator type to the end of the work array
TValuesBegin	Iterator type to the beginning of the values
TValuesEnd	Iterator type to the end of the values
FKey	Key accessor callable with signature TKey(T)
T	Value type
TKey	Key type

Parameters

wb	Iterator to the beginning of the work array
we	Iterator to the end of the work array
vb	Iterator to the beginning of values
ve	Iterator to the end of values
keyMin	Minimum key value
fKey	Key accessor callable

Precondition

*(wb+i) == 0 for all i in [0, std::distance(wb,we))

Counts()

template<std::integral TIndex>

auto pbat::common::Counts	(	auto	begin,
		auto	end,
		TIndex	ncounts ) -> Eigen::Vector<TIndex, Eigen::Dynamic>

Counts the number of occurrences of each integer in a contiguous range.

Template Parameters

TIndex

Integer type of counts

Parameters

begin	Range begin
end	Range end (exclusive)
ncounts	Upper bound on values in range

Returns

Counts of each integer in the range

CumSum()

template<CIndexRange R, std::integral TIndex = std::ranges::range_value_t<R>>

auto pbat::common::CumSum

(

R &&

sizes

)

-> Eigen::Vector<TIndex, Eigen::Dynamic>

Cumulative sum of a range of integers.

Template Parameters

R	Integer range type
TIndex	Type of the integers

Parameters

sizes

Range of integers

Returns

Cumulative sum of the range

Filter()

template<std::integral TIndexB, std::integral TIndexE, class Func, class TIndex = std::common_type_t<TIndexB, TIndexE>>

auto pbat::common::Filter	(	TIndexB	begin,
		TIndexE	end,
		Func &&	f ) -> Eigen::Vector<TIndex, Eigen::Dynamic>

Filters a range of integers based on a predicate function.

Template Parameters

TIndexB	Type of the beginning index
TIndexE	Type of the ending index
Func	Predicate function type (TIndex -> bool)
TIndex	Common type of the indices

Parameters

begin	Start of the range (inclusive)
end	End of the range (exclusive)
f	Predicate function to filter the range

Returns

Filtered range of integers

ForRange()

template<auto Begin, auto End, typename F>

void pbat::common::ForRange ( F && f )

constexpr

Compile-time for loop over a range of values.

Template Parameters

Begin	Starting loop index
End	Ending loop index (exclusive)
F	Callable with signature void operator()<decltype(Begin)>()

Parameters

f	Function object to call

ForTypes()

template<class... Ts, class F>

void pbat::common::ForTypes ( F && f )

constexpr

Compile-time for loop over types.

Template Parameters

Ts	Types to loop over
F	Callable with signature void operator()<T>()

Parameters

f	Function object to call

ForValues()

template<auto... Xs, class F>

void pbat::common::ForValues ( F && f )

constexpr

Compile-time for loop over values.

Template Parameters

Xs	Values to loop over
F	Callable with signature void operator()<X>()

Parameters

f	Function object to call

HashCombine()

template<typename... Types>

std::size_t pbat::common::HashCombine

(

Types const &...

args

)

Combine hash values of multiple arguments.

Template Parameters

Types

Hashable types

Parameters

args	Arguments to hash

Returns

Hash value

HashCombineAccumulate()

template<typename T>

void pbat::common::HashCombineAccumulate	(	std::size_t &	seed,
		T const &	val )

Incrementally combine hash values of multiple arguments.

Template Parameters

T	Hashable type

Parameters

seed	Starting hash value
val	Value to hash

Permute()

template<std::random_access_iterator TValuesBegin, std::random_access_iterator TValuesEnd, std::random_access_iterator TPermutationBegin>

void pbat::common::Permute	(	TValuesBegin	vb,
		TValuesEnd	ve,
		TPermutationBegin	pb )

Permute the values in-place according to the permutation.

Taken from SO

Template Parameters

TValuesBegin	Iterator type to the beginning of the values
TValuesEnd	Iterator type to the end of the values
TPermutationBegin	Iterator type to the beginning of the permutation

Parameters

vb	Iterator to the beginning of values
ve	Iterator to the end of values
pb	Iterator to the beginning of permutation

Note

The permutation is modified in-place for the duration of the function, but is restored to its original state before returning.

Postcondition

The permutation referenced by pb is un-modified.

The values referenced by [vb, ve) are permuted according to the permutation.

PrefixSumFromSortedKeys()

template<std::random_access_iterator TValuesBegin, std::random_access_iterator TValuesEnd, std::random_access_iterator TWorkBegin, class FKey>

void pbat::common::PrefixSumFromSortedKeys	(	TValuesBegin	vb,
		TValuesEnd	ve,
		TWorkBegin	wb,
		FKey	fKey )

Template Parameters

FKey
TValuesBegin
TValuesEnd
TWorkBegin

Parameters

vb
ve
wb
fKey

Repeat()

template<class TDerivedX, class TDerivedR, class TScalar = typename TDerivedX::Scalar, std::integral TIndex = typename TDerivedR::Scalar>

auto pbat::common::Repeat	(	Eigen::DenseBase< TDerivedX > const &	x,
		Eigen::DenseBase< TDerivedR > const &	r ) -> Eigen::Vector<TScalar, Eigen::Dynamic>

Repeats elements of a vector according to a repetition vector.

Similar to numpy.repeat

Template Parameters

TDerivedX	Eigen dense expression of the input vector
TDerivedR	Eigen dense expression of the repetition vector
TScalar	Scalar type of the input vector
TIndex	Integer type of the repetition vector

Parameters

x	Values to repeat
r	Repetition vector

Returns

Vector with repeated elements

Shuffle()

template<std::integral TIndex>

auto pbat::common::Shuffle	(	TIndex	begin,
		TIndex	end ) -> Eigen::Vector<TIndex, Eigen::Dynamic>

Randomly shuffle a range of integers.

Template Parameters

TIndex

Integer type of the range

Parameters

begin	Start of the range (inclusive)
end	End of the range (exclusive)

Returns

Shuffled range of integers

Slice()

template<std::ranges::random_access_range R>

auto pbat::common::Slice

(

R &&

r

)

Slice view over a range for Eigen advanced indexing.

Template Parameters

R	Range type

Parameters

r

Range

Returns

Type with size(), operator[] and operator() for Eigen advanced indexing

ToEigen()

template<CContiguousArithmeticRange R>

auto pbat::common::ToEigen

(

R &&

r

)

-> Eigen::Map<Eigen::Vector<std::ranges::range_value_t<R>, Eigen::Dynamic> const>

Map a range of scalars to an eigen vector of such scalars.

Map a range of scalar matrices to an eigen vector of such scalars.

Template Parameters

R	Range type

Parameters

r

Range

Returns

Eigen vector adaptor

Template Parameters

R	Range type

Parameters

r

Range

Returns

Eigen matrix adaptor

TraverseNAryTreePseudoPostOrder()

template<class FVisit, class FChild, class TIndex = Index, auto N = 2, auto kStackDepth = 64>

PBAT_HOST_DEVICE void pbat::common::TraverseNAryTreePseudoPostOrder	(	FVisit	fVisit,
		FChild	fChild,
		TIndex	root = 0 )

Post-order traversal over an n-ary tree starting from root.

Template Parameters

FVisit	Function to visit a node
FChild	Function to get the child of a node
TIndex	Type of the index
N	Number of children per node
kStackDepth	Maximum depth of the traversal's stack. The actual stack depth will be N*kStackDepth.

Parameters

fVisit	void(TIndex node) function to visit a node.
fChild	template <TIndex c> TIndex(TIndex node) function to get child c of a node. Returns the child index or -1 if no child.
root	Index of the root node to start the search from

Note

The traversal is deemed "pseudo" post-order because each visited node's children are visited in arbitrary order. The only guarantee is that a parent node is visited after its children. This is due to compile-time loops not being able to guarantee the order of execution.

The visitor does not support sub-tree pruning, since visited nodes are always processed after their sub-tree.

TraverseNAryTreePseudoPreOrder()

template<class FVisit, class FChild, class TIndex = Index, auto N = 2, auto kStackDepth = 64>

PBAT_HOST_DEVICE void pbat::common::TraverseNAryTreePseudoPreOrder	(	FVisit	fVisit,
		FChild	fChild,
		TIndex	root = 0 )

Pre-order traversal over an n-ary tree starting from root.

Template Parameters

FVisit	Function to visit a node
FChild	Function to get the child of a node
TIndex	Type of the index
N	Number of children per node
kStackDepth	Maximum depth of the traversal's stack

Parameters

fVisit	bool(TIndex node) function to visit a node. Returns true if node's sub-tree should be visited.
fChild	template <TIndex c> TIndex(TIndex node) function to get child c of a node. Returns the child index or -1 if no child.
root	Index of the root node to start the search from

Note

The traversal is deemed "pseudo" pre-order because each visited node's children are visited in arbitrary order. The only guarantee is that a parent node is visited before its children. This is due to compile-time loops not being able to guarantee the order of execution.