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 <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 
28 namespace tlx {
29 namespace 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  */
41 template <typename Int>
43 {
44  static_assert(std::is_integral<Int>::value,
45  "SignedInt has to be an integral type");
46 
47 public:
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 
67 private:
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)
90 template <size_t Size, bool SizeIsAtmost64>
92 
93 template <size_t Size>
94 class 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 
111 public:
112  static constexpr size_t size = Size;
113 
114  explicit BitArrayRecursive() noexcept = default;
115  BitArrayRecursive(const BitArrayRecursive&) noexcept = default;
116  BitArrayRecursive(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 
157 private:
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 
167 template <size_t Size>
168 class 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 
174 public:
175  static constexpr size_t size = Size;
176 
177  explicit BitArrayRecursive() noexcept : flags_(0) { }
178  BitArrayRecursive(const BitArrayRecursive&) noexcept = default;
179  BitArrayRecursive(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 
211 private:
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  */
225 template <size_t Size>
226 class BitArray
227 {
229 
230 public:
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 
270 private:
272 };
273 
274 template <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 
280 public:
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 
323 private:
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 
330 public:
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.
337 template <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  */
375 template <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 
384 public:
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 
391 protected:
394  using bucket_map_type =
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 
402 public:
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;
416  RadixHeap& operator = (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();
526  if (buckets_data_[current_bucket_].empty())
527  filled_.clear_bit(current_bucket_);
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());
539  size_ -= buckets_data_[current_bucket_].size();
540  buckets_data_[current_bucket_].swap(exchange_bucket);
541 
542  filled_.clear_bit(current_bucket_);
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 
551 protected:
552  KeyExtract key_extract_;
553  size_t size_ { 0 };
554  ranked_key_type insertion_limit_{ 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 
572  filled_.clear_all();
573  }
574 
575  void reorganize_() {
576  assert(!empty());
577 
578  // nothing do to if we already know a suited bucket
579  if (TLX_LIKELY(!buckets_data_[current_bucket_].empty())) {
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();
586  filled_.clear_bit(current_bucket_);
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) {
620  const ranked_key_type key = Encoder::rank_of_int(key_extract_(x));
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
640  current_bucket_ = filled_.find_lsb();
641  assert(current_bucket_ < Radix);
642  assert(!buckets_data_[current_bucket_].empty());
643  assert(mins_[current_bucket_] >= insertion_limit_);
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  */
651 template <typename DataType, unsigned Radix = 8, typename KeyExtract = void>
652 auto make_radix_heap(KeyExtract&& key_extract)->
653 RadixHeap<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  */
667 template <typename KeyType, typename DataType, unsigned Radix = 8>
668 using RadixHeapPair = RadixHeap<
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 /******************************************************************************/
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
Int upper_bound(const size_t idx) const
Return largest key possible in bucket idx assuming insertion_limit==0.
Definition: radix_heap.hpp:314
unsigned clz(Integral x)
std::pair< size_t, size_t > get_index_(size_t i) const
Definition: radix_heap.hpp:161
void reorganize_()
Definition: radix_heap.hpp:575
static unsigned ffs(int i)
find first set bit in integer, or zero if none are set.
Definition: ffs.hpp:79
static constexpr int_type int_at_rank(rank_type r)
Returns the r-th smallest number of int_r.
Definition: radix_heap.hpp:61
bool is_set(const size_t i) const
Returns value of the i-th.
Definition: radix_heap.hpp:250
typename std::make_unsigned< int_type >::type rank_type
Definition: radix_heap.hpp:49
bucket_index_type emplace(const key_type key, Args &&...args)
Construct and insert element with priority key.
Definition: radix_heap.hpp:434
bool empty() const
True if all bits are false.
Definition: radix_heap.hpp:260
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
void clear_bit(const size_t i)
Set the i-th bit to false.
Definition: radix_heap.hpp:245
void initialize_()
Definition: radix_heap.hpp:564
std::array< ranked_key_type, num_buckets > mins_
Definition: radix_heap.hpp:561
void swap_top_bucket(bucket_data_type &exchange_bucket)
Exchanges the top buckets with an empty user provided bucket.
Definition: radix_heap.hpp:535
const value_type & top()
Returns currently smallest key and data.
Definition: radix_heap.hpp:516
#define TLX_LIKELY(c)
Definition: likely.hpp:23
void clear()
Clears all internal queues and resets insertion limit.
Definition: radix_heap.hpp:546
bucket_map_type bucket_map_
Definition: radix_heap.hpp:557
This class implements a monotonic integer min priority queue, more specific a multi-level radix heap...
Definition: radix_heap.hpp:377
Used as an adapter to implement RadixHeapPair on top of RadixHeap.
Definition: radix_heap.hpp:338
radix_heap_detail::BitArray< num_buckets > filled_
Definition: radix_heap.hpp:562
size_t size() const
Returns number of elements currently stored.
Definition: radix_heap.hpp:503
static uint32_t min(uint32_t x, uint32_t y)
Definition: md5.cpp:32
std::vector< value_type > bucket_data_type
Definition: radix_heap.hpp:403
Compute the rank of an integer x (i.e.
Definition: radix_heap.hpp:42
KeyType key_type
Definition: radix_heap.hpp:385
std::array< bucket_data_type, num_buckets > buckets_data_
Definition: radix_heap.hpp:559
std::array< child_type, root_size > child_array_type
Definition: radix_heap.hpp:109
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
A BitArray of fixed size supporting reading, setting, and clearing of individual bits.
Definition: radix_heap.hpp:226
void clear_all()
Sets all bits to false.
Definition: radix_heap.hpp:255
bool empty() const
Indicates whether size() == 0.
Definition: radix_heap.hpp:498
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
static constexpr size_t num_buckets_(size_t bits)
Definition: radix_heap.hpp:324
RadixHeap(KeyExtract key_extract=KeyExtract{})
Definition: radix_heap.hpp:405
size_t find_lsb() const
Finds the bit with smallest index that is set.
Definition: radix_heap.hpp:266
static constexpr rank_type rank_of_int(int_type i)
Maps value i to its rank in int_type.
Definition: radix_heap.hpp:53
key_type peak_top_key() const
Returns currently smallest key without updating the insertion limit.
Definition: radix_heap.hpp:508
void set_bit(const size_t i)
Set the i-th bit to true.
Definition: radix_heap.hpp:240
Internal implementation of BitArray; do not invoke directly.
Definition: radix_heap.hpp:91
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 push(const value_type &value)
Insert element with priority key.
Definition: radix_heap.hpp:468
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
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
KeyExtract key_extract_
Definition: radix_heap.hpp:552
static constexpr bool use_identity_
Definition: radix_heap.hpp:68
typename std::conditional< Size<=32, uint32_t, uint64_t >::type uint_type
Definition: radix_heap.hpp:172
void pop()
Removes smallest element.
Definition: radix_heap.hpp:523
ValueType value_type
Definition: radix_heap.hpp:386
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 rank_type sign_bit_
Definition: radix_heap.hpp:71