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 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  */
  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 = data, and iv.value its priority.
  99  */
 100 ItemValue _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  */
 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