diff options
author | alberth <alberth@openttd.org> | 2010-08-29 13:35:51 +0000 |
---|---|---|
committer | alberth <alberth@openttd.org> | 2010-08-29 13:35:51 +0000 |
commit | 92801ac718a2bb735aac91c869239967a9cee7fc (patch) | |
tree | b23e35967857504ebce54ad93609f7cf4805630f /src | |
parent | 68e2a07479f1aed8ad0a8fe2f72e7affcf0f9427 (diff) | |
download | openttd-92801ac718a2bb735aac91c869239967a9cee7fc.tar.xz |
(svn r20681) -Codechange: Make BinaryHeap_Push() a method, introduce temporary THISBIN_HEAP_ARR macro.
Diffstat (limited to 'src')
-rw-r--r-- | src/pathfinder/npf/aystar.cpp | 4 | ||||
-rw-r--r-- | src/pathfinder/npf/queue.cpp | 41 | ||||
-rw-r--r-- | src/pathfinder/npf/queue.h | 7 |
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. |