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