summaryrefslogtreecommitdiff
path: root/src/pathfinder/npf
diff options
context:
space:
mode:
authoralberth <alberth@openttd.org>2010-08-29 13:38:06 +0000
committeralberth <alberth@openttd.org>2010-08-29 13:38:06 +0000
commit3f0cd8c9f0e3b1da2383f09fac1e4a18e782968e (patch)
tree02e34f909dd537de180917e7a49bb949da8f5720 /src/pathfinder/npf
parent10b182482e20f56c4a73a98f4578b03d0ff2c2b9 (diff)
downloadopenttd-3f0cd8c9f0e3b1da2383f09fac1e4a18e782968e.tar.xz
(svn r20683) -Codechange: Make BinaryHeap_Delete() a method.
Diffstat (limited to 'src/pathfinder/npf')
-rw-r--r--src/pathfinder/npf/aystar.cpp2
-rw-r--r--src/pathfinder/npf/queue.cpp38
-rw-r--r--src/pathfinder/npf/queue.h8
3 files changed, 23 insertions, 25 deletions
diff --git a/src/pathfinder/npf/aystar.cpp b/src/pathfinder/npf/aystar.cpp
index 1a651a740..4b0485bc0 100644
--- a/src/pathfinder/npf/aystar.cpp
+++ b/src/pathfinder/npf/aystar.cpp
@@ -127,7 +127,7 @@ static int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNod
uint i;
/* Yes, check if this g value is lower.. */
if (new_g > check->g) return AYSTAR_DONE;
- aystar->OpenListQueue.del(&aystar->OpenListQueue, check, 0);
+ aystar->OpenListQueue.Delete(check, 0);
/* It is lower, so change it to this item */
check->g = new_g;
check->path.parent = closedlist_parent;
diff --git a/src/pathfinder/npf/queue.cpp b/src/pathfinder/npf/queue.cpp
index 09885411b..a9fdadcb6 100644
--- a/src/pathfinder/npf/queue.cpp
+++ b/src/pathfinder/npf/queue.cpp
@@ -129,25 +129,30 @@ bool Queue::Push(void *item, int priority)
return true;
}
-static bool BinaryHeap_Delete(Queue *q, void *item, int priority)
+/**
+ * Deletes the item from the queue. priority should be specified if
+ * known, which speeds up the deleting for some queue's. Should be -1
+ * if not known.
+ */
+bool Queue::Delete(void *item, int priority)
{
uint i = 0;
#ifdef QUEUE_DEBUG
- printf("[BinaryHeap] Deleting an element. There are %d elements left\n", q->size);
+ printf("[BinaryHeap] Deleting an element. There are %d elements left\n", this->size);
#endif
/* First, we try to find the item.. */
do {
- if (BIN_HEAP_ARR(i + 1).item == item) break;
+ if (THISBIN_HEAP_ARR(i + 1).item == item) break;
i++;
- } while (i < q->size);
+ } while (i < this->size);
/* We did not find the item, so we return false */
- if (i == q->size) return false;
+ if (i == this->size) return false;
/* Now we put the last item over the current item while decreasing the size of the elements */
- q->size--;
- BIN_HEAP_ARR(i + 1) = BIN_HEAP_ARR(q->size + 1);
+ this->size--;
+ THISBIN_HEAP_ARR(i + 1) = THISBIN_HEAP_ARR(this->size + 1);
/* Now the only thing we have to do, is resort it..
* On place i there is the item to be sorted.. let's start there */
@@ -162,22 +167,22 @@ static bool BinaryHeap_Delete(Queue *q, void *item, int priority)
for (;;) {
j = i;
/* Check if we have 2 childs */
- if (2 * j + 1 <= q->size) {
+ if (2 * j + 1 <= this->size) {
/* Is this child smaller than the parent? */
- if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j;
+ if (THISBIN_HEAP_ARR(j).priority >= THISBIN_HEAP_ARR(2 * j).priority) i = 2 * j;
/* Yes, we _need_ to use i here, not j, because we want to have the smallest child
* This way we get that straight away! */
- if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2 * j + 1).priority) i = 2 * j + 1;
+ if (THISBIN_HEAP_ARR(i).priority >= THISBIN_HEAP_ARR(2 * j + 1).priority) i = 2 * j + 1;
/* Do we have one child? */
- } else if (2 * j <= q->size) {
- if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j;
+ } else if (2 * j <= this->size) {
+ if (THISBIN_HEAP_ARR(j).priority >= THISBIN_HEAP_ARR(2 * j).priority) i = 2 * j;
}
/* One of our childs is smaller than we are, switch */
if (i != j) {
- temp = BIN_HEAP_ARR(j);
- BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);
- BIN_HEAP_ARR(i) = temp;
+ temp = THISBIN_HEAP_ARR(j);
+ THISBIN_HEAP_ARR(j) = THISBIN_HEAP_ARR(i);
+ THISBIN_HEAP_ARR(i) = temp;
} else {
/* None of our childs is smaller, so we stay here.. stop :) */
break;
@@ -205,7 +210,7 @@ void *Queue::Pop()
/* The best item is always on top, so give that as result */
result = THISBIN_HEAP_ARR(1).item;
/* And now we should get rid of this item... */
- BinaryHeap_Delete(this, THISBIN_HEAP_ARR(1).item, THISBIN_HEAP_ARR(1).priority);
+ this->Delete(THISBIN_HEAP_ARR(1).item, THISBIN_HEAP_ARR(1).priority);
return result;
}
@@ -213,7 +218,6 @@ void *Queue::Pop()
void init_BinaryHeap(Queue *q, uint max_size)
{
assert(q != NULL);
- q->del = BinaryHeap_Delete;
q->clear = BinaryHeap_Clear;
q->free = BinaryHeap_Free;
q->max_size = max_size;
diff --git a/src/pathfinder/npf/queue.h b/src/pathfinder/npf/queue.h
index c65897dcf..766ecbf38 100644
--- a/src/pathfinder/npf/queue.h
+++ b/src/pathfinder/npf/queue.h
@@ -19,7 +19,6 @@
struct Queue;
-typedef bool Queue_DeleteProc(Queue *q, void *item, int priority);
typedef void Queue_ClearProc(Queue *q, bool free_values);
typedef void Queue_FreeProc(Queue *q, bool free_values);
@@ -32,12 +31,7 @@ struct BinaryHeapNode {
struct Queue {
bool Push(void *item, int priority);
void *Pop();
- /*
- * Deletes the item from the queue. priority should be specified if
- * known, which speeds up the deleting for some queue's. Should be -1
- * if not known.
- */
- Queue_DeleteProc *del;
+ bool Delete(void *item, int priority);
/* Clears the queue, by removing all values from it. Its state is
* effectively reset. If free_items is true, each of the items cleared