-
Notifications
You must be signed in to change notification settings - Fork 3
/
priority_queue.h
113 lines (99 loc) · 3.84 KB
/
priority_queue.h
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
* Header priority_queue.h
* Contains definition of a 'priority_queue' structure.
* It is implemented as binary heap. It can contain "unlimited"
* number of items.
* For detailed description see priority_queue.c.
*
* Dialect : ANSI C
* Compiler: any ANSI C-compatible
*
* Copyright (c) 2014 Martin Váňa
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H
/*
* Priority queue.
* Implemented as binary heap.
*/
typedef struct a_priority_queue
{
int (*comparator)( const void *, const void * ); /*
* Comparator is used during restoring heap properties
* (repair_top, repair_bottom)
*/
int min_capacity; /* Minimal capacity which is set during priority queue creation */
int capacity; /* Real capacity */
void **heap_array; /* Array of lenght 'capacity' containing pointers to some items */
int heap_size; /* Number of items in queue */
} priority_queue;
/*
* Creates priority queue with initial capacity.
* Returns priority queue on success, NULL otherwise.
*/
priority_queue *create_priority_queue( const int size, int (*comparator)( const void *, const void * ) );
/*
* Inserts item to the queue.
* Returns TRUE on success, FALSE otherwise.
*/
int priority_queue_insert( priority_queue *pq, void *item );
/*
* Returns pointer to an item on the peek.
* Does not remove item from queue.
*/
void *priority_queue_peek( priority_queue *pq );
/*
* Returns pointer to an item on the peek.
* Does remove item from queue.
*/
void *priority_queue_poll( priority_queue *pq );
/*
* Checks if is the priority queue empty.
* Returns TRUE if queue is empty, FALSE if queue is non empty,
* ERROR_VALUE if queue is uninitialized.
*/
int priority_queue_is_empty( const priority_queue *pq );
/*
* Returns number of items in the priority queue.
* Returns ERROR_VALUE if queue is uninitialized.
*/
int priority_queue_size( const priority_queue *pq );
/*
* Reduces priority queue size to number of inserted items.
* Returns TRUE on success, FALSE otherwise.
*/
int priority_queue_trim_to_size( priority_queue *pq );
/*
* Frees data stores in priority queue using free function.
*/
void free_priority_queue_data( priority_queue **pq, void (*free_function)( void * ) );
/*
* Frees priority queue.
*/
void free_priority_queue( priority_queue **pq );
/*
* Prints content in priority queue as it is stored in array.
*/
void print_priority_queue( const priority_queue *pq, char* (*to_string)( void * ) );
#endif