/**
* 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]);
}