Draft the priority queue

4 files changed, 40 insertions, 2 deletions

diff --git a/Makefile b/Makefile
index 5eff874..0b0fb84 100644
--- a/Makefile
+++ b/Makefile
@@ -1,10 +1,10 @@
 CC=gcc
 EXECUTABLE=astar
 
-astar: main.c map.c stack.c config.h
+astar: main.c map.c stack.c config.h priority_queue.h priority_queue.c
 	$(CC) -Wall -Wpedantic -Wextra -Werror -O3 -o $(EXECUTABLE) priority_queue.c map.c stack.c main.c -lncurses
 
-debug: main.c map.c stack.c config.h
+debug: main.c map.c stack.c config.h priority_queue.h priority_queue.c
 	$(CC) -Wall -g -o $(EXECUTABLE) priority_queue.c map.c stack.c main.c -lncurses
 
 clean: 
diff --git a/priority_queue.c b/priority_queue.c
new file mode 100644
index 0000000..ac5f254
--- /dev/null
+++ b/priority_queue.c
@@ -0,0 +1,5 @@
+#include "priority_queue.h"
+
+//TODO: implement
+
+typedef int the_compiler_isnt_happy_about_an_empty_file;
diff --git a/priority_queue.h b/priority_queue.h
new file mode 100644
index 0000000..45252a8
--- /dev/null
+++ b/priority_queue.h
@@ -0,0 +1,31 @@
+#ifndef PRIORITY_QUEUE_H_
+#define PRIORITY_QUEUE_H_
+
+#include "structs.h"
+
+/* This is basically a sorted linked list
+ * Not sure if we need *prev, to be fair */
+struct PositionPQNode_s {
+    Position pos;
+    size_t priority; /* Lower is "better" */
+    struct PositionPQNode_s *prev;
+    struct PositionPQNode_s *next;
+} PositionPQNode_s;
+
+typedef struct PositionPQNode_s PositionPQ;
+
+/* Create a new PositionPQ with pos and priority */
+PositionPQ ppq_new(Position pos, size_t priority);
+
+/* Insert a pos with priority into a given PositionPQ */
+void ppq_insert(PositionPQ ppq, Position pos, size_t priority);
+
+/* Remove and return the position with the lowest priority */
+Position ppq_remove(PositionPQ ppq);
+
+/* Change the priority of a given pos, moving it to a different place in the
+ * linked list ("POTENTIALLY NOT NEEDED" since we don't use different weights */
+void ppq_reprioritize(PositionPQ ppq, Position pos, size_t priority);
+
+
+#endif /* PRIORITY_QUEUE_H_ */
diff --git a/structs.h b/structs.h
index a82975d..5221829 100644
--- a/structs.h
+++ b/structs.h
@@ -1,6 +1,8 @@
 #ifndef STRUCTS_H_
 #define STRUCTS_H_
 
+#include <stddef.h>
+
 struct Position_s {
     size_t x;
     size_t y;