1 #ifndef PRIORITY_QUEUE 2 #define PRIORITY_QUEUE 3 4 #include "fibo.h" 5 6 /* 7 This is the struct for our elements in a PriorityQueue. 8 The node is at first place so we only have to use a cast to switch between QueueElement's pointer and Fibonode's pointer. 9 */ 10 typedef struct QueueElement_ 11 { 12 FiboNode node; /*the node used to insert the element in a FiboTree*/ 13 double key; /*the key of the element, elements are sorted in a descending order according to their key*/ 14 int value; 15 int isInQueue; 16 } QueueElement; 17 18 typedef struct PriorityQueue_ 19 { 20 FiboTree tree; 21 QueueElement ** elements; /*a vector of element with their value as key so we can easily retreive an element from its value */ 22 int size; /*the size allocated to the elements vector*/ 23 } PriorityQueue; 24 25 26 /* 27 PQ_init initiates a PriorityQueue with a size given in argument and sets compFunc as comparison function. Note that you have to allocate memory to the PriorityQueue pointer before calling this function. 28 Returns : 29 0 if success 30 !0 if failed 31 32 PQ_free simply empties the PriorityQueue but does not free the memory used by its elements. 33 PQ_exit destroys the PriorityQueue without freeing elements. The PriorityQueue is no longer usable without using PQ_init again. 34 Note that the PriorityQueue pointer is not deallocated. 35 */ 36 int PQ_init(PriorityQueue * const, int size); 37 void PQ_free(PriorityQueue * const); 38 void PQ_exit(PriorityQueue * const); 39 40 /* 41 PQ_isEmpty returns 1 if the PriorityQueue is empty, 0 otherwise. 42 */ 43 int PQ_isEmpty(PriorityQueue * const); 44 45 /* 46 PQ_insertElement inserts the given QueueElement in the given PriorityQueue 47 */ 48 void PQ_insertElement(PriorityQueue * const, QueueElement * const); 49 /* 50 PQ_deleteElement delete the element given in argument from the PriorityQueue. 51 */ 52 void PQ_deleteElement(PriorityQueue * const, QueueElement * const); 53 54 /* 55 PQ_insert inserts an element in the PriorityQueue with the value and key given in argument. 56 */ 57 void PQ_insert(PriorityQueue * const, int val, double key); 58 /* 59 PQ_delete removes the first element found with the value given in argument and frees it. 60 */ 61 void PQ_delete(PriorityQueue * const, int val); 62 63 64 /* 65 PQ_findMaxElement returns the QueueElement with the greatest key in the given PriorityQueue 66 */ 67 QueueElement * PQ_findMaxElement(PriorityQueue * const); 68 /* 69 PQ_deleteMaxElement returns the QueueElement with the geatest key in the given PriorityQueue and removes it from the queue. 70 */ 71 QueueElement * PQ_deleteMaxElement(PriorityQueue * const); 72 73 /* 74 PQ_findMax returns the key of the element with the geatest key in the given PriorityQueue 75 */ 76 double PQ_findMaxKey(PriorityQueue * const); 77 /* 78 PQ_deleteMax returns the value of the element with the greatest key in the given PriorityQueue and removes it from the queue. 79 */ 80 int PQ_deleteMax(PriorityQueue * const); 81 82 /* 83 PQ_increaseElementKey adds the value of i to the key of the given QueueElement 84 */ 85 void PQ_increaseElementKey(PriorityQueue * const, QueueElement * const, double i); 86 /* 87 PQ_decreaseElementKey substracts the value of i from the key of the given QueueElement 88 */ 89 void PQ_decreaseElementKey(PriorityQueue * const, QueueElement * const, double i); 90 /* 91 PQ_adjustElementKey sets to i the key of the given QueueElement. 92 */ 93 void PQ_adjustElementKey(PriorityQueue * const, QueueElement * const, double i); 94 95 /* 96 PQ_increaseKey adds i to the key of the first element found with a value equal to val in the PriorityQueue. 97 */ 98 void PQ_increaseKey(PriorityQueue * const, int val, double i); 99 /* 100 PQ_decreaseKey substracts i from the key of the first element found with a value equal to val in the PriorityQueue. 101 */ 102 void PQ_decreaseKey(PriorityQueue * const, int val, double i); 103 /* 104 PQ_adjustKey sets to i the key of the first element found with a value equal to val in the PriorityQueue. 105 */ 106 void PQ_adjustKey(PriorityQueue * const, int val, double i); 107 108 #endif /*PRIORITY_QUEUE*/