Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

PriorityQueue.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <utility>
35 #include <functional>
36 
37 #include <ogdf/basic/NodeArray.h>
38 #include <ogdf/basic/EdgeArray.h>
39 #include <ogdf/basic/HashArray.h>
40 
42 
43 namespace ogdf {
44 
45 
47 
60 template<
61  typename T,
62  class C=std::less<T>,
63  template<typename, class> class Impl=PairingHeap
64 >
66 public:
67  using size_type = std::size_t;
68 
69 private:
71  const C &m_cmp;
72  using SpecImpl = Impl<T, C>;
74 
75 public:
76  using value_type = T;
77  using handle = typename SpecImpl::Handle;
78  using reference = value_type &;
79  using const_reference = const value_type &;
80 
82 
86  explicit PriorityQueue(const C &cmp = C(), int initialSize = 128)
87  : m_size(0), m_cmp(cmp), m_impl(new SpecImpl(cmp, initialSize))
88  {
89  }
90 
93  : m_size(other.m_size), m_impl(new SpecImpl(other.m_impl))
94  {
95  }
96 
99  : PriorityQueue(other.m_impl->comparator())
100  {
101  other.swap(*this);
102  }
103 
105 
110  template<class InputIt>
111  PriorityQueue(InputIt first, InputIt last, const C &cmp = C())
112  : PriorityQueue(cmp)
113  {
114  push(first, last);
115  }
116 
118 
122  PriorityQueue(std::initializer_list<value_type> init, const C &cmp = C())
123  : PriorityQueue(std::begin(init), std::end(init), cmp)
124  {
125  }
126 
129  delete m_impl;
130  }
131 
134  other.swap(*this);
135  return *this;
136  }
137 
139 
143  PriorityQueue &operator=(std::initializer_list<value_type> ilist) {
144  PriorityQueue tmp(ilist);
145  tmp.swap(*this);
146  return *this;
147  }
148 
150  void swap(PriorityQueue &other) {
151  std::swap(m_size, other.m_size);
152  std::swap(m_impl, other.m_impl);
153  }
154 
156  friend void swap(PriorityQueue &a, PriorityQueue &b) {
157  a.swap(b);
158  }
159 
161  const T &top() const {
162  return m_impl->top();
163  }
164 
166  /*
167  * @param value A value to be inserted.
168  * @return Handle to the inserted node.
169  */
171  m_size++;
172  return m_impl->push(value);
173  }
174 
176 
180  template<class InputIt>
181  void push(InputIt first, InputIt last) {
182  while(first != last) {
183  push(*(first++));
184  }
185  }
186 
188 
191  void push(std::initializer_list<value_type> ilist) {
192  push(std::begin(ilist), std::end(ilist));
193  }
194 
196 
199  void pop() {
200  m_size--;
201  m_impl->pop();
202  }
203 
205 
212  void decrease(handle pos, const T &value) {
213  m_impl->decrease(pos, value);
214  }
215 
217 
222  void merge(PriorityQueue &other) {
223  m_impl->merge(*other.m_impl);
224  m_size += other.m_size;
225  other.m_size = 0;
226  }
227 
229  void clear() {
230  PriorityQueue tmp(m_cmp);
231  tmp.swap(*this);
232  }
233 
235  bool empty() const {
236  return size() == 0;
237  }
238 
240  size_type size() const {
241  return m_size;
242  }
243 
250  const T &value(handle pos) const {
251  return m_impl->value(pos);
252  }
253 };
254 
259 namespace pq_internal {
260 
262 template<
263  typename T,
264  typename C
265 >
266 class Compare
267 {
268 public:
269  Compare(const C &compare = C()) : m_compare(compare) {}
270 
271  Compare(const Compare& other) : m_compare(other.m_compare) {}
272 
273  bool operator()(const T &x, const T &y) const {
274  return m_compare(x.priority(), y.priority());
275  }
276 private:
278 };
279 
281 template<
282  typename E,
283  typename P
284 >
286 {
287 public:
289  : m_priority(-1)
290  {
291  }
292 
293  PairTemplate(const E &element, const P &priority)
295  {
296  }
297 
298  const E &element() const {
299  return m_element;
300  }
301 
302  const P &priority() const {
303  return m_priority;
304  }
305 
306 private:
309 };
310 
312 template<
313  typename E,
314  typename P,
315  class C,
316  template<typename, class> class Impl
317 >
319 
321 template<
322  typename E,
323  typename P,
324  class C,
325  template<typename, class> class Impl
326 >
327 class PrioritizedQueue : public SuperQueueTemplate<E, P, C, Impl>
328 {
329 private:
332 
334 
335 public:
337  using Handle = typename SuperQueue::handle;
338 
339  PrioritizedQueue(const C &cmp = C(), int initialSize = 128)
340  : SuperQueue(Compare<PairTemplate<E, P>, C>(cmp), initialSize), m_comp(cmp)
341  {
342  }
343 
345  const E &topElement() const {
346  return SuperQueue::top().element();
347  }
348 
350  const P &topPriority() const {
351  return SuperQueue::top().priority();
352  }
353 
360  Handle push(const E &element, const P &priority) {
361  Pair pair(element, priority);
362  Handle result = SuperQueue::push(pair);
363  return result;
364  }
365 
366  void decrease(Handle pos, const P &priority) {
367  OGDF_ASSERT(m_comp(priority, this->value(pos).priority()));
368  Pair pair(this->value(pos).element(), priority);
369  SuperQueue::decrease(pos, pair);
370  }
371 };
372 
373 template<
374  typename E,
375  typename P,
376  class C,
377  template<typename, class> class Impl,
378  typename Map
379 >
380 class PrioritizedArrayQueueBase : public PrioritizedQueue<E, P, C, Impl>
381 {
382 protected:
385 
386 public:
387 
389  bool contains(const E &element) const
390  {
391  return m_handles[element] != nullptr;
392  }
393 
394  /*
395  * Returns the priority of the key.
396  * Note, that the behaviour is undefined if the key is not present.
397  */
398  const P &priority(const E &element) const
399  {
400  OGDF_ASSERT(contains(element));
401  return this->value(m_handles[element]).priority();
402  }
403 
408  void push(const E &element, const P &priority) {
409  OGDF_ASSERT(m_handles[element] == nullptr);
410  m_handles[element] = SuperQueue::push(element, priority);
411  }
412 
416  void pop() {
417  m_handles[SuperQueue::topElement()] = nullptr;
418  SuperQueue::pop();
419  }
420 
426  void decrease(const E &element, const P &priority) {
427  Handle pos = m_handles[element];
429  }
430 
432  void clear() {
434  m_handles.clear();
435  }
436 
437 protected:
438  PrioritizedArrayQueueBase(const C &cmp, int initialSize, const Map &map)
439  : SuperQueue(cmp, initialSize), m_handles(map)
440  {
441  }
442 
444 };
445 
446 }
447 
449 
462 template<
463  typename E,
464  typename P,
465  class C=std::less<P>,
466  template<typename, class> class Impl=PairingHeap
467 >
469 
471 
491 template<
492  typename E,
493  typename P,
494  class C=std::less<P>,
495  template<typename, class> class Impl=PairingHeap,
496  template<typename> class HashFunc=DefHashFunc
497 >
498 class PrioritizedMapQueue : public pq_internal::PrioritizedArrayQueueBase<E, P, C, Impl, HashArray<E, typename PrioritizedQueue<E, P, C, Impl>::Handle, HashFunc<E>>>
499 {
500 private:
503 
504 public:
505 
512  PrioritizedMapQueue(const C &cmp = C(), int initialSize = 128)
513  : SuperQueue(cmp, initialSize, CustomHashArray(nullptr))
514  {
515  }
516 };
517 
519 template<
520  typename P,
521  class C,
522  template<typename, class> class Impl,
523  template<typename> class HashFunc
524 >
525 class PrioritizedMapQueue<node, P, C, Impl, HashFunc> : public pq_internal::PrioritizedArrayQueueBase<node, P, C, Impl, NodeArray<typename PrioritizedQueue<node, P, C, Impl>::Handle>>
526 {
527 private:
530 
531 public:
532 
541  PrioritizedMapQueue(const Graph &G, const C &cmp = C(), int initialSize = -1)
542  : SuperQueue(cmp, initialSize == -1 ? G.numberOfNodes() : initialSize, NodeArray<Handle>(G, nullptr))
543  {
544  }
545 
547  void clear() {
549  this->m_handles.init(*this->m_handles.graphOf(), nullptr);
550  }
551 };
552 
554 template<
555  typename P,
556  class C,
557  template<typename, class> class Impl,
558  template<typename> class HashFunc
559 >
560 class PrioritizedMapQueue<edge, P, C, Impl, HashFunc> : public pq_internal::PrioritizedArrayQueueBase<edge, P, C, Impl, EdgeArray<typename PrioritizedQueue<edge, P, C, Impl>::Handle>>
561 {
562 private:
565 
566 public:
567 
576  PrioritizedMapQueue(const Graph &G, const C &cmp = C(), int initialSize = -1)
577  : SuperQueue(cmp, initialSize == -1 ? G.numberOfEdges() : initialSize, EdgeArray<Handle>(G, nullptr))
578  {
579  }
580 
582  void clear() {
584  this->m_handles.init(*this->m_handles.graphOf(), nullptr);
585  }
586 };
587 
588 
589 }
ogdf::pq_internal::PrioritizedQueue::PrioritizedQueue
PrioritizedQueue(const C &cmp=C(), int initialSize=128)
Definition: PriorityQueue.h:339
HashArray.h
Declaration and implementation of HashArray class.
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::PriorityQueue::size_type
std::size_t size_type
Definition: PriorityQueue.h:67
ogdf::DefHashFunc
Default hash functions.
Definition: Hashing.h:218
ogdf::PriorityQueue::PriorityQueue
PriorityQueue(const PriorityQueue &other)
Copy constructor.
Definition: PriorityQueue.h:92
ogdf::PriorityQueue::PriorityQueue
PriorityQueue(std::initializer_list< value_type > init, const C &cmp=C())
Creates priority queue with contents of the given initializer list.
Definition: PriorityQueue.h:122
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::pq_internal::PrioritizedArrayQueueBase::pop
void pop()
Removes the topmost element from the queue.
Definition: PriorityQueue.h:416
ogdf::pq_internal::PrioritizedQueue::topPriority
const P & topPriority() const
Returns the priority of the topmost element in this queue.
Definition: PriorityQueue.h:350
ogdf::PriorityQueue::value
const T & value(handle pos) const
Returns the priority of that handle.
Definition: PriorityQueue.h:250
ogdf::pq_internal::PrioritizedArrayQueueBase::push
void push(const E &element, const P &priority)
Adds a new element to the queue.
Definition: PriorityQueue.h:408
ogdf::PrioritizedMapQueue< node, P, C, Impl, HashFunc >::clear
void clear()
Removes all elements from this queue.
Definition: PriorityQueue.h:547
ogdf::PriorityQueue::PriorityQueue
PriorityQueue(PriorityQueue &&other)
Move constructor.
Definition: PriorityQueue.h:98
ogdf::PriorityQueue::~PriorityQueue
~PriorityQueue()
Destroys the underlying data structure.
Definition: PriorityQueue.h:128
ogdf::pq_internal::PrioritizedArrayQueueBase::priority
const P & priority(const E &element) const
Definition: PriorityQueue.h:398
ogdf::PrioritizedMapQueue< node, P, C, Impl, HashFunc >::PrioritizedMapQueue
PrioritizedMapQueue(const Graph &G, const C &cmp=C(), int initialSize=-1)
Creates a new queue with the given comparer.
Definition: PriorityQueue.h:541
ogdf::pq_internal::PrioritizedQueue::decrease
void decrease(Handle pos, const P &priority)
Definition: PriorityQueue.h:366
ogdf::pq_internal::PairTemplate::PairTemplate
PairTemplate()
Definition: PriorityQueue.h:288
ogdf::PriorityQueue::push
void push(std::initializer_list< value_type > ilist)
Inserts new elements specified by the given initializer list.
Definition: PriorityQueue.h:191
ogdf::PriorityQueue::push
void push(InputIt first, InputIt last)
Inserts new elements specified by the given range.
Definition: PriorityQueue.h:181
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::pq_internal::PrioritizedQueue
Defines a queue for handling prioritized elements.
Definition: PriorityQueue.h:327
ogdf::PriorityQueue::m_size
size_type m_size
Number of entries.
Definition: PriorityQueue.h:70
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
ogdf::PriorityQueue::clear
void clear()
Removes all the entries from the queue.
Definition: PriorityQueue.h:229
ogdf::PrioritizedMapQueue< edge, P, C, Impl, HashFunc >::Handle
typename PrioritizedQueue< edge, P, C, Impl >::Handle Handle
Definition: PriorityQueue.h:563
ogdf::pq_internal::PrioritizedArrayQueueBase::contains
bool contains(const E &element) const
Returns whether this queue contains that key.
Definition: PriorityQueue.h:389
ogdf::PriorityQueue::pop
void pop()
Removes the top element from the heap.
Definition: PriorityQueue.h:199
ogdf::PriorityQueue::value_type
T value_type
Definition: PriorityQueue.h:76
ogdf::PriorityQueue::swap
friend void swap(PriorityQueue &a, PriorityQueue &b)
Swaps the contents.
Definition: PriorityQueue.h:156
ogdf::PriorityQueue::operator=
PriorityQueue & operator=(std::initializer_list< value_type > ilist)
Assigns the priority queue contents of the given initializer list.
Definition: PriorityQueue.h:143
ogdf::pq_internal::PairTemplate::m_element
E m_element
Definition: PriorityQueue.h:307
ogdf::pq_internal::Compare::Compare
Compare(const Compare &other)
Definition: PriorityQueue.h:271
ogdf::PriorityQueue::empty
bool empty() const
Checks whether the queue is empty.
Definition: PriorityQueue.h:235
ogdf::pq_internal::PairTemplate::element
const E & element() const
Definition: PriorityQueue.h:298
ogdf::PriorityQueue::PriorityQueue
PriorityQueue(const C &cmp=C(), int initialSize=128)
Creates empty priority queue.
Definition: PriorityQueue.h:86
ogdf::PriorityQueue::push
handle push(const value_type &value)
Inserts a new element with given value into the queue.
Definition: PriorityQueue.h:170
ogdf::PriorityQueue::decrease
void decrease(handle pos, const T &value)
Decreases value of the element specified by handle to value.
Definition: PriorityQueue.h:212
ogdf::pq_internal::PrioritizedQueue::push
Handle push(const E &element, const P &priority)
Pushes a new element with the respective priority to the queue.
Definition: PriorityQueue.h:360
ogdf::PairingHeap
Pairing heap implementation.
Definition: PairingHeap.h:72
ogdf::pq_internal::PairTemplate::priority
const P & priority() const
Definition: PriorityQueue.h:302
ogdf::PrioritizedMapQueue
Prioritized queue interface wrapper for heaps.
Definition: PriorityQueue.h:498
ogdf::PrioritizedMapQueue::PrioritizedMapQueue
PrioritizedMapQueue(const C &cmp=C(), int initialSize=128)
Creates a new queue with the given comparer.
Definition: PriorityQueue.h:512
EdgeArray.h
Declaration and implementation of EdgeArray class.
ogdf::pq_internal::PrioritizedArrayQueueBase::m_handles
Map m_handles
Definition: PriorityQueue.h:443
ogdf::pq_internal::PrioritizedArrayQueueBase
Definition: PriorityQueue.h:380
ogdf::HashArray
Indexed arrays using hashing for element access.
Definition: HashArray.h:94
ogdf::PrioritizedMapQueue< edge, P, C, Impl, HashFunc >::clear
void clear()
Removes all elements from this queue.
Definition: PriorityQueue.h:582
ogdf::PriorityQueue::m_cmp
const C & m_cmp
Definition: PriorityQueue.h:71
ogdf::pq_internal::Compare::operator()
bool operator()(const T &x, const T &y) const
Definition: PriorityQueue.h:273
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
PairingHeap.h
Implementation of pairing heap data structure.
ogdf::PriorityQueue::size
size_type size() const
Returns the number of enqueued elements.
Definition: PriorityQueue.h:240
ogdf::PriorityQueue::operator=
PriorityQueue & operator=(PriorityQueue other)
Copy and move assignment.
Definition: PriorityQueue.h:133
ogdf::PriorityQueue::PriorityQueue
PriorityQueue(InputIt first, InputIt last, const C &cmp=C())
Creates priority queue with contents of the given range.
Definition: PriorityQueue.h:111
ogdf::pq_internal::Compare::m_compare
C m_compare
Definition: PriorityQueue.h:277
ogdf::pq_internal::PairTemplate::PairTemplate
PairTemplate(const E &element, const P &priority)
Definition: PriorityQueue.h:293
ogdf::HashingBase::init
void init(int tableSize)
Initializes the table for given table size.
ogdf::PriorityQueue::reference
value_type & reference
Definition: PriorityQueue.h:78
ogdf::pq_internal::PrioritizedQueue::topElement
const E & topElement() const
Returns the topmost element in the queue.
Definition: PriorityQueue.h:345
ogdf::pq_internal::PairTemplate::m_priority
P m_priority
Definition: PriorityQueue.h:308
ogdf::pq_internal::PrioritizedArrayQueueBase::clear
void clear()
Removes all elements from this queue.
Definition: PriorityQueue.h:432
NodeArray.h
Declaration and implementation of NodeArray class.
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::pq_internal::PrioritizedArrayQueueBase::decrease
void decrease(const E &element, const P &priority)
Decreases the priority of the given element.
Definition: PriorityQueue.h:426
ogdf::PriorityQueue::top
const T & top() const
Returns reference to the top element in the queue.
Definition: PriorityQueue.h:161
ogdf::pq_internal::Compare::Compare
Compare(const C &compare=C())
Definition: PriorityQueue.h:269
std
Definition: GML.h:110
ogdf::pq_internal::PrioritizedQueue::m_comp
C m_comp
Definition: PriorityQueue.h:333
ogdf::PrioritizedMapQueue< node, P, C, Impl, HashFunc >::Handle
typename PrioritizedQueue< node, P, C, Impl >::Handle Handle
Definition: PriorityQueue.h:528
ogdf::pq_internal::PrioritizedQueue< E, P, std::less< P >, PairingHeap >::Handle
typename SuperQueue::handle Handle
The type of handle for accessing the elements of this queue.
Definition: PriorityQueue.h:337
ogdf::pq_internal::PrioritizedArrayQueueBase::PrioritizedArrayQueueBase
PrioritizedArrayQueueBase(const C &cmp, int initialSize, const Map &map)
Definition: PriorityQueue.h:438
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::PriorityQueue::handle
typename SpecImpl::Handle handle
Definition: PriorityQueue.h:77
ogdf::PriorityQueue::swap
void swap(PriorityQueue &other)
Swaps the contents.
Definition: PriorityQueue.h:150
ogdf::pq_internal::PairTemplate
Pair for storing an element and a priority.
Definition: PriorityQueue.h:285
ogdf::PriorityQueue::m_impl
SpecImpl * m_impl
Underlying heap data structure.
Definition: PriorityQueue.h:73
ogdf::PriorityQueue
Priority queue interface wrapper for heaps.
Definition: PriorityQueue.h:65
ogdf::pq_internal::Compare
Used to compare elements with assigned priorities.
Definition: PriorityQueue.h:266
ogdf::PrioritizedMapQueue< edge, P, C, Impl, HashFunc >::PrioritizedMapQueue
PrioritizedMapQueue(const Graph &G, const C &cmp=C(), int initialSize=-1)
Creates a new queue with the given comparer.
Definition: PriorityQueue.h:576
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::PriorityQueue::SpecImpl
Impl< T, C > SpecImpl
Definition: PriorityQueue.h:72
ogdf::PriorityQueue::merge
void merge(PriorityQueue &other)
Merges in enqueued values of other queue.
Definition: PriorityQueue.h:222
ogdf::PriorityQueue::const_reference
const value_type & const_reference
Definition: PriorityQueue.h:79