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
71
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
335 // Counters
336 // none
337
338 // ========================================================================== //
339 // RESTORE THE MIN HEAP PROPERTY //
340 // ========================================================================== //
341
342 // Index of childrens
343 L = 2*i + 1;
344 R = 2*(i + 1);
345
346 // Check children's key
347 if ((L < heap_size) && (keys[L] < keys[i])) {
348 idummy = L;
349 }
350 else {
351 idummy = i;
352 }
353 if ((R < heap_size) && (keys[R] < keys[idummy])) {
354 idummy = R;
355 }
356
357 // Move up-heap
358 if (idummy != i) {
359 T dummy = keys[i];
360 keys[i] = keys[idummy];
361 keys[idummy] = dummy;
362 if (use_labels) {
363 T1 dummy2 = labels[i];
364 labels[i] = labels[idummy];
365 labels[idummy] = std::move(dummy2);
366 }
367 if (map != NULL) {
368 imap = (*map)[i][0];
369 (*map)[i][0] = (*map)[idummy][0];
370 (*map)[idummy][0] = imap;
371 (*map)[(*map)[i][0]][1] = i;
372 (*map)[(*map)[idummy][0]][1] = idummy;
373 }
374 heapify(idummy);
375 }
376
377 return;
378};
379
380// -------------------------------------------------------------------------- //
384template <class T, class T1>
385void MinPQueue<T, T1>::buildHeap(
386 void
387 ) {
388
389 // ========================================================================== //
390 // VARIABLES DECLARATION //
391 // ========================================================================== //
392
393 // Local variables
394 // none
395
396 // Counters
397 int i;
398
399 // ========================================================================== //
400 // BUILD MIN HEAP //
401 // ========================================================================== //
402 for (i = (heap_size - 1)/2; i >= 0; i--) {
403 heapify(i);
404 } //next i
405
406 return;
407};
408
409// -------------------------------------------------------------------------- //
419template <class T, class T1>
420void MinPQueue<T, T1>::extract(
421 T &root,
422 T1 &root_label
423 ) {
424
425 // ========================================================================== //
426 // VARIABLES DECLARATION //
427 // ========================================================================== //
428
429 // Local variables
430 int imap;
431
432 // Counters
433 // none
434
435 // ========================================================================== //
436 // EXTRACT HEAP MIN ELEMENT //
437 // ========================================================================== //
438
439 // Extract min element
440 if (heap_size == 0) {
441 return;
442 }
443 root = keys[0];
444
445 // Update heap data structure
446 keys[0] = keys[heap_size-1];
447 if (use_labels) {
448 root_label = labels[0];
449 labels[0] = labels[heap_size-1];
450 }
451 if (map != NULL) {
452 imap = (*map)[0][0];
453 (*map)[0][0] = (*map)[heap_size-1][0];
454 (*map)[heap_size-1][0] = imap;
455 (*map)[imap][1] = heap_size-1;
456 (*map)[(*map)[0][0]][1] = 0;
457 }
458
459 // Reduce stack dimensions
460 heap_size--;
461 if (heap_size <= (long) keys.size() - MAXSTK) {
462 decreaseSTACK();
463 }
464
465 // Restore min-heap condition
466 heapify(0);
467
468 return;
469};
470
471// -------------------------------------------------------------------------- //
479template <class T, class T1>
480void MinPQueue<T, T1>::extract(
481 T &root
482 ) {
483
484 // ========================================================================== //
485 // VARIABLES DECLARATION //
486 // ========================================================================== //
487
488 // Local variables
489 int imap;
490
491 // Counters
492 // none
493
494 // ========================================================================== //
495 // EXTRACT HEAP MIN ELEMENT //
496 // ========================================================================== //
497
498 // Extract min element
499 if (heap_size == 0) {
500 return;
501 }
502 root = keys[0];
503
504 // Update heap data structure
505 keys[0] = keys[heap_size-1];
506 if (map != NULL) {
507 imap = (*map)[0][0];
508 (*map)[0][0] = (*map)[heap_size-1][0];
509 (*map)[heap_size-1][0] = imap;
510 (*map)[imap][1] = heap_size-1;
511 (*map)[(*map)[0][0]][1] = 0;
512 }
513
514 // Reduce stack dimensions
515 heap_size--;
516 if (heap_size <= keys.size() - MAXSTK) {
517 decreaseSTACK();
518 }
519
520 // Restore min-heap condition
521 heapify(0);
522
523 return;
524};
525
526// -------------------------------------------------------------------------- //
535template <class T, class T1>
536void MinPQueue<T, T1>::insert(
537 T &key_new,
538 T1 &label_new
539 ) {
540
541 // ========================================================================== //
542 // VARIABLES DECLARATION //
543 // ========================================================================== //
544
545 // Local variables
546 // none
547
548 // Counters
549 // none
550
551 // ========================================================================== //
552 // INSERT A NEW KEY //
553 // ========================================================================== //
554
555 // Insert key
556 if (heap_size+1 > (long) keys.size()) {
557 increaseSTACK();
558 }
559
560 // Add new key
561 keys[heap_size] = key_new;
562
563 // Update labels
564 if (use_labels) {
565 labels[heap_size] = label_new;
566 }
567
568 // Update heap size
569 heap_size++;
570
571 // Restore max heap condition
572 modify(heap_size-1, key_new, label_new);
573
574 return;
575};
576
577// -------------------------------------------------------------------------- //
584template <class T, class T1>
585void MinPQueue<T, T1>::insert(
586 T &key_new
587 ) {
588
589 // ========================================================================== //
590 // template <class T, class T1> //
591 // void MinPQueue<T, T1>::insert( //
592 // T &key_new) //
593 // //
594 // Insert new key into a min heap //
595 // ========================================================================== //
596 // INPUT //
597 // ========================================================================== //
598 // - key_new : T1, key to be inserted //
599 // ========================================================================== //
600 // OUTPUT //
601 // ========================================================================== //
602 // - none //
603 // ========================================================================== //
604
605 // ========================================================================== //
606 // VARIABLES DECLARATION //
607 // ========================================================================== //
608
609 // Local variables
610 // none
611
612 // Counters
613 // none
614
615 // ========================================================================== //
616 // INSERT A NEW KEY //
617 // ========================================================================== //
618
619 // Insert key
620 if (heap_size+1 > keys.size()) {
621 increaseSTACK();
622 }
623
624 // Add new key
625 keys[heap_size] = key_new;
626
627 // Update heap size
628 heap_size++;
629
630 // Restore max heap condition
631 modify(heap_size-1, key_new);
632
633 return;
634};
635
636// -------------------------------------------------------------------------- //
646template <class T, class T1>
647void MinPQueue<T, T1>::modify(
648 int i,
649 T &key_new,
650 T1 &label_new
651 ) {
652
653 // ========================================================================== //
654 // VARIABLES DECLARATION //
655 // ========================================================================== //
656
657 // Local variables
658 int imap;
659 T dummy1;
660 T1 dummy2;
661
662 // Counters
663 int j;
664
665 // ========================================================================== //
666 // INCREASE VALUE OF LAST KEY. //
667 // ========================================================================== //
668 if (key_new > keys[i]) {
669
670 // Update keys
671 keys[i] = key_new;
672 if (use_labels) {
673 labels[i] = label_new;
674 }
675
676 // move down-heap
677 heapify(i);
678
679 }
680 else {
681
682 // Update keys
683 keys[i] = key_new;
684 if (use_labels) {
685 labels[i] = label_new;
686 }
687
688 // move up-heap
689 j = (i + 1)/2 - 1;
690 while ((i > 0) && (keys[j] > keys[i])) {
691 dummy1 = keys[i];
692 keys[i] = keys[j];
693 keys[j] = dummy1;
694 if (use_labels) {
695 dummy2 = labels[i];
696 labels[i] = labels[j];
697 labels[j] = dummy2;
698 }
699 if (map != NULL) {
700 imap = (*map)[i][0];
701 (*map)[i][0] = (*map)[j][0];
702 (*map)[j][0] = imap;
703 (*map)[(*map)[i][0]][1] = i;
704 (*map)[(*map)[j][0]][1] = j;
705 }
706 i = j;
707 j = (i + 1)/2 - 1;
708 } //next parent
709 }
710
711 return;
712};
713
714// -------------------------------------------------------------------------- //
722template <class T, class T1>
723void MinPQueue<T, T1>::modify(
724 int i,
725 T &key_new
726 ) {
727
728 // ========================================================================== //
729 // VARIABLES DECLARATION //
730 // ========================================================================== //
731
732 // Local variables
733 int imap;
734 T dummy1;
735
736 // Counters
737 int j;
738
739 // ========================================================================== //
740 // INCREASE VALUE OF SELECTED KEY. //
741 // ========================================================================== //
742 if (key_new > keys[i]) {
743
744 // Update keys
745 keys[i] = key_new;
746
747 // move down-heap
748 heapify(i);
749
750 }
751 else {
752
753 // Update keys
754 keys[i] = key_new;
755
756 // move up-heap
757 j = (i + 1)/2 - 1;
758 while ((i > 0) && (keys[j] > keys[i])) {
759 dummy1 = keys[i];
760 keys[i] = keys[j];
761 keys[j] = dummy1;
762 if (map != NULL) {
763 imap = (*map)[i][0];
764 (*map)[i][0] = (*map)[j][0];
765 (*map)[j][0] = imap;
766 (*map)[(*map)[i][0]][1] = i;
767 (*map)[(*map)[j][0]][1] = j;
768 }
769 i = j;
770 j = (i + 1)/2 - 1;
771 } //next parent
772 }
773
774 return;
775};
776
777// -------------------------------------------------------------------------- //
784template <class T, class T1>
785void MinPQueue<T, T1>::display(
786 std::ostream &out
787 ) {
788
789 // ========================================================================== //
790 // VARIABLES DECLARATION //
791 // ========================================================================== //
792
793 // Local variables
794 // none
795
796 // Counters
797 int i, j, k;
798
799 // ========================================================================== //
800 // DISPLAY MIN-HEAP INFO //
801 // ========================================================================== //
802
803 // General info ------------------------------------------------------------- //
804 out << "min heap:" << std::endl;
805 out << "heap size: " << heap_size << std::endl;
806 out << "data struct. size: " << keys.size() << std::endl;
807 out << "max stack size: " << MAXSTK << std::endl;
808
809 // heap content ------------------------------------------------------------- //
810 out << "min heap data:" << std::endl;
811 i = 0;
812 k = 0;
813 while (i < heap_size) {
814 j = 0;
815 while ((j < pow(2, k)) && (i < heap_size)) {
816 out << "[" << keys[i];
817 if (use_labels) {
818 out << ", '" << labels[i] << "'";
819 }
820 out << "] ";
821 i++;
822 j++;
823 } //next j
824 out << std::endl;
825 k++;
826 } //next i
827
828 return;
829}
830
834
839
840// ========================================================================== //
841// TEMPLATE IMPLEMENTATIONS FOR MaxPQueue //
842// ========================================================================== //
843
871
872// Constructors ============================================================= //
873
874// -------------------------------------------------------------------------- //
884template <class T, class T1>
885MaxPQueue<T, T1>::MaxPQueue(
886 bool flag_label,
887 std::vector< std::array<int,2> >*map_
888 ) {
889
890 // ========================================================================== //
891 // VARIABLES DECLARATION //
892 // ========================================================================== //
893
894 // Local variables
895 // none
896
897 // Counters
898 // none
899
900 // ========================================================================== //
901 // CREATE LIFO STACK //
902 // ========================================================================== //
903
904 // Max stack dimensions
905 MAXSTK = 10;
906
907 // Currenst stack size
908 heap_size = 0;
909
910 // Set flag
911 use_labels = flag_label;
912
913 // Pointers
914 map = map_;
915
916 // Initialize stack
917 increaseSTACK();
918
919 return;
920};
921
922// -------------------------------------------------------------------------- //
934template <class T, class T1>
935MaxPQueue<T, T1>::MaxPQueue(
936 int maxstack,
937 bool flag_label,
938 std::vector< std::array<int,2> >*map_
939 ) {
940
941 // ========================================================================== //
942 // VARIABLES DECLARATION //
943 // ========================================================================== //
944
945 // Local variables
946 // none
947
948 // Counters
949 // none
950
951 // ========================================================================== //
952 // CREATE LIFO STACK //
953 // ========================================================================== //
954
955 // Max stack dimensions
956 MAXSTK = maxstack;
957
958 // Currenst stack size
959 heap_size = 0;
960
961 // Flags
962 use_labels = flag_label;
963
964 // Pointers
965 map = map_;
966
967 // Initialize stack
968 increaseSTACK();
969
970 return;
971};
972
973// Destructors ============================================================== //
974
975// -------------------------------------------------------------------------- //
980template <class T, class T1>
981MaxPQueue<T, T1>::~MaxPQueue(
982 void
983 ) {
984
985 // ========================================================================== //
986 // template <class T, class T1> //
987 // MaxPQueue<T, T1>::~MaxPQueue( //
988 // void) //
989 // //
990 // Standard destructor for max heap. //
991 // ========================================================================== //
992 // INPUT //
993 // ========================================================================== //
994 // - none //
995 // ========================================================================== //
996 // OUTPUT //
997 // ========================================================================== //
998 // - none //
999 // ========================================================================== //
1000
1001 // ========================================================================== //
1002 // VARIABLES DECLARATION //
1003 // ========================================================================== //
1004
1005 // Local variables
1006 // none
1007
1008 // Counters
1009 // none
1010
1011 // ========================================================================== //
1012 // DESTROY LIFO STACK //
1013 // ========================================================================== //
1014
1015 // Maximal stack size
1016 MAXSTK = 0;
1017
1018 // Current stack dimensions
1019 heap_size = 0;
1020
1021 // Destroy items
1022 keys.clear();
1023 if (use_labels) { labels.clear(); }
1024 map = NULL;
1025
1026 // Flags
1027 use_labels = false;
1028
1029 return;
1030};
1031
1032// Methods ================================================================== //
1033
1034// -------------------------------------------------------------------------- //
1038template <class T, class T1>
1039void MaxPQueue<T, T1>::clear(
1040 void
1041 ) {
1042
1043 // ========================================================================== //
1044 // VARIABLES DECLARATION //
1045 // ========================================================================== //
1046
1047 // Local variables
1048 // none
1049
1050 // Counters
1051 // none
1052
1053 // ========================================================================== //
1054 // CLEAR CONTENT //
1055 // ========================================================================== //
1056 heap_size = 0;
1057 keys.resize(MAXSTK);
1058 if (use_labels) { labels.resize(MAXSTK); }
1059
1060 return;
1061}
1062
1063// -------------------------------------------------------------------------- //
1068template <class T, class T1>
1069void MaxPQueue<T, T1>::increaseSTACK(
1070 void
1071 ) {
1072
1073 // ========================================================================== //
1074 // VARIABLES DECLARATION //
1075 // ========================================================================== //
1076
1077 // Local variables
1078 // none
1079
1080 // Counters
1081 // none
1082
1083 // ========================================================================== //
1084 // INCREASE STACK SIZE //
1085 // ========================================================================== //
1086
1087 // stack
1088 keys.resize(heap_size + MAXSTK);
1089
1090 // labels
1091 if (use_labels) {
1092 labels.resize(heap_size + MAXSTK);
1093 }
1094
1095 return;
1096};
1097
1098// -------------------------------------------------------------------------- //
1103template <class T, class T1>
1104void MaxPQueue<T, T1>::decreaseSTACK(
1105 void
1106 ) {
1107
1108 // ========================================================================== //
1109 // template <class T, class T1> //
1110 // void MaxPQueue<T, T1>::decreaseSTACK( //
1111 // void) //
1112 // //
1113 // Decrease stack size. //
1114 // ========================================================================== //
1115 // INPUT //
1116 // ========================================================================== //
1117 // - none //
1118 // ========================================================================== //
1119 // OUTPUT //
1120 // ========================================================================== //
1121 // - none //
1122 // ========================================================================== //
1123
1124 // ========================================================================== //
1125 // VARIABLES DECLARATION //
1126 // ========================================================================== //
1127
1128 // Local variables
1129 int n = keys.size();
1130
1131 // Counters
1132 // none
1133
1134 // ========================================================================== //
1135 // DECREASE STACK SIZE //
1136 // ========================================================================== //
1137
1138 // Stack
1139 keys.resize(std::max(n - MAXSTK, MAXSTK));
1140
1141 // labels
1142 if (use_labels) {
1143 labels.resize(std::max(n - MAXSTK, MAXSTK));
1144 }
1145
1146 return;
1147};
1148
1149// -------------------------------------------------------------------------- //
1155template <class T, class T1 >
1156void MaxPQueue<T, T1>::heapify(
1157 int i
1158 ) {
1159
1160 // ========================================================================== //
1161 // VARIABLES DECLARATION //
1162 // ========================================================================== //
1163
1164 // Local variables
1165 int L, R, idummy, imap;
1166 T dummy;
1167 T1 dummy2;
1168
1169 // Counters
1170 // none
1171
1172 // ========================================================================== //
1173 // RESTORE THE MIN HEAP PROPERTY //
1174 // ========================================================================== //
1175
1176 // Index of childrens
1177 L = 2*i + 1;
1178 R = 2*(i + 1);
1179
1180 // Check children's key
1181 if ((L < heap_size) && (keys[L] > keys[i])) {
1182 idummy = L;
1183 }
1184 else {
1185 idummy = i;
1186 }
1187 if ((R < heap_size) && (keys[R] > keys[idummy])) {
1188 idummy = R;
1189 }
1190
1191 // Move up-heap
1192 if (idummy != i) {
1193 dummy = keys[i];
1194 keys[i] = keys[idummy];
1195 keys[idummy] = dummy;
1196 if (use_labels) {
1197 dummy2 = labels[i];
1198 labels[i] = labels[idummy];
1199 labels[idummy] = dummy2;
1200 }
1201 if (map != NULL) {
1202 imap = (*map)[i][0];
1203 (*map)[i][0] = (*map)[idummy][0];
1204 (*map)[idummy][0] = imap;
1205 (*map)[(*map)[i][0]][1] = i;
1206 (*map)[(*map)[idummy][0]][1] = idummy;
1207 }
1208 heapify(idummy);
1209 }
1210
1211 return;
1212};
1213
1214// -------------------------------------------------------------------------- //
1218template <class T, class T1>
1219void MaxPQueue<T, T1>::buildHeap(
1220 void
1221 ) {
1222
1223 // ========================================================================== //
1224 // template <class T, class T1> //
1225 // void MaxPQueue<T, T1>::buildHeap( //
1226 // void) //
1227 // //
1228 // Build max heap tree. //
1229 // ========================================================================== //
1230 // INPUT //
1231 // ========================================================================== //
1232 // - none //
1233 // ========================================================================== //
1234 // OUTPUT //
1235 // ========================================================================== //
1236 // - none //
1237 // ========================================================================== //
1238
1239 // ========================================================================== //
1240 // VARIABLES DECLARATION //
1241 // ========================================================================== //
1242
1243 // Local variables
1244 // none
1245
1246 // Counters
1247 int i;
1248
1249 // ========================================================================== //
1250 // BUILD MAX HEAP //
1251 // ========================================================================== //
1252 for (i = (heap_size - 1)/2; i >= 0; i--) {
1253 heapify(i);
1254 } //next i
1255
1256 return;
1257};
1258
1259// -------------------------------------------------------------------------- //
1269template <class T, class T1>
1270void MaxPQueue<T, T1>::extract(
1271 T &root,
1272 T1 &root_label
1273 ) {
1274
1275 // ========================================================================== //
1276 // VARIABLES DECLARATION //
1277 // ========================================================================== //
1278
1279 // Local variables
1280 int imap;
1281
1282 // Counters
1283 // none
1284
1285 // ========================================================================== //
1286 // EXTRACT HEAP MAX ELEMENT //
1287 // ========================================================================== //
1288
1289 // Extract max element
1290 if (heap_size == 0) {
1291 return;
1292 }
1293 root = keys[0];
1294
1295 // Update heap data structure
1296 keys[0] = keys[heap_size-1];
1297 if (use_labels) {
1298 root_label = labels[0];
1299 labels[0] = labels[heap_size-1];
1300 }
1301 if (map != NULL) {
1302 imap = (*map)[0][0];
1303 (*map)[0][0] = (*map)[heap_size-1][0];
1304 (*map)[heap_size-1][0] = imap;
1305 (*map)[imap][1] = heap_size-1;
1306 (*map)[(*map)[0][0]][1] = 0;
1307 }
1308
1309 // Reduce stack dimensions
1310 heap_size--;
1311 if (heap_size <= (long) keys.size() - MAXSTK) {
1312 decreaseSTACK();
1313 }
1314
1315 // Restore max-heap condition
1316 heapify(0);
1317
1318 return;
1319};
1320
1321// -------------------------------------------------------------------------- //
1329template <class T, class T1>
1330void MaxPQueue<T, T1>::extract(
1331 T &root
1332 ) {
1333
1334 // ========================================================================== //
1335 // VARIABLES DECLARATION //
1336 // ========================================================================== //
1337
1338 // Local variables
1339 int imap;
1340
1341 // Counters
1342 // none
1343
1344 // ========================================================================== //
1345 // EXTRACT HEAP MAX ELEMENT //
1346 // ========================================================================== //
1347
1348 // Extract max element
1349 if (heap_size == 0) {
1350 return;
1351 }
1352 root = keys[0];
1353
1354 // Update heap data structure
1355 keys[0] = keys[heap_size-1];
1356 if (map != NULL) {
1357 imap = (*map)[0][0];
1358 (*map)[0][0] = (*map)[heap_size-1][0];
1359 (*map)[heap_size-1][0] = imap;
1360 (*map)[imap][1] = heap_size-1;
1361 (*map)[(*map)[0][0]][1] = 0;
1362 }
1363
1364 // Reduce stack dimensions
1365 heap_size--;
1366 if (heap_size <= keys.size() - MAXSTK) {
1367 decreaseSTACK();
1368 }
1369
1370 // Restore max-heap condition
1371 heapify(0);
1372
1373 return;
1374};
1375
1376// -------------------------------------------------------------------------- //
1385template <class T, class T1>
1386void MaxPQueue<T, T1>::insert(
1387 T &key_new,
1388 T1 &label_new
1389 ) {
1390
1391 // ========================================================================== //
1392 // VARIABLES DECLARATION //
1393 // ========================================================================== //
1394
1395 // Local variables
1396 // none
1397
1398 // Counters
1399 // none
1400
1401 // ========================================================================== //
1402 // INSERT A NEW KEY //
1403 // ========================================================================== //
1404
1405 // Insert key
1406 if (heap_size+1 > (long) keys.size()) {
1407 increaseSTACK();
1408 }
1409
1410 // Add new key
1411 keys[heap_size] = key_new;
1412
1413 // Update labels
1414 if (use_labels) {
1415 labels[heap_size] = label_new;
1416 }
1417
1418 // Update heap size
1419 heap_size++;
1420
1421 // Restore max heap condition
1422 modify(heap_size-1, key_new, label_new);
1423
1424 return;
1425};
1426
1427// -------------------------------------------------------------------------- //
1434template <class T, class T1>
1435void MaxPQueue<T, T1>::insert(
1436 T &key_new
1437 ) {
1438
1439 // ========================================================================== //
1440 // VARIABLES DECLARATION //
1441 // ========================================================================== //
1442
1443 // Local variables
1444 // none
1445
1446 // Counters
1447 // none
1448
1449 // ========================================================================== //
1450 // INSERT A NEW KEY //
1451 // ========================================================================== //
1452
1453 // Insert key
1454 if (heap_size+1 > keys.size()) {
1455 increaseSTACK();
1456 }
1457
1458 // Add new key
1459 keys[heap_size] = key_new;
1460
1461 // Update heap size
1462 heap_size++;
1463
1464 // Restore max heap condition
1465 modify(heap_size-1, key_new);
1466
1467 return;
1468};
1469
1470// -------------------------------------------------------------------------- //
1480template <class T, class T1>
1481void MaxPQueue<T, T1>::modify(
1482 int i,
1483 T &key_new,
1484 T1 &label_new
1485 ) {
1486
1487 // ========================================================================== //
1488 // VARIABLES DECLARATION //
1489 // ========================================================================== //
1490
1491 // Local variables
1492 int imap;
1493 T dummy1;
1494 T1 dummy2;
1495
1496 // Counters
1497 int j;
1498
1499 // ========================================================================== //
1500 // INCREASE VALUE OF LAST KEY. //
1501 // ========================================================================== //
1502 if (key_new < keys[i]) {
1503
1504 // Update keys
1505 keys[i] = key_new;
1506 if (use_labels) {
1507 labels[i] = label_new;
1508 }
1509
1510 // move down-heap
1511 heapify(i);
1512
1513 }
1514 else {
1515
1516 // Update keys
1517 keys[i] = key_new;
1518 if (use_labels) {
1519 labels[i] = label_new;
1520 }
1521
1522 // move up-heap
1523 j = (i + 1)/2 - 1;
1524 while ((i > 0) && (keys[j] < keys[i])) {
1525 dummy1 = keys[i];
1526 keys[i] = keys[j];
1527 keys[j] = dummy1;
1528 if (use_labels) {
1529 dummy2 = labels[i];
1530 labels[i] = labels[j];
1531 labels[j] = dummy2;
1532 }
1533 if (map != NULL) {
1534 imap = (*map)[i][0];
1535 (*map)[i][0] = (*map)[j][0];
1536 (*map)[j][0] = imap;
1537 (*map)[(*map)[i][0]][1] = i;
1538 (*map)[(*map)[j][0]][1] = j;
1539 }
1540 i = j;
1541 j = (i + 1)/2 - 1;
1542 } //next parent
1543 }
1544
1545 return;
1546};
1547
1548// -------------------------------------------------------------------------- //
1556template <class T, class T1>
1557void MaxPQueue<T, T1>::modify(
1558 int i,
1559 T &key_new
1560 ) {
1561
1562 // ========================================================================== //
1563 // VARIABLES DECLARATION //
1564 // ========================================================================== //
1565
1566 // Local variables
1567 int imap;
1568 T dummy1;
1569
1570 // Counters
1571 int j;
1572
1573 // ========================================================================== //
1574 // INCREASE VALUE OF SELECTED KEY. //
1575 // ========================================================================== //
1576 if (key_new < keys[i]) {
1577
1578 // Update keys
1579 keys[i] = key_new;
1580
1581 // move down-heap
1582 heapify(i);
1583
1584 }
1585 else {
1586
1587 // Update keys
1588 keys[i] = key_new;
1589
1590 // move up-heap
1591 j = (i + 1)/2 - 1;
1592 while ((i > 0) && (keys[j] < keys[i])) {
1593 dummy1 = keys[i];
1594 keys[i] = keys[j];
1595 keys[j] = dummy1;
1596 if (map != NULL) {
1597 imap = (*map)[i][0];
1598 (*map)[i][0] = (*map)[j][0];
1599 (*map)[j][0] = imap;
1600 (*map)[(*map)[i][0]][1] = i;
1601 (*map)[(*map)[j][0]][1] = j;
1602 }
1603 i = j;
1604 j = (i + 1)/2 - 1;
1605 } //next parent
1606 }
1607
1608 return;
1609};
1610
1611// -------------------------------------------------------------------------- //
1618template <class T, class T1>
1619void MaxPQueue<T, T1>::display(
1620 std::ostream &out
1621 ) {
1622
1623 // ========================================================================== //
1624 // VARIABLES DECLARATION //
1625 // ========================================================================== //
1626
1627 // Local variables
1628 // none
1629
1630 // Counters
1631 int i, j, k;
1632
1633 // ========================================================================== //
1634 // DISPLAY MAX-HEAP INFO //
1635 // ========================================================================== //
1636
1637 // General info ------------------------------------------------------------- //
1638 out << "max heap:" << std::endl;
1639 out << "heap size: " << heap_size << std::endl;
1640 out << "data struct. size: " << keys.size() << std::endl;
1641 out << "max stack size: " << MAXSTK << std::endl;
1642
1643 // heap content ------------------------------------------------------------- //
1644 out << "max heap data:" << std::endl;
1645 i = 0;
1646 k = 0;
1647 while (i < heap_size) {
1648 j = 0;
1649 while ((j < pow(2, k)) && (i < heap_size)) {
1650 out << "[" << keys[i];
1651 if (use_labels) {
1652 out << ", '" << labels[i] << "'";
1653 }
1654 out << "] ";
1655 i++;
1656 j++;
1657 } //next j
1658 out << std::endl;
1659 k++;
1660 } //next i
1661
1662 return;
1663}
1664
1665}
bitpit::MaxPQueue::insert
void insert(T &)
Definition PQueue.tpp:1435
bitpit::MaxPQueue::modify
void modify(int, T &)
Definition PQueue.tpp:1557
bitpit::MaxPQueue::extract
void extract(T &)
Definition PQueue.tpp:1330
bitpit::MaxPQueue::clear
void clear(void)
Definition PQueue.tpp:1039
bitpit::MaxPQueue::map
std::vector< std::array< int, 2 > > * map
Definition SortAlgorithms.hpp:251
bitpit::MaxPQueue::labels
std::vector< T1 > labels
Definition SortAlgorithms.hpp:250
bitpit::MaxPQueue::display
void display(std::ostream &)
Definition PQueue.tpp:1619
bitpit::MaxPQueue::MaxPQueue
MaxPQueue(bool a=false, std::vector< std::array< int, 2 > > *b=NULL)
Definition PQueue.tpp:885
bitpit::MaxPQueue::buildHeap
void buildHeap(void)
Definition PQueue.tpp:1219
bitpit::MaxPQueue::keys
std::vector< T > keys
Definition SortAlgorithms.hpp:249
bitpit::MinPQueue::display
void display(std::ostream &)
Definition PQueue.tpp:785
bitpit::MinPQueue::buildHeap
void buildHeap(void)
Definition PQueue.tpp:385
bitpit::MinPQueue::clear
void clear(void)
Definition PQueue.tpp:223
bitpit::MinPQueue::insert
void insert(T &)
Definition PQueue.tpp:585
bitpit::MinPQueue::keys
std::vector< T > keys
Definition SortAlgorithms.hpp:169
bitpit::MinPQueue::map
std::vector< std::array< int, 2 > > * map
Definition SortAlgorithms.hpp:171
bitpit::MinPQueue::modify
void modify(int, T &)
Definition PQueue.tpp:723
bitpit::MinPQueue::labels
std::vector< T1 > labels
Definition SortAlgorithms.hpp:170
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:480
pow
std::array< T, d > pow(std::array< T, d > &x, double p)
Definition MathOperators_array.tpp:637
Generated on Mon Apr 28 2025 20:53:28 for bitpit by   doxygen 1.13.2