aGrUM  0.14.2
priorityQueue_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  ***************************************************************************/
28 
29 namespace gum {
30 
31  // ===========================================================================
32  // === GENERAL IMPLEMENTATIION OF PRIORITY QUEUES ===
33  // ===========================================================================
34 
35  // basic constructor
36  template < typename Val,
37  typename Priority,
38  typename Cmp,
39  typename Alloc,
40  bool Gen >
42  PriorityQueueImplementation(Cmp compare, Size capacity) :
43  __indices(capacity >> 1, true, true),
44  __cmp(compare) {
45  __heap.reserve(capacity);
46 
47  // for debugging purposes
48  GUM_CONSTRUCTOR(PriorityQueueImplementation);
49  }
50 
51  // initializer list constructor
52  template < typename Val,
53  typename Priority,
54  typename Cmp,
55  typename Alloc,
56  bool Gen >
59  std::initializer_list< std::pair< Val, Priority > > list) :
60  __indices(Size(list.size()) / 2, true, true) {
61  // fill the queue
62  __heap.reserve(list.size());
63  for (const auto& elt : list) {
64  insert(elt.first, elt.second);
65  }
66 
67  // for debugging purposes
68  GUM_CONSTRUCTOR(PriorityQueueImplementation);
69  }
70 
71  // copy constructor
72  template < typename Val,
73  typename Priority,
74  typename Cmp,
75  typename Alloc,
76  bool Gen >
80  from) :
81  __heap(from.__heap),
82  __indices(from.__indices), __nb_elements(from.__nb_elements),
83  __cmp(from.__cmp) {
84  // fill the heap structure
85  for (const auto& elt : __indices) {
86  __heap[elt.second].second = &(elt.first);
87  }
88 
89  // for debugging purposes
90  GUM_CONS_CPY(PriorityQueueImplementation);
91  }
92 
93  // generalized copy constructor
94  template < typename Val,
95  typename Priority,
96  typename Cmp,
97  typename Alloc,
98  bool Gen >
99  template < typename OtherAlloc >
103  from) :
104  __indices(from.__indices),
105  __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
106  // fill the heap structure
107  if (__nb_elements) {
108  __heap.reserve(from.__heap.size());
109  for (const auto& elt : from.__heap) {
110  __heap.push_back(elt);
111  }
112  for (const auto& elt : __indices) {
113  __heap[elt.second].second = &(elt.first);
114  }
115  }
116 
117  // for debugging purposes
118  GUM_CONS_CPY(PriorityQueueImplementation);
119  }
120 
121  // move constructor
122  template < typename Val,
123  typename Priority,
124  typename Cmp,
125  typename Alloc,
126  bool Gen >
130  __heap(std::move(from.__heap)),
131  __indices(std::move(from.__indices)),
132  __nb_elements(std::move(from.__nb_elements)), __cmp(std::move(from.__cmp)) {
133  // for debugging purposes
134  GUM_CONS_MOV(PriorityQueueImplementation);
135  }
136 
137  // destructor
138  template < typename Val,
139  typename Priority,
140  typename Cmp,
141  typename Alloc,
142  bool Gen >
145  // for debugging purposes
146  GUM_DESTRUCTOR(PriorityQueueImplementation);
147  }
148 
149  // copy operator
150  template < typename Val,
151  typename Priority,
152  typename Cmp,
153  typename Alloc,
154  bool Gen >
158  from) {
159  // avoid self assignment
160  if (this != &from) {
161  // for debugging purposes
162  GUM_OP_CPY(PriorityQueueImplementation);
163 
164  try {
165  // set the comparison function
166  __cmp = from.__cmp;
167 
168  // copy the indices and the heap
169  __indices = from.__indices;
170  __heap = from.__heap;
171  __nb_elements = from.__nb_elements;
172 
173  // restore the link between __indices and __heap
174  for (const auto& elt : __indices) {
175  __heap[elt.second].second = &(elt.first);
176  }
177  } catch (...) {
178  __heap.clear();
179  __indices.clear();
180  __nb_elements = 0;
181 
182  throw;
183  }
184  }
185 
186  return *this;
187  }
188 
189  // generalized copy operator
190  template < typename Val,
191  typename Priority,
192  typename Cmp,
193  typename Alloc,
194  bool Gen >
195  template < typename OtherAlloc >
199  from) {
200  // for debugging purposes
201  GUM_OP_CPY(PriorityQueueImplementation);
202 
203  try {
204  // set the comprison function
205  __cmp = from.__cmp;
206 
207  // copy the indices and the heap
208  __indices = from.__indices;
209  __nb_elements = from.__nb_elements;
210 
211  __heap.clear();
212  if (__nb_elements) {
213  __heap.reserve(from.__heap.size());
214  for (const auto& elt : from.__heap) {
215  __heap.push_back(elt);
216  }
217  for (const auto& elt : __indices) {
218  __heap[elt.second].second = &(elt.first);
219  }
220  }
221  } catch (...) {
222  __heap.clear();
223  __indices.clear();
224  __nb_elements = 0;
225 
226  throw;
227  }
228 
229  return *this;
230  }
231 
232  // move operator
233  template < typename Val,
234  typename Priority,
235  typename Cmp,
236  typename Alloc,
237  bool Gen >
241  // avoid self assignment
242  if (this != &from) {
243  // for debugging purposes
244  GUM_OP_MOV(PriorityQueueImplementation);
245 
246  __indices = std::move(from.__indices);
247  __heap = std::move(from.__heap);
248  __cmp = std::move(from.__cmp);
249  __nb_elements = std::move(from.__nb_elements);
250  }
251 
252  return *this;
253  }
254 
255  // returns the element at the top of the priority queue
256  template < typename Val,
257  typename Priority,
258  typename Cmp,
259  typename Alloc,
260  bool Gen >
261  INLINE const Val&
263  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
264 
265  return *(__heap[0].second);
266  }
267 
268  // returns the priority of the top element
269  template < typename Val,
270  typename Priority,
271  typename Cmp,
272  typename Alloc,
273  bool Gen >
274  INLINE const Priority&
276  const {
277  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
278 
279  return __heap[0].first;
280  }
281 
282  // returns the number of elements in the priority queue
283  template < typename Val,
284  typename Priority,
285  typename Cmp,
286  typename Alloc,
287  bool Gen >
288  INLINE Size
290  noexcept {
291  return __nb_elements;
292  }
293 
294  // return the size of the array storing the priority queue
295  template < typename Val,
296  typename Priority,
297  typename Cmp,
298  typename Alloc,
299  bool Gen >
300  INLINE Size
302  const noexcept {
303  return Size(__heap.capacity());
304  }
305 
306  // changes the size of the array storing the priority queue
307  template < typename Val,
308  typename Priority,
309  typename Cmp,
310  typename Alloc,
311  bool Gen >
312  INLINE void
314  Size new_size) {
315  if (new_size < __nb_elements) return;
316 
317  __heap.reserve(new_size);
318  __indices.resize(new_size / 2);
319  }
320 
321  // removes all the elements from the queue
322  template < typename Val,
323  typename Priority,
324  typename Cmp,
325  typename Alloc,
326  bool Gen >
327  INLINE void
329  __nb_elements = 0;
330  __heap.clear();
331  __indices.clear();
332  }
333 
334  // removes the element at index elt from the priority queue
335  template < typename Val,
336  typename Priority,
337  typename Cmp,
338  typename Alloc,
339  bool Gen >
341  Size index) {
342  if (index >= __nb_elements) return;
343 
344  // remove the element from the hashtable
345  __indices.erase(*(__heap[index].second));
346 
347  // put the last element at the "index" location
348  std::pair< Priority, const Val* > last = std::move(__heap[__nb_elements - 1]);
349  __heap.pop_back();
350  --__nb_elements;
351 
352  if (!__nb_elements || (index == __nb_elements)) return;
353 
354  // restore the heap property
355  Size i = index;
356 
357  for (Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
358  // let j be the max child
359  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
360  ++j;
361 
362  // if "last" is lower than heap[j], "last" must be stored at index i
363  if (__cmp(last.first, __heap[j].first)) break;
364 
365  // else pull up the jth node
366  __heap[i] = std::move(__heap[j]);
367  __indices[*(__heap[i].second)] = i;
368  }
369 
370  // put "last" back into the heap
371  __heap[i] = std::move(last);
372  __indices[*(__heap[i].second)] = i;
373  }
374 
375  // removes a given element from the priority queue (but does not return it)
376  template < typename Val,
377  typename Priority,
378  typename Cmp,
379  typename Alloc,
380  bool Gen >
382  const Val& val) {
383  try {
384  eraseByPos(__indices[val]);
385  } catch (NotFound&) {}
386  }
387 
388  // removes the top of the priority queue (but does not return it)
389  template < typename Val,
390  typename Priority,
391  typename Cmp,
392  typename Alloc,
393  bool Gen >
394  INLINE void
396  eraseByPos(0);
397  }
398 
399  // removes the top element from the priority queue and return it
400  template < typename Val,
401  typename Priority,
402  typename Cmp,
403  typename Alloc,
404  bool Gen >
406  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
407 
408  Val v = *(__heap[0].second);
409  eraseByPos(0);
410 
411  return v;
412  }
413 
414  // returns a hashtable the keys of which are the values stored in the queue
415  template < typename Val,
416  typename Priority,
417  typename Cmp,
418  typename Alloc,
419  bool Gen >
420  INLINE const HashTable< Val, Size >&
422  const noexcept {
423  return reinterpret_cast< const HashTable< Val, Size >& >(__indices);
424  }
425 
426  // inserts a new (a copy) element in the priority queue
427  template < typename Val,
428  typename Priority,
429  typename Cmp,
430  typename Alloc,
431  bool Gen >
432  INLINE Size
434  const Val& val, const Priority& priority) {
435  // create the entry in the indices hashtable (if the element already exists,
436  // __indices.insert will raise a Duplicateelement exception)
438  __indices.insert(val, 0);
439 
440  try {
441  __heap.push_back(
442  std::pair< Priority, const Val* >(priority, &new_elt.first));
443  } catch (...) {
444  __indices.erase(val);
445  throw;
446  }
447 
448  std::pair< Priority, const Val* > new_heap_val =
449  std::move(__heap[__nb_elements]);
450  ++__nb_elements;
451 
452  // restore the heap property
453  Size i = __nb_elements - 1;
454 
455  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
456  i = j, j = (j - 1) >> 1) {
457  __heap[i] = std::move(__heap[j]);
458  __indices[*(__heap[i].second)] = i;
459  }
460 
461  // put the new bucket into the heap
462  __heap[i].first = std::move(new_heap_val.first);
463  __heap[i].second = &(new_elt.first);
464  new_elt.second = i;
465 
466  return i;
467  }
468 
469  // inserts by move a new element in the priority queue
470  template < typename Val,
471  typename Priority,
472  typename Cmp,
473  typename Alloc,
474  bool Gen >
475  INLINE Size
477  Val&& val, Priority&& priority) {
478  // create the entry in the indices hashtable (if the element already exists,
479  // __indices.insert will raise a Duplicateelement exception)
481  __indices.insert(std::move(val), 0);
482 
483  try {
484  __heap.push_back(
485  std::pair< Priority, const Val* >(std::move(priority), &(new_elt.first)));
486  } catch (...) {
487  __indices.erase(new_elt.first);
488  throw;
489  }
490 
491  std::pair< Priority, const Val* > new_heap_val =
492  std::move(__heap[__nb_elements]);
493  ++__nb_elements;
494 
495  // restore the heap property
496  Size i = __nb_elements - 1;
497 
498  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
499  i = j, j = (j - 1) >> 1) {
500  __heap[i] = std::move(__heap[j]);
501  __indices[*(__heap[i].second)] = i;
502  }
503 
504  // put the new bucket into the heap
505  __heap[i].first = std::move(new_heap_val.first);
506  __heap[i].second = &(new_elt.first);
507  new_elt.second = i;
508 
509  return i;
510  }
511 
512  // emplace a new element into the priority queue
513  template < typename Val,
514  typename Priority,
515  typename Cmp,
516  typename Alloc,
517  bool Gen >
518  template < typename... Args >
519  INLINE Size
521  Args&&... args) {
522  std::pair< Val, Priority > new_elt =
523  std::make_pair< Val, Priority >(std::forward< Args >(args)...);
524  return insert(std::move(new_elt.first), std::move(new_elt.second));
525  }
526 
527  // indicates whether the priority queue is empty
528  template < typename Val,
529  typename Priority,
530  typename Cmp,
531  typename Alloc,
532  bool Gen >
533  INLINE bool
535  noexcept {
536  return (__nb_elements == 0);
537  }
538 
539  // indicates whether the priority queue contains a given value
540  template < typename Val,
541  typename Priority,
542  typename Cmp,
543  typename Alloc,
544  bool Gen >
545  INLINE bool
547  const Val& val) const {
548  return __indices.exists(val);
549  }
550 
551  // returns the element at position "index" in the priority queue
552  template < typename Val,
553  typename Priority,
554  typename Cmp,
555  typename Alloc,
556  bool Gen >
558  operator[](Size index) const {
559  if (index >= __nb_elements) {
561  "not enough elements in the PriorityQueueImplementation");
562  }
563 
564  return *(__heap[index].second);
565  }
566 
567  // displays the content of the queue
568  template < typename Val,
569  typename Priority,
570  typename Cmp,
571  typename Alloc,
572  bool Gen >
573  std::string
575  const {
576  bool deja = false;
577  std::stringstream stream;
578  stream << "[";
579 
580  for (Size i = 0; i != __nb_elements; ++i, deja = true) {
581  if (deja) stream << " , ";
582 
583  stream << "(" << __heap[i].first << " , " << *(__heap[i].second) << ")";
584  }
585 
586  stream << "]";
587 
588  return stream.str();
589  }
590 
591  // changes the size of the internal structure storing the priority queue
592  template < typename Val,
593  typename Priority,
594  typename Cmp,
595  typename Alloc,
596  bool Gen >
598  setPriorityByPos(Size index, const Priority& new_priority) {
599  // check whether the element the priority of which should be changed exists
600  if (index >= __nb_elements) {
602  "not enough elements in the PriorityQueueImplementation");
603  }
604 
605  // get the element itself
606  const Val* val = __heap[index].second;
607 
608  // restore the heap property
609  Size i = index;
610 
611  // move val upward if needed
612  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
613  i = j, j = (j - 1) >> 1) {
614  __heap[i] = std::move(__heap[j]);
615  __indices[*(__heap[i].second)] = i;
616  }
617 
618  // move val downward if needed
619  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
620  // let j be the max child
621  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
622  ++j;
623 
624  // if "val" is lower than heap[j], "val" must be stored at index i
625  if (__cmp(new_priority, __heap[j].first)) break;
626 
627  // else pull up the jth node
628  __heap[i] = std::move(__heap[j]);
629  __indices[*(__heap[i].second)] = i;
630  }
631 
632  // update the index of val
633  __heap[i].first = new_priority;
634  __heap[i].second = val;
635  __indices[*val] = i;
636 
637  return i;
638  }
639 
640  // changes the size of the internal structure storing the priority queue
641  template < typename Val,
642  typename Priority,
643  typename Cmp,
644  typename Alloc,
645  bool Gen >
647  setPriorityByPos(Size index, Priority&& new_priority) {
648  // check whether the element the priority of which should be changed exists
649  if (index >= __nb_elements) {
651  "not enough elements in the PriorityQueueImplementation");
652  }
653 
654  // get the element itself
655  const Val* val = __heap[index].second;
656 
657  // restore the heap property
658  Size i = index;
659 
660  // move val upward if needed
661  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
662  i = j, j = (j - 1) >> 1) {
663  __heap[i] = std::move(__heap[j]);
664  __indices[*(__heap[i].second)] = i;
665  }
666 
667  // move val downward if needed
668  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
669  // let j be the max child
670  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
671  ++j;
672 
673  // if "val" is lower than heap[j], "val" must be stored at index i
674  if (__cmp(new_priority, __heap[j].first)) break;
675 
676  // else pull up the jth node
677  __heap[i] = std::move(__heap[j]);
678  __indices[*(__heap[i].second)] = i;
679  }
680 
681  // update the index of val
682  __heap[i].first = std::move(new_priority);
683  __heap[i].second = val;
684  __indices[*val] = i;
685 
686  return i;
687  }
688 
689  // modifies the priority of a given element
690  template < typename Val,
691  typename Priority,
692  typename Cmp,
693  typename Alloc,
694  bool Gen >
696  const Val& elt, const Priority& new_priority) {
697  setPriorityByPos(__indices[elt], new_priority);
698  }
699 
700  // modifies the priority of a given element
701  template < typename Val,
702  typename Priority,
703  typename Cmp,
704  typename Alloc,
705  bool Gen >
707  const Val& elt, Priority&& new_priority) {
708  setPriorityByPos(__indices[elt], std::move(new_priority));
709  }
710 
711  // returns the priority of a given element
712  template < typename Val,
713  typename Priority,
714  typename Cmp,
715  typename Alloc,
716  bool Gen >
717  INLINE const Priority&
719  const Val& elt) const {
720  return __heap[__indices[elt]].first;
721  }
722 
723  // returns the priority of a given element
724  template < typename Val,
725  typename Priority,
726  typename Cmp,
727  typename Alloc,
728  bool Gen >
729  INLINE const Priority&
731  Size index) const {
732  if (index > __nb_elements) {
734  "not enough elements in the PriorityQueueImplementation");
735  }
736  return __heap[index].first;
737  }
738 
739  // ===========================================================================
740  // === SCALAR OPTIMIZED IMPLEMENTATION OF PRIORITY QUEUES ===
741  // ===========================================================================
742 
743  // basic constructor
744  template < typename Val, typename Priority, typename Cmp, typename Alloc >
746  PriorityQueueImplementation(Cmp compare, Size capacity) :
747  __indices(capacity >> 1, true, true),
748  __cmp(compare) {
749  __heap.reserve(capacity);
750 
751  // for debugging purposes
752  GUM_CONSTRUCTOR(PriorityQueueImplementation);
753  }
754 
755  // initializer list constructor
756  template < typename Val, typename Priority, typename Cmp, typename Alloc >
759  std::initializer_list< std::pair< Val, Priority > > list) :
760  __indices(Size(list.size()) / 2, true, true) {
761  // fill the queue
762  __heap.reserve(list.size());
763  for (const auto& elt : list) {
764  insert(elt.first, elt.second);
765  }
766 
767  // for debugging purposes
768  GUM_CONSTRUCTOR(PriorityQueueImplementation);
769  }
770 
771  // copy constructor
772  template < typename Val, typename Priority, typename Cmp, typename Alloc >
776  from) :
777  __heap(from.__heap),
778  __indices(from.__indices), __nb_elements(from.__nb_elements),
779  __cmp(from.__cmp) {
780  // for debugging purposes
781  GUM_CONS_CPY(PriorityQueueImplementation);
782  }
783 
784  // generalized copy constructor
785  template < typename Val, typename Priority, typename Cmp, typename Alloc >
786  template < typename OtherAlloc >
790  from) :
791  __indices(from.__indices),
792  __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
793  // fill the heap structure
794  if (__nb_elements) {
795  __heap.reserve(from.__heap.size());
796  for (const auto& elt : from.__heap) {
797  __heap.push_back(elt);
798  }
799  }
800 
801  // for debugging purposes
802  GUM_CONS_CPY(PriorityQueueImplementation);
803  }
804 
805  // move constructor
806  template < typename Val, typename Priority, typename Cmp, typename Alloc >
810  __heap(std::move(from.__heap)),
811  __indices(std::move(from.__indices)),
812  __nb_elements(std::move(from.__nb_elements)), __cmp(std::move(from.__cmp)) {
813  // for debugging purposes
814  GUM_CONS_MOV(PriorityQueueImplementation);
815  }
816 
817  // destructor
818  template < typename Val, typename Priority, typename Cmp, typename Alloc >
821  // for debugging purposes
822  GUM_DESTRUCTOR(PriorityQueueImplementation);
823  }
824 
825  // copy operator
826  template < typename Val, typename Priority, typename Cmp, typename Alloc >
830  from) {
831  // avoid self assignment
832  if (this != &from) {
833  // for debugging purposes
834  GUM_OP_CPY(PriorityQueueImplementation);
835 
836  try {
837  // set the comparison function
838  __cmp = from.__cmp;
839 
840  // copy the indices and the heap
841  __indices = from.__indices;
842  __heap = from.__heap;
843  __nb_elements = from.__nb_elements;
844  } catch (...) {
845  __heap.clear();
846  __indices.clear();
847  __nb_elements = 0;
848 
849  throw;
850  }
851  }
852 
853  return *this;
854  }
855 
856  // generalized copy operator
857  template < typename Val, typename Priority, typename Cmp, typename Alloc >
858  template < typename OtherAlloc >
862  from) {
863  // for debugging purposes
864  GUM_OP_CPY(PriorityQueueImplementation);
865 
866  try {
867  // set the comprison function
868  __cmp = from.__cmp;
869 
870  // copy the indices and the heap
871  __indices = from.__indices;
872  __nb_elements = from.__nb_elements;
873 
874  __heap.clear();
875  if (__nb_elements) {
876  __heap.reserve(from.__heap.size());
877  for (const auto& elt : from.__heap) {
878  __heap.push_back(elt);
879  }
880  }
881  } catch (...) {
882  __heap.clear();
883  __indices.clear();
884  __nb_elements = 0;
885 
886  throw;
887  }
888 
889  return *this;
890  }
891 
892  // move operator
893  template < typename Val, typename Priority, typename Cmp, typename Alloc >
897  // avoid self assignment
898  if (this != &from) {
899  // for debugging purposes
900  GUM_OP_MOV(PriorityQueueImplementation);
901 
902  __indices = std::move(from.__indices);
903  __heap = std::move(from.__heap);
904  __cmp = std::move(from.__cmp);
905  __nb_elements = std::move(from.__nb_elements);
906  }
907 
908  return *this;
909  }
910 
911  // returns the element at the top of the priority queue
912  template < typename Val, typename Priority, typename Cmp, typename Alloc >
913  INLINE const Val&
915  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
916 
917  return __heap[0].second;
918  }
919 
920  // returns the priority of the top element
921  template < typename Val, typename Priority, typename Cmp, typename Alloc >
922  INLINE const Priority&
924  const {
925  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
926 
927  return __heap[0].first;
928  }
929 
930  // returns the number of elements in the priority queue
931  template < typename Val, typename Priority, typename Cmp, typename Alloc >
932  INLINE Size
934  noexcept {
935  return __nb_elements;
936  }
937 
938  // return the size of the array storing the priority queue
939  template < typename Val, typename Priority, typename Cmp, typename Alloc >
940  INLINE Size
942  const noexcept {
943  return Size(__heap.capacity());
944  }
945 
946  // changes the size of the array storing the priority queue
947  template < typename Val, typename Priority, typename Cmp, typename Alloc >
948  INLINE void
950  Size new_size) {
951  if (new_size < __nb_elements) return;
952 
953  __heap.reserve(new_size);
954  __indices.resize(new_size / 2);
955  }
956 
957  // removes all the elements from the queue
958  template < typename Val, typename Priority, typename Cmp, typename Alloc >
959  INLINE void
961  __nb_elements = 0;
962  __heap.clear();
963  __indices.clear();
964  }
965 
966  // removes the element at index elt from the priority queue
967  template < typename Val, typename Priority, typename Cmp, typename Alloc >
969  Size index) {
970  if (index >= __nb_elements) return;
971 
972  // remove the element from the hashtable
973  __indices.erase(__heap[index].second);
974 
975  // put the last element at the "index" location
976  std::pair< Priority, Val > last = std::move(__heap[__nb_elements - 1]);
977  __heap.pop_back();
978  --__nb_elements;
979 
980  if (!__nb_elements || (index == __nb_elements)) return;
981 
982  // restore the heap property
983  Size i = index;
984 
985  for (Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
986  // let j be the max child
987  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
988  ++j;
989 
990  // if "last" is lower than heap[j], "last" must be stored at index i
991  if (__cmp(last.first, __heap[j].first)) break;
992 
993  // else pull up the jth node
994  __heap[i] = std::move(__heap[j]);
995  __indices[__heap[i].second] = i;
996  }
997 
998  // put "last" back into the heap
999  __heap[i] = std::move(last);
1000  __indices[__heap[i].second] = i;
1001  }
1002 
1003  // removes a given element from the priority queue (but does not return it)
1004  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1005  INLINE void
1007  Val val) {
1008  try {
1009  eraseByPos(__indices[val]);
1010  } catch (NotFound&) {}
1011  }
1012 
1013  // removes the top of the priority queue (but does not return it)
1014  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1015  INLINE void
1017  eraseByPos(0);
1018  }
1019 
1020  // removes the top element from the priority queue and return it
1021  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1022  INLINE Val
1024  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
1025 
1026  Val v = __heap[0].second;
1027  eraseByPos(0);
1028 
1029  return v;
1030  }
1031 
1032  // returns a hashtable the keys of which are the values stored in the queue
1033  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1034  INLINE const HashTable< Val, Size >&
1036  const noexcept {
1037  return reinterpret_cast< const HashTable< Val, Size >& >(__indices);
1038  }
1039 
1040  // inserts a new (a copy) element in the priority queue
1041  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1042  INLINE Size
1044  Val val, const Priority& priority) {
1045  // create the entry in the indices hashtable (if the element already exists,
1046  // __indices.insert will raise a Duplicateelement exception)
1048  __indices.insert(val, 0);
1049 
1050  try {
1051  __heap.push_back(std::pair< Priority, Val >(priority, val));
1052  } catch (...) {
1053  __indices.erase(val);
1054  throw;
1055  }
1056 
1057  std::pair< Priority, Val > new_heap_val = std::move(__heap[__nb_elements]);
1058  ++__nb_elements;
1059 
1060  // restore the heap property
1061  Size i = __nb_elements - 1;
1062 
1063  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
1064  i = j, j = (j - 1) >> 1) {
1065  __heap[i] = std::move(__heap[j]);
1066  __indices[__heap[i].second] = i;
1067  }
1068 
1069  // put the new bucket into the heap
1070  __heap[i].first = std::move(new_heap_val.first);
1071  __heap[i].second = val;
1072  new_elt.second = i;
1073 
1074  return i;
1075  }
1076 
1077  // inserts by move a new element in the priority queue
1078  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1079  INLINE Size
1081  Val val, Priority&& priority) {
1082  // create the entry in the indices hashtable (if the element already exists,
1083  // __indices.insert will raise a Duplicateelement exception)
1085  __indices.insert(val, 0);
1086 
1087  try {
1088  __heap.push_back(std::pair< Priority, Val >(std::move(priority), val));
1089  } catch (...) {
1090  __indices.erase(val);
1091  throw;
1092  }
1093 
1094  std::pair< Priority, Val > new_heap_val = std::move(__heap[__nb_elements]);
1095  ++__nb_elements;
1096 
1097  // restore the heap property
1098  Size i = __nb_elements - 1;
1099 
1100  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
1101  i = j, j = (j - 1) >> 1) {
1102  __heap[i] = std::move(__heap[j]);
1103  __indices[__heap[i].second] = i;
1104  }
1105 
1106  // put the new bucket into the heap
1107  __heap[i].first = std::move(new_heap_val.first);
1108  __heap[i].second = val;
1109  new_elt.second = i;
1110 
1111  return i;
1112  }
1113 
1114  // emplace a new element into the priority queue
1115  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1116  template < typename... Args >
1117  INLINE Size
1119  Args&&... args) {
1120  std::pair< Val, Priority > new_elt =
1121  std::make_pair< Val, Priority >(std::forward< Args >(args)...);
1122  return insert(new_elt.first, std::move(new_elt.second));
1123  }
1124 
1125  // indicates whether the priority queue is empty
1126  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1127  INLINE bool
1129  noexcept {
1130  return (__nb_elements == 0);
1131  }
1132 
1133  // indicates whether the priority queue contains a given value
1134  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1135  INLINE bool
1137  Val val) const {
1138  return __indices.exists(val);
1139  }
1140 
1141  // returns the element at position "index" in the priority queue
1142  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1143  INLINE const Val&
1145  operator[](Size index) const {
1146  if (index >= __nb_elements) {
1148  "not enough elements in the PriorityQueueImplementation");
1149  }
1150 
1151  return __heap[index].second;
1152  }
1153 
1154  // displays the content of the queue
1155  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1156  std::string
1158  const {
1159  bool deja = false;
1160  std::stringstream stream;
1161  stream << "[";
1162 
1163  for (Size i = 0; i != __nb_elements; ++i, deja = true) {
1164  if (deja) stream << " , ";
1165 
1166  stream << "(" << __heap[i].first << " , " << __heap[i].second << ")";
1167  }
1168 
1169  stream << "]";
1170 
1171  return stream.str();
1172  }
1173 
1174  // changes the size of the internal structure storing the priority queue
1175  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1177  setPriorityByPos(Size index, const Priority& new_priority) {
1178  // check whether the element the priority of which should be changed exists
1179  if (index >= __nb_elements) {
1181  "not enough elements in the PriorityQueueImplementation");
1182  }
1183 
1184  // get the element itself
1185  Val val = __heap[index].second;
1186 
1187  // restore the heap property
1188  Size i = index;
1189 
1190  // move val upward if needed
1191  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
1192  i = j, j = (j - 1) >> 1) {
1193  __heap[i] = std::move(__heap[j]);
1194  __indices[__heap[i].second] = i;
1195  }
1196 
1197  // move val downward if needed
1198  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
1199  // let j be the max child
1200  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
1201  ++j;
1202 
1203  // if "val" is lower than heap[j], "val" must be stored at index i
1204  if (__cmp(new_priority, __heap[j].first)) break;
1205 
1206  // else pull up the jth node
1207  __heap[i] = std::move(__heap[j]);
1208  __indices[__heap[i].second] = i;
1209  }
1210 
1211  // update the index of val
1212  __heap[i].first = new_priority;
1213  __heap[i].second = val;
1214  __indices[val] = i;
1215 
1216  return i;
1217  }
1218 
1219  // changes the size of the internal structure storing the priority queue
1220  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1222  setPriorityByPos(Size index, Priority&& new_priority) {
1223  // check whether the element the priority of which should be changed exists
1224  if (index >= __nb_elements) {
1226  "not enough elements in the PriorityQueueImplementation");
1227  }
1228 
1229  // get the element itself
1230  Val val = __heap[index].second;
1231 
1232  // restore the heap property
1233  Size i = index;
1234 
1235  // move val upward if needed
1236  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
1237  i = j, j = (j - 1) >> 1) {
1238  __heap[i] = std::move(__heap[j]);
1239  __indices[__heap[i].second] = i;
1240  }
1241 
1242  // move val downward if needed
1243  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
1244  // let j be the max child
1245  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
1246  ++j;
1247 
1248  // if "val" is lower than heap[j], "val" must be stored at index i
1249  if (__cmp(new_priority, __heap[j].first)) break;
1250 
1251  // else pull up the jth node
1252  __heap[i] = std::move(__heap[j]);
1253  __indices[__heap[i].second] = i;
1254  }
1255 
1256  // update the index of val
1257  __heap[i].first = std::move(new_priority);
1258  __heap[i].second = val;
1259  __indices[val] = i;
1260 
1261  return i;
1262  }
1263 
1264  // modifies the priority of a given element
1265  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1267  Val elt, const Priority& new_priority) {
1268  setPriorityByPos(__indices[elt], new_priority);
1269  }
1270 
1271  // modifies the priority of a given element
1272  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1274  Val elt, Priority&& new_priority) {
1275  setPriorityByPos(__indices[elt], std::move(new_priority));
1276  }
1277 
1278  // returns the priority of a given element
1279  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1280  INLINE const Priority&
1282  Val elt) const {
1283  return __heap[__indices[elt]].first;
1284  }
1285 
1286  // returns the priority of a given element
1287  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1288  INLINE const Priority&
1290  Size index) const {
1291  if (index > __nb_elements) {
1293  "not enough elements in the PriorityQueueImplementation");
1294  }
1295  return __heap[index].first;
1296  }
1297 
1298  // ===========================================================================
1299  // === PRIORITY QUEUES ===
1300  // ===========================================================================
1301 
1302  // basic constructor
1303  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1305  Size capacity) :
1306  PriorityQueue< Val, Priority, Cmp, Alloc >::Implementation(cmp, capacity) {
1307  // for debugging purposes
1308  GUM_CONSTRUCTOR(PriorityQueue);
1309  }
1310 
1311  // initializer list constructor
1312  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1314  std::initializer_list< std::pair< Val, Priority > > list) :
1315  PriorityQueue< Val, Priority, Cmp, Alloc >::Implementation{list} {
1316  // for debugging purposes
1317  GUM_CONSTRUCTOR(PriorityQueue);
1318  }
1319 
1320  // copy constructor
1321  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1324  PriorityQueue< Val, Priority, Cmp, Alloc >::Implementation(from) {
1325  // for debugging purposes
1326  GUM_CONS_CPY(PriorityQueue);
1327  }
1328 
1329  // generalized copy constructor
1330  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1331  template < typename OtherAlloc >
1334  PriorityQueue< Val, Priority, Cmp, Alloc >::Implementation(from) {
1335  // for debugging purposes
1336  GUM_CONS_CPY(PriorityQueue);
1337  }
1338 
1339  // move constructor
1340  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1343  PriorityQueue< Val, Priority, Cmp, Alloc >::Implementation(std::move(from)) {
1344  // for debugging purposes
1345  GUM_CONS_MOV(PriorityQueue);
1346  }
1347 
1348  // destructor
1349  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1351  // for debugging purposes
1352  GUM_DESTRUCTOR(PriorityQueue);
1353  }
1354 
1355  // copy operator
1356  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1360  Implementation::operator=(from);
1361  return *this;
1362  }
1363 
1364  // generalized copy operator
1365  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1366  template < typename OtherAlloc >
1370  Implementation::operator=(from);
1371  return *this;
1372  }
1373 
1374  // move operator
1375  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1379  Implementation::operator=(std::move(from));
1380  return *this;
1381  }
1382 
1383  // A \c << operator for priority queues
1384  template < typename Val, typename Priority, typename Cmp, typename Alloc >
1385  INLINE std::ostream&
1386  operator<<(std::ostream& stream,
1388  stream << queue.toString();
1389  return stream;
1390  }
1391 
1392 } /* namespace gum */
INLINE std::ostream & operator<<(std::ostream &stream, const PriorityQueue< Val, Priority, Cmp, Alloc > &queue)
The internal class for representing priority queues.
Definition: priorityQueue.h:82
STL namespace.
Size __nb_elements
The number of elements in the heap.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
void erase(const Val &val)
Removes a given element from the priority queue (but does not return it).
HashTable< Val, Size, IndexAllocator > __indices
A hashtable for quickly finding the elements by their value.
A priorityQueue is a heap in which each element has a mutable priorityA priority queue is quite simil...
Definition: priorityQueue.h:48
std::vector< std::pair< Priority, const Val *>, HeapAllocator > __heap
An array storing all the elements of the heap as well as their score.
priority queues (in which an element cannot appear more than once)
void resize(Size new_size)
Changes the size of the internal structure storing the priority queue.
void clear()
Removes all the elements from the queue.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
friend class PriorityQueueImplementation
All gum::PriorityQueueImplementation are friends with themselves.
Definition: priorityQueue.h:88
Cmp __cmp
Comparison function.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52