From 9fb160d55e374900a59f4620f6d265e450f34485 Mon Sep 17 00:00:00 2001
From: 0scar <qgt268@alumni.ku.dk>
Date: Tue, 30 Nov 2021 10:12:58 +0100
Subject: Add btree_(first|last)

Returns first and last element
---
 src/btree.h       |  5 +++++
 src/btree_naive.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 59 insertions(+)

diff --git a/src/btree.h b/src/btree.h
index ecbb95e..dc0a868 100644
--- a/src/btree.h
+++ b/src/btree.h
@@ -43,4 +43,9 @@ int   btree_delete(struct btree *btree, void *elem);
 
 void  btree_print(struct btree *btree, void (*print_elem)(const void*));
 
+void* btree_first(struct btree *btree);
+void* btree_last(struct btree *btree);
+
+size_t btree_size(struct btree *btree);
+
 #endif
diff --git a/src/btree_naive.c b/src/btree_naive.c
index 6abf49a..9538004 100644
--- a/src/btree_naive.c
+++ b/src/btree_naive.c
@@ -572,6 +572,8 @@ struct btree* btree_new_with_allocator(size_t elem_size,
 	new_tree->elem_size = elem_size;
 	new_tree->degree    = t;
 
+	new_tree->root      = NULL;
+
 	new_tree->cmp       = cmp;
 
 	return new_tree;
@@ -656,3 +658,55 @@ void btree_print(struct btree *btree, void (*print_elem)(const void*)) {
 	printf("BTRee: degree:%ld\n", btree->degree);
 	node_print(btree->root, btree->elem_size, 0, print_elem);
 }
+
+void* btree_first(struct btree *btree) {
+	if (btree == NULL) return NULL;
+	struct node *root = btree->root;
+
+	if (root == NULL) return NULL;
+
+	while (!node_leaf(root)) root = root->children[0];
+
+	if (root->n == 0) return NULL;
+	return root->items; /* Return first element */
+}
+
+void* btree_last(struct btree *btree) {
+	if (btree == NULL) return NULL;
+	struct node *root = btree->root;
+
+	if (root == NULL) return NULL;
+
+	while (!node_leaf(root)) root = root->children[root->c];
+
+	if (root->n == 0) return NULL;
+	return root->items + btree->elem_size * (root->n - 1); /* Return first element */
+}
+
+size_t btree_height(struct btree *btree) {
+	if (btree == NULL) return 0;
+	struct node *root = btree->root;
+	size_t height = 0;
+
+	if (root == NULL) return 0;
+
+	while (!node_leaf(root)) {
+		root = root->children[root->c];
+		height++;
+	}
+
+	return height;
+}
+
+size_t u32_pow(size_t base, size_t exponent) {
+	size_t res = 1;
+	while (exponent > 0) {
+		res *= base;
+		exponent--;
+	}
+	return res;
+}
+
+size_t btree_size(struct btree *btree) {
+	return u32_pow(2 * btree->degree, btree_height(btree)) - 1;
+}
-- 
cgit v1.3