summaryrefslogtreecommitdiff
path: root/src/pathfinder/npf
diff options
context:
space:
mode:
authoralberth <alberth@openttd.org>2010-08-29 13:35:51 +0000
committeralberth <alberth@openttd.org>2010-08-29 13:35:51 +0000
commit92801ac718a2bb735aac91c869239967a9cee7fc (patch)
treeb23e35967857504ebce54ad93609f7cf4805630f /src/pathfinder/npf
parent68e2a07479f1aed8ad0a8fe2f72e7affcf0f9427 (diff)
downloadopenttd-92801ac718a2bb735aac91c869239967a9cee7fc.tar.xz
(svn r20681) -Codechange: Make BinaryHeap_Push() a method, introduce temporary THISBIN_HEAP_ARR macro.
Diffstat (limited to 'src/pathfinder/npf')
-rw-r--r--src/pathfinder/npf/aystar.cpp4
-rw-r--r--src/pathfinder/npf/queue.cpp41
-rw-r--r--src/pathfinder/npf/queue.h7
3 files changed, 26 insertions, 26 deletions
diff --git a/src/pathfinder/npf/aystar.cpp b/src/pathfinder/npf/aystar.cpp
index 581b76921..49ca4e1b6 100644
--- a/src/pathfinder/npf/aystar.cpp
+++ b/src/pathfinder/npf/aystar.cpp
@@ -82,7 +82,7 @@ static void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, const AySt
Hash_Set(&aystar->OpenListHash, node->tile, node->direction, new_node);
/* Add it to the queue */
- aystar->OpenListQueue.push(&aystar->OpenListQueue, new_node, f);
+ aystar->OpenListQueue.Push(new_node, f);
}
/*
@@ -136,7 +136,7 @@ static int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNod
check->path.node.user_data[i] = current->user_data[i];
}
/* Readd him in the OpenListQueue */
- aystar->OpenListQueue.push(&aystar->OpenListQueue, check, new_f);
+ aystar->OpenListQueue.Push(check, new_f);
} else {
/* A new node, add him to the OpenList */
AyStarMain_OpenList_Add(aystar, closedlist_parent, current, new_f, new_g);
diff --git a/src/pathfinder/npf/queue.cpp b/src/pathfinder/npf/queue.cpp
index 003cab88d..3ddef3a9c 100644
--- a/src/pathfinder/npf/queue.cpp
+++ b/src/pathfinder/npf/queue.cpp
@@ -27,6 +27,8 @@
* and C with array from 0 to n-1, and we don't like typing
* q->elements[i - 1] every time, we use this define. */
#define BIN_HEAP_ARR(i) q->elements[((i) - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i) - 1) & BINARY_HEAP_BLOCKSIZE_MASK]
+/** Temporary duplicate of #BIN_HEAP_ARR, except it uses 'this' instead of 'q'. */
+#define THISBIN_HEAP_ARR(i) this->elements[((i) - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i) - 1) & BINARY_HEAP_BLOCKSIZE_MASK]
static void BinaryHeap_Clear(Queue *q, bool free_values)
{
@@ -72,29 +74,33 @@ static void BinaryHeap_Free(Queue *q, bool free_values)
free(q->elements);
}
-static bool BinaryHeap_Push(Queue *q, void *item, int priority)
+/**
+ * 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)
{
#ifdef QUEUE_DEBUG
- printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->size);
+ printf("[BinaryHeap] Pushing an element. There are %d elements left\n", this->size);
#endif
- if (q->size == q->max_size) return false;
- assert(q->size < q->max_size);
+ if (this->size == this->max_size) return false;
+ assert(this->size < this->max_size);
- if (q->elements[q->size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {
+ if (this->elements[this->size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {
/* The currently allocated blocks are full, allocate a new one */
- assert((q->size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
- q->elements[q->size >> BINARY_HEAP_BLOCKSIZE_BITS] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
- q->blocks++;
+ assert((this->size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
+ this->elements[this->size >> BINARY_HEAP_BLOCKSIZE_BITS] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
+ this->blocks++;
#ifdef QUEUE_DEBUG
- printf("[BinaryHeap] Increasing size of elements to %d nodes\n", q->blocks * BINARY_HEAP_BLOCKSIZE);
+ printf("[BinaryHeap] Increasing size of elements to %d nodes\n", this->blocks * BINARY_HEAP_BLOCKSIZE);
#endif
}
/* Add the item at the end of the array */
- BIN_HEAP_ARR(q->size + 1).priority = priority;
- BIN_HEAP_ARR(q->size + 1).item = item;
- q->size++;
+ THISBIN_HEAP_ARR(this->size + 1).priority = priority;
+ THISBIN_HEAP_ARR(this->size + 1).item = item;
+ this->size++;
/* Now we are going to check where it belongs. As long as the parent is
* bigger, we switch with the parent */
@@ -103,15 +109,15 @@ static bool BinaryHeap_Push(Queue *q, void *item, int priority)
int i;
int j;
- i = q->size;
+ i = this->size;
while (i > 1) {
/* Get the parent of this object (divide by 2) */
j = i / 2;
/* Is the parent bigger than the current, switch them */
- if (BIN_HEAP_ARR(i).priority <= BIN_HEAP_ARR(j).priority) {
- temp = BIN_HEAP_ARR(j);
- BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);
- BIN_HEAP_ARR(i) = temp;
+ if (THISBIN_HEAP_ARR(i).priority <= THISBIN_HEAP_ARR(j).priority) {
+ temp = THISBIN_HEAP_ARR(j);
+ THISBIN_HEAP_ARR(j) = THISBIN_HEAP_ARR(i);
+ THISBIN_HEAP_ARR(i) = temp;
i = j;
} else {
/* It is not, we're done! */
@@ -203,7 +209,6 @@ static void *BinaryHeap_Pop(Queue *q)
void init_BinaryHeap(Queue *q, uint max_size)
{
assert(q != NULL);
- q->push = BinaryHeap_Push;
q->pop = BinaryHeap_Pop;
q->del = BinaryHeap_Delete;
q->clear = BinaryHeap_Clear;
diff --git a/src/pathfinder/npf/queue.h b/src/pathfinder/npf/queue.h
index b56f6b530..53d4ccad5 100644
--- a/src/pathfinder/npf/queue.h
+++ b/src/pathfinder/npf/queue.h
@@ -19,7 +19,6 @@
struct Queue;
-typedef bool Queue_PushProc(Queue *q, void *item, int priority);
typedef void *Queue_PopProc(Queue *q);
typedef bool Queue_DeleteProc(Queue *q, void *item, int priority);
typedef void Queue_ClearProc(Queue *q, bool free_values);
@@ -32,11 +31,7 @@ struct BinaryHeapNode {
struct Queue {
- /*
- * 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.
- */
- Queue_PushProc *push;
+ bool Push(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.