First commit on github -- NetBunch 1.0

1 files changed, 359 insertions, 0 deletions

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
+ *  <http://www.gnu.org/licenses/>.
+ *
+ *  (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk>
+ * 
+ *  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 <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+#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; i<N; i++){
+    q->handles[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; i<N; i++){
+    if (i < (N+1)/2){
+      if (2*i+1 < N)
+        if (2*i + 2 < N){
+          printf("%d: ", i);
+          q->funs.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]);
+  
+}