File size: 5,662 Bytes
0a95064 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | /*
* Max-Planck-Gesellschaft zur Förderung der Wissenschaften e.V. (MPG) is
* holder of all proprietary rights on this computer program.
* You can only use this computer program if you have closed
* a license agreement with MPG or you get the right to use the computer
* program from someone who is authorized to grant you that right.
* Any use of the computer program without a valid license is prohibited and
* liable to prosecution.
*
* Copyright©2019 Max-Planck-Gesellschaft zur Förderung
* der Wissenschaften e.V. (MPG). acting on behalf of its Max Planck Institute
* for Intelligent Systems. All rights reserved.
*
* @author Vasileios Choutas
* Contact: vassilis.choutas@tuebingen.mpg.de
* Contact: ps-license@tuebingen.mpg.de
*
*/
#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H
#include <float.h>
#include <stdio.h>
#include <utility>
#include <cuda.h>
#include "device_launch_parameters.h"
#include <cuda_runtime.h>
template<typename T>
__host__ __device__
void swap_array_els(T* array, int i, int j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
template <typename T, typename Obj, int QueueSize = 128, bool recursive = false>
class PriorityQueue {
public:
__host__ __device__
PriorityQueue() : heap_size(0) {}
inline
__host__ __device__
int get_size() {
return heap_size;
}
inline
__host__ __device__
int parent(int i) {
return (i - 1) / 2;
}
inline
__host__ __device__
int left_child(int i) {
return 2 * i + 1;
}
inline
__host__ __device__
int right_child(int i) {
return 2 * i + 2;
}
__host__ __device__
std::pair<T, Obj> get_min() {
if (heap_size > 0) {
return std::pair<T, Obj>(priority_heap[0], obj_heap[0]);
}
else {
return std::pair<T, Obj>(
std::is_same<T, float>::value ? FLT_MAX : DBL_MAX, nullptr);
}
}
__host__ __device__
void min_heapify(int index) {
if (recursive) {
int left = left_child(index);
int right = right_child(index);
int smallest = index;
if (left < heap_size && priority_heap[left] < priority_heap[index])
smallest = left;
if (right < heap_size && priority_heap[right] < priority_heap[index])
smallest = right;
if (smallest != index) {
swap_array_els(priority_heap, index, smallest);
swap_array_els(obj_heap, index, smallest);
min_heapify(smallest);
}
} else {
int ii = index;
int smallest;
while (true) {
int left = left_child(ii);
int right = right_child(ii);
smallest = ii;
if (left < heap_size && priority_heap[left] < priority_heap[ii])
smallest = left;
if (right < heap_size && priority_heap[right] < priority_heap[ii])
smallest = right;
if (smallest != ii) {
swap_array_els(priority_heap, ii, smallest);
swap_array_els(obj_heap, ii, smallest);
ii = smallest;
}
else
break;
}
}
}
__host__ __device__
void insert_key(T key, Obj obj) {
if (heap_size == QueueSize) {
printf("The queue has exceed its maximum size\n");
return;
}
heap_size++;
int ii = heap_size - 1;
priority_heap[ii] = key;
obj_heap[ii] = obj;
// Fix the min heap property if it is violated
min_heapify(0);
// while (ii != 0 && priority_heap[parent(ii)] > priority_heap[ii]) {
// swap_array_els(priority_heap, ii, parent(ii));
// swap_array_els(obj_heap, ii, parent(ii));
// ii = parent(ii);
// }
}
// void print() {
// for (int i = 0; i < heap_size; i++) {
// std::cout << i << ": " << heap[i] << std::endl;
// }
// }
__host__ __device__
std::pair<T, Obj> extract() {
if (heap_size <= 0)
return std::pair<T, Obj>(
std::is_same<T, float>::value ? FLT_MAX : DBL_MAX, nullptr);
T root_prio = priority_heap[0];
Obj root_obj = obj_heap[0];
// Replace the root with the last element
priority_heap[0] = priority_heap[heap_size - 1];
obj_heap[0] = obj_heap[heap_size - 1];
// Decrease the size of the heap
heap_size--;
min_heapify(0);
return std::pair<T, Obj>(root_prio, root_obj);
}
private:
T priority_heap[QueueSize];
Obj obj_heap[QueueSize];
int heap_size;
};
#endif // #ifndef PRIORITY_QUEUE_H
|