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