From 3aee2fd43e3059a699af2b63c6f2395e5a55e515 Mon Sep 17 00:00:00 2001 From: KatolaZ Date: Wed, 27 Sep 2017 15:06:31 +0100 Subject: First commit on github -- NetBunch 1.0 --- src/utils/gen_pqueue.c | 359 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 359 insertions(+) create mode 100644 src/utils/gen_pqueue.c (limited to 'src/utils/gen_pqueue.c') diff --git a/src/utils/gen_pqueue.c b/src/utils/gen_pqueue.c new file mode 100644 index 0000000..590bb98 --- /dev/null +++ b/src/utils/gen_pqueue.c @@ -0,0 +1,359 @@ +/** + * This program is free software: you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation, either version 3 of the + * License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * This file is part of NetBunch, a package for complex network + * analysis and modelling. For more information please visit: + * + * http://www.complex-networks.net/ + * + * If you use this software, please add a reference to + * + * V. Latora, V. Nicosia, G. Russo + * "Complex Networks: Principles, Methods and Applications" + * Cambridge University Press (2017) + * ISBN: 9781107103184 + * + *********************************************************************** + * + * This is an implementation of a (MIN/MAX)-priority-queue based on + * gen_heap. Most of the functions, with the only exception of + * gen_pqueue_change_key which is the core of the priority queue, are + * just wrappers around the corresponding functions in gen_heap + * + */ + + + + +#include +#include +#include + +#include "gen_pqueue.h" + +void __update_handle(gen_pqueue_t *q, int idx){ + + q->handles[q->funs.get_id(q->v[idx])] = idx; +} + + +gen_pqueue_t * gen_pqueue_init(unsigned int N, char qtype, gen_pqueue_func_t *funs){ + + gen_pqueue_t* q; + int i; + + q = malloc(sizeof(gen_pqueue_t)); + q->qtype = qtype; + q->N = N; + q->last = -1; + q->funs = *funs; + q->v = q->funs.alloc_vector(N); + q->handles = malloc(N * sizeof(int)); + for (i=0; ihandles[i] = -1; + } + return q; + +} + +void __gen_pqueue_sift_up(gen_pqueue_t *q, int i){ + + int idx, parent; + void *tmp; + + idx = i; + parent = PARENT(idx); + + switch(q->qtype){ + case MAX_QUEUE: + while ( idx >0 && q->funs.compare(q->v[idx], q->v[parent]) > 0){ + tmp = q->v[idx]; + q->v[idx] = q->v[parent]; + q->v[parent] = tmp; + __update_handle(q, idx); + __update_handle(q, parent); + idx = parent; + parent = PARENT(idx); + } + break; + case MIN_QUEUE: + while ( idx >0 && q-> funs.compare(q->v[idx], q->v[parent]) < 0){ + tmp = q->v[idx]; + q->v[idx] = q->v[parent]; + q->v[parent] = tmp; + __update_handle(q, idx); + __update_handle(q, parent); + idx = parent; + parent = PARENT(idx); + } + break; + } +} + + +void __gen_pqueue_sift_down(gen_pqueue_t *q, int i){ + + int left, right, largest, smallest; + void *tmp; + + switch(q->qtype){ + case MAX_QUEUE: + largest = i; + left = 2 * i + 1; + right = 2 * i + 2; + + if (left <= q->last && q->funs.compare(q->v[left], q->v[largest]) > 0){ + largest = left; + } + if (right <= q->last && q->funs.compare(q->v[right], q->v[largest]) > 0){ + largest = right; + } + if (largest != i){ + tmp = q->v[i]; + q->v[i] = q->v[largest]; + q->v[largest] = tmp; + __update_handle(q, i); + __update_handle(q, largest); + __gen_pqueue_sift_down(q, largest); + } + else{ + __update_handle(q, i); + } + break; + + case MIN_QUEUE: + smallest = i; + left = 2 * i + 1; + right = 2 * i + 2; + + if (left <= q->last && q->funs.compare(q->v[left], q->v[smallest]) < 0){ + smallest = left; + } + if (right <= q->last && q->funs.compare(q->v[right], q->v[smallest]) < 0){ + smallest = right; + } + if (smallest != i){ + tmp = q->v[i]; + q->v[i] = q->v[smallest]; + q->v[smallest] = tmp; + __update_handle(q, i); + __update_handle(q, smallest); + __gen_pqueue_sift_down(q, smallest); + } + else{ + __update_handle(q, i); + } + break; + } +} + + +void gen_pqueue_insert(gen_pqueue_t *q, void *elem){ + + if (q->last < q->N-1){ + q->last += 1; + q->v[q->last] = elem; + __update_handle(q, q->last); + } + else{ + fprintf(stderr, "Error! Trying to insert more than %d elements in the heap (%s:%d)\n", + q->N, __FILE__, __LINE__); + return; + } + __gen_pqueue_sift_up(q, q->last); +} + + + +int gen_pqueue_delete(gen_pqueue_t *q, void **val){ + + if (q->last >=0){ + *val = q->v[0]; + q->v[0] = q->v[q->last]; + q->last -= 1; + __gen_pqueue_sift_down(q, 0); + return 0; + } + else{ + return 1; + } +} + + + +void* gen_pqueue_peek(gen_pqueue_t *q){ + + return q->v[0]; +} + +gen_pqueue_t* gen_pqueue_from_array(void **v, unsigned int N, unsigned int last, char qtype, + gen_pqueue_func_t *funs){ + + gen_pqueue_t *q; + int i; + + q = gen_pqueue_init(N, qtype, funs); + /* FIXME!!!! WARNING!!!! we should associate the array v to the array of the pqueue!!!! */ + for (i=last >> 1 ; i>=0; i--){ + __gen_pqueue_sift_down(q, i); + } + return q; +} + + + + +int gen_pqueue_force_key(gen_pqueue_t *q, unsigned int idx, void *key){ + + + switch(q->qtype){ + case MAX_QUEUE: + if (q->funs.compare_to_key(q->v[idx], key) > 0){ + q->funs.set_key(q->v[idx], key); + __gen_pqueue_sift_down(q, idx); + } + else{ + q->funs.set_key(q->v[idx], key); + __gen_pqueue_sift_up(q, idx); + } + break; + case MIN_QUEUE: + if (q->funs.compare_to_key(q->v[idx], key) < 0){ + q->funs.set_key(q->v[idx], key); + __gen_pqueue_sift_down(q, idx); + } + else{ + q->funs.set_key(q->v[idx], key); + __gen_pqueue_sift_up(q, idx); + } + break; + } + return 0; +} + + +int gen_pqueue_change_key(gen_pqueue_t *q, unsigned int idx, void *key){ + + + switch(q->qtype){ + case MAX_QUEUE: + if (q->funs.compare_to_key(q->v[idx], key) > 0){ + return KEY_ERROR; /* we cannot assign a smaller key on a MAX_QUEUE*/ + } + /* If everything is OK, we then set the new key here */ + q->funs.set_key(q->v[idx], key); + if (idx == 0) + return 0; + __gen_pqueue_sift_up(q, idx); + break; + case MIN_QUEUE: + if (q->funs.compare_to_key(q->v[idx], key) < 0){ + return KEY_ERROR; /* we cannot assign a higher key on a MIN_QUEUE*/ + } + /* If everything is OK, we then set the new key here */ + q->funs.set_key(q->v[idx], key); + /* parent = (int)(floor((idx-1)/2)); */ + if (idx == 0) + return 0; + __gen_pqueue_sift_up(q, idx); + break; + } + return -1; +} + + + +void gen_pqueue_dump(gen_pqueue_t *q){ + + int i; + + unsigned int N; + + N = q->last+1; + + printf("N: %d last:%d root:", q->N, q->last); + if (q->last >=0) + q->funs.print_elem(q->v[0]); + else + printf("NULL"); + printf("\n"); + + for(i=0; ifuns.print_elem(q->v[i]); + printf(" ("); + q->funs.print_elem(q->v[2*i+1]); + printf(", "); + q->funs.print_elem(q->v[2*i+2]); + printf(")\n"); + } + else{ + printf("%d: ", i); + q->funs.print_elem(q->v[i]); + printf(" ("); + q->funs.print_elem(q->v[2*i+1]); + printf(", NULL)\n"); + } + else{ + printf("%d: ", i); + q->funs.print_elem(q->v[i]); + printf(" (NULL, NULL)\n"); + } + } + else{ + printf("%d: ", i); + q->funs.print_elem(q->v[i]); + printf(" (NULL, NULL)\n"); + } + } + printf("\n"); +} + + +void gen_pqueue_destroy(gen_pqueue_t *q){ + + int i; + + /* First deallocate all the remaining elems (those that have not + been deleted) */ + for(i=0; i<=q->last; i++){ + q->funs.dealloc_elem(q->v[i]); + } + + /* now we deallocate the array of elems */ + q->funs.dealloc_vector(q->v); + free(q->handles); + free(q); +} + + +int gen_pqueue_get_handle(gen_pqueue_t *q, int id){ + + if (id >= q->N){ + return ID_ERROR; + } + return q->handles[id]; +} + +void* gen_pqueue_get_key(gen_pqueue_t *q, int idx){ + + return q->funs.get_key(q->v[idx]); + +} -- cgit v1.2.3