diff options
author | alberth <alberth@openttd.org> | 2010-08-29 13:32:39 +0000 |
---|---|---|
committer | alberth <alberth@openttd.org> | 2010-08-29 13:32:39 +0000 |
commit | ded2acf02ea8b480a683da6982ecda39de48912e (patch) | |
tree | 12d85402a9ebb4d70c3e4b87f720621b5ce01635 /src/pathfinder | |
parent | fa6203fdc30a0879bcee79087573bba1315e0b62 (diff) | |
download | openttd-ded2acf02ea8b480a683da6982ecda39de48912e.tar.xz |
(svn r20679) -Codechange: Remove unused insertion sorter.
Diffstat (limited to 'src/pathfinder')
-rw-r--r-- | src/pathfinder/npf/queue.cpp | 76 | ||||
-rw-r--r-- | src/pathfinder/npf/queue.h | 18 |
2 files changed, 0 insertions, 94 deletions
diff --git a/src/pathfinder/npf/queue.cpp b/src/pathfinder/npf/queue.cpp index 791cbfe38..8463c2bfc 100644 --- a/src/pathfinder/npf/queue.cpp +++ b/src/pathfinder/npf/queue.cpp @@ -15,82 +15,6 @@ /* - * Insertion Sorter - */ - -static void InsSort_Clear(Queue *q, bool free_values) -{ - InsSortNode *node = q->data.inssort.first; - InsSortNode *prev; - - while (node != NULL) { - if (free_values) free(node->item); - prev = node; - node = node->next; - free(prev); - } - q->data.inssort.first = NULL; -} - -static void InsSort_Free(Queue *q, bool free_values) -{ - q->clear(q, free_values); -} - -static bool InsSort_Push(Queue *q, void *item, int priority) -{ - InsSortNode *newnode = MallocT<InsSortNode>(1); - - newnode->item = item; - newnode->priority = priority; - if (q->data.inssort.first == NULL || - q->data.inssort.first->priority >= priority) { - newnode->next = q->data.inssort.first; - q->data.inssort.first = newnode; - } else { - InsSortNode *node = q->data.inssort.first; - while (node != NULL) { - if (node->next == NULL || node->next->priority >= priority) { - newnode->next = node->next; - node->next = newnode; - break; - } - node = node->next; - } - } - return true; -} - -static void *InsSort_Pop(Queue *q) -{ - InsSortNode *node = q->data.inssort.first; - void *result; - - if (node == NULL) return NULL; - result = node->item; - q->data.inssort.first = q->data.inssort.first->next; - assert(q->data.inssort.first == NULL || q->data.inssort.first->priority >= node->priority); - free(node); - return result; -} - -static bool InsSort_Delete(Queue *q, void *item, int priority) -{ - return false; -} - -void init_InsSort(Queue *q) -{ - q->push = InsSort_Push; - q->pop = InsSort_Pop; - q->del = InsSort_Delete; - q->clear = InsSort_Clear; - q->free = InsSort_Free; - q->data.inssort.first = NULL; -} - - -/* * Binary Heap * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm */ diff --git a/src/pathfinder/npf/queue.h b/src/pathfinder/npf/queue.h index d7a7a7919..31dac0c0a 100644 --- a/src/pathfinder/npf/queue.h +++ b/src/pathfinder/npf/queue.h @@ -25,12 +25,6 @@ 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); -struct InsSortNode { - void *item; - int priority; - InsSortNode *next; -}; - struct BinaryHeapNode { void *item; int priority; @@ -68,9 +62,6 @@ struct Queue { union { struct { - InsSortNode *first; - } inssort; - struct { uint max_size; uint size; uint blocks; ///< The amount of blocks for which space is reserved in elements @@ -80,15 +71,6 @@ struct Queue { }; -/** - * Insertion Sorter - */ - -/* Initializes a inssort and allocates internal memory. There is no maximum - * size */ -void init_InsSort(Queue *q); - - /* * Binary Heap * For information, see: |