-
Notifications
You must be signed in to change notification settings - Fork 0
/
SPBPriorityQueue.c
254 lines (210 loc) · 5.48 KB
/
SPBPriorityQueue.c
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include "SPList.h"
#include "SPBPriorityQueue.h"
#define NULLCheck(something) if (something == NULL) { return NULL; }
SP_BPQUEUE_MSG convertMessage(SP_LIST_MSG);
struct sp_bp_queue_t {
SPList list;
int maxSize;
};
SPBPQueue spBPQueueCreate(int maxSize) {
if (maxSize <= 0) {
return NULL;
}
/* Memory allocation for PBQueue */
struct sp_bp_queue_t * q = (struct sp_bp_queue_t*) malloc(
sizeof(struct sp_bp_queue_t));
NULLCheck(q)
/* Creating new elements in struct */
q->list = spListCreate();
if (!q->list) {
free(q);
return NULL;
}
q->maxSize = maxSize;
return q;
}
SPBPQueue spBPQueueCopy(SPBPQueue source) {
NULLCheck(source)
/* Memory allocation for PBQueue */
struct sp_bp_queue_t * newQ = (struct sp_bp_queue_t*) malloc(
sizeof(struct sp_bp_queue_t));
NULLCheck(newQ)
newQ->list = spListCopy(source->list);
if (newQ->list == NULL) {
free(newQ);
return NULL;
}
newQ->maxSize = source->maxSize;
return newQ;
}
void spBPQueueDestroy(SPBPQueue source) {
if (source != NULL) {
spListDestroy(source->list);
free(source);
}
}
void spBPQueueClear(SPBPQueue source) {
if (source != NULL) {
if (source->list) {
spListClear(source->list);
}
}
}
int spBPQueueSize(SPBPQueue source) {
if (source) {
if (source->list) {
return spListGetSize(source->list);
}
}
return -1;
}
int spBPQueueGetMaxSize(SPBPQueue source) {
if (source) {
return source->maxSize;
}
return -1;
}
SP_BPQUEUE_MSG spBPQueueEnqueue(SPBPQueue source, SPListElement element) {
double value;
if (!source || !element || !source->list) {
return SP_BPQUEUE_INVALID_ARGUMENT;
}
SP_BPQUEUE_MSG msg = SP_BPQUEUE_SUCCESS;
value = spListElementGetValue(element);
/* If list is empty , insert at start*/
if (spBPQueueIsEmpty(source)) {
msg = convertMessage(spListInsertFirst(source->list, element));
}
/* If the value is bigger than the biggest insert him last*/
else if (value > spBPQueueMaxValue(source)) {
if (spBPQueueSize(source) != spBPQueueGetMaxSize(source)) {
msg = convertMessage(spListInsertLast(source->list, element));
}
else { /* If also, the list is full, do nothing */
msg = SP_BPQUEUE_FULL;
}
} else {
SPListElement curr = spListGetFirst(source->list);
/* Iterating through list until finding place for element*/
while (curr
&& spListElementGetValue(curr) < spListElementGetValue(element)) {
curr = spListGetNext(source->list);
}
/* Checks if value is equal to the next one's value
* if so, inserting smaller index first
* */
while (curr
&& spListElementGetValue(element) == spListElementGetValue(curr)
&& (spListElementGetIndex(element) > spListElementGetIndex(curr))) {
curr = spListGetNext(source->list);
}
/* inserting element to right place in list */
if (curr) {
msg = convertMessage(
spListInsertBeforeCurrent(source->list, element));
}
/* if reaches end of queue */
else {
msg = convertMessage(spListInsertLast(source->list, element));
}
}
/* updating last element if size limit breached */
if (spListGetSize(source->list) > spBPQueueGetMaxSize(source)) {
spListGetLast(source->list);
spListRemoveCurrent(source->list);
}
return msg;
}
double spBPQueueMinValue(SPBPQueue source) {
if (source != NULL) {
if (source->list != NULL) {
return spListElementGetValue(spListGetFirst(source->list));
}
}
return -1;
}
double spBPQueueMaxValue(SPBPQueue source) {
if (source) {
if (source->list) {
return spListElementGetValue(spListGetLast(source->list));
}
}
return -1;
}
bool spBPQueueIsEmpty(SPBPQueue source) {
if (source != NULL) {
if (source->list != NULL) {
return (spBPQueueSize(source) == 0);
}
}
return false;
}
SP_BPQUEUE_MSG spBPQueueDequeue(SPBPQueue source) {
if (source != NULL) {
if (source->list != NULL) {
if (spBPQueueIsEmpty(source)) {
return SP_BPQUEUE_EMPTY;
} else {
/* If queue is not empty destroy the first element,
* automatically assigns new "first"
*/
spListGetFirst(source->list);
spListRemoveCurrent(source->list);
return SP_BPQUEUE_SUCCESS;
}
}
}
return SP_BPQUEUE_INVALID_ARGUMENT;
}
SPListElement spBPQueuePeek(SPBPQueue source) {
if (source != NULL) {
if (source->list != NULL) {
if (spBPQueueIsEmpty(source)) {
return NULL;
} else {
return spListElementCopy(spListGetFirst(source->list));
}
}
}
return NULL;
}
SPListElement spBPQueuePeekLast(SPBPQueue source) {
if (source != NULL) {
if (source->list != NULL) {
if (spBPQueueIsEmpty(source)) {
return NULL;
} else {
return spListElementCopy(spListGetLast(source->list));
}
}
}
return NULL;
}
bool spBPQueueIsFull(SPBPQueue source) {
if (source != NULL) {
if (source->list != NULL) {
return (spBPQueueSize(source) == spBPQueueGetMaxSize(source));
}
}
return false;
}
/**
* converts SP_LIST_MSG type messages to a SP_BPQUEUE_MSG type message
*
* @param m - list type message
* @return - bpqueue type message fit the given list type message
*/
SP_BPQUEUE_MSG convertMessage(SP_LIST_MSG m) {
switch (m) {
case SP_LIST_SUCCESS:
return SP_BPQUEUE_SUCCESS;
case SP_LIST_OUT_OF_MEMORY:
return SP_BPQUEUE_OUT_OF_MEMORY;
default:
return SP_BPQUEUE_INVALID_ARGUMENT;
}
}