Concepts
concept	counting_integer
	Value concept for counting sort.

concept	radix_integer
	Value concept for radix sort.

Typedefs
template<typename IntT >
using	counting_unsigned_t = std::make_unsigned_t< std::remove_cv_t< IntT > >

template<typename IntT >
using	radix_unsigned_t = std::make_unsigned_t< std::remove_cv_t< IntT > >

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 counting_integer<IntT>
void	counting_sort_impl (C< IntT > &a)
	Internal implementation of counting sort for containers.

template<typename IntT > requires counting_integer<IntT>
void	counting_sort_impl (IntT *a, const size_t n)

template<typename IntT > requires counting_integer<IntT>
void	counting_sort_impl (DynList< IntT > &list)

template<typename IntT > requires counting_integer<IntT>
void	counting_sort_impl (DynDlist< IntT > &list)

template<typename IntT >
constexpr radix_unsigned_t< IntT >	radix_key (const IntT value) noexcept

template<template< typename > class C, typename IntT > requires radix_integer<IntT>
void	radix_sort_impl (C< IntT > &a)

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

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

template<typename IntT > requires radix_integer<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> >

Definition at line 4603 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> >

Definition at line 4607 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 4650 of file tpl_sort_utils.H.

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 4621 of file tpl_sort_utils.H.

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

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 counting_integer<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 4682 of file tpl_sort_utils.H.

References Aleph::count(), counting_bucket(), counting_bucket_count(), Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), 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 counting_integer<IntT>

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

Definition at line 4806 of file tpl_sort_utils.H.

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

◆ counting_sort_impl() [3/4]

template<typename IntT >
requires counting_integer<IntT>

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

Definition at line 4761 of file tpl_sort_utils.H.

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

◆ counting_sort_impl() [4/4]

template<typename IntT >
requires counting_integer<IntT>

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

Definition at line 4722 of file tpl_sort_utils.H.

References Aleph::count(), counting_bucket(), counting_bucket_count(), Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), 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 4667 of file tpl_sort_utils.H.

References Aleph::divide_and_conquer_partition_dp().

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

Definition at line 4851 of file tpl_sort_utils.H.

References Aleph::divide_and_conquer_partition_dp().

◆ radix_sort_impl() [1/4]

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

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

Definition at line 4864 of file tpl_sort_utils.H.

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

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 radix_integer<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 5003 of file tpl_sort_utils.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), 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 radix_integer<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 4963 of file tpl_sort_utils.H.

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

◆ radix_sort_impl() [4/4]

template<typename IntT >
requires radix_integer<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 4914 of file tpl_sort_utils.H.

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

Concepts

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]