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
|
#include "priority_queue.h"
#include <stdio.h>
#include <stdlib.h>
/**
* The equivalent of a constructor to create a PriorityQueue.
*/
PriorityQueue *initialize(void) {
PriorityQueue *self = malloc(sizeof(PriorityQueue));
self->size = 0;
self->head = NULL;
return self;
}
/**
* A function used to construct a Node for a singly linked list.
*
* @param priority the priority for the data
* @param data the data to store in the queue
* @return The Node to add to a singly linked list.
*/
static Node *create_node(int priority, int data) {
Node *node = malloc(sizeof(Node));
node->priority = priority;
node->data = data;
node->next = NULL;
return node;
}
/**
* Determines the number of items stored in a queue.
*
* @param self The queue to investigate
* @return The total number of items stored in the queue.
*/
int size(PriorityQueue *self) { return self->size; }
/**
* Compares two integers and returns:
* 1 if x is greater than y.
* 0 if x is equal to y.
* -1 if x is less than to y.
*
* @param x the integer to compare
* @param y the other integer to compare
* @return 1,0,-1 depending on the comparison of x and y
*/
static int compare(const int x, const int y) {
return x == y ? 0 : x > y ? 1 : -1;
}
/**
* Inserts a node into the queue in the best position based on the priority.
*
* @param self The head of the queue.
* @param priority The priority of the data.
* @param data the data to store.
*/
void enqueue(Node *self, int priority, int data) {
if (self->next == NULL) {
self->next = create_node(priority, data);
return;
}
int comparison = compare(self->next->priority, priority);
if (comparison == 0) {
return enqueue(self->next, priority, data);
}
if (comparison < 0) {
return enqueue(self->next, priority, data);
}
Node *tmp = self->next;
self->next = create_node(priority, data);
self->next->next = tmp;
}
/**
* Adds data with a specific priority to the queue
*
* @param self The queue to add data to
* @param priority The priority for the data
* @param data The data to store
*/
void add(PriorityQueue *self, int priority, int data) {
self->size++;
if (!self->head) {
self->head = create_node(priority, data);
return;
}
if (compare(self->head->priority, priority) <= 0)
return enqueue(self->head, priority, data);
Node *node = create_node(priority, data);
node->next = self->head;
self->head = node;
}
/**
* Removes the next item in the queue with the lowest priority.
*
* @param self The queue
* @return The data associated with the lowest priority in the queue
*/
int delete_min(PriorityQueue *self) {
if (self->head) {
Node *tmp = self->head;
int data = tmp->data;
self->head = tmp->next;
self->size--;
free(tmp);
return data;
}
return 0;
}
/**
* A helper function used to print a queue.
* This is useful for debugging.
*
* @param self The queue to print
*/
void inspect(PriorityQueue *self) {
Node *tmp = self->head;
printf("Items (%d): [ ", size(self));
while (tmp) {
printf("(%d,%d) ", tmp->priority, tmp->data);
tmp = tmp->next;
}
printf("]\n");
}
/**
* The equivalent of a destructor function.
* This function frees any memory associated with a queue
*
* @param self The queue to free
*/
void destroy(PriorityQueue *self) {
Node *current = self->head;
Node *tmp;
while (current) {
tmp = current, current = current->next;
if (tmp)
free(tmp);
}
free(self);
}
|
