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 
27 namespace tlx {
28 namespace 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  */
40 template <typename Int>
42 {
43  static_assert(std::is_integral<Int>::value,
44  "SignedInt has to be an integral type");
45 
46 public:
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 
66 private:
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
73  static_assert(rank_of_int(std::numeric_limits<int_type>::min()) == 0,
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)
89 template <size_t Size, bool SizeIsAtmost64>
91 
92 template <size_t Size>
93 class 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 
110 public:
111  static constexpr size_t size = Size;
112 
113  explicit BitArrayRecursive() noexcept = default;
114  BitArrayRecursive(const BitArrayRecursive&) noexcept = default;
115  BitArrayRecursive(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 
156 private:
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 
166 template <size_t Size>
167 class 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 
173 public:
174  static constexpr size_t size = Size;
175 
176  explicit BitArrayRecursive() noexcept : flags_(0) { }
177  BitArrayRecursive(const BitArrayRecursive&) noexcept = default;
178  BitArrayRecursive(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 
210 private:
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  */
224 template <size_t Size>
225 class BitArray
226 {
228 
229 public:
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 
269 private:
271 };
272 
273 template <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 
279 public:
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 
322 private:
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 
329 public:
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.
336 template <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  */
374 template <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 
383 public:
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 
390 protected:
393  using bucket_map_type =
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 
401 public:
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;
415  RadixHeap& operator = (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();
525  if (buckets_data_[current_bucket_].empty())
526  filled_.clear_bit(current_bucket_);
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());
538  size_ -= buckets_data_[current_bucket_].size();
539  buckets_data_[current_bucket_].swap(exchange_bucket);
540 
541  filled_.clear_bit(current_bucket_);
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 
550 protected:
551  KeyExtract key_extract_;
552  size_t size_ { 0 };
553  ranked_key_type insertion_limit_{ 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;
565  insertion_limit_ = std::numeric_limits<ranked_key_type>::min();
566  current_bucket_ = 0;
567 
568  std::fill(mins_.begin(), mins_.end(),
569  std::numeric_limits<ranked_key_type>::max());
570 
571  filled_.clear_all();
572  }
573 
574  void reorganize_() {
575  assert(!empty());
576 
577  // nothing do to if we already know a suited bucket
578  if (TLX_LIKELY(!buckets_data_[current_bucket_].empty())) {
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();
585  filled_.clear_bit(current_bucket_);
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) {
619  const ranked_key_type key = Encoder::rank_of_int(key_extract_(x));
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
639  current_bucket_ = filled_.find_lsb();
640  assert(current_bucket_ < Radix);
641  assert(!buckets_data_[current_bucket_].empty());
642  assert(mins_[current_bucket_] >= insertion_limit_);
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  */
650 template <typename DataType, unsigned Radix = 8, typename KeyExtract = void>
651 auto make_radix_heap(KeyExtract&& key_extract)->
652 RadixHeap<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  */
666 template <typename KeyType, typename DataType, unsigned Radix = 8>
667 using RadixHeapPair = RadixHeap<
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 /******************************************************************************/
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
Int upper_bound(const size_t idx) const
Return largest key possible in bucket idx assuming insertion_limit==0.
Definition: radix_heap.hpp:313
unsigned clz(Integral x)
std::pair< size_t, size_t > get_index_(size_t i) const
Definition: radix_heap.hpp:160
void reorganize_()
Definition: radix_heap.hpp:574
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:60
bool is_set(const size_t i) const
Returns value of the i-th.
Definition: radix_heap.hpp:249
typename std::make_unsigned< int_type >::type rank_type
Definition: radix_heap.hpp:48
bucket_index_type emplace(const key_type key, Args &&...args)
Construct and insert element with priority key.
Definition: radix_heap.hpp:433
bool empty() const
True if all bits are false.
Definition: radix_heap.hpp:259
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
void clear_bit(const size_t i)
Set the i-th bit to false.
Definition: radix_heap.hpp:244
void initialize_()
Definition: radix_heap.hpp:563
std::array< ranked_key_type, num_buckets > mins_
Definition: radix_heap.hpp:560
void swap_top_bucket(bucket_data_type &exchange_bucket)
Exchanges the top buckets with an empty user provided bucket.
Definition: radix_heap.hpp:534
const value_type & top()
Returns currently smallest key and data.
Definition: radix_heap.hpp:515
#define TLX_LIKELY(c)
Definition: likely.hpp:23
void clear()
Clears all internal queues and resets insertion limit.
Definition: radix_heap.hpp:545
bucket_map_type bucket_map_
Definition: radix_heap.hpp:556
This class implements a monotonic integer min priority queue, more specific a multi-level radix heap...
Definition: radix_heap.hpp:376
Used as an adapter to implement RadixHeapPair on top of RadixHeap.
Definition: radix_heap.hpp:337
radix_heap_detail::BitArray< num_buckets > filled_
Definition: radix_heap.hpp:561
size_t size() const
Returns number of elements currently stored.
Definition: radix_heap.hpp:502
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:402
Compute the rank of an integer x (i.e.
Definition: radix_heap.hpp:41
KeyType key_type
Definition: radix_heap.hpp:384
std::array< bucket_data_type, num_buckets > buckets_data_
Definition: radix_heap.hpp:558
std::array< child_type, root_size > child_array_type
Definition: radix_heap.hpp:108
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
A BitArray of fixed size supporting reading, setting, and clearing of individual bits.
Definition: radix_heap.hpp:225
void clear_all()
Sets all bits to false.
Definition: radix_heap.hpp:254
bool empty() const
Indicates whether size() == 0.
Definition: radix_heap.hpp:497
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
static constexpr size_t num_buckets_(size_t bits)
Definition: radix_heap.hpp:323
RadixHeap(KeyExtract key_extract=KeyExtract{})
Definition: radix_heap.hpp:404
size_t find_lsb() const
Finds the bit with smallest index that is set.
Definition: radix_heap.hpp:265
static constexpr rank_type rank_of_int(int_type i)
Maps value i to its rank in int_type.
Definition: radix_heap.hpp:52
key_type peak_top_key() const
Returns currently smallest key without updating the insertion limit.
Definition: radix_heap.hpp:507
void set_bit(const size_t i)
Set the i-th bit to true.
Definition: radix_heap.hpp:239
Internal implementation of BitArray; do not invoke directly.
Definition: radix_heap.hpp:90
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 push(const value_type &value)
Insert element with priority key.
Definition: radix_heap.hpp:467
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
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:551
static constexpr bool use_identity_
Definition: radix_heap.hpp:67
typename std::conditional< Size<=32, uint32_t, uint64_t >::type uint_type
Definition: radix_heap.hpp:171
void pop()
Removes smallest element.
Definition: radix_heap.hpp:522
ValueType value_type
Definition: radix_heap.hpp:385
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 rank_type sign_bit_
Definition: radix_heap.hpp:70