Detailed Description

template<typename Int>
class tlx::radix_heap_detail::IntegerRank< Int >

Compute the rank of an integer x (i.e.

the number of elements smaller than x that are representable using type Int) and vice versa. If Int is an unsigned integral type, all computations yield identity. If Int is a signed integrals, the smallest (negative) number is mapped to rank zero, the next larger value to one and so on.

The implementation assumes negative numbers are implemented as Two's complement and contains static_asserts failing if this is not the case.

Definition at line 41 of file radix_heap.hpp.

#include <radix_heap.hpp>

Public Types
using	int_type = Int

using	rank_type = typename std::make_unsigned< int_type >::type

Static Public Member Functions
static constexpr int_type	int_at_rank (rank_type r)

static constexpr rank_type	rank_of_int (int_type i)

Static Private Attributes
static constexpr rank_type	sign_bit_ = (rank_type(1) << (8 * sizeof(rank_type) - 1))

static constexpr bool	use_identity_ = !std::is_signed<int_type>::value

Member Typedef Documentation

◆ int_type

using int_type = Int

Definition at line 47 of file radix_heap.hpp.

◆ rank_type

using rank_type = typename std::make_unsigned<int_type>::type

Definition at line 48 of file radix_heap.hpp.

Member Function Documentation

◆ int_at_rank()

static constexpr int_type int_at_rank ( rank_type r )

inlinestatic

Returns the r-th smallest number of int_r. It is the inverse of rank_of_int, i.e. int_at_rank(rank_of_int(i)) == i for all i.

Definition at line 60 of file radix_heap.hpp.

References IntegerRank< Int >::sign_bit_, and IntegerRank< Int >::use_identity_.

◆ rank_of_int()

static constexpr rank_type rank_of_int ( int_type i )

inlinestatic

Maps value i to its rank in int_type. For any pair T x < y the invariant IntegerRank<T>::rank_of_int(x) < IntegerRank<T>::rank_of_int(y) holds.

Definition at line 52 of file radix_heap.hpp.

References IntegerRank< Int >::sign_bit_, and IntegerRank< Int >::use_identity_.

Member Data Documentation

◆ sign_bit_

constexpr rank_type sign_bit_ = (rank_type(1) << (8 * sizeof(rank_type) - 1))

staticprivate

Definition at line 70 of file radix_heap.hpp.

Referenced by IntegerRank< Int >::int_at_rank(), and IntegerRank< Int >::rank_of_int().

◆ use_identity_

constexpr bool use_identity_ = !std::is_signed<int_type>::value

staticprivate

Definition at line 67 of file radix_heap.hpp.