working priority queue

5 files changed, 103 insertions, 88 deletions

diff --git a/bin/main b/bin/main
index 74b629d..83298da 100755
--- a/bin/main
+++ b/bin/main
diff --git a/include/astar.hpp b/include/astar.hpp
index 06fcc85..c0eeee0 100644
--- a/include/astar.hpp
+++ b/include/astar.hpp
@@ -17,9 +17,6 @@ class Node {
 public:
 	// TODO These constructors have to change
 	Node();
-	Node(Node *prev_node);
-	Node(Node *prev_node, int g);
-	~Node();
 
 	// overloading operators for ease of use.
 	friend bool operator<(const Node& n1, const Node& n2);
diff --git a/include/priority_queue.hpp b/include/priority_queue.hpp
index 3975007..f3b78ca 100644
--- a/include/priority_queue.hpp
+++ b/include/priority_queue.hpp
@@ -3,45 +3,18 @@
 
 #include <iostream>
 
-using namespace std;
-
 template<typename T>
 class PriorityQueue {
 public:
-	PriorityQueue() : size(0), capacity(1) {
-		priority_array = new T;
-	}
-	~PriorityQueue() {
-		delete[] priority_array;
-	}
+	PriorityQueue();
+	~PriorityQueue();
 
 	// 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);
-	}
+	void push(const T& element);
 
 	// 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);
-	}
+	T pop();
 private:
 	// size of the current queue
 	unsigned int size;
@@ -50,50 +23,103 @@ private:
 	// 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];
+	void resize_queue(double factor);
 
-		for(unsigned int i = 0; i < size; ++i)
-			tmp_array[i] = priority_array[i];
+	void insert_queue(const T& element, const unsigned int& loc);
+
+	T remove_queue(const unsigned int& loc);
 
-		delete[] priority_array;
-		priority_array = tmp_array;
-	}
+	void delete_queue();
+};
 
-	void insert_queue(const T& element, const unsigned int& loc) {
-		T *tmp_array = new T[capacity];
+template<typename T>
+PriorityQueue<T>::PriorityQueue() : size(0), capacity(1) {
+	T *tmp_head = new T;
 
-		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];
+	std::cout << "constructor" << std::endl;
 
-		delete[] priority_array;
-		priority_array = tmp_array;
-	}
+	priority_array = tmp_head;
+}
 
-	T remove_queue(const unsigned int& loc) {
-		T element;
+template<typename T>
+PriorityQueue<T>::~PriorityQueue() {
+	std::cout << "destructor" << std::endl;
+	delete[] priority_array;
+}
 
-		T *tmp_array = new T[capacity];
+template<typename T>
+void PriorityQueue<T>::push(const T& element) {
+	unsigned int insert_loc = 0;
 
-		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];
+	if(size == capacity)
+		resize_queue(2);
 
-		delete[] priority_array;
-		priority_array = tmp_array;
+	while(insert_loc < size && element > priority_array[insert_loc])
+		++insert_loc;
 
-		return element;
-	}
-};
+	size++;
+
+	insert_queue(element, insert_loc);
+}
+
+template<typename T>
+T PriorityQueue<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);
+}
+
+template<typename T>
+void PriorityQueue<T>::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;
+}
+
+template<typename T>
+void PriorityQueue<T>::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;
+}
+
+template<typename T>
+T PriorityQueue<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 - 1] = priority_array[i];
+
+	delete[] priority_array;
+	priority_array = tmp_array;
+
+	return element;
+}
 
 #endif
diff --git a/src/astar.cpp b/src/astar.cpp
index e40a436..9dd9332 100644
--- a/src/astar.cpp
+++ b/src/astar.cpp
@@ -4,17 +4,6 @@ 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) {
-	update_f_score();
-}
-
-Node::Node(Node *prev_node, int g) : previous_node(prev_node), f_score(-1), g_score(g), h_score(-1) {
-	update_f_score();
-}
-
-Node::~Node() {
-}
-
 bool operator<(const Node& n1, const Node& n2) {
 	if(n1.f_score == n2.f_score)
 		return n1.h_score < n2.h_score;
diff --git a/src/main.cpp b/src/main.cpp
index bd647c2..e679134 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -15,19 +15,22 @@
 
 #include <iostream>
 #include <cstdlib>
+#include <vector>
 
 using namespace std;
 
 int main(int argc, char *argv[]) {
-	PriorityQueue<int> pq;
+	PriorityQueue<Node> pq;
 
-	pq.push(5);
-	pq.push(2);
-	pq.push(3);
-	pq.push(8);
-	pq.push(19);
-	pq.push(1);
+	Node n, n2, n3, n4, n5, n6;
+	pq.push(n);
+	pq.push(n2);
+	pq.push(n3);
+	pq.push(n4);
+	pq.push(n5);
+	pq.push(n6);
+
+	cout << "Node in first queue: " << pq.pop() << endl;
 
-	cout << pq.pop() << " " << pq.pop() << " " << pq.pop() << endl;
 	return 0;
 }