summaryrefslogtreecommitdiff
path: root/src/utils/gen_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/utils/gen_heap.c')
-rw-r--r--src/utils/gen_heap.c302
1 files changed, 302 insertions, 0 deletions
diff --git a/src/utils/gen_heap.c b/src/utils/gen_heap.c
new file mode 100644
index 0000000..586c7fd
--- /dev/null
+++ b/src/utils/gen_heap.c
@@ -0,0 +1,302 @@
+/**
+ * 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 binary heaps (both Min-Heap and
+ * Max-Heap).
+ *
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <string.h>
+
+#include "gen_heap.h"
+
+
+
+gen_heap_t * gen_heap_init(unsigned int N, char htype, gen_heap_func_t *funs){
+
+ gen_heap_t* h;
+
+ h = malloc(sizeof(gen_heap_t));
+ h->htype = htype;
+ h->N = N;
+ h->last = -1;
+ h->funs = *funs;
+ h->v = h->funs.alloc_vector(N);
+ return h;
+}
+
+
+void __gen_heap_sift_up(gen_heap_t *h, int i){
+
+ int idx, parent;
+ void *tmp;
+
+ idx = i;
+ parent = PARENT(idx);
+ switch(h->htype){
+ case MAX_HEAP:
+ while ( idx >0 && h->funs.compare(h->v[idx], h->v[parent]) > 0){
+ tmp = h->v[idx];
+ h->v[idx] = h->v[parent];
+ h->v[parent] = tmp;
+ idx = parent;
+ parent = PARENT(idx);
+ }
+ break;
+ case MIN_HEAP:
+ while ( idx >0 && h-> funs.compare(h->v[idx], h->v[parent]) < 0){
+ tmp = h->v[idx];
+ h->v[idx] = h->v[parent];
+ h->v[parent] = tmp;
+ idx = parent;
+ parent = PARENT(idx);
+ }
+ break;
+ }
+}
+
+
+void __gen_heap_sift_down(gen_heap_t *h, int i){
+
+ int left, right, largest, smallest;
+ void *tmp;
+
+
+ switch(h->htype){
+
+ case MAX_HEAP:
+ largest = i;
+ left = 2 * i + 1;
+ right = 2 * i + 2;
+
+ if (left <= h->last && h->funs.compare(h->v[left], h->v[largest]) > 0){
+ largest = left;
+ }
+ if (right <= h->last && h->funs.compare(h->v[right], h->v[largest]) > 0){
+ largest = right;
+ }
+ if (largest != i){
+ tmp = h->v[i];
+ h->v[i] = h->v[largest];
+ h->v[largest] = tmp;
+ __gen_heap_sift_down(h, largest);
+ }
+ break;
+
+ case MIN_HEAP:
+ smallest = i;
+ left = 2 * i + 1;
+ right = 2 * i + 2;
+
+ if (left <= h->last && h->funs.compare(h->v[left], h->v[smallest]) < 0){
+ smallest = left;
+ }
+ if (right <= h->last && h->funs.compare(h->v[right], h->v[smallest]) < 0){
+ smallest = right;
+ }
+ if (smallest != i){
+ tmp = h->v[i];
+ h->v[i] = h->v[smallest];
+ h->v[smallest] = tmp;
+ __gen_heap_sift_down(h, smallest);
+ }
+ break;
+ }
+
+}
+
+
+void gen_heap_insert(gen_heap_t *h, void *elem){
+
+ if (h->last < h->N-1){
+ h->last += 1;
+ h->v[h->last] = elem;
+ }
+ else{
+ fprintf(stderr, "Error! Trying to insert more than %d elements in the heap (%s:%d)\n",
+ h->N, __FILE__, __LINE__);
+ return;
+ }
+ __gen_heap_sift_up(h, h->last);
+}
+
+
+
+int gen_heap_delete(gen_heap_t *h, void **val){
+
+ if (h->last >=0){
+ *val = h->v[0];
+ h->v[0] = h->v[h->last];
+ h->last -= 1;
+ __gen_heap_sift_down(h,0);
+ return 0;
+ }
+ else{
+ return 1;
+ }
+}
+
+
+
+void* gen_heap_peek(gen_heap_t *h){
+ return h->v[0];
+}
+
+
+gen_heap_t* gen_heap_from_array(void **v, unsigned int N, unsigned int last,
+ char htype, gen_heap_func_t *funs){
+
+ gen_heap_t *h;
+ int i;
+
+ h = malloc(sizeof(gen_heap_t));
+ h->N = N;
+ h->last = last;
+ h->htype = htype;
+ h->funs = *funs;
+ h->v = v;
+
+ for (i=last >> 1 ; i>=0; i--){
+ __gen_heap_sift_down(h, i);
+ }
+ return h;
+}
+
+
+
+void gen_heap_dump(gen_heap_t* h){
+
+ int i;
+
+ unsigned int N;
+
+ N = h->last+1;
+
+ printf("N: %d last:%d root:", h->N, h->last);
+ if (h->last >=0)
+ h->funs.print_elem(h->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);
+ h->funs.print_elem(h->v[i]);
+ printf(" (");
+ h->funs.print_elem(h->v[2*i+1]);
+ printf(", ");
+ h->funs.print_elem(h->v[2*i+2]);
+ printf(")\n");
+ }
+ else{
+ printf("%d: ", i);
+ h->funs.print_elem(h->v[i]);
+ printf(" (");
+ h->funs.print_elem(h->v[2*i+1]);
+ printf(", NULL)\n");
+ }
+ else{
+ printf("%d: ", i);
+ h->funs.print_elem(h->v[i]);
+ printf(" (NULL, NULL)\n");
+ }
+ }
+ else{
+ printf("%d: ", i);
+ h->funs.print_elem(h->v[i]);
+ printf(" (NULL, NULL)\n");
+ }
+ }
+ printf("\n");
+}
+
+void gen_heap_destroy(gen_heap_t *h){
+
+ int i;
+
+ /* First deallocate all the elems */
+ for(i=0; i<=h->last; i++){
+ h->funs.dealloc_elem(h->v[i]);
+ }
+
+ /* now we deallocate the array */
+ h->funs.dealloc_vector(h->v);
+ h->v = NULL;
+ free(h);
+}
+
+
+int gen_heap_sort(void *v, unsigned int N, size_t size, char dir,
+ int (*compar)(const void *, const void *)){
+
+ gen_heap_func_t funs;
+ gen_heap_t *h;
+ void *val, **new_v=NULL, *tmp_v=NULL;
+ char htype;
+ int i;
+
+ funs.compare = compar;
+
+ htype = MAX_HEAP;
+
+ if (dir == SORT_DESC)
+ htype = MIN_HEAP;
+
+ new_v = malloc(N * sizeof(void*));
+ tmp_v = malloc(N * size);
+
+ for (i=0; i<N; i++){
+ new_v[i] = (char*)v+ i* size;
+ }
+
+ h = gen_heap_from_array(new_v, N, N-1, htype, &funs);
+ for(i = 0; i<N; i++){
+ if (gen_heap_delete(h, (void **)&val)){
+ free(new_v);
+ free(tmp_v);
+ return ERR_DELETE;
+ }
+ //fprintf(stderr, "(%p <- %p) ", (char*) v + (N-i-1) * size, val);
+ memcpy((char*)tmp_v + (N-i-1) * size, val, size);
+ }
+ memcpy(v, tmp_v, N*size);
+ free(new_v);
+ free(tmp_v);
+ return 0;
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-03 16:34:18 +0000