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(\
  37  *   <Type> type, OrderType pType, UInt arity)
  38  */
  39 #define priorityqueue_new(type, pType, arity) \
  40     _priorityqueue_new(sizeof(type), pType, arity)
  41
  42 /**
  43  * @brief Copy constructor (shallow copy, ok for basic types).
  44  */
  45 PriorityQueue* priorityqueue_copy(
  46     PriorityQueue* priorityQueue ///< "this" pointer.
  47 );
  48
  49 /**
  50  * @brief Check if the priority queue is empty.
  51  */
  52 bool priorityqueue_empty(
  53     PriorityQueue* priorityQueue ///< "this" pointer.
  54 );
  55
  56 /**
  57  * @brief Return the size of current priority queue.
  58  */
  59 UInt priorityqueue_size(
  60     PriorityQueue* priorityQueue ///< "this" pointer.
  61 );
  62
  63 /**
  64  * @brief Add an (item,priority) inside the priority queue.
  65  * @param priorityQueue "this" pointer.
  66  * @param item Item to be added.
  67  * @param priority Priority of the added item.
  68  *
  69  * Usage: void priorityqueue_insert(\
  70  *   PriorityQueue* priorityQueue, void item, Real priority)
  71  */
  72 #define priorityqueue_insert(priorityQueue, item, priority) \
  73     heap_insert(priorityQueue->heap, item, priority)
  74
  75 /**
  76  * @brief Change the priority of an item in the queue.
  77  * @param priorityQueue "this" pointer.
  78  * @param item Item to be modified.
  79  * @param newPriority New priority of the modified item.
  80  * @note If several similar items are present, only the first is affected.
  81  *
  82  * Usage: void priorityqueue_set_priority(\
  83  *   PriorityQueue* priorityQueue, void item, Real newPriority)
  84  */
  85 #define priorityqueue_set(priorityQueue, item, newPriority) \
  86     heap_modify(priorityQueue->heap, item, newPriority)
  87
  88 /**
  89  * @brief Remove an item in the queue.
  90  * @param priorityQueue "this" pointer.
  91  * @param item Item to be removed.
  92  * @note If several similar items are present, only the first is deleted.
  93  *
  94  * Usage: void priorityqueue_remove(PriorityQueue* priorityQueue, void item)
  95  */
  96 #define priorityqueue_remove(priorityQueue, item) \
  97     heap_remove(priorityQueue->heap, item)
  98
  99 /**
 100  * @brief Return what is at the beginning of the queue.
 101  * @return An ItemValue* 'iv' with iv->item = data, and iv->value its priority.
 102  */
 103 ItemValue* priorityqueue_peek_raw(
 104     PriorityQueue* priorityQueue ///< "this" pointer.
 105 );
 106
 107 /**
 108  * @brief Peek the item at the beginning of the queue.
 109  * @param priorityQueue "this" pointer.
 110  * @param item Item to be assigned.
 111  *
 112  * Usage: void priorityqueue_peek(PriorityQueue* priorityQueue, void item)
 113  */
 114 #define priorityqueue_peek(priorityQueue, item) \
 115     heap_top(priorityQueue->heap, item)
 116
 117 /**
 118  * @brief Remove the top element in the queue.
 119  */
 120 void priorityqueue_pop(
 121     PriorityQueue* priorityQueue ///< "this" pointer.
 122 );
 123
 124 /**
 125  * @brief Clear the entire queue.
 126  */
 127 void priorityqueue_clear(
 128     PriorityQueue* priorityQueue ///< "this" pointer.
 129 );
 130
 131 /**
 132  * @brief Destroy the queue: clear it and free 'priorityQueue' memory.
 133  */
 134 void priorityqueue_destroy(
 135     PriorityQueue* priorityQueue ///< "this" pointer.
 136 );
 137
 138 #endif