Add basic Set implementation - TODO: add iterators for Set and HashTable
[cgds.git] / src / PriorityQueue.h
CommitLineData
a7868768
BA
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 {
e45132ac 18 Heap* heap; ///< Internal heap.
a7868768
BA
19} PriorityQueue;
20
21/**
22 * @brief Return an allocated and initialized Queue.
23 */
24PriorityQueue* _priorityqueue_new(
e45132ac
BA
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.
a7868768
BA
28);
29
30/**
31 * @brief Return an allocated and initialized Queue.
32 * @param type Type of a priority queue item (int, char*, ...).
1ff641f9 33 * @param pType type of priority queue: max or min first (MAX_T or MIN_T).
a7868768 34 * @param arity Arity of the wrapped heap: any integer >=2.
1ff641f9 35 *
e45132ac 36 * Usage: PriorityQueue* priorityqueue_new(<Type> type, OrderType pType, UInt arity)
a7868768
BA
37 */
38#define priorityqueue_new(type, pType, arity) \
eed1b5d2 39 _priorityqueue_new(sizeof(type), pType, arity)
a7868768
BA
40
41/**
1ff641f9 42 * @brief Copy constructor (shallow copy, ok for basic types).
a7868768
BA
43 */
44PriorityQueue* priorityqueue_copy(
e45132ac 45 PriorityQueue* priorityQueue ///< "this" pointer.
a7868768
BA
46);
47
48/**
49 * @brief Check if the priority queue is empty.
50 */
1ff641f9 51bool priorityqueue_empty(
e45132ac 52 PriorityQueue* priorityQueue ///< "this" pointer.
a7868768
BA
53);
54
55/**
56 * @brief Return the size of current priority queue.
57 */
58UInt priorityqueue_size(
e45132ac 59 PriorityQueue* priorityQueue ///< "this" pointer.
a7868768
BA
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.
1ff641f9 67 *
e45132ac 68 * Usage: void priorityqueue_insert(PriorityQueue* priorityQueue, void item, Real priority)
a7868768
BA
69 */
70#define priorityqueue_insert(priorityQueue, item, priority) \
e45132ac 71 heap_insert(priorityQueue->heap, item, priority)
a7868768
BA
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.
1ff641f9 79 *
e45132ac 80 * Usage: void priorityqueue_set_priority(PriorityQueue* priorityQueue, void item, Real newPriority)
a7868768
BA
81 */
82#define priorityqueue_set(priorityQueue, item, newPriority) \
e45132ac 83 heap_modify(priorityQueue->heap, item, newPriority)
a7868768
BA
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.
1ff641f9 90 *
a7868768
BA
91 * Usage: void priorityqueue_remove(PriorityQueue* priorityQueue, void item)
92 */
93#define priorityqueue_remove(priorityQueue, item) \
e45132ac 94 heap_remove(priorityQueue->heap, item)
a7868768
BA
95
96/**
97 * @brief Return what is at the beginning of the queue.
1ff641f9 98 * @return An ItemValue* 'iv' with iv->item = data, and iv->value its priority.
a7868768
BA
99 */
100ItemValue* priorityqueue_peek_raw(
e45132ac 101 PriorityQueue* priorityQueue ///< "this" pointer.
a7868768
BA
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.
1ff641f9 108 *
a7868768
BA
109 * Usage: void priorityqueue_peek(PriorityQueue* priorityQueue, void item)
110 */
111#define priorityqueue_peek(priorityQueue, item) \
e45132ac 112 heap_top(priorityQueue->heap, item)
a7868768
BA
113
114/**
115 * @brief Remove the top element in the queue.
116 */
117void priorityqueue_pop(
e45132ac 118 PriorityQueue* priorityQueue ///< "this" pointer.
a7868768
BA
119);
120
1ff641f9 121/**
a7868768
BA
122 * @brief Clear the entire queue.
123 */
124void priorityqueue_clear(
e45132ac 125 PriorityQueue* priorityQueue ///< "this" pointer.
a7868768
BA
126);
127
128/**
129 * @brief Destroy the queue: clear it and free 'priorityQueue' memory.
130 */
131void priorityqueue_destroy(
e45132ac 132 PriorityQueue* priorityQueue ///< "this" pointer.
a7868768
BA
133);
134
135#endif