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
|
#ifndef _PASSENGER_PRIORITY_QUEUE_H_
#define _PASSENGER_PRIORITY_QUEUE_H_
#include "fib.h"
namespace Passenger {
template<typename T>
class PriorityQueue {
private:
struct fibheap heap;
public:
typedef struct fibheap_el * Handle;
PriorityQueue() {
fh_initheap(&heap);
heap.fh_keys = 1;
}
~PriorityQueue() {
fh_destroyheap(&heap);
}
Handle push(T *item, int priority) {
return fh_insertkey(&heap, priority, item);
}
T *pop() {
return (T *) fh_extractmin(&heap);
}
T *top() const {
return (T *) fh_min(const_cast<struct fibheap *>(&heap));
}
void decrease(Handle handle, int priority) {
fh_replacekeydata(&heap, handle, priority, handle->fhe_data);
}
void erase(Handle handle) {
fh_delete(&heap, handle);
}
void clear() {
fh_destroyheap(&heap);
fh_initheap(&heap);
heap.fh_keys = 1;
}
};
} // namespace Passenger
#endif /* _PASSENGER_PRIORITY_QUEUE_H_ */
|
