1 /*! 2 \file gk_mkpqueue2.h 3 \brief Templates for priority queues that do not utilize locators and as such 4 they can use different types of values. 5 6 \date Started 4/09/07 7 \author George 8 */ 9 10 11 #ifndef _GK_MKPQUEUE2_H 12 #define _GK_MKPQUEUE2_H 13 14 15 #define GK_MKPQUEUE2(FPRFX, PQT, KT, VT, KMALLOC, VMALLOC, KMAX, KEY_LT)\ 16 /*************************************************************************/\ 17 /*! This function creates and initializes a priority queue */\ 18 /**************************************************************************/\ 19 PQT *FPRFX ## Create2(ssize_t maxnodes)\ 20 {\ 21 PQT *queue; \ 22 \ 23 if ((queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate2: queue")) != NULL) {\ 24 memset(queue, 0, sizeof(PQT));\ 25 queue->nnodes = 0;\ 26 queue->maxnodes = maxnodes;\ 27 queue->keys = KMALLOC(maxnodes, "gk_pqCreate2: keys");\ 28 queue->vals = VMALLOC(maxnodes, "gk_pqCreate2: vals");\ 29 \ 30 if (queue->keys == NULL || queue->vals == NULL)\ 31 gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\ 32 }\ 33 \ 34 return queue;\ 35 }\ 36 \ 37 \ 38 /*************************************************************************/\ 39 /*! This function resets the priority queue */\ 40 /**************************************************************************/\ 41 void FPRFX ## Reset2(PQT *queue)\ 42 {\ 43 queue->nnodes = 0;\ 44 }\ 45 \ 46 \ 47 /*************************************************************************/\ 48 /*! This function frees the internal datastructures of the priority queue */\ 49 /**************************************************************************/\ 50 void FPRFX ## Destroy2(PQT **r_queue)\ 51 {\ 52 PQT *queue = *r_queue; \ 53 if (queue == NULL) return;\ 54 gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\ 55 *r_queue = NULL;\ 56 }\ 57 \ 58 \ 59 /*************************************************************************/\ 60 /*! This function returns the length of the queue */\ 61 /**************************************************************************/\ 62 size_t FPRFX ## Length2(PQT *queue)\ 63 {\ 64 return queue->nnodes;\ 65 }\ 66 \ 67 \ 68 /*************************************************************************/\ 69 /*! This function adds an item in the priority queue. */\ 70 /**************************************************************************/\ 71 int FPRFX ## Insert2(PQT *queue, VT val, KT key)\ 72 {\ 73 ssize_t i, j;\ 74 KT *keys=queue->keys;\ 75 VT *vals=queue->vals;\ 76 \ 77 ASSERT2(FPRFX ## CheckHeap2(queue));\ 78 \ 79 if (queue->nnodes == queue->maxnodes) \ 80 return 0;\ 81 \ 82 ASSERT2(FPRFX ## CheckHeap2(queue));\ 83 \ 84 i = queue->nnodes++;\ 85 while (i > 0) {\ 86 j = (i-1)>>1;\ 87 if (KEY_LT(key, keys[j])) {\ 88 keys[i] = keys[j];\ 89 vals[i] = vals[j];\ 90 i = j;\ 91 }\ 92 else\ 93 break;\ 94 }\ 95 ASSERT(i >= 0);\ 96 keys[i] = key;\ 97 vals[i] = val;\ 98 \ 99 ASSERT2(FPRFX ## CheckHeap2(queue));\ 100 \ 101 return 1;\ 102 }\ 103 \ 104 \ 105 /*************************************************************************/\ 106 /*! This function returns the item at the top of the queue and removes\ 107 it from the priority queue */\ 108 /**************************************************************************/\ 109 int FPRFX ## GetTop2(PQT *queue, VT *r_val)\ 110 {\ 111 ssize_t i, j;\ 112 KT key, *keys=queue->keys;\ 113 VT val, *vals=queue->vals;\ 114 \ 115 ASSERT2(FPRFX ## CheckHeap2(queue));\ 116 \ 117 if (queue->nnodes == 0)\ 118 return 0;\ 119 \ 120 queue->nnodes--;\ 121 \ 122 *r_val = vals[0];\ 123 \ 124 if ((i = queue->nnodes) > 0) {\ 125 key = keys[i];\ 126 val = vals[i];\ 127 i = 0;\ 128 while ((j=2*i+1) < queue->nnodes) {\ 129 if (KEY_LT(keys[j], key)) {\ 130 if (j+1 < queue->nnodes && KEY_LT(keys[j+1], keys[j]))\ 131 j = j+1;\ 132 keys[i] = keys[j];\ 133 vals[i] = vals[j];\ 134 i = j;\ 135 }\ 136 else if (j+1 < queue->nnodes && KEY_LT(keys[j+1], key)) {\ 137 j = j+1;\ 138 keys[i] = keys[j];\ 139 vals[i] = vals[j];\ 140 i = j;\ 141 }\ 142 else\ 143 break;\ 144 }\ 145 \ 146 keys[i] = key;\ 147 vals[i] = val;\ 148 }\ 149 \ 150 ASSERT2(FPRFX ## CheckHeap2(queue));\ 151 \ 152 return 1;\ 153 }\ 154 \ 155 \ 156 /*************************************************************************/\ 157 /*! This function returns the item at the top of the queue. The item is not\ 158 deleted from the queue. */\ 159 /**************************************************************************/\ 160 int FPRFX ## SeeTopVal2(PQT *queue, VT *r_val)\ 161 {\ 162 if (queue->nnodes == 0) \ 163 return 0;\ 164 \ 165 *r_val = queue->vals[0];\ 166 \ 167 return 1;\ 168 }\ 169 \ 170 \ 171 /*************************************************************************/\ 172 /*! This function returns the key of the top item. The item is not\ 173 deleted from the queue. */\ 174 /**************************************************************************/\ 175 KT FPRFX ## SeeTopKey2(PQT *queue)\ 176 {\ 177 return (queue->nnodes == 0 ? KMAX : queue->keys[0]);\ 178 }\ 179 \ 180 \ 181 /*************************************************************************/\ 182 /*! This functions checks the consistency of the heap */\ 183 /**************************************************************************/\ 184 int FPRFX ## CheckHeap2(PQT *queue)\ 185 {\ 186 ssize_t i;\ 187 KT *keys=queue->keys;\ 188 \ 189 if (queue->nnodes == 0)\ 190 return 1;\ 191 \ 192 for (i=1; i<queue->nnodes; i++) {\ 193 ASSERT(!KEY_LT(keys[i], keys[(i-1)/2]));\ 194 }\ 195 for (i=1; i<queue->nnodes; i++)\ 196 ASSERT(!KEY_LT(keys[i], keys[0]));\ 197 \ 198 return 1;\ 199 }\ 200 201 202 #define GK_MKPQUEUE2_PROTO(FPRFX, PQT, KT, VT)\ 203 PQT * FPRFX ## Create2(ssize_t maxnodes);\ 204 void FPRFX ## Reset2(PQT *queue);\ 205 void FPRFX ## Destroy2(PQT **r_queue);\ 206 size_t FPRFX ## Length2(PQT *queue);\ 207 int FPRFX ## Insert2(PQT *queue, VT node, KT key);\ 208 int FPRFX ## GetTop2(PQT *queue, VT *r_val);\ 209 int FPRFX ## SeeTopVal2(PQT *queue, VT *r_val);\ 210 KT FPRFX ## SeeTopKey2(PQT *queue);\ 211 int FPRFX ## CheckHeap2(PQT *queue);\ 212 213 214 #endif 215