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