summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/pathfinder/npf/aystar.h2
-rw-r--r--src/pathfinder/npf/queue.cpp20
-rw-r--r--src/pathfinder/npf/queue.h11
3 files changed, 16 insertions, 17 deletions
diff --git a/src/pathfinder/npf/aystar.h b/src/pathfinder/npf/aystar.h
index 864cdd486..a71fef299 100644
--- a/src/pathfinder/npf/aystar.h
+++ b/src/pathfinder/npf/aystar.h
@@ -161,7 +161,7 @@ struct AyStar {
/* The actual closed list */
Hash ClosedListHash;
/* The open queue */
- Queue OpenListQueue;
+ BinaryHeap OpenListQueue;
/* An extra hash to speed up the process of looking up an element in
* the open list */
Hash OpenListHash;
diff --git a/src/pathfinder/npf/queue.cpp b/src/pathfinder/npf/queue.cpp
index 047d54192..0edac387f 100644
--- a/src/pathfinder/npf/queue.cpp
+++ b/src/pathfinder/npf/queue.cpp
@@ -7,7 +7,7 @@
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
*/
-/** @file queue.cpp Implementation of the Queue/Hash. */
+/** @file queue.cpp Implementation of the #BinaryHeap/#Hash. */
#include "../../stdafx.h"
#include "../../core/alloc_func.hpp"
@@ -19,16 +19,16 @@
* For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
*/
-const int Queue::BINARY_HEAP_BLOCKSIZE_BITS = 10; ///< The number of elements that will be malloc'd at a time.
-const int Queue::BINARY_HEAP_BLOCKSIZE = 1 << Queue::BINARY_HEAP_BLOCKSIZE_BITS;
-const int Queue::BINARY_HEAP_BLOCKSIZE_MASK = Queue::BINARY_HEAP_BLOCKSIZE - 1;
+const int BinaryHeap::BINARY_HEAP_BLOCKSIZE_BITS = 10; ///< The number of elements that will be malloc'd at a time.
+const int BinaryHeap::BINARY_HEAP_BLOCKSIZE = 1 << BinaryHeap::BINARY_HEAP_BLOCKSIZE_BITS;
+const int BinaryHeap::BINARY_HEAP_BLOCKSIZE_MASK = BinaryHeap::BINARY_HEAP_BLOCKSIZE - 1;
/**
* Clears the queue, by removing all values from it. Its state is
* effectively reset. If free_items is true, each of the items cleared
* in this way are free()'d.
*/
-void Queue::Clear(bool free_values)
+void BinaryHeap::Clear(bool free_values)
{
/* Free all items if needed and free all but the first blocks of memory */
uint i;
@@ -65,7 +65,7 @@ void Queue::Clear(bool free_values)
* this it is no longer usable. If free_items is true, any remaining
* items are free()'d too.
*/
-void Queue::Free(bool free_values)
+void BinaryHeap::Free(bool free_values)
{
uint i;
@@ -81,7 +81,7 @@ void Queue::Free(bool free_values)
* Pushes an element into the queue, at the appropriate place for the queue.
* Requires the queue pointer to be of an appropriate type, of course.
*/
-bool Queue::Push(void *item, int priority)
+bool BinaryHeap::Push(void *item, int priority)
{
#ifdef QUEUE_DEBUG
printf("[BinaryHeap] Pushing an element. There are %d elements left\n", this->size);
@@ -137,7 +137,7 @@ bool Queue::Push(void *item, int priority)
* known, which speeds up the deleting for some queue's. Should be -1
* if not known.
*/
-bool Queue::Delete(void *item, int priority)
+bool BinaryHeap::Delete(void *item, int priority)
{
uint i = 0;
@@ -200,7 +200,7 @@ bool Queue::Delete(void *item, int priority)
* Pops the first element from the queue. What exactly is the first element,
* is defined by the exact type of queue.
*/
-void *Queue::Pop()
+void *BinaryHeap::Pop()
{
void *result;
@@ -222,7 +222,7 @@ void *Queue::Pop()
* Initializes a binary heap and allocates internal memory for maximum of
* max_size elements
*/
-void Queue::Init(uint max_size)
+void BinaryHeap::Init(uint max_size)
{
this->max_size = max_size;
this->size = 0;
diff --git a/src/pathfinder/npf/queue.h b/src/pathfinder/npf/queue.h
index 2dc075b93..897351ae6 100644
--- a/src/pathfinder/npf/queue.h
+++ b/src/pathfinder/npf/queue.h
@@ -7,7 +7,7 @@
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
*/
-/** @file queue.h Simple Queue/Hash implementations. */
+/** @file queue.h Binary heap implementation, hash implementation. */
#ifndef QUEUE_H
#define QUEUE_H
@@ -24,12 +24,11 @@ struct BinaryHeapNode {
};
-/*
- * Binary Heap
- * For information, see:
- * http://www.policyalmanac.org/games/binaryHeaps.htm
+/**
+ * Binary Heap.
+ * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
*/
-struct Queue {
+struct BinaryHeap {
static const int BINARY_HEAP_BLOCKSIZE;
static const int BINARY_HEAP_BLOCKSIZE_BITS;
static const int BINARY_HEAP_BLOCKSIZE_MASK;