adding priority queue class

5 files changed, 128 insertions, 21 deletions

diff --git a/bin/main b/bin/main
index 3f32396..74b629d 100755
--- a/bin/main
+++ b/bin/main
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
diff --git a/src/astar.cpp b/src/astar.cpp
index b5c424e..e40a436 100644
--- a/src/astar.cpp
+++ b/src/astar.cpp
@@ -1,20 +1,14 @@
 #include "astar.hpp"
 
-Node::Node() : previous_node(NULL), f_score(-1), g_score(0), h_score(-1), visited(false) {
-	for(unsigned int i = 0; i < NEIGHBOUR_NUM; ++i)
-		next_nodes[i] = NULL;
+Node::Node() : previous_node(NULL), f_score(-1), g_score(0), h_score(-1) {
 	update_f_score();
 }
 
-Node::Node(Node *prev_node) : previous_node(prev_node), f_score(-1), g_score(0), h_score(-1), visited(false) {
-	for(unsigned int i = 0; i < NEIGHBOUR_NUM; ++i)
-		next_nodes[i] = NULL;
+Node::Node(Node *prev_node) : previous_node(prev_node), f_score(-1), g_score(0), h_score(-1) {
 	update_f_score();
 }
 
-Node::Node(Node *prev_node, int g) : previous_node(prev_node), f_score(-1), g_score(g), h_score(-1), visited(false) {
-	for(unsigned int i = 0; i < NEIGHBOUR_NUM; ++i)
-		next_nodes[i] = NULL;
+Node::Node(Node *prev_node, int g) : previous_node(prev_node), f_score(-1), g_score(g), h_score(-1) {
 	update_f_score();
 }
 
@@ -22,6 +16,8 @@ Node::~Node() {
 }
 
 bool operator<(const Node& n1, const Node& n2) {
+	if(n1.f_score == n2.f_score)
+		return n1.h_score < n2.h_score;
 	return n1.f_score < n2.f_score;
 }
 
@@ -30,15 +26,17 @@ bool operator==(const Node& n1, const Node& n2) {
 }
 
 bool operator>(const Node& n1, const Node& n2) {
-	return !(n1 < n2) && !(n1 == n2);
+	if(n1.f_score == n2.f_score)
+		return n1.h_score > n2.h_score;
+	return n1.f_score > n2.f_score;
 }
 
 bool operator<=(const Node& n1, const Node& n2) {
-	return (n1 < n2) || (n1 == n2);
+	return n1.f_score <= n2.f_score;
 }
 
 bool operator>=(const Node& n1, const Node& n2) {
-	return !(n1 < n2);
+	return n1.f_score >= n2.f_score;
 }
 
 bool operator!=(const Node& n1, const Node& n2) {
diff --git a/src/main.cpp b/src/main.cpp
index 5b950ea..bd647c2 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -9,6 +9,7 @@
 
 #include "tilemap.hpp"
 #include "astar.hpp"
+#include "priority_queue.hpp"
 
 #include <SFML/Graphics.hpp>
 
@@ -18,12 +19,15 @@
 using namespace std;
 
 int main(int argc, char *argv[]) {
-	Node n1(NULL, 5);
-	Node n2(NULL, 2);
+	PriorityQueue<int> pq;
 
-	cout << "n1 > n2: " << (n1 > n2) << endl;
-	cout << "n1 < n2: " << (n1 < n2) << endl;
-	cout << "n1 <= n2: " << (n1 <= n2) << endl;
-	cout << "n1 >= n2: " << (n1 >= n2) << endl;
+	pq.push(5);
+	pq.push(2);
+	pq.push(3);
+	pq.push(8);
+	pq.push(19);
+	pq.push(1);
+
+	cout << pq.pop() << " " << pq.pop() << " " << pq.pop() << endl;
 	return 0;
 }