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 first (hType==MAX_T) or min first (hType==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 first (hType==MAX_T) or min first (hType==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) \
39 _priorityqueue_new(sizeof(type), pType, arity)
42 * @brief Copy constructor (works well if items do not have allocated sub-pointers).
44 PriorityQueue
* priorityqueue_copy(
45 PriorityQueue
* priorityQueue
///< "this" pointer.
49 * @brief Check if the priority queue is empty.
51 Bool
priorityqueue_empty(
52 PriorityQueue
* priorityQueue
///< "this" pointer.
56 * @brief Return the size of current priority queue.
58 UInt
priorityqueue_size(
59 PriorityQueue
* priorityQueue
///< "this" pointer.
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.
68 * Usage: void priorityqueue_insert(PriorityQueue* priorityQueue, void item, Real priority)
70 #define priorityqueue_insert(priorityQueue, item, priority) \
71 heap_insert(priorityQueue->heap, item, priority)
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.
80 * Usage: void priorityqueue_set_priority(PriorityQueue* priorityQueue, void item, Real newPriority)
82 #define priorityqueue_set(priorityQueue, item, newPriority) \
83 heap_modify(priorityQueue->heap, item, newPriority)
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.
91 * Usage: void priorityqueue_remove(PriorityQueue* priorityQueue, void item)
93 #define priorityqueue_remove(priorityQueue, item) \
94 heap_remove(priorityQueue->heap, item)
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.
100 ItemValue
* priorityqueue_peek_raw(
101 PriorityQueue
* priorityQueue
///< "this" pointer.
105 * @brief Peek the item at the beginning of the queue.
106 * @param priorityQueue "this" pointer.
107 * @param item Item to be assigned.
109 * Usage: void priorityqueue_peek(PriorityQueue* priorityQueue, void item)
111 #define priorityqueue_peek(priorityQueue, item) \
112 heap_top(priorityQueue->heap, item)
115 * @brief Remove the top element in the queue.
117 void priorityqueue_pop(
118 PriorityQueue
* priorityQueue
///< "this" pointer.
122 * @brief Clear the entire queue.
124 void priorityqueue_clear(
125 PriorityQueue
* priorityQueue
///< "this" pointer.
129 * @brief Destroy the queue: clear it and free 'priorityQueue' memory.
131 void priorityqueue_destroy(
132 PriorityQueue
* priorityQueue
///< "this" pointer.