Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

RadixHeap.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <functional>
35 #include <utility>
36 #include <array>
37 #include <vector>
38 
39 
40 namespace ogdf {
41 
42 
43 template<typename V, typename P>
45 public:
46  V value;
48 
51 
52  RadixHeapNode(const V &nodeValue, const P &nodePriority)
53  : value(nodeValue), priority(nodePriority),
54  prev(nullptr), next(nullptr)
55  {
56  }
57 };
58 
59 
61 
73 template<typename V, typename P>
74 class RadixHeap {
75 public:
77  RadixHeap();
78 
80  ~RadixHeap();
81 
82 
84 
89  RadixHeapNode<V, P> *push(const V &value, const P &priority);
90 
92 
97  V pop();
98 
100  std::size_t size() const {
101  return m_size;
102  }
103 
105  bool empty() const {
106  return size() == 0;
107  }
108 
109 private:
111  static constexpr std::size_t BITS = sizeof(P) * 8;
112 
113  std::size_t m_size;
114 
117  std::array<Bucket, BITS + 1> m_buckets;
118 
120  void insert(RadixHeapNode<V, P> *heapNode);
121 
123  template<typename T>
124  static std::size_t msbSet(T mask) {
125  std::size_t i = 0;
126  while(mask != 0) {
127  mask >>= 1;
128  i++;
129  }
130  return i;
131  }
132 
133 #ifdef __has_builtin
134 #if __has_builtin(__builtin_clz)
135  static std::size_t msbSet(unsigned int mask) {
136  return mask == 0 ? 0 : (BITS - __builtin_clz(mask));
137  }
138 
139  static std::size_t msbSet(unsigned long mask) {
140  return mask == 0 ? 0 : (BITS - __builtin_clzl(mask));
141  }
142 
143  static std::size_t msbSet(unsigned long long mask) {
144  return mask == 0 ? 0 : (BITS - __builtin_clzll(mask));
145  }
146 #endif
147 #endif
148 
149 };
150 
151 
152 template<typename V, typename P>
154 : m_size(0), m_minimum(0), m_bucketMask(0)
155 {
156  m_buckets.fill(nullptr);
157 }
158 
159 
160 template<typename V, typename P>
162 {
163  for(Bucket &bucket : m_buckets) {
164  auto it = bucket;
165  while(it != nullptr) {
166  auto next = it->next;
167  delete it;
168  it = next;
169  }
170  }
171 }
172 
173 
174 template<typename V, typename P>
175 RadixHeapNode<V, P> *RadixHeap<V, P>::push(const V &value, const P &priority)
176 {
177  m_size++;
178 
179  RadixHeapNode<V, P> *heapNode = new RadixHeapNode<V, P>(value, priority);
180  insert(heapNode);
181  return heapNode;
182 }
183 
184 
185 template<typename V, typename P>
187 {
188  m_size--;
189 
190  if(m_buckets[0] != nullptr) {
191  V result = std::move(m_buckets[0]->value);
192 
193  Bucket tmp = m_buckets[0]->next;
194  delete m_buckets[0];
195  m_buckets[0] = tmp;
196 
197  if(m_buckets[0] != nullptr) {
198  m_buckets[0]->prev = nullptr;
199  }
200  return result;
201  }
202 
203  std::size_t ind = BITS + 1 - msbSet(m_bucketMask);
204 
205  Bucket bucket = m_buckets[ind];
206  m_buckets[ind] = nullptr;
207  if(ind != 0) {
208  m_bucketMask ^= (P(1) << (8 * sizeof(P) - ind));
209  }
210 
211 
212  Bucket min = bucket;
213  for(Bucket it = bucket; it != nullptr; it = it->next) {
214  if(it->priority < min->priority) {
215  min = it;
216  }
217  }
218 
219  if(min->prev != nullptr) {
220  min->prev->next = min->next;
221  } else {
222  bucket = min->next;
223  }
224 
225  if(min->next != nullptr) {
226  min->next->prev = min->prev;
227  }
228 
229  V result = std::move(min->value);
230  m_minimum = std::move(min->priority);
231  delete min;
232 
233  while(bucket != nullptr) {
234  Bucket next = bucket->next;
235  bucket->prev = nullptr;
236  insert(bucket);
237 
238  bucket = next;
239  }
240 
241  return result;
242 }
243 
244 
245 template<typename V, typename P>
247 {
248  std::size_t ind = msbSet(heapNode->priority ^ m_minimum);
249 
250  heapNode->next = m_buckets[ind];
251  if(m_buckets[ind] != nullptr) {
252  m_buckets[ind]->prev = heapNode;
253  }
254  m_buckets[ind] = heapNode;
255 
256  if(ind != 0) {
257  m_bucketMask |= (P(1) << (BITS - ind));
258  }
259 }
260 
261 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::RadixHeap::m_bucketMask
P m_bucketMask
Priority of the lowest element so far.
Definition: RadixHeap.h:116
ogdf::RadixHeap::m_minimum
P m_minimum
Number of elements.
Definition: RadixHeap.h:115
ogdf::RadixHeap::BITS
static constexpr std::size_t BITS
Definition: RadixHeap.h:111
ogdf::RadixHeap::msbSet
static std::size_t msbSet(T mask)
Returns most significant bit set on given mask.
Definition: RadixHeap.h:124
ogdf::RadixHeap::m_size
std::size_t m_size
Definition: RadixHeap.h:113
ogdf::RadixHeap::~RadixHeap
~RadixHeap()
Destructs the heap.
Definition: RadixHeap.h:161
ogdf::RadixHeap::size
std::size_t size() const
Number of elements contained within the heap.
Definition: RadixHeap.h:100
backward::details::move
const T & move(const T &v)
Definition: backward.hpp:243
ogdf::RadixHeap::pop
V pop()
Removes the top element from the heap and returns its value.
Definition: RadixHeap.h:186
ogdf::RadixHeapNode::next
RadixHeapNode< V, P > * next
Definition: RadixHeap.h:50
ogdf::RadixHeap::insert
void insert(RadixHeapNode< V, P > *heapNode)
Buckets with values.
Definition: RadixHeap.h:246
ogdf::RadixHeapNode::prev
RadixHeapNode< V, P > * prev
Definition: RadixHeap.h:49
ogdf::RadixHeapNode::priority
P priority
Definition: RadixHeap.h:47
ogdf::RadixHeap
Radix heap data structure implementation.
Definition: RadixHeap.h:74
ogdf::RadixHeapNode::RadixHeapNode
RadixHeapNode(const V &nodeValue, const P &nodePriority)
Definition: RadixHeap.h:52
ogdf::RadixHeap::m_buckets
std::array< Bucket, BITS+1 > m_buckets
Mask describing state of buckets (for fast lookup).
Definition: RadixHeap.h:117
ogdf::RadixHeap::RadixHeap
RadixHeap()
Creates empty heap.
Definition: RadixHeap.h:153
ogdf::RadixHeapNode::value
V value
Definition: RadixHeap.h:46
ogdf::RadixHeapNode
Definition: RadixHeap.h:44
ogdf::RadixHeap::empty
bool empty() const
Checks whether the heap is empty.
Definition: RadixHeap.h:105
ogdf::RadixHeap::push
RadixHeapNode< V, P > * push(const V &value, const P &priority)
Inserts a new node with given value and priority into a heap.
Definition: RadixHeap.h:175