1 #ifndef PRIORITY_QUEUE
2 #define PRIORITY_QUEUE
3
4 #include "fibo.h"
5
6 /*
7 This is the struct for our elements in a PriorityQueue.
8 The node is at first place so we only have to use a cast to switch between QueueElement's pointer and Fibonode's pointer.
9 */
10 typedef struct QueueElement_
11 {
12 FiboNode node; /*the node used to insert the element in a FiboTree*/
13 double key; /*the key of the element, elements are sorted in a descending order according to their key*/
14 int value;
15 int isInQueue;
16 } QueueElement;
17
18 typedef struct PriorityQueue_
19 {
20 FiboTree tree;
21 QueueElement ** elements; /*a vector of element with their value as key so we can easily retreive an element from its value */
22 int size; /*the size allocated to the elements vector*/
23 } PriorityQueue;
24
25
26 /*
27 PQ_init initiates a PriorityQueue with a size given in argument and sets compFunc as comparison function. Note that you have to allocate memory to the PriorityQueue pointer before calling this function.
28 Returns :
29 0 if success
30 !0 if failed
31
32 PQ_free simply empties the PriorityQueue but does not free the memory used by its elements.
33 PQ_exit destroys the PriorityQueue without freeing elements. The PriorityQueue is no longer usable without using PQ_init again.
34 Note that the PriorityQueue pointer is not deallocated.
35 */
36 int PQ_init(PriorityQueue * const, int size);
37 void PQ_free(PriorityQueue * const);
38 void PQ_exit(PriorityQueue * const);
39
40 /*
41 PQ_isEmpty returns 1 if the PriorityQueue is empty, 0 otherwise.
42 */
43 int PQ_isEmpty(PriorityQueue * const);
44
45 /*
46 PQ_insertElement inserts the given QueueElement in the given PriorityQueue
47 */
48 void PQ_insertElement(PriorityQueue * const, QueueElement * const);
49 /*
50 PQ_deleteElement delete the element given in argument from the PriorityQueue.
51 */
52 void PQ_deleteElement(PriorityQueue * const, QueueElement * const);
53
54 /*
55 PQ_insert inserts an element in the PriorityQueue with the value and key given in argument.
56 */
57 void PQ_insert(PriorityQueue * const, int val, double key);
58 /*
59 PQ_delete removes the first element found with the value given in argument and frees it.
60 */
61 void PQ_delete(PriorityQueue * const, int val);
62
63
64 /*
65 PQ_findMaxElement returns the QueueElement with the greatest key in the given PriorityQueue
66 */
67 QueueElement * PQ_findMaxElement(PriorityQueue * const);
68 /*
69 PQ_deleteMaxElement returns the QueueElement with the geatest key in the given PriorityQueue and removes it from the queue.
70 */
71 QueueElement * PQ_deleteMaxElement(PriorityQueue * const);
72
73 /*
74 PQ_findMax returns the key of the element with the geatest key in the given PriorityQueue
75 */
76 double PQ_findMaxKey(PriorityQueue * const);
77 /*
78 PQ_deleteMax returns the value of the element with the greatest key in the given PriorityQueue and removes it from the queue.
79 */
80 int PQ_deleteMax(PriorityQueue * const);
81
82 /*
83 PQ_increaseElementKey adds the value of i to the key of the given QueueElement
84 */
85 void PQ_increaseElementKey(PriorityQueue * const, QueueElement * const, double i);
86 /*
87 PQ_decreaseElementKey substracts the value of i from the key of the given QueueElement
88 */
89 void PQ_decreaseElementKey(PriorityQueue * const, QueueElement * const, double i);
90 /*
91 PQ_adjustElementKey sets to i the key of the given QueueElement.
92 */
93 void PQ_adjustElementKey(PriorityQueue * const, QueueElement * const, double i);
94
95 /*
96 PQ_increaseKey adds i to the key of the first element found with a value equal to val in the PriorityQueue.
97 */
98 void PQ_increaseKey(PriorityQueue * const, int val, double i);
99 /*
100 PQ_decreaseKey substracts i from the key of the first element found with a value equal to val in the PriorityQueue.
101 */
102 void PQ_decreaseKey(PriorityQueue * const, int val, double i);
103 /*
104 PQ_adjustKey sets to i the key of the first element found with a value equal to val in the PriorityQueue.
105 */
106 void PQ_adjustKey(PriorityQueue * const, int val, double i);
107
108 #endif /*PRIORITY_QUEUE*/