Commit | Line | Data |
---|---|---|
a7868768 BA |
1 | /** |
2 | * @file PriorityQueue.h | |
3 | */ | |
4 | ||
5 | #ifndef CGDS_PRIORITY_QUEUE_H | |
6 | #define CGDS_PRIORITY_QUEUE_H | |
7 | ||
8 | #include <stdlib.h> | |
9 | #include <string.h> | |
10 | #include "types.h" | |
11 | #include "cgds/Heap.h" | |
12 | #include "cgds/safe_alloc.h" | |
13 | ||
14 | /** | |
15 | * @brief Priority queue data structure (wrapper around Heap). | |
16 | */ | |
17 | typedef struct PriorityQueue { | |
e45132ac | 18 | Heap* heap; ///< Internal heap. |
a7868768 BA |
19 | } PriorityQueue; |
20 | ||
21 | /** | |
22 | * @brief Return an allocated and initialized Queue. | |
23 | */ | |
24 | PriorityQueue* _priorityqueue_new( | |
e45132ac BA |
25 | size_t dataSize, ///< Size in bytes of a priority queue element. |
26 | OrderType pType, ///< Type of priority queue: max or min first (MAX_T or MIN_T). | |
27 | UInt arity ///< Arity of the wrapped heap: any integer >=2. | |
a7868768 BA |
28 | ); |
29 | ||
30 | /** | |
31 | * @brief Return an allocated and initialized Queue. | |
32 | * @param type Type of a priority queue item (int, char*, ...). | |
1ff641f9 | 33 | * @param pType type of priority queue: max or min first (MAX_T or MIN_T). |
a7868768 | 34 | * @param arity Arity of the wrapped heap: any integer >=2. |
1ff641f9 | 35 | * |
e45132ac | 36 | * Usage: PriorityQueue* priorityqueue_new(<Type> type, OrderType pType, UInt arity) |
a7868768 BA |
37 | */ |
38 | #define priorityqueue_new(type, pType, arity) \ | |
e45132ac BA |
39 | { \ |
40 | _priorityqueue_new(sizeof(type), pType, arity); \ | |
41 | } | |
a7868768 BA |
42 | |
43 | /** | |
1ff641f9 | 44 | * @brief Copy constructor (shallow copy, ok for basic types). |
a7868768 BA |
45 | */ |
46 | PriorityQueue* priorityqueue_copy( | |
e45132ac | 47 | PriorityQueue* priorityQueue ///< "this" pointer. |
a7868768 BA |
48 | ); |
49 | ||
50 | /** | |
51 | * @brief Check if the priority queue is empty. | |
52 | */ | |
1ff641f9 | 53 | bool priorityqueue_empty( |
e45132ac | 54 | PriorityQueue* priorityQueue ///< "this" pointer. |
a7868768 BA |
55 | ); |
56 | ||
57 | /** | |
58 | * @brief Return the size of current priority queue. | |
59 | */ | |
60 | UInt priorityqueue_size( | |
e45132ac | 61 | PriorityQueue* priorityQueue ///< "this" pointer. |
a7868768 BA |
62 | ); |
63 | ||
64 | /** | |
65 | * @brief Add an (item,priority) inside the priority queue. | |
66 | * @param priorityQueue "this" pointer. | |
67 | * @param item Item to be added. | |
68 | * @param priority Priority of the added item. | |
1ff641f9 | 69 | * |
e45132ac | 70 | * Usage: void priorityqueue_insert(PriorityQueue* priorityQueue, void item, Real priority) |
a7868768 BA |
71 | */ |
72 | #define priorityqueue_insert(priorityQueue, item, priority) \ | |
e45132ac | 73 | heap_insert(priorityQueue->heap, item, priority) |
a7868768 BA |
74 | |
75 | /** | |
76 | * @brief Change the priority of an item in the queue. | |
77 | * @param priorityQueue "this" pointer. | |
78 | * @param item Item to be modified. | |
79 | * @param newPriority New priority of the modified item. | |
80 | * @note If several similar items are present, only the first is affected. | |
1ff641f9 | 81 | * |
e45132ac | 82 | * Usage: void priorityqueue_set_priority(PriorityQueue* priorityQueue, void item, Real newPriority) |
a7868768 BA |
83 | */ |
84 | #define priorityqueue_set(priorityQueue, item, newPriority) \ | |
e45132ac | 85 | heap_modify(priorityQueue->heap, item, newPriority) |
a7868768 BA |
86 | |
87 | /** | |
88 | * @brief Remove an item in the queue. | |
89 | * @param priorityQueue "this" pointer. | |
90 | * @param item Item to be removed. | |
91 | * @note If several similar items are present, only the first is deleted. | |
1ff641f9 | 92 | * |
a7868768 BA |
93 | * Usage: void priorityqueue_remove(PriorityQueue* priorityQueue, void item) |
94 | */ | |
95 | #define priorityqueue_remove(priorityQueue, item) \ | |
e45132ac | 96 | heap_remove(priorityQueue->heap, item) |
a7868768 BA |
97 | |
98 | /** | |
99 | * @brief Return what is at the beginning of the queue. | |
1ff641f9 | 100 | * @return An ItemValue* 'iv' with iv->item = data, and iv->value its priority. |
a7868768 BA |
101 | */ |
102 | ItemValue* priorityqueue_peek_raw( | |
e45132ac | 103 | PriorityQueue* priorityQueue ///< "this" pointer. |
a7868768 BA |
104 | ); |
105 | ||
106 | /** | |
107 | * @brief Peek the item at the beginning of the queue. | |
108 | * @param priorityQueue "this" pointer. | |
109 | * @param item Item to be assigned. | |
1ff641f9 | 110 | * |
a7868768 BA |
111 | * Usage: void priorityqueue_peek(PriorityQueue* priorityQueue, void item) |
112 | */ | |
113 | #define priorityqueue_peek(priorityQueue, item) \ | |
e45132ac | 114 | heap_top(priorityQueue->heap, item) |
a7868768 BA |
115 | |
116 | /** | |
117 | * @brief Remove the top element in the queue. | |
118 | */ | |
119 | void priorityqueue_pop( | |
e45132ac | 120 | PriorityQueue* priorityQueue ///< "this" pointer. |
a7868768 BA |
121 | ); |
122 | ||
1ff641f9 | 123 | /** |
a7868768 BA |
124 | * @brief Clear the entire queue. |
125 | */ | |
126 | void priorityqueue_clear( | |
e45132ac | 127 | PriorityQueue* priorityQueue ///< "this" pointer. |
a7868768 BA |
128 | ); |
129 | ||
130 | /** | |
131 | * @brief Destroy the queue: clear it and free 'priorityQueue' memory. | |
132 | */ | |
133 | void priorityqueue_destroy( | |
e45132ac | 134 | PriorityQueue* priorityQueue ///< "this" pointer. |
a7868768 BA |
135 | ); |
136 | ||
137 | #endif |