36 template <
typename Val,
43 __indices(capacity >> 1, true, true),
45 __heap.reserve(capacity);
52 template <
typename Val,
59 std::initializer_list< std::pair< Val, Priority > > list) :
60 __indices(
Size(list.size()) / 2, true, true) {
62 __heap.reserve(list.size());
63 for (
const auto& elt : list) {
64 insert(elt.first, elt.second);
72 template <
typename Val,
82 __indices(from.__indices), __nb_elements(from.__nb_elements),
85 for (
const auto& elt : __indices) {
86 __heap[elt.second].second = &(elt.first);
94 template <
typename Val,
99 template <
typename OtherAlloc >
104 __indices(from.__indices),
105 __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
108 __heap.reserve(from.
__heap.size());
109 for (
const auto& elt : from.
__heap) {
110 __heap.push_back(elt);
112 for (
const auto& elt : __indices) {
113 __heap[elt.second].second = &(elt.first);
122 template <
typename Val,
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)) {
138 template <
typename Val,
150 template <
typename Val,
174 for (
const auto& elt : __indices) {
175 __heap[elt.second].second = &(elt.first);
190 template <
typename Val,
195 template <
typename OtherAlloc >
213 __heap.reserve(from.
__heap.size());
214 for (
const auto& elt : from.
__heap) {
215 __heap.push_back(elt);
217 for (
const auto& elt : __indices) {
218 __heap[elt.second].second = &(elt.first);
233 template <
typename Val,
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);
256 template <
typename Val,
265 return *(__heap[0].second);
269 template <
typename Val,
274 INLINE
const Priority&
279 return __heap[0].first;
283 template <
typename Val,
291 return __nb_elements;
295 template <
typename Val,
303 return Size(__heap.capacity());
307 template <
typename Val,
315 if (new_size < __nb_elements)
return;
317 __heap.reserve(new_size);
318 __indices.
resize(new_size / 2);
322 template <
typename Val,
335 template <
typename Val,
342 if (index >= __nb_elements)
return;
345 __indices.
erase(*(__heap[index].second));
348 std::pair< Priority, const Val* > last = std::move(__heap[__nb_elements - 1]);
352 if (!__nb_elements || (index == __nb_elements))
return;
357 for (
Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
359 if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
363 if (__cmp(last.first, __heap[j].first))
break;
366 __heap[i] = std::move(__heap[j]);
367 __indices[*(__heap[i].second)] = i;
371 __heap[i] = std::move(last);
372 __indices[*(__heap[i].second)] = i;
376 template <
typename Val,
384 eraseByPos(__indices[val]);
389 template <
typename Val,
400 template <
typename Val,
408 Val v = *(__heap[0].second);
415 template <
typename Val,
427 template <
typename Val,
434 const Val& val,
const Priority& priority) {
442 std::pair< Priority, const Val* >(priority, &new_elt.first));
444 __indices.erase(val);
448 std::pair< Priority, const Val* > new_heap_val =
449 std::move(__heap[__nb_elements]);
453 Size i = __nb_elements - 1;
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;
462 __heap[i].first = std::move(new_heap_val.first);
463 __heap[i].second = &(new_elt.first);
470 template <
typename Val,
477 Val&& val, Priority&& priority) {
481 __indices.
insert(std::move(val), 0);
485 std::pair< Priority, const Val* >(std::move(priority), &(new_elt.first)));
487 __indices.erase(new_elt.first);
491 std::pair< Priority, const Val* > new_heap_val =
492 std::move(__heap[__nb_elements]);
496 Size i = __nb_elements - 1;
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;
505 __heap[i].first = std::move(new_heap_val.first);
506 __heap[i].second = &(new_elt.first);
513 template <
typename Val,
518 template <
typename... 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));
528 template <
typename Val,
536 return (__nb_elements == 0);
540 template <
typename Val,
547 const Val& val)
const {
548 return __indices.exists(val);
552 template <
typename Val,
559 if (index >= __nb_elements) {
561 "not enough elements in the PriorityQueueImplementation");
564 return *(__heap[index].second);
568 template <
typename Val,
577 std::stringstream stream;
580 for (
Size i = 0; i != __nb_elements; ++i, deja =
true) {
581 if (deja) stream <<
" , ";
583 stream <<
"(" << __heap[i].first <<
" , " << *(__heap[i].second) <<
")";
592 template <
typename Val,
600 if (index >= __nb_elements) {
602 "not enough elements in the PriorityQueueImplementation");
606 const Val* val = __heap[index].second;
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;
619 for (
Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
621 if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
625 if (__cmp(new_priority, __heap[j].first))
break;
628 __heap[i] = std::move(__heap[j]);
629 __indices[*(__heap[i].second)] = i;
633 __heap[i].first = new_priority;
634 __heap[i].second = val;
641 template <
typename Val,
649 if (index >= __nb_elements) {
651 "not enough elements in the PriorityQueueImplementation");
655 const Val* val = __heap[index].second;
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;
668 for (
Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
670 if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
674 if (__cmp(new_priority, __heap[j].first))
break;
677 __heap[i] = std::move(__heap[j]);
678 __indices[*(__heap[i].second)] = i;
682 __heap[i].first = std::move(new_priority);
683 __heap[i].second = val;
690 template <
typename Val,
696 const Val& elt,
const Priority& new_priority) {
697 setPriorityByPos(__indices[elt], new_priority);
701 template <
typename Val,
707 const Val& elt, Priority&& new_priority) {
708 setPriorityByPos(__indices[elt], std::move(new_priority));
712 template <
typename Val,
717 INLINE
const Priority&
719 const Val& elt)
const {
720 return __heap[__indices[elt]].first;
724 template <
typename Val,
729 INLINE
const Priority&
732 if (index > __nb_elements) {
734 "not enough elements in the PriorityQueueImplementation");
736 return __heap[index].first;
744 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
747 __indices(capacity >> 1,
true,
true),
749 __heap.reserve(capacity);
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) {
762 __heap.reserve(list.size());
763 for (
const auto& elt : list) {
764 insert(elt.first, elt.second);
772 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
778 __indices(from.__indices), __nb_elements(from.__nb_elements),
785 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
786 template <
typename OtherAlloc >
791 __indices(from.__indices),
792 __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
795 __heap.reserve(from.
__heap.size());
796 for (
const auto& elt : from.
__heap) {
797 __heap.push_back(elt);
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)) {
818 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
826 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
857 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
858 template <
typename OtherAlloc >
876 __heap.reserve(from.
__heap.size());
877 for (
const auto& elt : from.
__heap) {
878 __heap.push_back(elt);
893 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
903 __heap = std::move(from.
__heap);
904 __cmp = std::move(from.
__cmp);
912 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
917 return __heap[0].second;
921 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
922 INLINE
const Priority&
927 return __heap[0].first;
931 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
935 return __nb_elements;
939 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
943 return Size(__heap.capacity());
947 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
951 if (new_size < __nb_elements)
return;
953 __heap.reserve(new_size);
954 __indices.
resize(new_size / 2);
958 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
967 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
970 if (index >= __nb_elements)
return;
973 __indices.
erase(__heap[index].second);
976 std::pair< Priority, Val > last = std::move(__heap[__nb_elements - 1]);
980 if (!__nb_elements || (index == __nb_elements))
return;
985 for (
Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
987 if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
991 if (__cmp(last.first, __heap[j].first))
break;
994 __heap[i] = std::move(__heap[j]);
995 __indices[__heap[i].second] = i;
999 __heap[i] = std::move(last);
1000 __indices[__heap[i].second] = i;
1004 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1009 eraseByPos(__indices[val]);
1014 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1021 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1026 Val v = __heap[0].second;
1033 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1041 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1044 Val val,
const Priority& priority) {
1048 __indices.
insert(val, 0);
1051 __heap.push_back(std::pair< Priority, Val >(priority, val));
1053 __indices.erase(val);
1057 std::pair< Priority, Val > new_heap_val = std::move(__heap[__nb_elements]);
1061 Size i = __nb_elements - 1;
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;
1070 __heap[i].first = std::move(new_heap_val.first);
1071 __heap[i].second = val;
1078 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1081 Val val, Priority&& priority) {
1085 __indices.
insert(val, 0);
1088 __heap.push_back(std::pair< Priority, Val >(std::move(priority), val));
1090 __indices.erase(val);
1094 std::pair< Priority, Val > new_heap_val = std::move(__heap[__nb_elements]);
1098 Size i = __nb_elements - 1;
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;
1107 __heap[i].first = std::move(new_heap_val.first);
1108 __heap[i].second = val;
1115 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1116 template <
typename... 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));
1126 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1130 return (__nb_elements == 0);
1134 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1138 return __indices.exists(val);
1142 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1146 if (index >= __nb_elements) {
1148 "not enough elements in the PriorityQueueImplementation");
1151 return __heap[index].second;
1155 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1160 std::stringstream stream;
1163 for (
Size i = 0; i != __nb_elements; ++i, deja =
true) {
1164 if (deja) stream <<
" , ";
1166 stream <<
"(" << __heap[i].first <<
" , " << __heap[i].second <<
")";
1171 return stream.str();
1175 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1179 if (index >= __nb_elements) {
1181 "not enough elements in the PriorityQueueImplementation");
1185 Val val = __heap[index].second;
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;
1198 for (
Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
1200 if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
1204 if (__cmp(new_priority, __heap[j].first))
break;
1207 __heap[i] = std::move(__heap[j]);
1208 __indices[__heap[i].second] = i;
1212 __heap[i].first = new_priority;
1213 __heap[i].second = val;
1220 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1224 if (index >= __nb_elements) {
1226 "not enough elements in the PriorityQueueImplementation");
1230 Val val = __heap[index].second;
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;
1243 for (
Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
1245 if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
1249 if (__cmp(new_priority, __heap[j].first))
break;
1252 __heap[i] = std::move(__heap[j]);
1253 __indices[__heap[i].second] = i;
1257 __heap[i].first = std::move(new_priority);
1258 __heap[i].second = val;
1265 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1267 Val elt,
const Priority& new_priority) {
1268 setPriorityByPos(__indices[elt], new_priority);
1272 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1274 Val elt, Priority&& new_priority) {
1275 setPriorityByPos(__indices[elt], std::move(new_priority));
1279 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1280 INLINE
const Priority&
1283 return __heap[__indices[elt]].first;
1287 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1288 INLINE
const Priority&
1291 if (index > __nb_elements) {
1293 "not enough elements in the PriorityQueueImplementation");
1295 return __heap[index].first;
1303 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1312 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1314 std::initializer_list< std::pair< Val, Priority > > list) :
1321 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1330 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1331 template <
typename OtherAlloc >
1340 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1349 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1356 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1360 Implementation::operator=(from);
1365 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1366 template <
typename OtherAlloc >
1370 Implementation::operator=(from);
1375 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1379 Implementation::operator=(std::move(from));
1384 template <
typename Val,
typename Priority,
typename Cmp,
typename Alloc >
1385 INLINE std::ostream&
INLINE std::ostream & operator<<(std::ostream &stream, const PriorityQueue< Val, Priority, Cmp, Alloc > &queue)
The internal class for representing priority queues.
Size __nb_elements
The number of elements in the heap.
gum is the global namespace for all aGrUM entities
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...
std::string toString() const
Displays the content of the queue.
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.
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.
Cmp __cmp
Comparison function.
#define GUM_ERROR(type, msg)