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