From d8c53d9d9ba4f275db25c3a98c6e1b380b3c69e1 Mon Sep 17 00:00:00 2001 From: ymherklotz Date: Fri, 9 Dec 2016 22:10:53 +0000 Subject: working priority queue --- bin/main | Bin 209448 -> 209120 bytes include/astar.hpp | 3 - include/priority_queue.hpp | 158 ++++++++++++++++++++++++++------------------- src/astar.cpp | 11 ---- src/main.cpp | 19 +++--- 5 files changed, 103 insertions(+), 88 deletions(-) diff --git a/bin/main b/bin/main index 74b629d..83298da 100755 Binary files a/bin/main and b/bin/main differ 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 -using namespace std; - template 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 +PriorityQueue::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 +PriorityQueue::~PriorityQueue() { + std::cout << "destructor" << std::endl; + delete[] priority_array; +} - T *tmp_array = new T[capacity]; +template +void PriorityQueue::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 +T PriorityQueue::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 +void PriorityQueue::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 +void PriorityQueue::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 +T PriorityQueue::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 #include +#include using namespace std; int main(int argc, char *argv[]) { - PriorityQueue pq; + PriorityQueue 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; } -- cgit