1 files changed, 159 insertions, 0 deletions
diff --git a/src/cnm/bst_pq.h b/src/cnm/bst_pq.h
new file mode 100644
index 0000000..892eef0
--- /dev/null
+++ b/src/cnm/bst_pq.h
@@ -0,0 +1,159 @@
+/**
+ *  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 Binary Search Tree augmented by a
+ *  Priority Queue.  This data structure is central to the
+ *  implementation of the Clauset-Newman-Moore greedy modularity
+ *  optimisation algorithm
+ *
+ */
+
+#ifndef __BST_PQ_H__
+#define __BST_PQ_H__
+
+#include "gen_stack.h"
+
+
+/**
+ *
+ * This is an implementation of a Binary Search Tree augmented by a
+ * Priority Queue. 
+ *
+ */
+
+#define PARENT(i) (int)(floor((i-1)/2))
+
+#define MIN_QUEUE 0x01
+#define MAX_QUEUE 0x02
+
+typedef struct node{
+  unsigned int info; /* This is the ID of the neighbour used in  the BST */
+  double key; /* This is the \DeltaQ values used as a key in the
+                    PQ */
+  struct node* left; /* left child of the current element in the BST */
+  struct node* right; /* right child of the current element in the BST */
+  int index; /* Index of the current node in the PQ */
+  struct node *parent; /* Parent of the current node in the BST */
+  char active; /* indicates whether the node is active or not */
+} node_t;
+
+
+typedef struct{
+  void* (*alloc)();
+  void (*dealloc)(void*);
+  //void (*copy)(void *src, void *dst);
+  int (*compare)(unsigned int e1, unsigned int e2);
+  void (*print)(unsigned int, void*);
+  void *fileout;
+} ilfunc_t;
+
+
+typedef struct{
+  int (*compare)(double e1, double e2); /* compare two elements (standard comparator) */
+  void* (*alloc_vector)(unsigned int N); /* */
+  void (*dealloc_vector)(void *v); /* */
+  void* (*alloc_key)(void); /* Allocate an element for the key */
+  void (*copy_key)(void *src, void *dst); /* copy into key */
+  void (*print_elem)(void *e); /* print an element */
+  void (*set_key)(void *e, double k); /* set a new key to element e */
+  int (*compare_to_key)(void *e, double key); /* compare a key with the one of element e */
+} gen_pqueue_func_t;
+
+
+typedef struct {
+  node_t* root; /* root of the BST */
+  int N; /* Maximum size of the PQ */
+  int last; /* last element in the PQ */
+  node_t **v; /* vector of pointers to the nodes of the BST */
+  char qtype; /* type of PQ, either MIN_QUEUE or MAX_QUEUE */
+  ilfunc_t bst_funs;
+  gen_pqueue_func_t pq_funs;
+  gen_stack_t *node_cache; /* this is a pointer to a cache of
+                              allocated nodes, implemented as a stack */
+} bst_pq_struct_t;
+
+
+typedef bst_pq_struct_t* bst_pq_t;
+
+
+
+
+
+/* bst_pq interface */
+
+/* init the BST_PQ */
+
+bst_pq_t bst_pq_create(ilfunc_t* bst_funs, gen_pqueue_func_t* pq_funs, char qtype, 
+                       unsigned int N, gen_stack_t *node_cache);
+
+/* Destroy an existing BST_PQ */
+void bst_pq_destroy(bst_pq_t b, char clear_cache);
+
+/* lookup an element in the BST */
+node_t* bst_pq_lookup(bst_pq_t b, unsigned int info);
+
+/* insert a new element in the BST_PQ */
+void bst_pq_insert(bst_pq_t b, unsigned int info, double key);
+
+/* delete (or deactivate) an element in the BST_PQ */
+int bst_pq_delete(bst_pq_t b, unsigned int info);
+
+/* change the key of an element in the BST_PQ */
+int bst_pq_change_key(bst_pq_t b, unsigned int info, double key);
+
+/* return the head of the PQ */
+void* bst_pq_peek(bst_pq_t);
+
+/* Read the key of a given node of the BST */
+double bst_pq_get_key(bst_pq_t b, unsigned int info);
+
+/* Read the key of the element of index "index" in the PQ */
+double bst_pq_get_key_from_index(bst_pq_t b, int index);
+
+/* Dump the BST  */
+void bst_pq_dump_bst(bst_pq_t b);
+
+/* Show the PQ */
+void bst_pq_dump_pq(bst_pq_t b);
+
+/* See if a node is in the BST, either active or inactive */
+node_t* bst_pq_lookup(bst_pq_t b, unsigned int info);
+
+/* See if a node is in the BST and is ACTIVE */
+node_t* bst_pq_lookup_active(bst_pq_t b, unsigned int info);
+
+
+/* Insert a pre-allocated node_t in the BST_PQ */
+//void bst_pq_insert_existing(bst_pq_t b, node_t *n);
+
+
+
+#endif /*__BST_PQ_H__*/