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