Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
PriorityQueue.h
Go to the documentation of this file.
1
32#pragma once
33
38
39#include <functional>
40#include <utility>
41
42namespace ogdf {
43
44
46
59template<typename T, class C = std::less<T>, template<typename, class> class Impl = PairingHeap>
61public:
62 using size_type = std::size_t;
63
64private:
66 const C& m_cmp;
69
70public:
71 using value_type = T;
72 using handle = typename SpecImpl::Handle;
75
77
81 explicit PriorityQueue(const C& cmp = C(), int initialSize = 128)
83
87
90 other.swap(*this);
91 }
92
94
99 template<class InputIt>
100 PriorityQueue(InputIt first, InputIt last, const C& cmp = C()) : PriorityQueue(cmp) {
101 push(first, last);
102 }
103
105
109 PriorityQueue(std::initializer_list<value_type> init, const C& cmp = C())
110 : PriorityQueue(std::begin(init), std::end(init), cmp) { }
111
113 ~PriorityQueue() { delete m_impl; }
114
117 other.swap(*this);
118 return *this;
119 }
120
122
126 PriorityQueue& operator=(std::initializer_list<value_type> ilist) {
128 tmp.swap(*this);
129 return *this;
130 }
131
134 std::swap(m_size, other.m_size);
135 std::swap(m_impl, other.m_impl);
136 }
137
139 friend void swap(PriorityQueue& a, PriorityQueue& b) { a.swap(b); }
140
142 const T& top() const { return m_impl->top(); }
143
145 /*
146 * @param value A value to be inserted.
147 * @return Handle to the inserted node.
148 */
150 m_size++;
151 return m_impl->push(value);
152 }
153
155
159 template<class InputIt>
160 void push(InputIt first, InputIt last) {
161 while (first != last) {
162 push(*(first++));
163 }
164 }
165
167
170 void push(std::initializer_list<value_type> ilist) { push(std::begin(ilist), std::end(ilist)); }
171
173
176 void pop() {
177 m_size--;
178 m_impl->pop();
179 }
180
182
189 void decrease(handle pos, const T& value) { m_impl->decrease(pos, value); }
190
192
198 m_impl->merge(*other.m_impl);
199 m_size += other.m_size;
200 other.m_size = 0;
201 }
202
204 void clear() {
206 tmp.swap(*this);
207 }
208
210 bool empty() const { return size() == 0; }
211
213 size_type size() const { return m_size; }
214
221 const T& value(handle pos) const { return m_impl->value(pos); }
222};
223
228namespace pq_internal {
229
231template<typename T, typename C>
232class Compare {
233public:
234 Compare(const C& compare = C()) : m_compare(compare) { }
235
237
238 bool operator()(const T& x, const T& y) const { return m_compare(x.priority(), y.priority()); }
239
240private:
242};
243
245template<typename E, typename P>
247public:
249
251
252 const E& element() const { return m_element; }
253
254 const P& priority() const { return m_priority; }
255
256private:
259};
260
262template<typename E, typename P, class C, template<typename, class> class Impl>
264
266template<typename E, typename P, class C, template<typename, class> class Impl>
267class PrioritizedQueue : public SuperQueueTemplate<E, P, C, Impl> {
268private:
271
273
274public:
276 using Handle = typename SuperQueue::handle;
277
278 PrioritizedQueue(const C& cmp = C(), int initialSize = 128)
280
282 const E& topElement() const { return SuperQueue::top().element(); }
283
285 const P& topPriority() const { return SuperQueue::top().priority(); }
286
293 Handle push(const E& element, const P& priority) {
294 Pair pair(element, priority);
295 Handle result = SuperQueue::push(pair);
296 return result;
297 }
298
299 void decrease(Handle pos, const P& priority) {
300 OGDF_ASSERT(m_comp(priority, this->value(pos).priority()));
301 Pair pair(this->value(pos).element(), priority);
302 SuperQueue::decrease(pos, pair);
303 }
304};
305
306template<typename E, typename P, class C, template<typename, class> class Impl, typename Map>
307class PrioritizedArrayQueueBase : public PrioritizedQueue<E, P, C, Impl> {
308protected:
311
312public:
314 bool contains(const E& element) const { return m_handles[element] != nullptr; }
315
316 /*
317 * Returns the priority of the key.
318 * Note, that the behaviour is undefined if the key is not present.
319 */
320 const P& priority(const E& element) const {
321 OGDF_ASSERT(contains(element));
322 return this->value(m_handles[element]).priority();
323 }
324
329 void push(const E& element, const P& priority) {
330 OGDF_ASSERT(m_handles[element] == nullptr);
331 m_handles[element] = SuperQueue::push(element, priority);
332 }
333
337 void pop() {
340 }
341
347 void decrease(const E& element, const P& priority) {
348 Handle pos = m_handles[element];
350 }
351
353 void clear() {
355 m_handles.clear();
356 }
357
358protected:
359 PrioritizedArrayQueueBase(const C& cmp, int initialSize, const Map& map)
360 : SuperQueue(cmp, initialSize), m_handles(map) { }
361
363};
364
365}
366
368
381template<typename E, typename P, class C = std::less<P>, template<typename, class> class Impl = PairingHeap>
383
385
405template<typename E, typename P, class C = std::less<P>,
406 template<typename, class> class Impl = PairingHeap, template<typename> class HashFunc = DefHashFunc>
408 : public pq_internal::PrioritizedArrayQueueBase<E, P, C, Impl,
409 HashArray<E, typename PrioritizedQueue<E, P, C, Impl>::Handle, HashFunc<E>>> {
410private:
414
415public:
424};
425
427template<typename P, class C, template<typename, class> class Impl, template<typename> class HashFunc>
429 : public pq_internal::PrioritizedArrayQueueBase<node, P, C, Impl,
430 NodeArray<typename PrioritizedQueue<node, P, C, Impl>::Handle>> {
431private:
434
435public:
444 PrioritizedMapQueue(const Graph& G, const C& cmp = C(), int initialSize = -1)
445 : SuperQueue(cmp, initialSize == -1 ? G.numberOfNodes() : initialSize,
446 NodeArray<Handle>(G, nullptr)) { }
447
449 void clear() {
451 this->m_handles.init(*this->m_handles.graphOf(), nullptr);
452 }
453};
454
456template<typename P, class C, template<typename, class> class Impl, template<typename> class HashFunc>
458 : public pq_internal::PrioritizedArrayQueueBase<edge, P, C, Impl,
459 EdgeArray<typename PrioritizedQueue<edge, P, C, Impl>::Handle>> {
460private:
464
465public:
474 PrioritizedMapQueue(const Graph& G, const C& cmp = C(), int initialSize = -1)
475 : SuperQueue(cmp, initialSize == -1 ? G.numberOfEdges() : initialSize,
476 EdgeArray<Handle>(G, nullptr)) { }
477
479 void clear() {
481 this->m_handles.init(*this->m_handles.graphOf(), nullptr);
482 }
483};
484
485
486}
Declaration and implementation of EdgeArray class.
Declaration and implementation of HashArray class.
Declaration and implementation of NodeArray class.
Implementation of pairing heap data structure.
Default hash functions.
Definition Hashing.h:213
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Indexed arrays using hashing for element access.
Definition HashArray.h:93
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Pairing heap implementation.
Definition PairingHeap.h:70
void clear()
Removes all elements from this queue.
PrioritizedMapQueue(const Graph &G, const C &cmp=C(), int initialSize=-1)
Creates a new queue with the given comparer.
typename PrioritizedQueue< edge, P, C, Impl >::Handle Handle
typename PrioritizedQueue< node, P, C, Impl >::Handle Handle
PrioritizedMapQueue(const Graph &G, const C &cmp=C(), int initialSize=-1)
Creates a new queue with the given comparer.
void clear()
Removes all elements from this queue.
Prioritized queue interface wrapper for heaps.
PrioritizedMapQueue(const C &cmp=C(), int initialSize=128)
Creates a new queue with the given comparer.
Priority queue interface wrapper for heaps.
void pop()
Removes the top element from the heap.
void push(std::initializer_list< value_type > ilist)
Inserts new elements specified by the given initializer list.
const value_type & const_reference
void push(InputIt first, InputIt last)
Inserts new elements specified by the given range.
PriorityQueue & operator=(PriorityQueue other)
Copy and move assignment.
void swap(PriorityQueue &other)
Swaps the contents.
const T & value(handle pos) const
Returns the priority of that handle.
typename SpecImpl::Handle handle
value_type & reference
PriorityQueue(std::initializer_list< value_type > init, const C &cmp=C())
Creates priority queue with contents of the given initializer list.
PriorityQueue(PriorityQueue &&other)
Move constructor.
handle push(const value_type &value)
Inserts a new element with given value into the queue.
PriorityQueue(InputIt first, InputIt last, const C &cmp=C())
Creates priority queue with contents of the given range.
PriorityQueue & operator=(std::initializer_list< value_type > ilist)
Assigns the priority queue contents of the given initializer list.
Impl< T, C > SpecImpl
~PriorityQueue()
Destroys the underlying data structure.
void merge(PriorityQueue &other)
Merges in enqueued values of other queue.
PriorityQueue(const PriorityQueue &other)
Copy constructor.
PriorityQueue(const C &cmp=C(), int initialSize=128)
Creates empty priority queue.
std::size_t size_type
void decrease(handle pos, const T &value)
Decreases value of the element specified by handle to value.
size_type m_size
Number of entries.
void clear()
Removes all the entries from the queue.
friend void swap(PriorityQueue &a, PriorityQueue &b)
Swaps the contents.
SpecImpl * m_impl
Underlying heap data structure.
bool empty() const
Checks whether the queue is empty.
const T & top() const
Returns reference to the top element in the queue.
size_type size() const
Returns the number of enqueued elements.
Used to compare elements with assigned priorities.
bool operator()(const T &x, const T &y) const
Compare(const Compare &other)
Compare(const C &compare=C())
Pair for storing an element and a priority.
PairTemplate(const E &element, const P &priority)
void decrease(const E &element, const P &priority)
Decreases the priority of the given element.
bool contains(const E &element) const
Returns whether this queue contains that key.
typename PrioritizedQueue< E, P, C, Impl >::Handle Handle
void pop()
Removes the topmost element from the queue.
void clear()
Removes all elements from this queue.
PrioritizedArrayQueueBase(const C &cmp, int initialSize, const Map &map)
void push(const E &element, const P &priority)
Adds a new element to the queue.
const P & priority(const E &element) const
Defines a queue for handling prioritized elements.
const E & topElement() const
Returns the topmost element in the queue.
const P & topPriority() const
Returns the priority of the topmost element in this queue.
Handle push(const E &element, const P &priority)
Pushes a new element with the respective priority to the queue.
typename SuperQueue::handle Handle
The type of handle for accessing the elements of this queue.
PrioritizedQueue(const C &cmp=C(), int initialSize=128)
void decrease(Handle pos, const P &priority)
EdgeElement * edge
The type of edges.
Definition Graph_d.h:68
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Definition GML.h:110