Graphviz  2.41.20170921.2350
PriorityQueue.h
Go to the documentation of this file.
1 #ifndef PRIORITY_QUEUE_H
2 #define PRIORITY_QUEUE_H
3 #include "LinkedList.h"
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.*/
19 
20  /* a mapping which maps an entry's index to an element in a DoubleLinkedList */
22 
23  /* the gain of entry i is gain[i] */
24  int *gain;
25 };
26 
28 
29 
30 PriorityQueue PriorityQueue_new(int n, int ngain);
31 
32 void PriorityQueue_delete(PriorityQueue q);
33 
34 /* if entry i is already in the list, then an update of gain is carried out*/
35 PriorityQueue PriorityQueue_push(PriorityQueue q, int i, int gain);
36 
37 int PriorityQueue_pop(PriorityQueue q, int *i, int *gain);/* return 0 if nmothing left, 1 otherwise */
38 
39 int PriorityQueue_remove(PriorityQueue q, int i);/* return 0 if error */
40 int PriorityQueue_get_gain(PriorityQueue q, int i);
41 
42 #endif
PriorityQueue PriorityQueue_push(PriorityQueue q, int i, int gain)
Definition: PriorityQueue.c:65
int PriorityQueue_remove(PriorityQueue q, int i)
DoubleLinkedList * buckets
Definition: PriorityQueue.h:18
DoubleLinkedList * where
Definition: PriorityQueue.h:21
PriorityQueue PriorityQueue_new(int n, int ngain)
Definition: PriorityQueue.c:27
int PriorityQueue_pop(PriorityQueue q, int *i, int *gain)
void PriorityQueue_delete(PriorityQueue q)
Definition: PriorityQueue.c:47
int PriorityQueue_get_gain(PriorityQueue q, int i)
struct PriorityQueue_struct * PriorityQueue
Definition: PriorityQueue.h:27