aboutsummaryrefslogtreecommitdiff
path: root/sparse.c
diff options
context:
space:
mode:
Diffstat (limited to 'sparse.c')
-rw-r--r--sparse.c88
1 files changed, 88 insertions, 0 deletions
diff --git a/sparse.c b/sparse.c
new file mode 100644
index 0000000..9ab6902
--- /dev/null
+++ b/sparse.c
@@ -0,0 +1,88 @@
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+
+struct bin_tree {
+ size_t index;
+ unsigned long long value;
+ struct bin_tree *right;
+ struct bin_tree *left;
+};
+
+typedef struct bin_tree node;
+
+void insert(node ** tree, size_t index) {
+ node *temp = NULL;
+ if(!(*tree)) {
+ temp = (node *)malloc(sizeof(node));
+ temp->left = temp->right = NULL;
+ temp->index = index;
+ temp->value = 1;
+ *tree = temp;
+ return;
+ }
+
+ if(index < (*tree)->index)
+ insert(&(*tree)->left, index);
+ else if(index > (*tree)->index)
+ insert(&(*tree)->right, index);
+
+}
+
+void deltree(node * tree) {
+ if (tree) {
+ deltree(tree->left);
+ deltree(tree->right);
+ free(tree);
+ }
+}
+
+node* search(node ** tree, size_t index) {
+ if(!(*tree))
+ return NULL;
+
+ if(index < (*tree)->index)
+ search(&((*tree)->left), index);
+
+ else if(index > (*tree)->index)
+ search(&((*tree)->right), index);
+
+ else if(index == (*tree)->index)
+ return *tree;
+}
+
+unsigned long long *lookup(node **tree, size_t index) {
+ node *ret = search(tree, index);
+ if(ret)
+ return ret->value;
+ else
+ return 0;
+}
+
+void print_sparse(node *tree, bool label, bool nonzero, unsigned int kmer) {
+
+ if (tree) {
+ print_sparse(tree->left, label, nonzero, kmer);
+ if(label && nonzero) {
+ char *kmer_str = index_to_kmer(tree->index, kmer);
+ if (tree->value != 0)
+ fprintf(stdout, "%s\t%llu\n", kmer_str, tree->value);
+ free(kmer_str);
+ }
+ else if(label) {
+ char *kmer_str = index_to_kmer(tree->index, kmer);
+ fprintf(stdout, "%s\t%llu\n", kmer_str, tree->value);
+ free(kmer_str);
+ }
+ else if(nonzero) {
+ if (tree->value != 0)
+ fprintf(stdout, "%zu\t%llu\n", tree->index, tree->value);
+ }
+ else
+ fprintf(stdout, "%llu\n", tree->value);
+
+ print_sparse(tree->right, label, nonzero, kmer);
+ }
+}