1 /** 2 * @file 3 * @brief Header file for the priority queue implementation. 4 */ 5 6 /* 7 Originally written by Justin-Heyes Jones 8 Modified by Shlomi Fish, 2000 9 Modified by Florian Festi, 2007 10 11 This file is in the public domain (it's uncopyrighted). 12 13 Check out Justin-Heyes Jones' A* page from which this code has 14 originated: 15 http://www.geocities.com/jheyesjones/astar.html 16 */ 17 18 #pragma once 19 20 #include "../shared/shared.h" 21 22 /** @defgroup pqueue Priority Queue (priorityQueue_t) 23 * @ingroup datastructure 24 * Implementation of a priority queue by using a binary heap. Manage a priority 25 * queue as a heap - the heap is implemented as an array. 26 */ 27 28 typedef int priorityQueueRating_t; 29 30 typedef struct priorityQueueElement_s { 31 pos4_t item; 32 priorityQueueRating_t rating; 33 } priorityQueueElement_t; 34 35 /** 36 * @brief the priority queue struct 37 * the actual data is stored in @c priorityQueueElement_t 38 */ 39 typedef struct priorityQueue_s { 40 uint32_t maxSize; 41 uint32_t currentSize; 42 priorityQueueElement_t* elements; 43 } priorityQueue_t; 44 45 void PQueueInitialise(priorityQueue_t* pq, uint32_t maxElements); 46 void PQueueFree(priorityQueue_t* pq); 47 48 #define PQueueIsEmpty(pq) ((pq)->currentSize == 0) 49 void PQueuePush(priorityQueue_t* pq, const pos4_t item, priorityQueueRating_t rating); 50 void PQueuePop(priorityQueue_t* pq, pos4_t item); 51