Typedefs
template<typename IntT >
using	counting_unsigned_t = std::make_unsigned_t< std::remove_cv_t< IntT > >
	Unsigned counterpart used to measure counting-sort key ranges.

template<typename IntT >
using	radix_unsigned_t = std::make_unsigned_t< std::remove_cv_t< IntT > >
	Unsigned key type used by radix sort passes.

Functions
template<typename IntT >
size_t	counting_bucket_count (const IntT min_key, const IntT max_key)
	Compute the number of buckets required for a counting sort range.

template<typename IntT >
size_t	counting_bucket (const IntT value, const IntT min_key) noexcept
	Map a value to its bucket index in counting sort.

template<typename IntT >
IntT	counting_value_from_bucket (const size_t bucket, const IntT min_key) noexcept
	Retrieve the original value from a bucket index in counting sort.

template<template< typename > class C, typename IntT > requires IntegerSortableValue<IntT>
void	counting_sort_impl (C< IntT > &a)
	Internal implementation of counting sort for containers.

template<typename IntT > requires IntegerSortableValue<IntT>
void	counting_sort_impl (IntT *a, const size_t n)
	Internal implementation of counting sort for raw pointer ranges.

template<typename IntT > requires IntegerSortableValue<IntT>
void	counting_sort_impl (DynList< IntT > &list)
	Internal counting-sort implementation for `DynList`.

template<typename IntT > requires IntegerSortableValue<IntT>
void	counting_sort_impl (DynDlist< IntT > &list)
	Internal counting-sort implementation for `DynDlist`.

template<typename IntT >
constexpr radix_unsigned_t< IntT >	radix_key (const IntT value) noexcept
	Map an integer value to an unsigned radix key.

template<template< typename > class C, typename IntT > requires IntegerSortableValue<IntT>
void	radix_sort_impl (C< IntT > &a)
	Internal radix-sort implementation for array-like containers.

template<typename IntT > requires IntegerSortableValue<IntT>
void	radix_sort_impl (IntT *a, const size_t n)
	Core radix sort implementation for raw pointer ranges.

template<typename IntT > requires IntegerSortableValue<IntT>
void	radix_sort_impl (DynList< IntT > &list)
	LSD radix sort implementation for DynList.

template<typename IntT > requires IntegerSortableValue<IntT>
void	radix_sort_impl (DynDlist< IntT > &list)
	LSD radix sort implementation for DynDlist.

Typedef Documentation

◆ counting_unsigned_t

template<typename IntT >

using Aleph::sort_utils_detail::counting_unsigned_t = typedef std::make_unsigned_t<std::remove_cv_t<IntT> >

Unsigned counterpart used to measure counting-sort key ranges.

The cv-qualifiers are removed before mapping to the corresponding unsigned integer type. This lets the range arithmetic work uniformly for signed and unsigned integral keys.

Template Parameters

IntT	Integral key type.

Definition at line 4673 of file tpl_sort_utils.H.

◆ radix_unsigned_t

template<typename IntT >

using Aleph::sort_utils_detail::radix_unsigned_t = typedef std::make_unsigned_t<std::remove_cv_t<IntT> >

Unsigned key type used by radix sort passes.

Radix sort works on unsigned byte digits. Signed values are first mapped to this unsigned type with radix_key() so their natural signed order is preserved.

Template Parameters

IntT	Integral value type.

Definition at line 4684 of file tpl_sort_utils.H.

Function Documentation

◆ counting_bucket()

template<typename IntT >

size_t Aleph::sort_utils_detail::counting_bucket	(	const IntT	value,
		const IntT	min_key
	)

inlinenoexcept

Map a value to its bucket index in counting sort.

Template Parameters

IntT	Integer type.

Parameters

value	Value to map.
min_key	Minimum key in the range.

Returns: Bucket index in [0, bucket_count).

Definition at line 4721 of file tpl_sort_utils.H.

References value.

Referenced by counting_sort_impl(), counting_sort_impl(), counting_sort_impl(), and counting_sort_impl().

◆ counting_bucket_count()

template<typename IntT >

size_t Aleph::sort_utils_detail::counting_bucket_count	(	const IntT	min_key,
		const IntT	max_key
	)

Compute the number of buckets required for a counting sort range.

Template Parameters

IntT	Integer type.

Parameters

min_key	Minimum value in the range.
max_key	Maximum value in the range.

Returns: Total number of buckets needed.

Exceptions

ah_domain_error	if max_key < min_key.
ah_runtime_error	if the range exceeds size_t capacity.

Definition at line 4696 of file tpl_sort_utils.H.

References ah_domain_error_if, ah_runtime_error_unless, and Aleph::blossom_maximum_cardinality_matching().

Referenced by counting_sort_impl(), counting_sort_impl(), counting_sort_impl(), and counting_sort_impl().

◆ counting_sort_impl() [1/4]

template<template< typename > class C, typename IntT >
requires IntegerSortableValue<IntT>

void Aleph::sort_utils_detail::counting_sort_impl ( C< IntT > & a )

Internal implementation of counting sort for containers.

Template Parameters

C	Container template type.
IntT	Integer type.

Parameters

[in,out] a Container to sort.

Definition at line 4749 of file tpl_sort_utils.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), counting_bucket(), counting_bucket_count(), Aleph::Array< T >::create(), and k.

Referenced by Aleph::counting_sort(), Aleph::counting_sort(), Aleph::counting_sort(), Aleph::counting_sort(), and Aleph::counting_sort().

◆ counting_sort_impl() [2/4]

template<typename IntT >
requires IntegerSortableValue<IntT>

void Aleph::sort_utils_detail::counting_sort_impl ( DynDlist< IntT > & list )

Internal counting-sort implementation for DynDlist.

Rewrites node values in sorted order without reallocating or relinking the doubly-linked list nodes.

Template Parameters

IntT	Integer type accepted by `CountingSortable`.

Parameters

[in,out] list List whose values are sorted in place.

Definition at line 4895 of file tpl_sort_utils.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), counting_bucket(), counting_bucket_count(), counting_value_from_bucket(), Aleph::Array< T >::create(), Aleph::DynDlist< T >::Iterator::get_curr_ne(), Aleph::Dlink::Iterator::has_curr(), k, Aleph::DynDlist< T >::Iterator::next_ne(), out, Aleph::DynDlist< T >::size(), and value.

◆ counting_sort_impl() [3/4]

template<typename IntT >
requires IntegerSortableValue<IntT>

void Aleph::sort_utils_detail::counting_sort_impl ( DynList< IntT > & list )

Internal counting-sort implementation for DynList.

Rewrites node values in sorted order without reallocating or relinking the list nodes.

Template Parameters

IntT	Integer type accepted by `CountingSortable`.

Parameters

[in,out] list List whose values are sorted in place.

Definition at line 4843 of file tpl_sort_utils.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), counting_bucket(), counting_bucket_count(), counting_value_from_bucket(), Aleph::Array< T >::create(), Aleph::DynList< T >::Iterator::get_curr_ne(), Aleph::HTList::Iterator::has_curr(), k, Aleph::HTList::Iterator::next_ne(), out, Aleph::HTList::size(), and value.

◆ counting_sort_impl() [4/4]

template<typename IntT >
requires IntegerSortableValue<IntT>

void Aleph::sort_utils_detail::counting_sort_impl	(	IntT *	a,
		const size_t	n
	)

Internal implementation of counting sort for raw pointer ranges.

Sorts a[0..n) in nondecreasing order using a stable counting-sort pass over the observed value range.

Template Parameters

IntT	Integer type accepted by `CountingSortable`.

Parameters

[in,out]	a	Pointer to the first element in the range.
[in]	n	Number of elements in the range.

Definition at line 4797 of file tpl_sort_utils.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), counting_bucket(), counting_bucket_count(), Aleph::Array< T >::create(), and k.

◆ counting_value_from_bucket()

template<typename IntT >

IntT Aleph::sort_utils_detail::counting_value_from_bucket	(	const size_t	bucket,
		const IntT	min_key
	)

inlinenoexcept

Retrieve the original value from a bucket index in counting sort.

Template Parameters

IntT	Integer type.

Parameters

bucket	Bucket index.
min_key	Minimum key in the range.

Returns: The original value corresponding to the bucket.

Definition at line 4735 of file tpl_sort_utils.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by counting_sort_impl(), and counting_sort_impl().

◆ radix_key()

template<typename IntT >

constexpr radix_unsigned_t< IntT > Aleph::sort_utils_detail::radix_key ( const IntT value )

constexprnoexcept

Map an integer value to an unsigned radix key.

Unsigned values are returned unchanged. Signed values are biased by flipping the sign bit, which makes their unsigned byte order match the natural signed order required by radix sort.

Template Parameters

IntT	Integer type.

Parameters

value Value to map.

Returns: Unsigned key used by radix passes.

Definition at line 4948 of file tpl_sort_utils.H.

References Aleph::blossom_maximum_cardinality_matching(), and value.

◆ radix_sort_impl() [1/4]

template<template< typename > class C, typename IntT >
requires IntegerSortableValue<IntT>

void Aleph::sort_utils_detail::radix_sort_impl ( C< IntT > & a )

Internal radix-sort implementation for array-like containers.

Performs a stable least-significant-byte radix sort using a fixed 256-bucket counting pass for each byte of the unsigned radix key.

Template Parameters

C	Aleph array-like container template.
IntT	Integer type accepted by `RadixSortable`.

Parameters

[in,out] a Container sorted in place.

Definition at line 4968 of file tpl_sort_utils.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), and Aleph::Array< T >::create().

Referenced by Aleph::radix_sort(), Aleph::radix_sort(), Aleph::radix_sort(), Aleph::radix_sort(), and Aleph::radix_sort().

◆ radix_sort_impl() [2/4]

template<typename IntT >
requires IntegerSortableValue<IntT>

void Aleph::sort_utils_detail::radix_sort_impl ( DynDlist< IntT > & list )

LSD radix sort implementation for DynDlist.

Performs a stable radix sort on a doubly-linked list.

Template Parameters

IntT	Integer type.

Parameters

[in,out] list The doubly-linked list to sort.

Definition at line 5104 of file tpl_sort_utils.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Dnode< T >::get_data(), Aleph::Dnode< T >::remove_first_ne(), Aleph::Array< T >::reserve(), and Aleph::DynDlist< T >::size().

◆ radix_sort_impl() [3/4]

template<typename IntT >
requires IntegerSortableValue<IntT>

void Aleph::sort_utils_detail::radix_sort_impl ( DynList< IntT > & list )

LSD radix sort implementation for DynList.

Performs a stable radix sort on a linked list. This implementation is memory efficient as it reuses the original list nodes.

Template Parameters

IntT	Integer type.

Parameters

[in,out] list The list to sort.

Definition at line 5065 of file tpl_sort_utils.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::HTList::is_empty(), Aleph::Array< T >::reserve(), and Aleph::HTList::size().

◆ radix_sort_impl() [4/4]

template<typename IntT >
requires IntegerSortableValue<IntT>

void Aleph::sort_utils_detail::radix_sort_impl	(	IntT *	a,
		const size_t	n
	)

Core radix sort implementation for raw pointer ranges.

Uses counting sort as a stable subroutine to sort by each byte digit.

Template Parameters

IntT	Integer type.

Parameters

[in,out]	a	Pointer to the array.
[in]	n	Number of elements.

Definition at line 5017 of file tpl_sort_utils.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), and Aleph::Array< T >::create().

Typedefs

Functions

Typedef Documentation

◆ counting_unsigned_t

◆ radix_unsigned_t

Function Documentation

◆ counting_bucket()

◆ counting_bucket_count()

◆ counting_sort_impl() [1/4]

◆ counting_sort_impl() [2/4]

◆ counting_sort_impl() [3/4]

◆ counting_sort_impl() [4/4]

◆ counting_value_from_bucket()

◆ radix_key()

◆ radix_sort_impl() [1/4]

◆ radix_sort_impl() [2/4]

◆ radix_sort_impl() [3/4]

◆ radix_sort_impl() [4/4]