srcs/toolbox/pqueue.c
00001
00002
00003
00004
00005 #include <toolbox/carpal.h>
00006 #include <toolbox/misc.h>
00007 #include <toolbox/pqueue.h>
00008
00009 typedef struct u_pq_item_s
00010 {
00011 double key;
00012 void *val;
00013 } u_pq_item_t;
00014
00015 struct u_pq_s
00016 {
00017 size_t nelems, nitems;
00018 u_pq_item_t *q;
00019 };
00020
00021 static int pq_item_comp (u_pq_item_t *pi, u_pq_item_t *pj);
00022 static void pq_item_swap (u_pq_item_t *pi, u_pq_item_t *pj);
00023 static void bubble_up (u_pq_item_t *pi, size_t k);
00024 static void bubble_down (u_pq_item_t *pi, size_t k, size_t n);
00025
00089 int u_pq_create (size_t nitems, u_pq_t **ppq)
00090 {
00091 u_pq_t *pq = NULL;
00092
00093 dbg_return_if (ppq == NULL, ~0);
00094 dbg_return_if (nitems < 2, ~0);
00095
00096
00097 dbg_err_sif ((pq = u_zalloc(sizeof *pq)) == NULL);
00098 dbg_err_sif ((pq->q = u_calloc(nitems + 1, sizeof(u_pq_item_t))) == NULL);
00099
00100
00101
00102 pq->nelems = 0;
00103 pq->nitems = nitems;
00104
00105 *ppq = pq;
00106
00107 return 0;
00108 err:
00109 u_pq_free(pq);
00110 return ~0;
00111 }
00112
00120 int u_pq_empty (u_pq_t *pq)
00121 {
00122 return (pq->nelems == 0);
00123 }
00124
00132 int u_pq_full (u_pq_t *pq)
00133 {
00134 return (pq->nelems == pq->nitems);
00135 }
00136
00146 void u_pq_free (u_pq_t *pq)
00147 {
00148 dbg_return_if (pq == NULL, );
00149
00150 if (pq->q)
00151 u_free(pq->q);
00152 u_free(pq);
00153
00154 return;
00155 }
00156
00171 int u_pq_push (u_pq_t *pq, double key, const void *val)
00172 {
00173 u_pq_item_t *pi;
00174
00175 dbg_return_if (pq == NULL, -1);
00176
00177
00178 if (u_pq_full(pq))
00179 return -2;
00180
00181 pq->nelems += 1;
00182
00183
00184 pi = &pq->q[pq->nelems];
00185
00186
00187 pi->key = key;
00188 memcpy(&pi->val, &val, sizeof(void **));
00189
00190
00191 bubble_up(pq->q, pq->nelems);
00192
00193 return 0;
00194 }
00195
00206 void *u_pq_peekmax (u_pq_t *pq, double *pkey)
00207 {
00208 u_pq_item_t *pmax = &pq->q[1];
00209
00210 if (pkey)
00211 *pkey = pmax->key;
00212
00213 return pmax->val;
00214 }
00215
00226 void *u_pq_delmax (u_pq_t *pq, double *pkey)
00227 {
00228 u_pq_item_t *pmax;
00229
00230 dbg_return_if (pq == NULL, NULL);
00231
00232
00233 if (pq->nelems == 0)
00234 return NULL;
00235
00236
00237 pq_item_swap(&pq->q[1], &pq->q[pq->nelems]);
00238
00239
00240 bubble_down(pq->q, 1, pq->nelems - 1);
00241
00242 pmax = &pq->q[pq->nelems];
00243
00244 pq->nelems -= 1;
00245
00246
00247 if (pkey)
00248 *pkey = pmax->key;
00249
00250 return pmax->val;
00251 }
00252
00257 static void pq_item_swap (u_pq_item_t *pi, u_pq_item_t *pj)
00258 {
00259 void *tmpval = pi->val;
00260 double tmpkey = pi->key;
00261
00262 pi->key = pj->key;
00263 pi->val = pj->val;
00264
00265 pj->key = tmpkey;
00266 pj->val = tmpval;
00267
00268 return;
00269 }
00270
00271 static int pq_item_comp (u_pq_item_t *pi, u_pq_item_t *pj)
00272 {
00273 return (pi->key < pj->key);
00274 }
00275
00276 static void bubble_up (u_pq_item_t *pi, size_t k)
00277 {
00278
00279
00280 while (k > 1 && pq_item_comp(&pi[k / 2], &pi[k]))
00281 {
00282 pq_item_swap(&pi[k], &pi[k / 2]);
00283 k = k / 2;
00284 }
00285
00286 return;
00287 }
00288
00289 static void bubble_down (u_pq_item_t *pi, size_t k, size_t n)
00290 {
00291 size_t j;
00292
00293
00294
00295
00296 while (2 * k <= n)
00297 {
00298 j = 2 * k;
00299
00300
00301 if (j < n && pq_item_comp(&pi[j], &pi[j + 1]))
00302 j++;
00303
00304 if (!pq_item_comp(&pi[k], &pi[j]))
00305 break;
00306
00307 pq_item_swap(&pi[k], &pi[j]);
00308
00309 k = j;
00310 }
00311
00312 return;
00313 }