1 #include <stdlib.h>
2 #include "PriorityQueue.h"
3
4 /*
5 This comparison function is used to sort elements in key descending order.
6 */
compFunc(const FiboNode * const node1,const FiboNode * const node2)7 static int compFunc(const FiboNode * const node1, const FiboNode * const node2)
8 {
9 return
10 ( ( ((QueueElement*)(node1))->key > ((QueueElement*)(node2))->key ) ? -1 : 1);
11 }
12
PQ_init(PriorityQueue * const q,int size)13 int PQ_init(PriorityQueue * const q, int size)
14 {
15 int i;
16 q->size = size;
17 q->elements = malloc(sizeof(QueueElement *) * size);
18 for(i=0; i < size; i++)
19 q->elements[i]=NULL;
20 return fiboTreeInit((FiboTree *)q, compFunc);
21 }
22
PQ_exit(PriorityQueue * const q)23 void PQ_exit(PriorityQueue * const q)
24 {
25
26 int i;
27 for(i = 0; i < q->size; i++)
28 {
29 if(q->elements[i] != NULL)
30 free(q->elements[i]);
31 }
32 if(q->elements != NULL)
33 free(q->elements);
34 fiboTreeExit((FiboTree *)q);
35 }
PQ_free(PriorityQueue * const q)36 void PQ_free(PriorityQueue * const q)
37 {
38 int i;
39 for(i = 0; i < q->size; i++)
40 {
41 if(q->elements[i] != NULL)
42 free(q->elements[i]);
43 }
44 fiboTreeFree((FiboTree *)q);
45 }
46
PQ_isEmpty(PriorityQueue * const q)47 int PQ_isEmpty(PriorityQueue * const q)
48 {
49 FiboTree * tree = (FiboTree *)q;
50 /* if the tree root is linked to itself then the tree is empty */
51 if(&(tree->rootdat) == (tree->rootdat.linkdat.nextptr))
52 return 1;
53 return 0;
54 }
55
PQ_insertElement(PriorityQueue * const q,QueueElement * const e)56 void PQ_insertElement(PriorityQueue * const q, QueueElement * const e)
57 {
58 if(e->value >= 0 && e->value < q->size)
59 {
60 fiboTreeAdd((FiboTree *)q, (FiboNode *)(e));
61 q->elements[e->value] = e;
62 e->isInQueue = 1;
63 }
64 }
PQ_deleteElement(PriorityQueue * const q,QueueElement * const e)65 void PQ_deleteElement(PriorityQueue * const q, QueueElement * const e)
66 {
67 fiboTreeDel((FiboTree *)q, (FiboNode *)(e));
68 q->elements[e->value] = NULL;
69 e->isInQueue = 0;
70 }
71
PQ_insert(PriorityQueue * const q,int val,double key)72 void PQ_insert(PriorityQueue * const q, int val, double key)
73 {
74 if( val >= 0 && val < q->size)
75 {
76 QueueElement * e = malloc(sizeof(QueueElement));
77 e->value = val;
78 e->key = key;
79 PQ_insertElement(q, e);
80 }
81 }
82
PQ_delete(PriorityQueue * const q,int val)83 void PQ_delete(PriorityQueue * const q, int val)
84 {
85 QueueElement * e = q->elements[val];
86 PQ_deleteElement(q, e);
87 free(e);
88 }
89
PQ_findMaxElement(PriorityQueue * const q)90 QueueElement * PQ_findMaxElement(PriorityQueue * const q)
91 {
92 QueueElement * e = (QueueElement *)(fiboTreeMin((FiboTree *)q));
93 return e;
94 }
PQ_deleteMaxElement(PriorityQueue * const q)95 QueueElement * PQ_deleteMaxElement(PriorityQueue * const q)
96 {
97 QueueElement * e = (QueueElement *)(fiboTreeMin((FiboTree *)q));
98 if(e != NULL)
99 {
100 PQ_deleteElement(q, e);
101 }
102 return e;
103 }
104
PQ_findMaxKey(PriorityQueue * const q)105 double PQ_findMaxKey(PriorityQueue * const q)
106 {
107 QueueElement * e = PQ_findMaxElement(q);
108 if(e!=NULL)
109 return e->key;
110 return 0;
111 }
112
PQ_deleteMax(PriorityQueue * const q)113 int PQ_deleteMax(PriorityQueue * const q)
114 {
115 QueueElement * e = PQ_deleteMaxElement(q);
116 int res = -1;
117 if(e != NULL)
118 res = e->value;
119 free(e);
120 return res;
121 }
122
PQ_increaseElementKey(PriorityQueue * const q,QueueElement * const e,double i)123 void PQ_increaseElementKey(PriorityQueue * const q, QueueElement * const e, double i)
124 {
125 if(e->isInQueue)
126 {
127 PQ_deleteElement(q, e);
128 e->key += i;
129 PQ_insertElement(q, e);
130 }
131 }
PQ_decreaseElementKey(PriorityQueue * const q,QueueElement * const e,double i)132 void PQ_decreaseElementKey(PriorityQueue * const q, QueueElement * const e, double i)
133 {
134 if(e->isInQueue)
135 {
136 PQ_deleteElement(q, e);
137 e->key -= i;
138 PQ_insertElement(q, e);
139 }
140 }
PQ_adjustElementKey(PriorityQueue * const q,QueueElement * const e,double i)141 void PQ_adjustElementKey(PriorityQueue * const q, QueueElement * const e, double i)
142 {
143 if(e->isInQueue)
144 {
145 PQ_deleteElement(q, e);
146 e->key = i;
147 PQ_insertElement(q, e);
148 }
149 }
150
PQ_increaseKey(PriorityQueue * const q,int val,double i)151 void PQ_increaseKey(PriorityQueue * const q, int val, double i)
152 {
153 QueueElement * e = q->elements[val];
154 if(e != NULL)
155 PQ_increaseElementKey(q, e, i);
156 }
157
PQ_decreaseKey(PriorityQueue * const q,int val,double i)158 void PQ_decreaseKey(PriorityQueue * const q, int val, double i)
159 {
160 QueueElement * e = q->elements[val];
161 if(e != NULL)
162 PQ_decreaseElementKey(q, e, i);
163 }
164
PQ_adjustKey(PriorityQueue * const q,int val,double i)165 void PQ_adjustKey(PriorityQueue * const q, int val, double i)
166 {
167 QueueElement * e = q->elements[val];
168 if(e != NULL)
169 PQ_adjustElementKey(q, e, i);
170 }
171