| 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 |