update
[cgds.git] / src / PriorityQueue.h
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