File: pqueue.h

package info (click to toggle)
ufoai 2.5-4
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 82,128 kB
  • sloc: cpp: 225,227; python: 5,111; ansic: 4,133; php: 2,209; perl: 1,931; sh: 1,517; xml: 1,115; makefile: 401; sed: 11
file content (50 lines) | stat: -rw-r--r-- 1,312 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * @file
 * @brief Header file for the priority queue implementation.
 */

/*
Originally written by Justin-Heyes Jones
Modified by Shlomi Fish, 2000
Modified by Florian Festi, 2007

This file is in the public domain (it's uncopyrighted).

Check out Justin-Heyes Jones' A* page from which this code has
originated:
	http://www.geocities.com/jheyesjones/astar.html
*/

#pragma once

#include "../shared/shared.h"

/** @defgroup pqueue Priority Queue (priorityQueue_t)
 * @ingroup datastructure
 * Implementation of a priority queue by using a binary heap. Manage a priority
 * queue as a heap - the heap is implemented as an array.
 */

typedef int priorityQueueRating_t;

typedef struct priorityQueueElement_s {
	pos4_t item;
	priorityQueueRating_t rating;
} priorityQueueElement_t;

/**
 * @brief the priority queue struct
 * the actual data is stored in @c priorityQueueElement_t
 */
typedef struct priorityQueue_s {
	uint32_t maxSize;
	uint32_t currentSize;
	priorityQueueElement_t* elements;
} priorityQueue_t;

void PQueueInitialise(priorityQueue_t* pq, uint32_t maxElements);
void PQueueFree(priorityQueue_t* pq);

#define PQueueIsEmpty(pq) ((pq)->currentSize == 0)
void PQueuePush(priorityQueue_t* pq, const pos4_t item, priorityQueueRating_t rating);
void PQueuePop(priorityQueue_t* pq, pos4_t item);