Some fixes + improvements (Vector) + code reformatting
[cgds.git] / src / PriorityQueue.h
... / ...
CommitLineData
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 */
17typedef struct PriorityQueue {
18 Heap* heap; ///< Internal heap.
19} PriorityQueue;
20
21/**
22 * @brief Return an allocated and initialized Queue.
23 */
24PriorityQueue* _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.
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 or min first (MAX_T or 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 (shallow copy, ok for basic types).
43 */
44PriorityQueue* priorityqueue_copy(
45 PriorityQueue* priorityQueue ///< "this" pointer.
46);
47
48/**
49 * @brief Check if the priority queue is empty.
50 */
51bool priorityqueue_empty(
52 PriorityQueue* priorityQueue ///< "this" pointer.
53);
54
55/**
56 * @brief Return the size of current priority queue.
57 */
58UInt 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 = data, and iv.value its priority.
99 */
100ItemValue _priorityqueue_peek(
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 */
117void priorityqueue_pop(
118 PriorityQueue* priorityQueue ///< "this" pointer.
119);
120
121/**
122 * @brief Clear the entire queue.
123 */
124void priorityqueue_clear(
125 PriorityQueue* priorityQueue ///< "this" pointer.
126);
127
128/**
129 * @brief Destroy the queue: clear it and free 'priorityQueue' memory.
130 */
131void priorityqueue_destroy(
132 PriorityQueue* priorityQueue ///< "this" pointer.
133);
134
135#endif