11#ifndef TLX_CONTAINER_RADIX_HEAP_HEADER
12#define TLX_CONTAINER_RADIX_HEAP_HEADER
30namespace radix_heap_detail {
42template <
typename Int>
45 static_assert(std::is_integral<Int>::value,
46 "SignedInt has to be an integral type");
50 using rank_type =
typename std::make_unsigned<int_type>::type;
75 static_assert(
rank_of_int(std::numeric_limits<int_type>::min()) == 0,
76 "Rank of minimum is not zero");
77 static_assert(
rank_of_int(std::numeric_limits<int_type>::min() + 1) == 1,
78 "Rank of minimum+1 is not one");
79 static_assert(
rank_of_int(std::numeric_limits<int_type>::max())
80 == std::numeric_limits<rank_type>::max(),
81 "Rank of maximum is not maximum rank");
82 static_assert(
rank_of_int(std::numeric_limits<int_type>::max()) >
84 "Rank of maximum is not larger than rank of zero");
91template <
size_t Size,
bool SizeIsAtmost64>
97 static constexpr size_t leaf_width = 6;
99 static_assert(width > leaf_width,
100 "Size has to be larger than 2**leaf_width");
101 static constexpr size_t root_width = (width % leaf_width)
102 ? (width % leaf_width)
104 static constexpr size_t child_width = width - root_width;
107 static constexpr size_t root_size =
div_ceil(Size, child_type::size);
108 using root_type = BitArrayRecursive < root_size <= 32 ? 32 : 64, true >;
113 static constexpr size_t size = Size;
121 void set_bit(const
size_t i) {
122 const auto idx = get_index_(i);
123 root_.set_bit(idx.first);
124 children_[idx.first].set_bit(idx.second);
128 const auto idx = get_index_(i);
129 children_[idx.first].clear_bit(idx.second);
130 if (children_[idx.first].empty())
131 root_.clear_bit(idx.first);
135 const auto idx = get_index_(i);
136 return children_[idx.first].is_set(idx.second);
141 for (
auto& child : children_)
146 return root_.empty();
152 const size_t child_idx = root_.find_lsb();
153 const size_t child_val = children_[child_idx].find_lsb();
155 return child_idx * child_type::size + child_val;
164 return { i / child_type::size, i % child_type::size };
168template <
size_t Size>
171 static_assert(Size <= 64,
"Support at most 64 bits");
173 Size <= 32, std::uint32_t, std::uint64_t>::type;
176 static constexpr size_t size = Size;
184 void set_bit(const
size_t i) {
196 return (flags_ & (
uint_type(1) << i)) != 0;
226template <
size_t Size>
232 static constexpr size_t size = Size;
252 return impl_.is_set(i);
262 return impl_.empty();
268 return impl_.find_lsb();
275template <
unsigned Radix,
typename Int>
278 static_assert(std::is_unsigned<Int>::value,
"Require unsigned integer");
283 size_t operator () (
const Int x,
const Int insertion_limit)
const {
286 assert(x >= insertion_limit);
288 const auto diff = x ^ insertion_limit;
291 const auto diff_in_bit = (8 *
sizeof(Int) - 1) -
clz(diff);
294 const auto bucket_in_row = ((x >> (
radix_bits * row)) & mask) - row;
296 const auto result = row * Radix + bucket_in_row;
306 return static_cast<Int
>(idx);
308 const size_t row = (idx - 1) / (Radix - 1);
309 const auto digit =
static_cast<Int
>(idx - row * (Radix - 1));
319 return std::numeric_limits<Int>::max();
338template <
typename KeyType,
typename DataType>
342 KeyType
operator () (
const std::pair<KeyType, DataType>& p)
const {
376template <
typename ValueType,
typename KeyExtract,
377 typename KeyType,
unsigned Radix = 8>
381 "Radix has to be power of two");
383 static constexpr bool debug =
false;
390 static constexpr unsigned radix = Radix;
406 explicit RadixHeap(KeyExtract key_extract = KeyExtract { })
434 template <
typename... Args>
446 template <
typename... Args>
448 return emplace(key, key, std::forward<Args>(args) ...);
455 template <
typename... Args>
458 buckets_data_[idx].emplace_back(std::forward<Args>(args) ...);
539 assert(exchange_bucket.empty());
562 std::array<ranked_key_type, num_buckets>
mins_;
571 std::numeric_limits<ranked_key_type>::max());
595 for (
size_t i = 0; i < first_non_empty; i++) {
597 assert(
mins_[i] == std::numeric_limits<ranked_key_type>::max());
613 const auto new_ins_limit =
mins_[first_non_empty];
620 for (
auto& x : data_source) {
622 assert(key >=
mins_[first_non_empty]);
623 assert(first_non_empty ==
mins_.size() - 1
624 || key <
mins_[first_non_empty + 1]);
626 assert(idx < first_non_empty);
637 mins_[first_non_empty] = std::numeric_limits<ranked_key_type>::max();
652template <
typename DataType,
unsigned Radix = 8,
typename KeyExtract =
void>
654RadixHeap<DataType, KeyExtract,
655 decltype(key_extract(std::declval<DataType>())), Radix> {
658 decltype(key_extract(DataType{ })), Radix> {
668template <
typename KeyType,
typename DataType,
unsigned Radix = 8>
670 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, std::uint32_t, std::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.