tlx
Loading...
Searching...
No Matches
radix_heap.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/container/radix_heap.hpp
3 *
4 * Part of tlx - http://panthema.net/tlx
5 *
6 * Copyright (C) 2018 Manuel Penschuck <tlx@manuel.jetzt>
7 *
8 * All rights reserved. Published under the Boost Software License, Version 1.0
9 ******************************************************************************/
10
11#ifndef TLX_CONTAINER_RADIX_HEAP_HEADER
12#define TLX_CONTAINER_RADIX_HEAP_HEADER
13
14#include <array>
15#include <cassert>
16#include <cstddef>
17#include <cstdint>
18#include <limits>
19#include <type_traits>
20#include <utility>
21#include <vector>
22
23#include <tlx/define/likely.hpp>
24#include <tlx/math/clz.hpp>
25#include <tlx/math/div_ceil.hpp>
26#include <tlx/math/ffs.hpp>
27#include <tlx/meta/log2.hpp>
28
29namespace tlx {
30namespace radix_heap_detail {
31
32/*!
33 * Compute the rank of an integer x (i.e. the number of elements smaller than x
34 * that are representable using type Int) and vice versa.
35 * If Int is an unsigned integral type, all computations yield identity.
36 * If Int is a signed integrals, the smallest (negative) number is mapped to
37 * rank zero, the next larger value to one and so on.
38 *
39 * The implementation assumes negative numbers are implemented as Two's
40 * complement and contains static_asserts failing if this is not the case.
41 */
42template <typename Int>
44{
45 static_assert(std::is_integral<Int>::value,
46 "SignedInt has to be an integral type");
47
48public:
49 using int_type = Int;
50 using rank_type = typename std::make_unsigned<int_type>::type;
51
52 //! Maps value i to its rank in int_type. For any pair T x < y the invariant
53 //! IntegerRank<T>::rank_of_int(x) < IntegerRank<T>::rank_of_int(y) holds.
54 static constexpr rank_type rank_of_int(int_type i) {
55 return use_identity_
56 ? static_cast<rank_type>(i)
57 : static_cast<rank_type>(i) ^ sign_bit_;
58 }
59
60 //! Returns the r-th smallest number of int_r. It is the inverse of
61 //! rank_of_int, i.e. int_at_rank(rank_of_int(i)) == i for all i.
62 static constexpr int_type int_at_rank(rank_type r) {
63 return use_identity_
64 ? static_cast<int_type>(r)
65 : static_cast<int_type>(r ^ sign_bit_);
66 }
67
68private:
69 constexpr static bool use_identity_ = !std::is_signed<int_type>::value;
70
71 constexpr static rank_type sign_bit_
72 = (rank_type(1) << (8 * sizeof(rank_type) - 1));
73
74 // These test fail if a signed type does not use Two's complement
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");
85};
86
87//! Internal implementation of BitArray; do not invoke directly
88//! \tparam Size Number of bits the data structure is supposed to store
89//! \tparam SizeIsAtmost64 Switch between inner node implementation (false)
90//! and leaf implementation (true)
91template <size_t Size, bool SizeIsAtmost64>
93
94template <size_t Size>
95class BitArrayRecursive<Size, false>
96{
97 static constexpr size_t leaf_width = 6;
98 static constexpr size_t width = tlx::Log2<Size>::ceil;
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)
103 : leaf_width;
104 static constexpr size_t child_width = width - root_width;
106
107 static constexpr size_t root_size = div_ceil(Size, child_type::size);
108 using root_type = BitArrayRecursive < root_size <= 32 ? 32 : 64, true >;
109
110 using child_array_type = std::array<child_type, root_size>;
111
112public:
113 static constexpr size_t size = Size;
114
115 explicit BitArrayRecursive() noexcept = default;
116 BitArrayRecursive(const BitArrayRecursive&) noexcept = default;
118 BitArrayRecursive& operator = (const BitArrayRecursive&) noexcept = default;
119 BitArrayRecursive& operator = (BitArrayRecursive&&) noexcept = default;
120
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);
125 }
126
127 void clear_bit(const size_t i) {
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);
132 }
133
134 bool is_set(const size_t i) const {
135 const auto idx = get_index_(i);
136 return children_[idx.first].is_set(idx.second);
137 }
138
139 void clear_all() {
140 root_.clear_all();
141 for (auto& child : children_)
142 child.clear_all();
143 }
144
145 bool empty() const {
146 return root_.empty();
147 }
148
149 size_t find_lsb() const {
150 assert(!empty());
151
152 const size_t child_idx = root_.find_lsb();
153 const size_t child_val = children_[child_idx].find_lsb();
154
155 return child_idx * child_type::size + child_val;
156 }
157
158private:
161
162 std::pair<size_t, size_t> get_index_(size_t i) const {
163 assert(i < size);
164 return { i / child_type::size, i % child_type::size };
165 }
166};
167
168template <size_t Size>
169class BitArrayRecursive<Size, true>
170{
171 static_assert(Size <= 64, "Support at most 64 bits");
172 using uint_type = typename std::conditional<
173 Size <= 32, std::uint32_t, std::uint64_t>::type;
174
175public:
176 static constexpr size_t size = Size;
177
178 explicit BitArrayRecursive() noexcept : flags_(0) { }
179 BitArrayRecursive(const BitArrayRecursive&) noexcept = default;
181 BitArrayRecursive& operator = (const BitArrayRecursive&) noexcept = default;
182 BitArrayRecursive& operator = (BitArrayRecursive&&) noexcept = default;
183
184 void set_bit(const size_t i) {
185 assert(i < size);
186 flags_ |= uint_type(1) << i;
187 }
188
189 void clear_bit(const size_t i) {
190 assert(i < size);
191 flags_ &= ~(uint_type(1) << i);
192 }
193
194 bool is_set(const size_t i) const {
195 assert(i < size);
196 return (flags_ & (uint_type(1) << i)) != 0;
197 }
198
199 void clear_all() {
200 flags_ = 0;
201 }
202
203 bool empty() const {
204 return !flags_;
205 }
206
207 size_t find_lsb() const {
208 assert(!empty());
209 return tlx::ffs(flags_) - 1;
210 }
211
212private:
214};
215
216/*!
217 * A BitArray of fixed size supporting reading, setting, and clearing
218 * of individual bits. The data structure is optimized to find the bit with
219 * smallest index that is set (find_lsb).
220 *
221 * The BitArray is implemented as a search tree with a fan-out of up to 64.
222 * It is thus very flat, and all operations but with the exception of clear_all
223 * have a complexity of O(log_64(Size)) which is << 10 for all practical
224 * purposes.
225 */
226template <size_t Size>
228{
230
231public:
232 static constexpr size_t size = Size;
233
234 explicit BitArray() noexcept = default;
235 BitArray(const BitArray&) noexcept = default;
236 BitArray(BitArray&&) noexcept = default;
237 BitArray& operator = (const BitArray&) noexcept = default;
238 BitArray& operator = (BitArray&&) noexcept = default;
239
240 //! Set the i-th bit to true
241 void set_bit(const size_t i) {
242 impl_.set_bit(i);
243 }
244
245 //! Set the i-th bit to false
246 void clear_bit(const size_t i) {
247 impl_.clear_bit(i);
248 }
249
250 //! Returns value of the i-th
251 bool is_set(const size_t i) const {
252 return impl_.is_set(i);
253 }
254
255 //! Sets all bits to false
256 void clear_all() {
257 impl_.clear_all();
258 }
259
260 //! True if all bits are false
261 bool empty() const {
262 return impl_.empty();
263 }
264
265 //! Finds the bit with smallest index that is set
266 //! \warning If empty() is true, the result is undefined
267 size_t find_lsb() const {
268 return impl_.find_lsb();
269 }
270
271private:
273};
274
275template <unsigned Radix, typename Int>
277{
278 static_assert(std::is_unsigned<Int>::value, "Require unsigned integer");
279 static constexpr unsigned radix_bits = tlx::Log2<Radix>::floor;
280
281public:
282 //! Return bucket index key x belongs to given the current insertion limit
283 size_t operator () (const Int x, const Int insertion_limit) const {
284 constexpr Int mask = (1u << radix_bits) - 1;
285
286 assert(x >= insertion_limit);
287
288 const auto diff = x ^ insertion_limit;
289 if (!diff) return 0;
290
291 const auto diff_in_bit = (8 * sizeof(Int) - 1) - clz(diff);
292
293 const auto row = diff_in_bit / radix_bits;
294 const auto bucket_in_row = ((x >> (radix_bits * row)) & mask) - row;
295
296 const auto result = row * Radix + bucket_in_row;
297
298 return result;
299 }
300
301 //! Return smallest key possible in bucket idx assuming insertion_limit==0
302 Int lower_bound(const size_t idx) const {
303 assert(idx < num_buckets);
304
305 if (idx < Radix)
306 return static_cast<Int>(idx);
307
308 const size_t row = (idx - 1) / (Radix - 1);
309 const auto digit = static_cast<Int>(idx - row * (Radix - 1));
310
311 return digit << radix_bits * row;
312 }
313
314 //! Return largest key possible in bucket idx assuming insertion_limit==0
315 Int upper_bound(const size_t idx) const {
316 assert(idx < num_buckets);
317
318 if (idx == num_buckets - 1)
319 return std::numeric_limits<Int>::max();
320
321 return lower_bound(idx + 1) - 1;
322 }
323
324private:
325 constexpr static size_t num_buckets_(size_t bits) {
326 return (bits >= radix_bits)
327 ? (Radix - 1) + num_buckets_(bits - radix_bits)
328 : (1 << bits) - 1;
329 }
330
331public:
332 //! Number of buckets required given Radix and the current data type Int
333 static constexpr size_t num_buckets =
334 num_buckets_(std::numeric_limits<Int>::digits) + 1;
335};
336
337//! Used as an adapter to implement RadixHeapPair on top of RadixHeap.
338template <typename KeyType, typename DataType>
340 using allow_emplace_pair = bool;
341
342 KeyType operator () (const std::pair<KeyType, DataType>& p) const {
343 return p.first;
344 }
345};
346
347} // namespace radix_heap_detail
348
349//! \addtogroup tlx_container
350//! \{
351
352/*!
353 * This class implements a monotonic integer min priority queue, more specific
354 * a multi-level radix heap.
355 *
356 * Here, monotonic refers to the fact that the heap maintains an insertion limit
357 * and does not allow the insertion of keys smaller than this limit. The
358 * frontier is increased to the current minimum when invoking the methods top(),
359 * pop() and swap_top_bucket(). To query the currently smallest item without
360 * updating the insertion limit use peak_top_key().
361 *
362 * We implement a two level radix heap. Let k=sizeof(KeyType)*8 be the number of
363 * bits in a key. In contrast to an ordinary radix heap which contains k
364 * buckets, we maintain ceil(k/log2(Radix)) rows each containing Radix-many
365 * buckets. This reduces the number of move operations when reorganizing the
366 * data structure.
367 *
368 * The implementation loosly follows the description of "An Experimental Study
369 * of Priority Queues in External Memory" [Bregel et al.] and is also inspired
370 * by https://github.com/iwiwi/radix-heap
371 *
372 * \tparam KeyType Has to be an unsigned integer type
373 * \tparam DataType Type of data payload
374 * \tparam Radix A power of two <= 64.
375 */
376template <typename ValueType, typename KeyExtract,
377 typename KeyType, unsigned Radix = 8>
379{
380 static_assert(Log2<Radix>::floor == Log2<Radix>::ceil,
381 "Radix has to be power of two");
382
383 static constexpr bool debug = false;
384
385public:
386 using key_type = KeyType;
387 using value_type = ValueType;
388 using bucket_index_type = size_t;
389
390 static constexpr unsigned radix = Radix;
391
392protected:
397
398 static constexpr unsigned radix_bits = tlx::Log2<radix>::floor;
399 static constexpr unsigned num_layers =
400 div_ceil(8 * sizeof(ranked_key_type), radix_bits);
401 static constexpr unsigned num_buckets = bucket_map_type::num_buckets;
402
403public:
404 using bucket_data_type = std::vector<value_type>;
405
406 explicit RadixHeap(KeyExtract key_extract = KeyExtract { })
407 : key_extract_(key_extract) {
408 initialize_();
409 }
410
411 // Copy
412 RadixHeap(const RadixHeap&) = default;
413 RadixHeap& operator = (const RadixHeap&) = default;
414
415 // Move
416 RadixHeap(RadixHeap&&) = default;
418
420 return get_bucket_key(key_extract_(value));
421 }
422
424 const auto enc = Encoder::rank_of_int(key);
425 assert(enc >= insertion_limit_);
426
427 return bucket_map_(enc, insertion_limit_);
428 }
429
430 //! Construct and insert element with priority key
431 //! \warning In contrast to all other methods the key has to be provided
432 //! explicitly as the first argument. All other arguments are passed to
433 //! the constructor of the element.
434 template <typename... Args>
435 bucket_index_type emplace(const key_type key, Args&& ... args) {
436 const auto enc = Encoder::rank_of_int(key);
437 assert(enc >= insertion_limit_);
438 const auto idx = bucket_map_(enc, insertion_limit_);
439
440 emplace_in_bucket(idx, std::forward<Args>(args) ...);
441 return idx;
442 }
443
444 //! In case the first parameter can be directly casted into key_type,
445 //! using this method avoid repeating it.
446 template <typename... Args>
447 bucket_index_type emplace_keyfirst(const key_type key, Args&& ... args) {
448 return emplace(key, key, std::forward<Args>(args) ...);
449 }
450
451 //! Construct and insert element into bucket idx (useful if an item
452 //! was inserted into the same bucket directly before)
453 //! \warning Calling any method which updates the current
454 //! can invalidate this hint
455 template <typename... Args>
456 void emplace_in_bucket(const bucket_index_type idx, Args&& ... args) {
457 if (buckets_data_[idx].empty()) filled_.set_bit(idx);
458 buckets_data_[idx].emplace_back(std::forward<Args>(args) ...);
459
460 const auto enc = Encoder::rank_of_int(
461 key_extract_(buckets_data_[idx].back()));
462 if (mins_[idx] > enc) mins_[idx] = enc;
463 assert(idx == bucket_map_(enc, insertion_limit_));
464
465 size_++;
466 }
467
468 //! Insert element with priority key
470 const auto enc = Encoder::rank_of_int(key_extract_(value));
471 assert(enc >= insertion_limit_);
472
473 const auto idx = bucket_map_(enc, insertion_limit_);
474
475 push_to_bucket(idx, value);
476
477 return idx;
478 }
479
480 //! Insert element into specific bucket (useful if an item
481 //! was inserted into the same bucket directly before)
482 //! \warning Calling any method which updates the current
483 //! can invalidate this hint
484 void push_to_bucket(const bucket_index_type idx, const value_type& value) {
485 const auto enc = Encoder::rank_of_int(key_extract_(value));
486
487 assert(enc >= insertion_limit_);
488 assert(idx == get_bucket(value));
489
490 if (buckets_data_[idx].empty()) filled_.set_bit(idx);
491 buckets_data_[idx].push_back(value);
492
493 if (mins_[idx] > enc) mins_[idx] = enc;
494
495 size_++;
496 }
497
498 //! Indicates whether size() == 0
499 bool empty() const {
500 return size() == 0;
501 }
502
503 //! Returns number of elements currently stored
504 size_t size() const {
505 return size_;
506 }
507
508 //! Returns currently smallest key without updating the insertion limit
510 assert(!empty());
511 const auto first = filled_.find_lsb();
512 return Encoder::int_at_rank(mins_[first]);
513 }
514
515 //! Returns currently smallest key and data
516 //! \warning Updates insertion limit; no smaller keys can be inserted later
517 const value_type& top() {
518 reorganize_();
519 return buckets_data_[current_bucket_].back();
520 }
521
522 //! Removes smallest element
523 //! \warning Updates insertion limit; no smaller keys can be inserted later
531
532 //! Exchanges the top buckets with an *empty* user provided bucket.
533 //! Can be used for bulk removals and may reduce allocation overhead
534 //! \warning The exchange bucket has to be empty
535 //! \warning Updates insertion limit; no smaller keys can be inserted later
536 void swap_top_bucket(bucket_data_type& exchange_bucket) {
537 reorganize_();
538
539 assert(exchange_bucket.empty());
541 buckets_data_[current_bucket_].swap(exchange_bucket);
542
544 }
545
546 //! Clears all internal queues and resets insertion limit
547 void clear() {
548 for (auto& x : buckets_data_) x.clear();
549 initialize_();
550 }
551
552protected:
553 KeyExtract key_extract_;
554 size_t size_ { 0 };
556 size_t current_bucket_{ 0 };
557
559
560 std::array<bucket_data_type, num_buckets> buckets_data_;
561
562 std::array<ranked_key_type, num_buckets> mins_;
564
565 void initialize_() {
566 size_ = 0;
567 insertion_limit_ = std::numeric_limits<ranked_key_type>::min();
568 current_bucket_ = 0;
569
570 std::fill(mins_.begin(), mins_.end(),
571 std::numeric_limits<ranked_key_type>::max());
572
574 }
575
576 void reorganize_() {
577 assert(!empty());
578
579 // nothing do to if we already know a suited bucket
581 assert(current_bucket_ < Radix);
582 return;
583 }
584
585 // mark current bucket as empty
586 mins_[current_bucket_] = std::numeric_limits<ranked_key_type>::max();
588
589 // find a non-empty bucket
590 const auto first_non_empty = filled_.find_lsb();
591#ifndef NDEBUG
592 {
593 assert(first_non_empty < num_buckets);
594
595 for (size_t i = 0; i < first_non_empty; i++) {
596 assert(buckets_data_[i].empty());
597 assert(mins_[i] == std::numeric_limits<ranked_key_type>::max());
598 }
599
600 assert(!buckets_data_[first_non_empty].empty());
601 }
602#endif
603
604 if (TLX_LIKELY(first_non_empty < Radix)) {
605 // the first_non_empty non-empty bucket belongs to the smallest row
606 // it hence contains only one key and we do not need to reorganise
607 current_bucket_ = first_non_empty;
608 return;
609 }
610
611 // update insertion limit
612 {
613 const auto new_ins_limit = mins_[first_non_empty];
614 assert(new_ins_limit > insertion_limit_);
615 insertion_limit_ = new_ins_limit;
616 }
617
618 auto& data_source = buckets_data_[first_non_empty];
619
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]);
625 const auto idx = bucket_map_(key, insertion_limit_);
626 assert(idx < first_non_empty);
627
628 // insert into bucket
629 if (buckets_data_[idx].empty()) filled_.set_bit(idx);
630 buckets_data_[idx].push_back(std::move(x));
631 if (mins_[idx] > key) mins_[idx] = key;
632 }
633
634 data_source.clear();
635
636 // mark consumed bucket as empty
637 mins_[first_non_empty] = std::numeric_limits<ranked_key_type>::max();
638 filled_.clear_bit(first_non_empty);
639
640 // update global pointers and minima
642 assert(current_bucket_ < Radix);
645 }
646};
647
648/*!
649 * Helper to easily derive type of RadixHeap for a pre-C++17 compiler.
650 * Refer to RadixHeap for description of parameters.
651 */
652template <typename DataType, unsigned Radix = 8, typename KeyExtract = void>
653auto make_radix_heap(KeyExtract&& key_extract)->
654RadixHeap<DataType, KeyExtract,
655 decltype(key_extract(std::declval<DataType>())), Radix> {
656 return (RadixHeap<DataType,
657 KeyExtract,
658 decltype(key_extract(DataType{ })), Radix> {
659 key_extract
660 });
661}
662
663/*!
664 * This class is a variant of tlx::RadixHeap for data types which do not
665 * include the key directly. Hence each entry is stored as an (Key,Value)-Pair
666 * implemented with std::pair.
667 */
668template <typename KeyType, typename DataType, unsigned Radix = 8>
670 std::pair<KeyType, DataType>,
672 KeyType, Radix
673 >;
674
675//! \}
676
677} // namespace tlx
678
679#endif // !TLX_CONTAINER_RADIX_HEAP_HEADER
680
681/******************************************************************************/
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...
ValueType value_type
ranked_key_type insertion_limit_
static constexpr unsigned num_buckets
bool empty() const
Indicates whether size() == 0.
static constexpr bool debug
KeyExtract key_extract_
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
size_t bucket_index_type
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_
size_t current_bucket_
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
std::array< child_type, root_size > child_array_type
std::pair< size_t, size_t > get_index_(size_t i) const
BitArrayRecursive(const BitArrayRecursive &) noexcept=default
BitArrayRecursive(BitArrayRecursive &&) noexcept=default
typename std::conditional< Size<=32, std::uint32_t, std::uint64_t >::type uint_type
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
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 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.
#define TLX_LIKELY(c)
Definition likely.hpp:23
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!
Definition div_ceil.hpp:25
unsigned clz(Integral x)
static unsigned ffs(int i)
find first set bit in integer, or zero if none are set.
Definition ffs.hpp:79
Used as an adapter to implement RadixHeapPair on top of RadixHeap.
KeyType operator()(const std::pair< KeyType, DataType > &p) const