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