-
Notifications
You must be signed in to change notification settings - Fork 0
/
SPBPriorityQueue.h
183 lines (154 loc) · 5.62 KB
/
SPBPriorityQueue.h
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
#ifndef SPBPRIORITYQUEUE_H_
#define SPBPRIORITYQUEUE_H_
#include "SPListElement.h"
#include <stdbool.h>
/**
* SP Bounded Priority Queue
* -------------------------
* Data structure of a bounded priority Queue.
* Implemented as a fixe-length array.
* More "sophisticated" implementations (heap) is not needed,
* as we assume the queue length remains small.
*/
/** type used to define Bounded priority queue **/
typedef struct sp_bp_queue_t* SPBPQueue;
/** type for error reporting **/
typedef enum sp_bp_queue_msg_t {
SP_BPQUEUE_OUT_OF_MEMORY,
SP_BPQUEUE_FULL,
SP_BPQUEUE_EMPTY,
SP_BPQUEUE_INVALID_ARGUMENT,
SP_BPQUEUE_SUCCESS
} SP_BPQUEUE_MSG;
/**
* Allocates a new empty Bounded Priority Queue.
*
* @param maxSize maximum capacity (the upper bound of queue size) of the queue.
* @return
* NULL in case maxSize<=0 || memory allocation fails
* A new queue in case of success
*/
SPBPQueue spBPQueueCreate(int maxSize);
/**
* Creates a deep and complete copy from an existing queue.
*
* @param source existing queue
* @return
* NULL in case source == NULL || memory allocation fails
* A copy of the source queue.
*/
SPBPQueue spBPQueueCopy(SPBPQueue source);
/**
* Deallocates an existing queue.
* Clears all elements and field by using the free function.
*
* @param source Target queue to be deallocated. If queue is NULL nothing will be done
*/
void spBPQueueDestroy(SPBPQueue source);
/**
* Removes all elements from source queue.
* The elements are deallocated using the stored freeing function
*
* @param source - Target queue to remove all element from. If queue is NULL nothing will be done
*
*/
void spBPQueueClear(SPBPQueue source);
/**
* Returns the number of elements in a queue.
*
* @param source - The target source of which its size is requested.
* @return
* -1 if a NULL pointer was sent.
* Otherwise the number of elements in the queue.
*/
int spBPQueueSize(SPBPQueue source);
/**
* Returns the maximum capacity of elements in a queue.
*
* @param source - The target source of which its maximum size is requested.
* @return
* -1 if a NULL pointer was sent.
* Otherwise the maximum number of elements the queue can contain.
*/
int spBPQueueGetMaxSize(SPBPQueue source);
/**
* Inserting a copy of the element to the source queue.
* After inserting queue will be sorted by value, than by index.
*
* @param source - The target source queue to be enqueued into.
* @param element - element to be enqueued
*
* @return
* SP_BPQUEUE_INVALID_ARGUMENT - if NULL was sent as at least one of the arguments
* SP_BPQUEUE_FULL - If source if full and the value of element is bigger than the last element of source
* Or the source is full and the value equals to the last's value, but has bigger index.
* SP_BPQUEUE_SUCCESS - if insert was successful (Otherwise).
*
*/
SP_BPQUEUE_MSG spBPQueueEnqueue(SPBPQueue source, SPListElement element);
/**
* Removes from the target queue the element with the lowest value.
*
* @param source - The target source of which its maximum size is requested.
* @return
* SP_BPQUEUE_INVALID_ARGUMENT - if NULL was sent as an argument
* SP_BPQUEUE_EMPTY - if an source queue is empty
* SP_BPQUEUE_SUCCESS - if remove was successful.
*
*/
SP_BPQUEUE_MSG spBPQueueDequeue(SPBPQueue source);
/**
* Returns a copy of the lowest value in the queue (the first element).
*
* @param source - the priority queue
* @return
* If the queue is empty (source.size == 0), or the source is not valid (NULL), or source-> is not valid, return NULL
* otherwise, return a copy of the first element in the queue, using spListElementCopy(source)
*/
SPListElement spBPQueuePeek(SPBPQueue source);
/**
* Returns a copy of the highest value in the queue (the last element).
*
* @param source - the priority queue
* @return
* If the queue is empty (source.size == 0), or the source is not valid (NULL), or source-> is not valid, return NULL
* otherwise, return a copy of the last element in the queue, using spListElementCopy(source)
*/
SPListElement spBPQueuePeekLast(SPBPQueue source);
/**
* the function finds the first element in the queue and returns its value.
*
* @param source - the priority queue
* @pre source->list->value > 0
*
* @return
* (-1) - If the queue is empty (source.size == 0), or the source is not valid (NULL), or source-> is not valid
* otherwise, return the value of the first element, using SPListGetFirst(source)
*/
double spBPQueueMinValue(SPBPQueue source);
/**
* the function finds the last element in the queue and returns its value.
* @param source - the priority queue
* @pre source->list->value > 0
* @return
* (-1) - If the queue is empty (source.size == 0), or the source is not valid (NULL), or source-> is not valid, return -1
* otherwise, return the value of the last element, using SPListGetLast(source)
*/
double spBPQueueMaxValue(SPBPQueue source);
/**
* the function returns true if the priority queue source is empty, AKA size of queue equals 0
* @param source - the priority queue
* @return
* True if the queue is empty (source.size == 0)), and false otherwise.
* the function deals NULL input as false.
*/
bool spBPQueueIsEmpty(SPBPQueue source);
/**
* the function returns true if the priority queue source is full, and false otherwise
* @param source - the priority queue
* @return
* True if the queue is full (source.size == source.maxsize), and false otherwise.
* the function deals NULL input as false.
*/
bool spBPQueueIsFull(SPBPQueue source);
#endif