adding priority queue class

2 files changed, 108 insertions, 3 deletions

diff --git a/include/astar.hpp b/include/astar.hpp
index 5a379fb..06fcc85 100644
--- a/include/astar.hpp
+++ b/include/astar.hpp
@@ -3,8 +3,11 @@
 
 #include <ostream>
 
-#define NEIGHBOUR_NUM 4
+// defines the number of nodes one can go to
+// we don't need this as we will have the queues
+//#define NEIGHBOUR_NUM 4
 
+// TODO add constructors and functions to calculate heuristics etc..
 class AStar {
 public:
 private:
@@ -12,6 +15,7 @@ private:
 
 class Node {
 public:
+	// TODO These constructors have to change
 	Node();
 	Node(Node *prev_node);
 	Node(Node *prev_node, int g);
@@ -29,7 +33,8 @@ private:
 	// pointer to previous node so that I can backtrack without using recursion.
 	Node *previous_node;
 	// pointers to the next nodes of which there are 4 in a grid.
-	Node *next_nodes[NEIGHBOUR_NUM];
+	// We do not need this as we are implementing a priority queue;
+	//Node *next_nodes[NEIGHBOUR_NUM];
 
 	// score that is used to compare to other nodes to see if the other path is
 	// more efficient.
@@ -40,7 +45,8 @@ private:
 	int h_score;
 
 	// see if node has been visited.
-	bool visited;
+	// We don't need this as we will have an open and a closed set
+	//bool visited;
 
 	// updates the f_score accordingly.
 	void update_f_score();
diff --git a/include/priority_queue.hpp b/include/priority_queue.hpp
new file mode 100644
index 0000000..3975007
--- /dev/null
+++ b/include/priority_queue.hpp
@@ -0,0 +1,99 @@
+#ifndef PRIORITY_QUEUE_HPP
+#define PRIORITY_QUEUE_HPP
+
+#include <iostream>
+
+using namespace std;
+
+template<typename T>
+class PriorityQueue {
+public:
+	PriorityQueue() : size(0), capacity(1) {
+		priority_array = new T;
+	}
+	~PriorityQueue() {
+		delete[] priority_array;
+	}
+
+	// pushes element to the queue which is sorted by smallest element first
+	void push(const T& element) {
+		unsigned int insert_loc = 0;
+
+		if(size == capacity)
+			resize_queue(2);
+
+		while(insert_loc < size && element > priority_array[insert_loc])
+			++insert_loc;
+
+		size++;
+
+		insert_queue(element, insert_loc);
+	}
+
+	// pops the first element from the queue and removes it while returning
+	// it
+	T pop() {
+		if(!size)
+			throw "Priority Queue is empty, no item to pop";
+		else if(size - 1 == capacity / 2)
+			resize_queue(0.5);
+
+		size--;
+
+		return remove_queue(0);
+	}
+private:
+	// size of the current queue
+	unsigned int size;
+	// capacity of the queue, this will just increase in multiples of 2
+	unsigned int capacity;
+	// array that will represent the priority queue
+	T *priority_array;
+
+	void resize_queue(double factor) {
+		capacity = (double)capacity * factor;
+		T *tmp_array = new T[capacity];
+
+		for(unsigned int i = 0; i < size; ++i)
+			tmp_array[i] = priority_array[i];
+
+		delete[] priority_array;
+		priority_array = tmp_array;
+	}
+
+	void insert_queue(const T& element, const unsigned int& loc) {
+		T *tmp_array = new T[capacity];
+
+		for(unsigned int i = 0; i < size; ++i)
+			if(i == loc)
+				tmp_array[i] = element;
+			else if(i < loc)
+				tmp_array[i] = priority_array[i];
+			else
+				tmp_array[i] = priority_array[i - 1];
+
+		delete[] priority_array;
+		priority_array = tmp_array;
+	}
+
+	T remove_queue(const unsigned int& loc) {
+		T element;
+
+		T *tmp_array = new T[capacity];
+
+		for(unsigned int i = 0; i < size; ++i)
+			if(i == loc)
+				element = priority_array[i];
+			else if(i < loc)
+				tmp_array[i] = priority_array[i];
+			else
+				tmp_array[i] = priority_array[i + 1];
+
+		delete[] priority_array;
+		priority_array = tmp_array;
+
+		return element;
+	}
+};
+
+#endif