Loading...
Searching...
No Matches
PQueue.tpp
1/*---------------------------------------------------------------------------*\
2 *
3 * bitpit
4 *
5 * Copyright (C) 2015-2021 OPTIMAD engineering Srl
6 *
7 * -------------------------------------------------------------------------
8 * License
9 * This file is part of bitpit.
10 *
11 * bitpit is free software: you can redistribute it and/or modify it
12 * under the terms of the GNU Lesser General Public License v3 (LGPL)
13 * as published by the Free Software Foundation.
14 *
15 * bitpit is distributed in the hope that it will be useful, but WITHOUT
16 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18 * License for more details.
19 *
20 * You should have received a copy of the GNU Lesser General Public License
21 * along with bitpit. If not, see <http://www.gnu.org/licenses/>.
22 *
23\*---------------------------------------------------------------------------*/
24
25// ========================================================================== //
26// - SORTING ALGORITHMS - //
27// //
28// Functions for data sorting. //
29// ========================================================================== //
30// INFO //
31// Author : Alessandro Alaia //
32// Version : v2.0 //
33// //
34// All rights reserved. //
35// ========================================================================== //
36
37namespace bitpit{
38
39// ========================================================================== //
40// TEMPLATE IMPLEMENTATIONS FOR MinPQueue //
41// ========================================================================== //
42
72// Constructors ============================================================= //
73
74// -------------------------------------------------------------------------- //
84template <class T, class T1>
85MinPQueue<T, T1>::MinPQueue(
86 bool flag_label,
87 std::vector< std::array<int,2> >*map_
88 ) {
89
90 // ========================================================================== //
91 // VARIABLES DECLARATION //
92 // ========================================================================== //
93
94 // Local variables
95 // none
96
97 // Counters
98 // none
99
100 // ========================================================================== //
101 // CREATE LIFO STACK //
102 // ========================================================================== //
103
104 // Max stack dimensions
105 MAXSTK = 10;
106
107 // Currenst stack size
108 heap_size = 0;
109
110 // Set flag
111 use_labels = flag_label;
112
113 // Pointers
114 map = map_;
115
116 // Initialize stack
117 increaseSTACK();
118
119 return;
120};
121
122// -------------------------------------------------------------------------- //
134template <class T, class T1>
135MinPQueue<T, T1>::MinPQueue(
136 int maxstack,
137 bool flag_label,
138 std::vector< std::array<int,2> >*map_
139 ) {
140
141 // ========================================================================== //
142 // VARIABLES DECLARATION //
143 // ========================================================================== //
144
145 // Local variables
146 // none
147
148 // Counters
149 // none
150
151 // ========================================================================== //
152 // CREATE LIFO STACK //
153 // ========================================================================== //
154
155 // Max stack dimensions
156 MAXSTK = maxstack;
157
158 // Currenst stack size
159 heap_size = 0;
160
161 // Flags
162 use_labels = flag_label;
163
164 // Pointers
165 map = map_;
166
167 // Initialize stack
168 increaseSTACK();
169
170 return;
171};
172
173// Destructors ============================================================== //
174
175// -------------------------------------------------------------------------- //
180template <class T, class T1>
181MinPQueue<T, T1>::~MinPQueue(
182 void
183 ) {
184
185 // ========================================================================== //
186 // VARIABLES DECLARATION //
187 // ========================================================================== //
188
189 // Local variables
190 // none
191
192 // Counters
193 // none
194
195 // ========================================================================== //
196 // DESTROY LIFO STACK //
197 // ========================================================================== //
198
199 // Maximal stack size
200 MAXSTK = 0;
201
202 // Current stack dimensions
203 heap_size = 0;
204
205 // Destroy items
206 keys.clear();
207 if (use_labels) { labels.clear(); }
208 map = NULL;
209
210 // Flags
211 use_labels = false;
212
213 return;
214};
215
216// Methods ================================================================== //
217
218// -------------------------------------------------------------------------- //
222template <class T, class T1>
223void MinPQueue<T, T1>::clear(
224 void
225 ) {
226
227 // ========================================================================== //
228 // VARIABLES DECLARATION //
229 // ========================================================================== //
230
231 // Local variables
232 // none
233
234 // Counters
235 // none
236
237 // ========================================================================== //
238 // CLEAR CONTENT //
239 // ========================================================================== //
240 heap_size = 0;
241 keys.resize(MAXSTK);
242 if (use_labels) { labels.resize(MAXSTK); }
243
244 return;
245}
246
247// -------------------------------------------------------------------------- //
252template <class T, class T1>
253void MinPQueue<T, T1>::increaseSTACK(
254 void
255 ) {
256
257 // ========================================================================== //
258 // VARIABLES DECLARATION //
259 // ========================================================================== //
260
261 // Local variables
262 // none
263
264 // Counters
265 // none
266
267 // ========================================================================== //
268 // INCREASE STACK SIZE //
269 // ========================================================================== //
270
271 // stack
272 keys.resize(heap_size + MAXSTK);
273
274 // labels
275 if (use_labels) {
276 labels.resize(heap_size + MAXSTK);
277 }
278
279 return;
280};
281
282// -------------------------------------------------------------------------- //
287template <class T, class T1>
288void MinPQueue<T, T1>::decreaseSTACK(
289 void
290 ) {
291
292 // ========================================================================== //
293 // VARIABLES DECLARATION //
294 // ========================================================================== //
295
296 // Local variables
297 int n = keys.size();
298
299 // Counters
300 // none
301
302 // ========================================================================== //
303 // DECREASE STACK SIZE //
304 // ========================================================================== //
305
306 // Stack
307 keys.resize(std::max(n - MAXSTK, MAXSTK));
308
309 // labels
310 if (use_labels) {
311 labels.resize(std::max(n - MAXSTK, MAXSTK));
312 }
313
314 return;
315};
316
317// -------------------------------------------------------------------------- //
323template <class T, class T1 >
324void MinPQueue<T, T1>::heapify(
325 int i
326 ) {
327
328 // ========================================================================== //
329 // VARIABLES DECLARATION //
330 // ========================================================================== //
331
332 // Local variables
333 int L, R, idummy, imap;
334 T dummy;
335 T1 dummy2;
336
337 // Counters
338 // none
339
340 // ========================================================================== //
341 // RESTORE THE MIN HEAP PROPERTY //
342 // ========================================================================== //
343
344 // Index of childrens
345 L = 2*i + 1;
346 R = 2*(i + 1);
347
348 // Check children's key
349 if ((L < heap_size) && (keys[L] < keys[i])) {
350 idummy = L;
351 }
352 else {
353 idummy = i;
354 }
355 if ((R < heap_size) && (keys[R] < keys[idummy])) {
356 idummy = R;
357 }
358
359 // Move up-heap
360 if (idummy != i) {
361 dummy = keys[i];
362 keys[i] = keys[idummy];
363 keys[idummy] = dummy;
364 if (use_labels) {
365 dummy2 = labels[i];
366 labels[i] = labels[idummy];
367 labels[idummy] = dummy2;
368 }
369 if (map != NULL) {
370 imap = (*map)[i][0];
371 (*map)[i][0] = (*map)[idummy][0];
372 (*map)[idummy][0] = imap;
373 (*map)[(*map)[i][0]][1] = i;
374 (*map)[(*map)[idummy][0]][1] = idummy;
375 }
376 heapify(idummy);
377 }
378
379 return;
380};
381
382// -------------------------------------------------------------------------- //
386template <class T, class T1>
387void MinPQueue<T, T1>::buildHeap(
388 void
389 ) {
390
391 // ========================================================================== //
392 // VARIABLES DECLARATION //
393 // ========================================================================== //
394
395 // Local variables
396 // none
397
398 // Counters
399 int i;
400
401 // ========================================================================== //
402 // BUILD MIN HEAP //
403 // ========================================================================== //
404 for (i = (heap_size - 1)/2; i >= 0; i--) {
405 heapify(i);
406 } //next i
407
408 return;
409};
410
411// -------------------------------------------------------------------------- //
421template <class T, class T1>
422void MinPQueue<T, T1>::extract(
423 T &root,
424 T1 &root_label
425 ) {
426
427 // ========================================================================== //
428 // VARIABLES DECLARATION //
429 // ========================================================================== //
430
431 // Local variables
432 int imap;
433
434 // Counters
435 // none
436
437 // ========================================================================== //
438 // EXTRACT HEAP MIN ELEMENT //
439 // ========================================================================== //
440
441 // Extract min element
442 if (heap_size == 0) {
443 return;
444 }
445 root = keys[0];
446
447 // Update heap data structure
448 keys[0] = keys[heap_size-1];
449 if (use_labels) {
450 root_label = labels[0];
451 labels[0] = labels[heap_size-1];
452 }
453 if (map != NULL) {
454 imap = (*map)[0][0];
455 (*map)[0][0] = (*map)[heap_size-1][0];
456 (*map)[heap_size-1][0] = imap;
457 (*map)[imap][1] = heap_size-1;
458 (*map)[(*map)[0][0]][1] = 0;
459 }
460
461 // Reduce stack dimensions
462 heap_size--;
463 if (heap_size <= (long) keys.size() - MAXSTK) {
464 decreaseSTACK();
465 }
466
467 // Restore min-heap condition
468 heapify(0);
469
470 return;
471};
472
473// -------------------------------------------------------------------------- //
481template <class T, class T1>
482void MinPQueue<T, T1>::extract(
483 T &root
484 ) {
485
486 // ========================================================================== //
487 // VARIABLES DECLARATION //
488 // ========================================================================== //
489
490 // Local variables
491 int imap;
492
493 // Counters
494 // none
495
496 // ========================================================================== //
497 // EXTRACT HEAP MIN ELEMENT //
498 // ========================================================================== //
499
500 // Extract min element
501 if (heap_size == 0) {
502 return;
503 }
504 root = keys[0];
505
506 // Update heap data structure
507 keys[0] = keys[heap_size-1];
508 if (map != NULL) {
509 imap = (*map)[0][0];
510 (*map)[0][0] = (*map)[heap_size-1][0];
511 (*map)[heap_size-1][0] = imap;
512 (*map)[imap][1] = heap_size-1;
513 (*map)[(*map)[0][0]][1] = 0;
514 }
515
516 // Reduce stack dimensions
517 heap_size--;
518 if (heap_size <= keys.size() - MAXSTK) {
519 decreaseSTACK();
520 }
521
522 // Restore min-heap condition
523 heapify(0);
524
525 return;
526};
527
528// -------------------------------------------------------------------------- //
537template <class T, class T1>
538void MinPQueue<T, T1>::insert(
539 T &key_new,
540 T1 &label_new
541 ) {
542
543 // ========================================================================== //
544 // VARIABLES DECLARATION //
545 // ========================================================================== //
546
547 // Local variables
548 // none
549
550 // Counters
551 // none
552
553 // ========================================================================== //
554 // INSERT A NEW KEY //
555 // ========================================================================== //
556
557 // Insert key
558 if (heap_size+1 > (long) keys.size()) {
559 increaseSTACK();
560 }
561
562 // Add new key
563 keys[heap_size] = key_new;
564
565 // Update labels
566 if (use_labels) {
567 labels[heap_size] = label_new;
568 }
569
570 // Update heap size
571 heap_size++;
572
573 // Restore max heap condition
574 modify(heap_size-1, key_new, label_new);
575
576 return;
577};
578
579// -------------------------------------------------------------------------- //
586template <class T, class T1>
587void MinPQueue<T, T1>::insert(
588 T &key_new
589 ) {
590
591 // ========================================================================== //
592 // template <class T, class T1> //
593 // void MinPQueue<T, T1>::insert( //
594 // T &key_new) //
595 // //
596 // Insert new key into a min heap //
597 // ========================================================================== //
598 // INPUT //
599 // ========================================================================== //
600 // - key_new : T1, key to be inserted //
601 // ========================================================================== //
602 // OUTPUT //
603 // ========================================================================== //
604 // - none //
605 // ========================================================================== //
606
607 // ========================================================================== //
608 // VARIABLES DECLARATION //
609 // ========================================================================== //
610
611 // Local variables
612 // none
613
614 // Counters
615 // none
616
617 // ========================================================================== //
618 // INSERT A NEW KEY //
619 // ========================================================================== //
620
621 // Insert key
622 if (heap_size+1 > keys.size()) {
623 increaseSTACK();
624 }
625
626 // Add new key
627 keys[heap_size] = key_new;
628
629 // Update heap size
630 heap_size++;
631
632 // Restore max heap condition
633 modify(heap_size-1, key_new);
634
635 return;
636};
637
638// -------------------------------------------------------------------------- //
648template <class T, class T1>
649void MinPQueue<T, T1>::modify(
650 int i,
651 T &key_new,
652 T1 &label_new
653 ) {
654
655 // ========================================================================== //
656 // VARIABLES DECLARATION //
657 // ========================================================================== //
658
659 // Local variables
660 int imap;
661 T dummy1;
662 T1 dummy2;
663
664 // Counters
665 int j;
666
667 // ========================================================================== //
668 // INCREASE VALUE OF LAST KEY. //
669 // ========================================================================== //
670 if (key_new > keys[i]) {
671
672 // Update keys
673 keys[i] = key_new;
674 if (use_labels) {
675 labels[i] = label_new;
676 }
677
678 // move down-heap
679 heapify(i);
680
681 }
682 else {
683
684 // Update keys
685 keys[i] = key_new;
686 if (use_labels) {
687 labels[i] = label_new;
688 }
689
690 // move up-heap
691 j = (i + 1)/2 - 1;
692 while ((i > 0) && (keys[j] > keys[i])) {
693 dummy1 = keys[i];
694 keys[i] = keys[j];
695 keys[j] = dummy1;
696 if (use_labels) {
697 dummy2 = labels[i];
698 labels[i] = labels[j];
699 labels[j] = dummy2;
700 }
701 if (map != NULL) {
702 imap = (*map)[i][0];
703 (*map)[i][0] = (*map)[j][0];
704 (*map)[j][0] = imap;
705 (*map)[(*map)[i][0]][1] = i;
706 (*map)[(*map)[j][0]][1] = j;
707 }
708 i = j;
709 j = (i + 1)/2 - 1;
710 } //next parent
711 }
712
713 return;
714};
715
716// -------------------------------------------------------------------------- //
724template <class T, class T1>
725void MinPQueue<T, T1>::modify(
726 int i,
727 T &key_new
728 ) {
729
730 // ========================================================================== //
731 // VARIABLES DECLARATION //
732 // ========================================================================== //
733
734 // Local variables
735 int imap;
736 T dummy1;
737
738 // Counters
739 int j;
740
741 // ========================================================================== //
742 // INCREASE VALUE OF SELECTED KEY. //
743 // ========================================================================== //
744 if (key_new > keys[i]) {
745
746 // Update keys
747 keys[i] = key_new;
748
749 // move down-heap
750 heapify(i);
751
752 }
753 else {
754
755 // Update keys
756 keys[i] = key_new;
757
758 // move up-heap
759 j = (i + 1)/2 - 1;
760 while ((i > 0) && (keys[j] > keys[i])) {
761 dummy1 = keys[i];
762 keys[i] = keys[j];
763 keys[j] = dummy1;
764 if (map != NULL) {
765 imap = (*map)[i][0];
766 (*map)[i][0] = (*map)[j][0];
767 (*map)[j][0] = imap;
768 (*map)[(*map)[i][0]][1] = i;
769 (*map)[(*map)[j][0]][1] = j;
770 }
771 i = j;
772 j = (i + 1)/2 - 1;
773 } //next parent
774 }
775
776 return;
777};
778
779// -------------------------------------------------------------------------- //
786template <class T, class T1>
787void MinPQueue<T, T1>::display(
788 std::ostream &out
789 ) {
790
791 // ========================================================================== //
792 // VARIABLES DECLARATION //
793 // ========================================================================== //
794
795 // Local variables
796 // none
797
798 // Counters
799 int i, j, k;
800
801 // ========================================================================== //
802 // DISPLAY MIN-HEAP INFO //
803 // ========================================================================== //
804
805 // General info ------------------------------------------------------------- //
806 out << "min heap:" << std::endl;
807 out << "heap size: " << heap_size << std::endl;
808 out << "data struct. size: " << keys.size() << std::endl;
809 out << "max stack size: " << MAXSTK << std::endl;
810
811 // heap content ------------------------------------------------------------- //
812 out << "min heap data:" << std::endl;
813 i = 0;
814 k = 0;
815 while (i < heap_size) {
816 j = 0;
817 while ((j < pow(2, k)) && (i < heap_size)) {
818 out << "[" << keys[i];
819 if (use_labels) {
820 out << ", '" << labels[i] << "'";
821 }
822 out << "] ";
823 i++;
824 j++;
825 } //next j
826 out << std::endl;
827 k++;
828 } //next i
829
830 return;
831}
832
842// ========================================================================== //
843// TEMPLATE IMPLEMENTATIONS FOR MaxPQueue //
844// ========================================================================== //
845
874// Constructors ============================================================= //
875
876// -------------------------------------------------------------------------- //
886template <class T, class T1>
887MaxPQueue<T, T1>::MaxPQueue(
888 bool flag_label,
889 std::vector< std::array<int,2> >*map_
890 ) {
891
892 // ========================================================================== //
893 // VARIABLES DECLARATION //
894 // ========================================================================== //
895
896 // Local variables
897 // none
898
899 // Counters
900 // none
901
902 // ========================================================================== //
903 // CREATE LIFO STACK //
904 // ========================================================================== //
905
906 // Max stack dimensions
907 MAXSTK = 10;
908
909 // Currenst stack size
910 heap_size = 0;
911
912 // Set flag
913 use_labels = flag_label;
914
915 // Pointers
916 map = map_;
917
918 // Initialize stack
919 increaseSTACK();
920
921 return;
922};
923
924// -------------------------------------------------------------------------- //
936template <class T, class T1>
937MaxPQueue<T, T1>::MaxPQueue(
938 int maxstack,
939 bool flag_label,
940 std::vector< std::array<int,2> >*map_
941 ) {
942
943 // ========================================================================== //
944 // VARIABLES DECLARATION //
945 // ========================================================================== //
946
947 // Local variables
948 // none
949
950 // Counters
951 // none
952
953 // ========================================================================== //
954 // CREATE LIFO STACK //
955 // ========================================================================== //
956
957 // Max stack dimensions
958 MAXSTK = maxstack;
959
960 // Currenst stack size
961 heap_size = 0;
962
963 // Flags
964 use_labels = flag_label;
965
966 // Pointers
967 map = map_;
968
969 // Initialize stack
970 increaseSTACK();
971
972 return;
973};
974
975// Destructors ============================================================== //
976
977// -------------------------------------------------------------------------- //
982template <class T, class T1>
983MaxPQueue<T, T1>::~MaxPQueue(
984 void
985 ) {
986
987 // ========================================================================== //
988 // template <class T, class T1> //
989 // MaxPQueue<T, T1>::~MaxPQueue( //
990 // void) //
991 // //
992 // Standard destructor for max heap. //
993 // ========================================================================== //
994 // INPUT //
995 // ========================================================================== //
996 // - none //
997 // ========================================================================== //
998 // OUTPUT //
999 // ========================================================================== //
1000 // - none //
1001 // ========================================================================== //
1002
1003 // ========================================================================== //
1004 // VARIABLES DECLARATION //
1005 // ========================================================================== //
1006
1007 // Local variables
1008 // none
1009
1010 // Counters
1011 // none
1012
1013 // ========================================================================== //
1014 // DESTROY LIFO STACK //
1015 // ========================================================================== //
1016
1017 // Maximal stack size
1018 MAXSTK = 0;
1019
1020 // Current stack dimensions
1021 heap_size = 0;
1022
1023 // Destroy items
1024 keys.clear();
1025 if (use_labels) { labels.clear(); }
1026 map = NULL;
1027
1028 // Flags
1029 use_labels = false;
1030
1031 return;
1032};
1033
1034// Methods ================================================================== //
1035
1036// -------------------------------------------------------------------------- //
1040template <class T, class T1>
1041void MaxPQueue<T, T1>::clear(
1042 void
1043 ) {
1044
1045 // ========================================================================== //
1046 // VARIABLES DECLARATION //
1047 // ========================================================================== //
1048
1049 // Local variables
1050 // none
1051
1052 // Counters
1053 // none
1054
1055 // ========================================================================== //
1056 // CLEAR CONTENT //
1057 // ========================================================================== //
1058 heap_size = 0;
1059 keys.resize(MAXSTK);
1060 if (use_labels) { labels.resize(MAXSTK); }
1061
1062 return;
1063}
1064
1065// -------------------------------------------------------------------------- //
1070template <class T, class T1>
1071void MaxPQueue<T, T1>::increaseSTACK(
1072 void
1073 ) {
1074
1075 // ========================================================================== //
1076 // VARIABLES DECLARATION //
1077 // ========================================================================== //
1078
1079 // Local variables
1080 // none
1081
1082 // Counters
1083 // none
1084
1085 // ========================================================================== //
1086 // INCREASE STACK SIZE //
1087 // ========================================================================== //
1088
1089 // stack
1090 keys.resize(heap_size + MAXSTK);
1091
1092 // labels
1093 if (use_labels) {
1094 labels.resize(heap_size + MAXSTK);
1095 }
1096
1097 return;
1098};
1099
1100// -------------------------------------------------------------------------- //
1105template <class T, class T1>
1106void MaxPQueue<T, T1>::decreaseSTACK(
1107 void
1108 ) {
1109
1110 // ========================================================================== //
1111 // template <class T, class T1> //
1112 // void MaxPQueue<T, T1>::decreaseSTACK( //
1113 // void) //
1114 // //
1115 // Decrease stack size. //
1116 // ========================================================================== //
1117 // INPUT //
1118 // ========================================================================== //
1119 // - none //
1120 // ========================================================================== //
1121 // OUTPUT //
1122 // ========================================================================== //
1123 // - none //
1124 // ========================================================================== //
1125
1126 // ========================================================================== //
1127 // VARIABLES DECLARATION //
1128 // ========================================================================== //
1129
1130 // Local variables
1131 int n = keys.size();
1132
1133 // Counters
1134 // none
1135
1136 // ========================================================================== //
1137 // DECREASE STACK SIZE //
1138 // ========================================================================== //
1139
1140 // Stack
1141 keys.resize(std::max(n - MAXSTK, MAXSTK));
1142
1143 // labels
1144 if (use_labels) {
1145 labels.resize(std::max(n - MAXSTK, MAXSTK));
1146 }
1147
1148 return;
1149};
1150
1151// -------------------------------------------------------------------------- //
1157template <class T, class T1 >
1158void MaxPQueue<T, T1>::heapify(
1159 int i
1160 ) {
1161
1162 // ========================================================================== //
1163 // VARIABLES DECLARATION //
1164 // ========================================================================== //
1165
1166 // Local variables
1167 int L, R, idummy, imap;
1168 T dummy;
1169 T1 dummy2;
1170
1171 // Counters
1172 // none
1173
1174 // ========================================================================== //
1175 // RESTORE THE MIN HEAP PROPERTY //
1176 // ========================================================================== //
1177
1178 // Index of childrens
1179 L = 2*i + 1;
1180 R = 2*(i + 1);
1181
1182 // Check children's key
1183 if ((L < heap_size) && (keys[L] > keys[i])) {
1184 idummy = L;
1185 }
1186 else {
1187 idummy = i;
1188 }
1189 if ((R < heap_size) && (keys[R] > keys[idummy])) {
1190 idummy = R;
1191 }
1192
1193 // Move up-heap
1194 if (idummy != i) {
1195 dummy = keys[i];
1196 keys[i] = keys[idummy];
1197 keys[idummy] = dummy;
1198 if (use_labels) {
1199 dummy2 = labels[i];
1200 labels[i] = labels[idummy];
1201 labels[idummy] = dummy2;
1202 }
1203 if (map != NULL) {
1204 imap = (*map)[i][0];
1205 (*map)[i][0] = (*map)[idummy][0];
1206 (*map)[idummy][0] = imap;
1207 (*map)[(*map)[i][0]][1] = i;
1208 (*map)[(*map)[idummy][0]][1] = idummy;
1209 }
1210 heapify(idummy);
1211 }
1212
1213 return;
1214};
1215
1216// -------------------------------------------------------------------------- //
1220template <class T, class T1>
1221void MaxPQueue<T, T1>::buildHeap(
1222 void
1223 ) {
1224
1225 // ========================================================================== //
1226 // template <class T, class T1> //
1227 // void MaxPQueue<T, T1>::buildHeap( //
1228 // void) //
1229 // //
1230 // Build max heap tree. //
1231 // ========================================================================== //
1232 // INPUT //
1233 // ========================================================================== //
1234 // - none //
1235 // ========================================================================== //
1236 // OUTPUT //
1237 // ========================================================================== //
1238 // - none //
1239 // ========================================================================== //
1240
1241 // ========================================================================== //
1242 // VARIABLES DECLARATION //
1243 // ========================================================================== //
1244
1245 // Local variables
1246 // none
1247
1248 // Counters
1249 int i;
1250
1251 // ========================================================================== //
1252 // BUILD MAX HEAP //
1253 // ========================================================================== //
1254 for (i = (heap_size - 1)/2; i >= 0; i--) {
1255 heapify(i);
1256 } //next i
1257
1258 return;
1259};
1260
1261// -------------------------------------------------------------------------- //
1271template <class T, class T1>
1272void MaxPQueue<T, T1>::extract(
1273 T &root,
1274 T1 &root_label
1275 ) {
1276
1277 // ========================================================================== //
1278 // VARIABLES DECLARATION //
1279 // ========================================================================== //
1280
1281 // Local variables
1282 int imap;
1283
1284 // Counters
1285 // none
1286
1287 // ========================================================================== //
1288 // EXTRACT HEAP MAX ELEMENT //
1289 // ========================================================================== //
1290
1291 // Extract max element
1292 if (heap_size == 0) {
1293 return;
1294 }
1295 root = keys[0];
1296
1297 // Update heap data structure
1298 keys[0] = keys[heap_size-1];
1299 if (use_labels) {
1300 root_label = labels[0];
1301 labels[0] = labels[heap_size-1];
1302 }
1303 if (map != NULL) {
1304 imap = (*map)[0][0];
1305 (*map)[0][0] = (*map)[heap_size-1][0];
1306 (*map)[heap_size-1][0] = imap;
1307 (*map)[imap][1] = heap_size-1;
1308 (*map)[(*map)[0][0]][1] = 0;
1309 }
1310
1311 // Reduce stack dimensions
1312 heap_size--;
1313 if (heap_size <= (long) keys.size() - MAXSTK) {
1314 decreaseSTACK();
1315 }
1316
1317 // Restore max-heap condition
1318 heapify(0);
1319
1320 return;
1321};
1322
1323// -------------------------------------------------------------------------- //
1331template <class T, class T1>
1332void MaxPQueue<T, T1>::extract(
1333 T &root
1334 ) {
1335
1336 // ========================================================================== //
1337 // VARIABLES DECLARATION //
1338 // ========================================================================== //
1339
1340 // Local variables
1341 int imap;
1342
1343 // Counters
1344 // none
1345
1346 // ========================================================================== //
1347 // EXTRACT HEAP MAX ELEMENT //
1348 // ========================================================================== //
1349
1350 // Extract max element
1351 if (heap_size == 0) {
1352 return;
1353 }
1354 root = keys[0];
1355
1356 // Update heap data structure
1357 keys[0] = keys[heap_size-1];
1358 if (map != NULL) {
1359 imap = (*map)[0][0];
1360 (*map)[0][0] = (*map)[heap_size-1][0];
1361 (*map)[heap_size-1][0] = imap;
1362 (*map)[imap][1] = heap_size-1;
1363 (*map)[(*map)[0][0]][1] = 0;
1364 }
1365
1366 // Reduce stack dimensions
1367 heap_size--;
1368 if (heap_size <= keys.size() - MAXSTK) {
1369 decreaseSTACK();
1370 }
1371
1372 // Restore max-heap condition
1373 heapify(0);
1374
1375 return;
1376};
1377
1378// -------------------------------------------------------------------------- //
1387template <class T, class T1>
1388void MaxPQueue<T, T1>::insert(
1389 T &key_new,
1390 T1 &label_new
1391 ) {
1392
1393 // ========================================================================== //
1394 // VARIABLES DECLARATION //
1395 // ========================================================================== //
1396
1397 // Local variables
1398 // none
1399
1400 // Counters
1401 // none
1402
1403 // ========================================================================== //
1404 // INSERT A NEW KEY //
1405 // ========================================================================== //
1406
1407 // Insert key
1408 if (heap_size+1 > (long) keys.size()) {
1409 increaseSTACK();
1410 }
1411
1412 // Add new key
1413 keys[heap_size] = key_new;
1414
1415 // Update labels
1416 if (use_labels) {
1417 labels[heap_size] = label_new;
1418 }
1419
1420 // Update heap size
1421 heap_size++;
1422
1423 // Restore max heap condition
1424 modify(heap_size-1, key_new, label_new);
1425
1426 return;
1427};
1428
1429// -------------------------------------------------------------------------- //
1436template <class T, class T1>
1437void MaxPQueue<T, T1>::insert(
1438 T &key_new
1439 ) {
1440
1441 // ========================================================================== //
1442 // VARIABLES DECLARATION //
1443 // ========================================================================== //
1444
1445 // Local variables
1446 // none
1447
1448 // Counters
1449 // none
1450
1451 // ========================================================================== //
1452 // INSERT A NEW KEY //
1453 // ========================================================================== //
1454
1455 // Insert key
1456 if (heap_size+1 > keys.size()) {
1457 increaseSTACK();
1458 }
1459
1460 // Add new key
1461 keys[heap_size] = key_new;
1462
1463 // Update heap size
1464 heap_size++;
1465
1466 // Restore max heap condition
1467 modify(heap_size-1, key_new);
1468
1469 return;
1470};
1471
1472// -------------------------------------------------------------------------- //
1482template <class T, class T1>
1483void MaxPQueue<T, T1>::modify(
1484 int i,
1485 T &key_new,
1486 T1 &label_new
1487 ) {
1488
1489 // ========================================================================== //
1490 // VARIABLES DECLARATION //
1491 // ========================================================================== //
1492
1493 // Local variables
1494 int imap;
1495 T dummy1;
1496 T1 dummy2;
1497
1498 // Counters
1499 int j;
1500
1501 // ========================================================================== //
1502 // INCREASE VALUE OF LAST KEY. //
1503 // ========================================================================== //
1504 if (key_new < keys[i]) {
1505
1506 // Update keys
1507 keys[i] = key_new;
1508 if (use_labels) {
1509 labels[i] = label_new;
1510 }
1511
1512 // move down-heap
1513 heapify(i);
1514
1515 }
1516 else {
1517
1518 // Update keys
1519 keys[i] = key_new;
1520 if (use_labels) {
1521 labels[i] = label_new;
1522 }
1523
1524 // move up-heap
1525 j = (i + 1)/2 - 1;
1526 while ((i > 0) && (keys[j] < keys[i])) {
1527 dummy1 = keys[i];
1528 keys[i] = keys[j];
1529 keys[j] = dummy1;
1530 if (use_labels) {
1531 dummy2 = labels[i];
1532 labels[i] = labels[j];
1533 labels[j] = dummy2;
1534 }
1535 if (map != NULL) {
1536 imap = (*map)[i][0];
1537 (*map)[i][0] = (*map)[j][0];
1538 (*map)[j][0] = imap;
1539 (*map)[(*map)[i][0]][1] = i;
1540 (*map)[(*map)[j][0]][1] = j;
1541 }
1542 i = j;
1543 j = (i + 1)/2 - 1;
1544 } //next parent
1545 }
1546
1547 return;
1548};
1549
1550// -------------------------------------------------------------------------- //
1558template <class T, class T1>
1559void MaxPQueue<T, T1>::modify(
1560 int i,
1561 T &key_new
1562 ) {
1563
1564 // ========================================================================== //
1565 // VARIABLES DECLARATION //
1566 // ========================================================================== //
1567
1568 // Local variables
1569 int imap;
1570 T dummy1;
1571
1572 // Counters
1573 int j;
1574
1575 // ========================================================================== //
1576 // INCREASE VALUE OF SELECTED KEY. //
1577 // ========================================================================== //
1578 if (key_new < keys[i]) {
1579
1580 // Update keys
1581 keys[i] = key_new;
1582
1583 // move down-heap
1584 heapify(i);
1585
1586 }
1587 else {
1588
1589 // Update keys
1590 keys[i] = key_new;
1591
1592 // move up-heap
1593 j = (i + 1)/2 - 1;
1594 while ((i > 0) && (keys[j] < keys[i])) {
1595 dummy1 = keys[i];
1596 keys[i] = keys[j];
1597 keys[j] = dummy1;
1598 if (map != NULL) {
1599 imap = (*map)[i][0];
1600 (*map)[i][0] = (*map)[j][0];
1601 (*map)[j][0] = imap;
1602 (*map)[(*map)[i][0]][1] = i;
1603 (*map)[(*map)[j][0]][1] = j;
1604 }
1605 i = j;
1606 j = (i + 1)/2 - 1;
1607 } //next parent
1608 }
1609
1610 return;
1611};
1612
1613// -------------------------------------------------------------------------- //
1620template <class T, class T1>
1621void MaxPQueue<T, T1>::display(
1622 std::ostream &out
1623 ) {
1624
1625 // ========================================================================== //
1626 // VARIABLES DECLARATION //
1627 // ========================================================================== //
1628
1629 // Local variables
1630 // none
1631
1632 // Counters
1633 int i, j, k;
1634
1635 // ========================================================================== //
1636 // DISPLAY MAX-HEAP INFO //
1637 // ========================================================================== //
1638
1639 // General info ------------------------------------------------------------- //
1640 out << "max heap:" << std::endl;
1641 out << "heap size: " << heap_size << std::endl;
1642 out << "data struct. size: " << keys.size() << std::endl;
1643 out << "max stack size: " << MAXSTK << std::endl;
1644
1645 // heap content ------------------------------------------------------------- //
1646 out << "max heap data:" << std::endl;
1647 i = 0;
1648 k = 0;
1649 while (i < heap_size) {
1650 j = 0;
1651 while ((j < pow(2, k)) && (i < heap_size)) {
1652 out << "[" << keys[i];
1653 if (use_labels) {
1654 out << ", '" << labels[i] << "'";
1655 }
1656 out << "] ";
1657 i++;
1658 j++;
1659 } //next j
1660 out << std::endl;
1661 k++;
1662 } //next i
1663
1664 return;
1665}
1666
1667}
bitpit::MaxPQueue
class for max priority queue.
Definition SortAlgorithms.hpp:243
bitpit::MaxPQueue::insert
void insert(T &)
Definition PQueue.tpp:1437
bitpit::MaxPQueue::modify
void modify(int, T &)
Definition PQueue.tpp:1559
bitpit::MaxPQueue::extract
void extract(T &)
Definition PQueue.tpp:1332
bitpit::MaxPQueue::clear
void clear(void)
Definition PQueue.tpp:1041
bitpit::MaxPQueue::display
void display(std::ostream &)
Definition PQueue.tpp:1621
bitpit::MaxPQueue::MaxPQueue
MaxPQueue(bool a=false, std::vector< std::array< int, 2 > > *b=NULL)
Definition PQueue.tpp:887
bitpit::MaxPQueue::buildHeap
void buildHeap(void)
Definition PQueue.tpp:1221
bitpit::MinPQueue
class for min priority queue.
Definition SortAlgorithms.hpp:163
bitpit::MinPQueue::display
void display(std::ostream &)
Definition PQueue.tpp:787
bitpit::MinPQueue::buildHeap
void buildHeap(void)
Definition PQueue.tpp:387
bitpit::MinPQueue::clear
void clear(void)
Definition PQueue.tpp:223
bitpit::MinPQueue::insert
void insert(T &)
Definition PQueue.tpp:587
bitpit::MinPQueue::modify
void modify(int, T &)
Definition PQueue.tpp:725
bitpit::MinPQueue::MinPQueue
MinPQueue(bool a=false, std::vector< std::array< int, 2 > > *b=NULL)
Definition PQueue.tpp:85
bitpit::MinPQueue::extract
void extract(T &)
Definition PQueue.tpp:482
pow
std::array< T, d > pow(std::array< T, d > &x, double p)
Definition MathOperators_array.tpp:637
--- layout: doxygen_footer ---
Generated on Wed Jun 19 2024 10:21:05 for bitpit by   doxygen 1.10.0