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