1 files changed, 291 insertions, 0 deletions
diff --git a/src/utils/iltree.c b/src/utils/iltree.c
new file mode 100644
index 0000000..28e8d90
--- /dev/null
+++ b/src/utils/iltree.c
@@ -0,0 +1,291 @@
+/**
+ *  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 simple insert-lookup Binary Search
+ *  Tree.  It supports adding nodes, checking for the presence of
+ *  keys, visiting the BST in pre-order, getting the maximum/minumum
+ *  key, and applying a function to all the nodes. There is no support
+ *  for deleting nodes.
+ *
+ */
+
+
+/*
+ *
+ * A simple insert-lookup static binary tree datatype
+ *
+ */
+
+#include <stdlib.h>
+#include "iltree.h"
+#include <stdio.h>
+
+
+void __recursive_preorder(node_t *cur, ilfunc_t *funs){
+  
+  if(cur->left){
+    __recursive_preorder(cur->left, funs);
+  }
+  funs->print(cur->info, funs->fileout);
+  if(cur->right){
+    __recursive_preorder(cur->right, funs);
+  }
+}
+
+/*
+ *
+ * Recursive push of nodes in the nodecache :-)
+ *
+ */
+
+void __recursive_destroy(node_t *cur, ilfunc_t *funs){
+  if(cur->left){
+    __recursive_destroy(cur->left, funs);
+    free(cur->left);
+    cur->left = NULL;
+  }
+  if(cur->right){
+    __recursive_destroy(cur->right, funs);
+    free(cur->right);
+    cur->right = NULL;
+  }
+  funs->dealloc(cur->info);
+}
+
+
+int __recursive_insert(node_t *cur, node_t *elem, ilfunc_t *f){
+  
+  int res ;
+  res = f->compare(cur->info, elem->info);
+  /*  printf("res: %d\n", res); */
+  if ( res > 0){
+    if (cur->left){
+      return __recursive_insert(cur->left, elem, f);
+    }
+    else{
+      cur->left = elem;
+      return 0;
+    }
+  }
+  else if (res < 0){
+    if (cur->right){
+      return __recursive_insert(cur->right, elem, f);
+    }
+    else{
+      cur->right = elem;
+      return 0;
+    }
+  }
+  printf("warning!!!!! duplicate entry!!!!!!\n\n");
+  return -1;
+}
+
+
+
+void* __recursive_lookup(node_t *cur, void *v, ilfunc_t *f){
+  
+  int res;
+
+  res = f->compare(cur->info, v);
+
+  if (res > 0){
+    if(cur->left)
+      return __recursive_lookup(cur->left, v, f);
+    else
+      return NULL;
+    
+  }
+  else if (res < 0){
+    if(cur->right)
+      return __recursive_lookup(cur->right, v, f);
+    else
+      return NULL;
+  }
+  else
+    return cur->info;
+}
+
+void __recursive_map(node_t *cur, void (*func)(void*)){
+  
+  if (cur->left)
+    __recursive_map(cur->left, func);
+  func(cur->info);
+  if (cur->right)
+    __recursive_map(cur->right, func);
+}
+
+void __recursive_map_args(node_t *cur, void (*func)(void*, void*), void *args){
+  
+  if (cur->left)
+    __recursive_map_args(cur->left, func, args);
+  func(cur->info, args);
+  if (cur->right)
+    __recursive_map_args(cur->right, func, args);
+}
+
+
+
+iltree_t iltree_create(iltree_t t){
+  if (!t) {
+    t = (iltree_t)malloc(sizeof(iltree_struct_t));
+  }
+  t->root = NULL;
+  return t;
+}
+
+
+void iltree_set_funs(iltree_t t, ilfunc_t *funs){
+  
+  t->funs = *funs;
+}
+
+
+void iltree_insert(iltree_t t, void *elem){
+  
+  node_t *n;
+  
+  n = (node_t*)malloc(sizeof(node_t));
+  n->info = t->funs.alloc(); 
+  t->funs.copy(elem, n->info);
+  n->left = n->right = NULL;
+  if (t->root == NULL){
+    t->root = n;
+  }
+  else{
+    __recursive_insert(t->root, n, & (t->funs));
+  }
+}
+
+
+void iltree_destroy(iltree_t t){
+  
+  if(t->root)
+    __recursive_destroy(t->root, & (t->funs));
+  free(t->root);
+  free(t);
+}
+
+
+
+
+void iltree_view_pre(iltree_t t){
+  
+  if (t->root){
+    /*printf("----\n");*/
+    __recursive_preorder(t->root, & (t->funs));
+    /*printf("----\n");*/
+  }
+  else
+    printf("----- Empty tree!!!! -----\n");
+  
+}
+
+
+
+void* iltree_lookup(iltree_t t , void *elem){
+
+  if(t->root)
+    return __recursive_lookup(t->root, elem, & (t->funs) );
+  else 
+    return NULL;
+}
+
+
+void iltree_map(iltree_t t, void (*func)(void*)){
+  
+  __recursive_map(t->root, func);
+  
+}
+
+
+void iltree_map_args(iltree_t t, void (*func)(void*, void*), void *args){
+  
+  __recursive_map_args(t->root, func, args);
+  
+}
+
+void* iltree_get_fileout(iltree_t t){
+
+  return t->funs.fileout;
+}
+
+void iltree_set_fileout(iltree_t t, void *f){
+  
+  t->funs.fileout = f;
+}
+
+void* __recursive_getmin(node_t *cur){
+  
+  if(cur->left){
+    return __recursive_getmin(cur->left);
+  }
+  else{
+    return cur->info;
+  }
+
+}
+
+
+void* iltree_getmin(iltree_t t){
+  
+  if (!t){
+    return NULL;
+  }
+  else{
+    return __recursive_getmin(t->root);
+  }
+
+}
+
+
+void* __recursive_getmax(node_t *cur){
+  
+  if(cur->right){
+    return __recursive_getmax(cur->right);
+  }
+  else{
+    return cur->info;
+  }
+
+}
+
+
+void* iltree_getmax(iltree_t t){
+  
+  if (!t){
+    return NULL;
+  }
+  else{
+    return __recursive_getmax(t->root);
+  }
+
+}
+