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);
+	}
+}