1#ifndef PRIORITY_QUEUE_H
2#define PRIORITY_QUEUE_H
3#include "LinkedList.h"
4struct PriorityQueue_struct {
5 /* a simple priority queue structure: entries are all integers, gains are all integers in [0, gainmax], total n elements */
6 int count;/* how many entries are in?*/
7
8 /* max index value of an entry */
9 int n;
10
11 /* only ngain buckets are allowed */
12 int ngain;
13
14 /* current highest gain */
15 int gain_max;
16
17 /* the ngain buckets. Each bucket i holds all entries with gain = i.*/
18 DoubleLinkedList *buckets;
19
20 /* a mapping which maps an entry's index to an element in a DoubleLinkedList */
21 DoubleLinkedList *where;
22
23 /* the gain of entry i is gain[i] */
24 int *gain;
25};
26
27typedef struct PriorityQueue_struct *PriorityQueue;
28
29
30PriorityQueue PriorityQueue_new(int n, int ngain);
31
32void PriorityQueue_delete(PriorityQueue q);
33
34/* if entry i is already in the list, then an update of gain is carried out*/
35PriorityQueue PriorityQueue_push(PriorityQueue q, int i, int gain);
36
37int PriorityQueue_pop(PriorityQueue q, int *i, int *gain);/* return 0 if nmothing left, 1 otherwise */
38
39int PriorityQueue_remove(PriorityQueue q, int i);/* return 0 if error */
40int PriorityQueue_get_gain(PriorityQueue q, int i);
41
42#endif
43