01b7789019025581f164106dfaaaa7a56db31f06
2 * @file PriorityQueue.h
5 #ifndef CGDS_PRIORITY_QUEUE_H
6 #define CGDS_PRIORITY_QUEUE_H
11 #include "cgds/Heap.h"
12 #include "cgds/safe_alloc.h"
15 * @brief Priority queue data structure (wrapper around Heap).
17 typedef struct PriorityQueue
{
18 Heap
* heap
; ///< Internal heap.
22 * @brief Return an allocated and initialized Queue.
24 PriorityQueue
* _priorityqueue_new(
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.
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 or min first (MAX_T or MIN_T).
34 * @param arity Arity of the wrapped heap: any integer >=2.
36 * Usage: PriorityQueue* priorityqueue_new(<Type> type, OrderType pType, UInt arity)
38 #define priorityqueue_new(type, pType, arity) \
40 _priorityqueue_new(sizeof(type), pType, arity); \
44 * @brief Copy constructor (shallow copy, ok for basic types).
46 PriorityQueue
* priorityqueue_copy(
47 PriorityQueue
* priorityQueue
///< "this" pointer.
51 * @brief Check if the priority queue is empty.
53 bool priorityqueue_empty(
54 PriorityQueue
* priorityQueue
///< "this" pointer.
58 * @brief Return the size of current priority queue.
60 UInt
priorityqueue_size(
61 PriorityQueue
* priorityQueue
///< "this" pointer.
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.
70 * Usage: void priorityqueue_insert(PriorityQueue* priorityQueue, void item, Real priority)
72 #define priorityqueue_insert(priorityQueue, item, priority) \
73 heap_insert(priorityQueue->heap, item, priority)
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.
82 * Usage: void priorityqueue_set_priority(PriorityQueue* priorityQueue, void item, Real newPriority)
84 #define priorityqueue_set(priorityQueue, item, newPriority) \
85 heap_modify(priorityQueue->heap, item, newPriority)
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.
93 * Usage: void priorityqueue_remove(PriorityQueue* priorityQueue, void item)
95 #define priorityqueue_remove(priorityQueue, item) \
96 heap_remove(priorityQueue->heap, item)
99 * @brief Return what is at the beginning of the queue.
100 * @return An ItemValue* 'iv' with iv->item = data, and iv->value its priority.
102 ItemValue
* priorityqueue_peek_raw(
103 PriorityQueue
* priorityQueue
///< "this" pointer.
107 * @brief Peek the item at the beginning of the queue.
108 * @param priorityQueue "this" pointer.
109 * @param item Item to be assigned.
111 * Usage: void priorityqueue_peek(PriorityQueue* priorityQueue, void item)
113 #define priorityqueue_peek(priorityQueue, item) \
114 heap_top(priorityQueue->heap, item)
117 * @brief Remove the top element in the queue.
119 void priorityqueue_pop(
120 PriorityQueue
* priorityQueue
///< "this" pointer.
124 * @brief Clear the entire queue.
126 void priorityqueue_clear(
127 PriorityQueue
* priorityQueue
///< "this" pointer.
131 * @brief Destroy the queue: clear it and free 'priorityQueue' memory.
133 void priorityqueue_destroy(
134 PriorityQueue
* priorityQueue
///< "this" pointer.