11#ifndef TLX_CONTAINER_RADIX_HEAP_HEADER
12#define TLX_CONTAINER_RADIX_HEAP_HEADER
29namespace radix_heap_detail {
41template <
typename Int>
44 static_assert(std::is_integral<Int>::value,
45 "SignedInt has to be an integral type");
49 using rank_type =
typename std::make_unsigned<int_type>::type;
74 static_assert(
rank_of_int(std::numeric_limits<int_type>::min()) == 0,
75 "Rank of minimum is not zero");
76 static_assert(
rank_of_int(std::numeric_limits<int_type>::min() + 1) == 1,
77 "Rank of minimum+1 is not one");
78 static_assert(
rank_of_int(std::numeric_limits<int_type>::max())
79 == std::numeric_limits<rank_type>::max(),
80 "Rank of maximum is not maximum rank");
81 static_assert(
rank_of_int(std::numeric_limits<int_type>::max()) >
83 "Rank of maximum is not larger than rank of zero");
90template <
size_t Size,
bool SizeIsAtmost64>
96 static constexpr size_t leaf_width = 6;
98 static_assert(width > leaf_width,
99 "Size has to be larger than 2**leaf_width");
100 static constexpr size_t root_width = (width % leaf_width)
101 ? (width % leaf_width)
103 static constexpr size_t child_width = width - root_width;
106 static constexpr size_t root_size =
div_ceil(Size, child_type::size);
112 static constexpr size_t size = Size;
120 void set_bit(const
size_t i) {
121 const auto idx = get_index_(i);
122 root_.set_bit(idx.first);
123 children_[idx.first].set_bit(idx.second);
127 const auto idx = get_index_(i);
128 children_[idx.first].clear_bit(idx.second);
129 if (children_[idx.first].empty())
130 root_.clear_bit(idx.first);
134 const auto idx = get_index_(i);
135 return children_[idx.first].is_set(idx.second);
140 for (
auto& child : children_)
145 return root_.empty();
151 const size_t child_idx = root_.find_lsb();
152 const size_t child_val = children_[child_idx].find_lsb();
154 return child_idx * child_type::size + child_val;
163 return { i / child_type::size, i % child_type::size };
167template <
size_t Size>
170 static_assert(Size <= 64,
"Support at most 64 bits");
172 Size <= 32, uint32_t, uint64_t>::type;
175 static constexpr size_t size = Size;
183 void set_bit(const
size_t i) {
195 return (flags_ & (
uint_type(1) << i)) != 0;
225template <
size_t Size>
231 static constexpr size_t size = Size;
251 return impl_.is_set(i);
261 return impl_.empty();
267 return impl_.find_lsb();
274template <
unsigned Radix,
typename Int>
277 static_assert(std::is_unsigned<Int>::value,
"Require unsigned integer");
282 size_t operator () (
const Int x,
const Int insertion_limit)
const {
285 assert(x >= insertion_limit);
287 const auto diff = x ^ insertion_limit;
290 const auto diff_in_bit = (8 *
sizeof(Int) - 1) -
clz(diff);
293 const auto bucket_in_row = ((x >> (
radix_bits * row)) & mask) - row;
295 const auto result = row * Radix + bucket_in_row;
305 return static_cast<Int
>(idx);
307 const size_t row = (idx - 1) / (Radix - 1);
308 const auto digit =
static_cast<Int
>(idx - row * (Radix - 1));
318 return std::numeric_limits<Int>::max();
337template <
typename KeyType,
typename DataType>
341 KeyType
operator () (
const std::pair<KeyType, DataType>& p)
const {
375template <
typename ValueType,
typename KeyExtract,
376 typename KeyType,
unsigned Radix = 8>
380 "Radix has to be power of two");
382 static constexpr bool debug =
false;
389 static constexpr unsigned radix = Radix;
405 explicit RadixHeap(KeyExtract key_extract = KeyExtract { })
433 template <
typename... Args>
445 template <
typename... Args>
447 return emplace(key, key, std::forward<Args>(args) ...);
454 template <
typename... Args>
457 buckets_data_[idx].emplace_back(std::forward<Args>(args) ...);
538 assert(exchange_bucket.empty());
561 std::array<ranked_key_type, num_buckets>
mins_;
570 std::numeric_limits<ranked_key_type>::max());
594 for (
size_t i = 0; i < first_non_empty; i++) {
596 assert(
mins_[i] == std::numeric_limits<ranked_key_type>::max());
612 const auto new_ins_limit =
mins_[first_non_empty];
619 for (
auto& x : data_source) {
621 assert(key >=
mins_[first_non_empty]);
622 assert(first_non_empty ==
mins_.size() - 1
623 || key <
mins_[first_non_empty + 1]);
625 assert(idx < first_non_empty);
636 mins_[first_non_empty] = std::numeric_limits<ranked_key_type>::max();
651template <
typename DataType,
unsigned Radix = 8,
typename KeyExtract =
void>
653RadixHeap<DataType, KeyExtract,
654 decltype(key_extract(std::declval<DataType>())), Radix> {
657 decltype(key_extract(DataType{ })), Radix > {
667template <
typename KeyType,
typename DataType,
unsigned Radix = 8>
669 std::pair<KeyType, DataType>,
This class implements a monotonic integer min priority queue, more specific a multi-level radix heap.
RadixHeap(const RadixHeap &)=default
RadixHeap(RadixHeap &&)=default
key_type peak_top_key() const
Returns currently smallest key without updating the insertion limit.
size_t size() const
Returns number of elements currently stored.
void pop()
Removes smallest element.
RadixHeap(KeyExtract key_extract=KeyExtract { })
typename Encoder::rank_type ranked_key_type
bucket_index_type get_bucket(const value_type &value) const
static constexpr unsigned radix_bits
void emplace_in_bucket(const bucket_index_type idx, Args &&... args)
Construct and insert element into bucket idx (useful if an item was inserted into the same bucket dir...
ranked_key_type insertion_limit_
static constexpr unsigned num_buckets
bool empty() const
Indicates whether size() == 0.
static constexpr bool debug
bucket_map_type bucket_map_
void swap_top_bucket(bucket_data_type &exchange_bucket)
Exchanges the top buckets with an empty user provided bucket.
static constexpr unsigned radix
std::array< bucket_data_type, num_buckets > buckets_data_
bucket_index_type push(const value_type &value)
Insert element with priority key.
std::array< ranked_key_type, num_buckets > mins_
const value_type & top()
Returns currently smallest key and data.
RadixHeap & operator=(const RadixHeap &)=default
bucket_index_type get_bucket_key(const key_type key) const
void clear()
Clears all internal queues and resets insertion limit.
radix_heap_detail::BitArray< num_buckets > filled_
bucket_index_type emplace(const key_type key, Args &&... args)
Construct and insert element with priority key.
static constexpr unsigned num_layers
void push_to_bucket(const bucket_index_type idx, const value_type &value)
Insert element into specific bucket (useful if an item was inserted into the same bucket directly bef...
bucket_index_type emplace_keyfirst(const key_type key, Args &&... args)
In case the first parameter can be directly casted into key_type, using this method avoid repeating i...
std::vector< value_type > bucket_data_type
BitArrayRecursive() noexcept=default
child_array_type children_
void clear_bit(const size_t i)
bool is_set(const size_t i) const
std::array< child_type, root_size > child_array_type
std::pair< size_t, size_t > get_index_(size_t i) const
typename std::conditional< Size<=32, uint32_t, uint64_t >::type uint_type
BitArrayRecursive(const BitArrayRecursive &) noexcept=default
BitArrayRecursive(BitArrayRecursive &&) noexcept=default
void clear_bit(const size_t i)
bool is_set(const size_t i) const
BitArrayRecursive() noexcept
Internal implementation of BitArray; do not invoke directly.
A BitArray of fixed size supporting reading, setting, and clearing of individual bits.
size_t find_lsb() const
Finds the bit with smallest index that is set.
bool empty() const
True if all bits are false.
void clear_bit(const size_t i)
Set the i-th bit to false.
bool is_set(const size_t i) const
Returns value of the i-th.
void set_bit(const size_t i)
Set the i-th bit to true.
void clear_all()
Sets all bits to false.
static constexpr size_t size
BitArray() noexcept=default
Int lower_bound(const size_t idx) const
Return smallest key possible in bucket idx assuming insertion_limit==0.
static constexpr size_t num_buckets_(size_t bits)
static constexpr unsigned radix_bits
static constexpr size_t num_buckets
Number of buckets required given Radix and the current data type Int.
size_t operator()(const Int x, const Int insertion_limit) const
Return bucket index key x belongs to given the current insertion limit.
Int upper_bound(const size_t idx) const
Return largest key possible in bucket idx assuming insertion_limit==0.
Compute the rank of an integer x (i.e.
static constexpr rank_type rank_of_int(int_type i)
Maps value i to its rank in int_type.
static constexpr bool use_identity_
static constexpr int_type int_at_rank(rank_type r)
Returns the r-th smallest number of int_r.
static constexpr rank_type sign_bit_
typename std::make_unsigned< int_type >::type rank_type
auto make_radix_heap(KeyExtract &&key_extract) -> RadixHeap< DataType, KeyExtract, decltype(key_extract(std::declval< DataType >())), Radix >
Helper to easily derive type of RadixHeap for a pre-C++17 compiler.
static constexpr auto div_ceil(const IntegralN &n, const IntegralK &k) -> decltype(n+k)
calculate n div k with rounding up, for n and k positive!
static unsigned ffs(int i)
find first set bit in integer, or zero if none are set.