aGrUM  0.13.2
multiPriorityQueue_tpl.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
27 // to help IDE parser
29 
30 namespace gum {
31 
32  // basic constructor
33  template < typename Val, typename Priority, typename Cmp, typename Alloc >
35  Cmp compare, Size capacity) :
36  __indices(capacity >> 1, true, false),
37  __cmp(compare) {
38  __heap.reserve(capacity);
39 
40  // for debugging purposes
41  GUM_CONSTRUCTOR(MultiPriorityQueue);
42  }
43 
44  // initializer list constructor
45  template < typename Val, typename Priority, typename Cmp, typename Alloc >
47  std::initializer_list< std::pair< Val, Priority > > list) :
48  __indices(Size(list.size()) / 2, true, false) {
49  // fill the queue
50  __heap.reserve(list.size());
51  for (const auto& elt : list) {
52  insert(elt.first, elt.second);
53  }
54 
55  // for debugging purposes
56  GUM_CONSTRUCTOR(MultiPriorityQueue);
57  }
58 
59  // copy constructor
60  template < typename Val, typename Priority, typename Cmp, typename Alloc >
63  __heap(from.__heap),
65  __cmp(from.__cmp) {
66  // for debugging purposes
67  GUM_CONS_CPY(MultiPriorityQueue);
68 
69  // fill the heap structure
70  for (const auto& val_and_index : __indices) {
71  const Val* val = &(val_and_index.first);
72  const std::vector< Size >& vect = val_and_index.second;
73  for (auto index : vect) {
74  __heap[index].second = val;
75  }
76  }
77  }
78 
79  // generalized copy constructor
80  template < typename Val, typename Priority, typename Cmp, typename Alloc >
81  template < typename OtherAlloc >
84  __indices(from.__indices),
85  __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
86  // for debugging purposes
87  GUM_CONS_CPY(MultiPriorityQueue);
88 
89  // fill the heap structure
90  if (__nb_elements) {
91  __heap.reserve(from.__heap.size());
92  for (const auto& elt : from.__heap) {
93  __heap.push_back(elt);
94  }
95  for (const auto& val_and_index : __indices) {
96  const Val* val = &(val_and_index.first);
97  const std::vector< Size >& vect = val_and_index.second;
98  for (auto index : vect) {
99  __heap[index].second = val;
100  }
101  }
102  }
103  }
104 
105  // move constructor
106  template < typename Val, typename Priority, typename Cmp, typename Alloc >
109  __heap(std::move(from.__heap)),
110  __indices(std::move(from.__indices)),
111  __nb_elements(std::move(from.__nb_elements)), __cmp(std::move(from.__cmp)) {
112  // for debugging purposes
113  GUM_CONS_MOV(MultiPriorityQueue);
114  }
115 
116  // destructor
117  template < typename Val, typename Priority, typename Cmp, typename Alloc >
119  // for debugging purposes
120  GUM_DESTRUCTOR(MultiPriorityQueue);
121  }
122 
123  // copy operator
124  template < typename Val, typename Priority, typename Cmp, typename Alloc >
128  // for debugging purposes
129  GUM_OP_CPY(MultiPriorityQueue);
130 
131  try {
132  // set the comprison function
133  __cmp = from.__cmp;
134 
135  // copy the indices and the heap
136  __indices = from.__indices;
137  __heap = from.__heap;
139 
140  // restore the link between __indices and __heap
141  for (const auto& val_and_index : __indices) {
142  const Val* val = &(val_and_index.first);
143  const std::vector< Size >& vect = val_and_index.second;
144  for (auto index : vect) {
145  __heap[index].second = val;
146  }
147  }
148  } catch (...) {
149  __heap.clear();
150  __indices.clear();
151  __nb_elements = 0;
152 
153  throw;
154  }
155 
156  return *this;
157  }
158 
159  // generalized copy operator
160  template < typename Val, typename Priority, typename Cmp, typename Alloc >
161  template < typename OtherAlloc >
165  // for debugging purposes
166  GUM_OP_CPY(MultiPriorityQueue);
167 
168  try {
169  // set the comprison function
170  __cmp = from.__cmp;
171 
172  // copy the indices and the heap
173  __indices = from.__indices;
175 
176  // restore the link between __indices and __heap
177  __heap.clear();
178  __heap.reserve(from.__heap.size());
179  for (const auto& elt : from.__heap) {
180  __heap.push_back(elt);
181  }
182  for (const auto& val_and_index : __indices) {
183  const Val* val = &(val_and_index.first);
184  const std::vector< Size >& vect = val_and_index.second;
185  for (auto index : vect) {
186  __heap[index].second = val;
187  }
188  }
189  } catch (...) {
190  __heap.clear();
191  __indices.clear();
192  __nb_elements = 0;
193 
194  throw;
195  }
196 
197  return *this;
198  }
199 
200  // move operator
201  template < typename Val, typename Priority, typename Cmp, typename Alloc >
205  // avoid self assignment
206  if (this != &from) {
207  // for debugging purposes
208  GUM_OP_MOV(MultiPriorityQueue);
209 
210  __cmp = std::move(from.__cmp);
211  __indices = std::move(from.__indices);
212  __heap = std::move(from.__heap);
213  __nb_elements = std::move(from.__nb_elements);
214  }
215 
216  return *this;
217  }
218 
219  // returns the element at the top of the priority queue
220  template < typename Val, typename Priority, typename Cmp, typename Alloc >
222  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
223 
224  return *(__heap[0].second);
225  }
226 
227  // returns the priority of the top element
228  template < typename Val, typename Priority, typename Cmp, typename Alloc >
229  INLINE const Priority&
231  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
232 
233  return __heap[0].first;
234  }
235 
236  // returns the number of elements in the priority queue
237  template < typename Val, typename Priority, typename Cmp, typename Alloc >
239  noexcept {
240  return __nb_elements;
241  }
242 
243  // return the size of the array storing the priority queue
244  template < typename Val, typename Priority, typename Cmp, typename Alloc >
246  noexcept {
247  return Size(__heap.capacity());
248  }
249 
250  // changes the size of the array storing the priority queue
251  template < typename Val, typename Priority, typename Cmp, typename Alloc >
252  INLINE void
254  if (new_size < __nb_elements) return;
255 
256  __heap.reserve(new_size);
257  __indices.resize(new_size / 2);
258  }
259 
260  // removes all the elements from the queue
261  template < typename Val, typename Priority, typename Cmp, typename Alloc >
263  __nb_elements = 0;
264  __heap.clear();
265  __indices.clear();
266  }
267 
268  // removes the element at index elt from the priority queue
269  template < typename Val, typename Priority, typename Cmp, typename Alloc >
271  if (index >= __nb_elements) return;
272 
273  // remove the element from the hashtable
274  const Val& del_val = *(__heap[index].second);
275  std::vector< Size >& vect_index = __indices[del_val];
276  if (vect_index.size() == 1)
277  __indices.erase(del_val);
278  else {
279  for (auto& v_index : vect_index) {
280  if (v_index == index) {
281  v_index = vect_index.back();
282  vect_index.pop_back();
283  break;
284  }
285  }
286  }
287 
288  // put the last element at the "index" location
289  std::pair< Priority, const Val* > last = std::move(__heap.back());
290  __heap.pop_back();
291  --__nb_elements;
292 
293  if (!__nb_elements || (index == __nb_elements)) return;
294 
295  // restore the heap property
296  Size i = index;
297 
298  for (Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
299  // let j be the max child
300  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
301  ++j;
302 
303  // if "last" is lower than heap[j], "last" must be stored at index i
304  if (__cmp(last.first, __heap[j].first)) break;
305 
306  // else pull up the jth node
307  __heap[i] = std::move(__heap[j]);
308  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
309  for (auto& v_index : vect_index) {
310  if (v_index == j) {
311  v_index = i;
312  break;
313  }
314  }
315  }
316 
317  // put "last" back into the heap
318  __heap[i] = std::move(last);
319  std::vector< Size >& last_indices = __indices[*(__heap[i].second)];
320  for (auto& v_index : last_indices) {
321  if (v_index == __nb_elements) {
322  v_index = i;
323  break;
324  }
325  }
326  }
327 
328  // removes a given element from the priority queue (but does not return it)
329  template < typename Val, typename Priority, typename Cmp, typename Alloc >
330  INLINE void
332  try {
333  eraseByPos(__indices[val][0]);
334  } catch (NotFound&) {}
335  }
336 
337  // removes the top of the priority queue (but does not return it)
338  template < typename Val, typename Priority, typename Cmp, typename Alloc >
340  eraseByPos(0);
341  }
342 
343  // removes the top element from the priority queue and return it
344  template < typename Val, typename Priority, typename Cmp, typename Alloc >
346  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
347 
348  Val v = *(__heap[0].second);
349  eraseByPos(0);
350 
351  return v;
352  }
353 
354  // returns a hashtable the keys of which are the values stored in the queue
355  template < typename Val, typename Priority, typename Cmp, typename Alloc >
358  return reinterpret_cast< const HashTable< Val, std::vector< Size > >& >(
359  __indices);
360  }
361 
362  // inserts a new (a copy) element in the priority queue
363  template < typename Val, typename Priority, typename Cmp, typename Alloc >
365  const Val& val, const Priority& priority) {
366  // create the entry in the indices hashtable
367  const Val* new_val;
368  std::vector< Size >* new_vect;
369  if (!__indices.exists(val)) {
370  auto& new_elt = __indices.insert(val, std::vector< Size >());
371  new_val = &(new_elt.first);
372  new_vect = &(new_elt.second);
373  } else {
374  new_val = &(__indices.key(val));
375  new_vect = &(__indices[val]);
376  }
377 
378  try {
379  new_vect->push_back(0);
380  } catch (...) {
381  if (new_vect->empty()) { __indices.erase(val); }
382  throw;
383  }
384 
385  try {
386  __heap.push_back(std::pair< Priority, const Val* >(priority, new_val));
387  } catch (...) {
388  if (new_vect->size() == 1) { __indices.erase(val); }
389  throw;
390  }
391 
392  std::pair< Priority, const Val* > new_heap_val =
393  std::move(__heap[__nb_elements]);
394  ++__nb_elements;
395 
396  // restore the heap property
397  Size i = __nb_elements - 1;
398 
399  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
400  i = j, j = (j - 1) >> 1) {
401  __heap[i] = std::move(__heap[j]);
402  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
403  for (auto& index : vect_index) {
404  if (index == j) {
405  index = i;
406  break;
407  }
408  }
409  }
410 
411  // put the new bucket into the heap
412  __heap[i].first = std::move(new_heap_val.first);
413  __heap[i].second = new_val;
414  new_vect->back() = i;
415 
416  return i;
417  }
418 
419  // inserts a new (a copy) element in the priority queue
420  template < typename Val, typename Priority, typename Cmp, typename Alloc >
421  Size
423  Priority&& priority) {
424  // create the entry in the indices hashtable
425  const Val* new_val;
426  std::vector< Size >* new_vect;
427  if (!__indices.exists(val)) {
428  auto& new_elt = __indices.insert(std::move(val), std::vector< Size >());
429  new_val = &(new_elt.first);
430  new_vect = &(new_elt.second);
431  } else {
432  new_val = &(__indices.key(val));
433  new_vect = &(__indices[val]);
434  }
435 
436  try {
437  new_vect->push_back(0);
438  } catch (...) {
439  if (new_vect->empty()) { __indices.erase(*new_val); }
440  throw;
441  }
442 
443  try {
444  __heap.push_back(
445  std::pair< Priority, const Val* >(std::move(priority), new_val));
446  } catch (...) {
447  if (new_vect->size() == 1) { __indices.erase(*new_val); }
448  throw;
449  }
450 
451  std::pair< Priority, const Val* > new_heap_val =
452  std::move(__heap[__nb_elements]);
453  ++__nb_elements;
454 
455  // restore the heap property
456  Size i = __nb_elements - 1;
457 
458  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
459  i = j, j = (j - 1) >> 1) {
460  __heap[i] = std::move(__heap[j]);
461  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
462  for (auto& index : vect_index) {
463  if (index == j) {
464  index = i;
465  break;
466  }
467  }
468  }
469 
470  // put the new bucket into the heap
471  __heap[i].first = std::move(new_heap_val.first);
472  __heap[i].second = new_val;
473  new_vect->back() = i;
474 
475  return i;
476  }
477 
478  // emplace a new element into the priority queue
479  template < typename Val, typename Priority, typename Cmp, typename Alloc >
480  template < typename... Args >
481  INLINE Size
483  std::pair< Val, Priority > new_elt =
484  std::make_pair< Val, Priority >(std::forward< Args >(args)...);
485  return insert(std::move(new_elt.first), std::move(new_elt.second));
486  }
487 
488  // indicates whether the priority queue is empty
489  template < typename Val, typename Priority, typename Cmp, typename Alloc >
491  noexcept {
492  return (__nb_elements == 0);
493  }
494 
495  // indicates whether the priority queue contains a given value
496  template < typename Val, typename Priority, typename Cmp, typename Alloc >
498  const Val& val) const {
499  return __indices.exists(val);
500  }
501 
502  // returns the element at position "index" in the priority queue
503  template < typename Val, typename Priority, typename Cmp, typename Alloc >
505  operator[](Size index) const {
506  if (index >= __nb_elements) {
507  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
508  }
509 
510  return *(__heap[index].second);
511  }
512 
513  // displays the content of the queue
514  template < typename Val, typename Priority, typename Cmp, typename Alloc >
516  bool deja = false;
517  std::stringstream stream;
518  stream << "[";
519 
520  for (Size i = 0; i != __nb_elements; ++i, deja = true) {
521  if (deja) stream << " , ";
522 
523  stream << "(" << __heap[i].first << " , " << *(__heap[i].second) << ")";
524  }
525 
526  stream << "]";
527 
528  return stream.str();
529  }
530 
531  // changes the size of the internal structure storing the priority queue
532  template < typename Val, typename Priority, typename Cmp, typename Alloc >
534  Size index, const Priority& new_priority) {
535  // check whether the element the priority of which should be changed exists
536  if (index >= __nb_elements) {
537  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
538  }
539 
540  // get the element itself
541  const Val* val = __heap[index].second;
542 
543  // restore the heap property
544  Size i = index;
545 
546  // move val upward if needed
547  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
548  i = j, j = (j - 1) >> 1) {
549  __heap[i] = std::move(__heap[j]);
550  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
551  for (auto& idx : vect_index) {
552  if (idx == j) {
553  idx = i;
554  break;
555  }
556  }
557  }
558 
559  // move val downward if needed
560  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
561  // let j be the max child
562  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
563  ++j;
564 
565  // if "val" is lower than heap[j], "val" must be stored at index i
566  if (__cmp(new_priority, __heap[j].first)) break;
567 
568  // else pull up the jth node
569  __heap[i] = std::move(__heap[j]);
570  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
571  for (auto& idx : vect_index) {
572  if (idx == j) {
573  idx = i;
574  break;
575  }
576  }
577  }
578 
579  // update the index of val
580  __heap[i].first = new_priority;
581  __heap[i].second = val;
582  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
583  for (auto& idx : vect_index) {
584  if (idx == index) {
585  idx = i;
586  break;
587  }
588  }
589 
590  return i;
591  }
592 
593  // changes the size of the internal structure storing the priority queue
594  template < typename Val, typename Priority, typename Cmp, typename Alloc >
596  Size index, Priority&& new_priority) {
597  // check whether the element the priority of which should be changed exists
598  if (index >= __nb_elements) {
599  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
600  }
601 
602  // get the element itself
603  const Val* val = __heap[index].second;
604 
605  // restore the heap property
606  Size i = index;
607 
608  // move val upward if needed
609  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
610  i = j, j = (j - 1) >> 1) {
611  __heap[i] = std::move(__heap[j]);
612  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
613  for (auto& idx : vect_index) {
614  if (idx == j) {
615  idx = i;
616  break;
617  }
618  }
619  }
620 
621  // move val downward if needed
622  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
623  // let j be the max child
624  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
625  ++j;
626 
627  // if "val" is lower than heap[j], "val" must be stored at index i
628  if (__cmp(new_priority, __heap[j].first)) break;
629 
630  // else pull up the jth node
631  __heap[i] = std::move(__heap[j]);
632  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
633  for (auto& idx : vect_index) {
634  if (idx == j) {
635  idx = i;
636  break;
637  }
638  }
639  }
640 
641  // update the index of val
642  __heap[i].first = std::move(new_priority);
643  __heap[i].second = val;
644  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
645  for (auto& idx : vect_index) {
646  if (idx == index) {
647  idx = i;
648  break;
649  }
650  }
651 
652  return i;
653  }
654 
655  // modifies the priority of each instance of a given element
656  template < typename Val, typename Priority, typename Cmp, typename Alloc >
658  const Val& elt, const Priority& new_priority) {
659  std::vector< Size >& vect_index = __indices[elt];
660 
661  for (auto index : vect_index) {
662  setPriorityByPos(index, new_priority);
663  }
664  }
665 
666  // modifies the priority of each instance of a given element
667  template < typename Val, typename Priority, typename Cmp, typename Alloc >
669  const Val& elt) const {
670  return __heap[__indices[elt][0]].first;
671  }
672 
673  // A \c << operator for priority queues
674  template < typename Val, typename Priority, typename Cmp, typename Alloc >
675  INLINE std::ostream&
676  operator<<(std::ostream& stream,
678  stream << queue.toString();
679  return stream;
680  }
681 
682 } /* namespace gum */
void resize(Size new_size)
Changes the number of slots in the &#39;nodes&#39; vector of the hash table.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
void setPriority(const Val &elt, const Priority &new_priority)
Modifies the priority of each instance of a given element.
Priority queues in which the same element can appear several times.
Size setPriorityByPos(Size index, const Priority &new_priority)
Modifies the priority of the element at position "index" of the queue.
std::vector< std::pair< Priority, const Val * >, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size __nb_elements
The number of elements in the heap.
std::string toString() const
Displays the content of the queue.
Cmp __cmp
Comparison function.
void clear()
Removes all the elements from the queue.
const Priority & priority(const Val &elt) const
Returns the priority of an instance of the value passed in argument.
void erase(const Val &val)
Removes a given element from the priority queue (but does not return it).
void erase(const Key &key)
Removes a given element from the hash table.
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
Size size() const noexcept
Returns the number of elements in the priority queue.
STL namespace.
Val pop()
Removes the top element from the priority queue and return it.
void eraseByPos(Size index)
Removes the element at position "index" from the priority queue.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
bool empty() const noexcept
Indicates whether the priority queue is empty.
const Key & key(const Key &key) const
Returns a reference on a given key.
The class for generic Hash Tables.
Definition: hashTable.h:676
Size capacity() const noexcept
Return the size of the internal structure storing the priority queue.
const HashTable< Val, std::vector< Size > > & allValues() const
Returns a gum::HashTable the keys of which are the values stored in the queue.
std::ostream & operator<<(std::ostream &output, const BayesNet< GUM_SCALAR > &bn)
Prints map&#39;s DAG in output using the Graphviz-dot format.
Definition: BayesNet_tpl.h:573
Size insert(const Val &val, const Priority &priority)
Inserts a new (a copy) element in the priority queue.
void resize(Size new_size)
Changes the size of the internal structure storing the priority queue.
Size emplace(Args &&...args)
Emplace a new element into the priority queue.
MultiPriorityQueue< Val, Priority, Cmp, Alloc > & operator=(const MultiPriorityQueue< Val, Priority, Cmp, Alloc > &from)
Copy operator.
void clear()
Removes all the elements in the hash table.
const Priority & topPriority() const
Returns the priority of the top element.
~MultiPriorityQueue()
Class destructor.
const Val & operator[](Size index_elt) const
Returns the element at index "index_elt" from the priority queue.
const Val & top() const
Returns the element at the top of the priority queue.
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
void eraseTop()
Removes the top of the priority queue (but does not return it).
A MultiPriorityQueue is a heap in which each element has a mutable priority and duplicates are allowe...
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
bool contains(const Val &val) const
Indicates whether the priority queue contains a given value.