1#include "priority_queue.h"
  2#include <stdio.h>
  3#include <stdlib.h>
  4
  5/**
  6 * The equivalent of a constructor to create a PriorityQueue.
  7 */
  8PriorityQueue *initialize(void) {
  9  PriorityQueue *self = malloc(sizeof(PriorityQueue));
 10  self->size = 0;
 11  self->head = NULL;
 12  return self;
 13}
 14
 15/**
 16 * A function used to construct a Node for a singly linked list.
 17 *
 18 * @param priority the priority for the data
 19 * @param data the data to store in the queue
 20 * @return The Node to add to a singly linked list.
 21 */
 22static Node *create_node(int priority, int data) {
 23  Node *node = malloc(sizeof(Node));
 24  node->priority = priority;
 25  node->data = data;
 26  node->next = NULL;
 27  return node;
 28}
 29
 30/**
 31 * Determines the number of items stored in a queue.
 32 *
 33 * @param self The queue to investigate
 34 * @return The total number of items stored in the queue.
 35 */
 36int size(PriorityQueue *self) { return self->size; }
 37
 38/**
 39 * Compares two integers and returns:
 40 * 1 if x is greater than y.
 41 * 0 if x is equal to y.
 42 * -1 if x is less than to y.
 43 *
 44 *  @param x the integer to compare
 45 *  @param y the other integer to compare
 46 *  @return 1,0,-1 depending on the comparison of x and y
 47 */
 48static int compare(const int x, const int y) {
 49  return x == y ? 0 : x > y ? 1 : -1;
 50}
 51
 52/**
 53 * Inserts a node into the queue in the best position based on the priority.
 54 *
 55 * @param self The head of the queue.
 56 * @param priority The priority of the data.
 57 * @param data the data to store.
 58 */
 59void enqueue(Node *self, int priority, int data) {
 60  if (self->next == NULL) {
 61    self->next = create_node(priority, data);
 62    return;
 63  }
 64
 65  int comparison = compare(self->next->priority, priority);
 66  if (comparison == 0) {
 67    return enqueue(self->next, priority, data);
 68  }
 69
 70  if (comparison < 0) {
 71    return enqueue(self->next, priority, data);
 72  }
 73
 74  Node *tmp = self->next;
 75  self->next = create_node(priority, data);
 76  self->next->next = tmp;
 77}
 78
 79/**
 80 * Adds data with a specific priority to the queue
 81 *
 82 * @param self The queue to add data to
 83 * @param priority The priority for the data
 84 * @param data The data to store
 85 */
 86void add(PriorityQueue *self, int priority, int data) {
 87  self->size++;
 88
 89  if (!self->head) {
 90    self->head = create_node(priority, data);
 91    return;
 92  }
 93
 94  if (compare(self->head->priority, priority) <= 0)
 95    return enqueue(self->head, priority, data);
 96
 97  Node *node = create_node(priority, data);
 98  node->next = self->head;
 99  self->head = node;
100}
101
102/**
103 * Removes the next item in the queue with the lowest priority.
104 *
105 * @param self The queue
106 * @return The data associated with the lowest priority in the queue
107 */
108int delete_min(PriorityQueue *self) {
109  if (self->head) {
110    Node *tmp = self->head;
111    int data = tmp->data;
112    self->head = tmp->next;
113    self->size--;
114    free(tmp);
115    return data;
116  }
117  return 0;
118}
119
120/**
121 * A helper function used to print a queue.
122 * This is useful for debugging.
123 *
124 * @param self The queue to print
125 */
126void inspect(PriorityQueue *self) {
127  Node *tmp = self->head;
128
129  printf("Items (%d): [ ", size(self));
130  while (tmp) {
131    printf("(%d,%d) ", tmp->priority, tmp->data);
132    tmp = tmp->next;
133  }
134  printf("]\n");
135}
136
137/**
138 * The equivalent of a destructor function.
139 * This function frees any memory associated with a queue
140 *
141 * @param self The queue to free
142 */
143void destroy(PriorityQueue *self) {
144  Node *current = self->head;
145  Node *tmp;
146
147  while (current) {
148    tmp = current, current = current->next;
149
150    if (tmp)
151      free(tmp);
152  }
153  free(self);
154}