Start to work on inserting into a btree

5 files changed, 130 insertions, 0 deletions

diff --git a/src/02/03/Makefile b/src/02/03/Makefile
new file mode 100644
index 0000000..3e1c4e6
--- /dev/null
+++ b/src/02/03/Makefile
@@ -0,0 +1,37 @@
+#!/usr/bin/make -f
+SHELL=/bin/sh
+
+CC=clang
+TEST_LIBS = -lcgreen
+
+BUILDDIR := build
+OBJS := $(addprefix $(BUILDDIR)/,btree.o)
+TEST_OBJS := $(addprefix $(BUILDDIR)/,btree_test.o)
+
+$(BUILDDIR)/%.o : %.c
+	$(COMPILE.c) $(OUTPUT_OPTION) $<
+
+.PHONY: all
+all: $(OBJS) $(BUILDDIR)/main.o
+	$(CC) $(OBJS) $(BUILDDIR)/main.o -o $(BUILDDIR)/program
+
+.PHONY: test
+test: $(OBJS) $(TEST_OBJS)
+	$(CC) $(OBJS) $(TEST_OBJS) $(TEST_LIBS) -o $(BUILDDIR)/test
+
+$(OBJS): | $(BUILDDIR)
+
+$(TEST_OBJS): | $(BUILDDIR)
+
+$(BUILDDIR):
+	mkdir $(BUILDDIR)
+
+.PHONY: clean
+clean:
+	rm -fr build
+
+run : all
+	./build/program
+
+run_test : test
+	cgreen-runner -c -v $(BUILDDIR)/test
diff --git a/src/02/03/btree.c b/src/02/03/btree.c
new file mode 100644
index 0000000..c5b1ed8
--- /dev/null
+++ b/src/02/03/btree.c
@@ -0,0 +1,22 @@
+#include "btree.h"
+
+BTree *btree_init(int data) {
+  BTree *tree = malloc(sizeof(BTree));
+  tree->left = NULL;
+  tree->right = NULL;
+  tree->data = data;
+  return tree;
+}
+
+BTree *btree_insert(BTree *tree, int data) {
+  if (!tree)
+    return btree_init(data);
+
+  if (data <= tree->data) {
+    tree->left = btree_init(data);
+  } else {
+    tree->right = btree_init(data);
+  }
+
+  return tree;
+}
diff --git a/src/02/03/btree.h b/src/02/03/btree.h
new file mode 100644
index 0000000..6a1302c
--- /dev/null
+++ b/src/02/03/btree.h
@@ -0,0 +1,11 @@
+#include <stdlib.h>
+#include <stdbool.h>
+
+typedef struct btree_node {
+  struct btree_node *left;
+  struct btree_node *right;
+  int data;
+} BTree;
+
+BTree *btree_init(int data);
+BTree *btree_insert(BTree *root, int data);
diff --git a/src/02/03/btree_test.c b/src/02/03/btree_test.c
new file mode 100644
index 0000000..84720f5
--- /dev/null
+++ b/src/02/03/btree_test.c
@@ -0,0 +1,56 @@
+#include "btree.h"
+#include <cgreen/cgreen.h>
+#include <string.h>
+
+Describe(BinaryTree);
+BeforeEach(BinaryTree) {}
+AfterEach(BinaryTree) {}
+
+Ensure(BinaryTree, when_the_tree_is_NULL) {
+  BTree *tree = btree_insert(NULL, 10);
+
+  assert_that(tree, is_not_equal_to(NULL));
+  assert_that(tree->data, is_equal_to(10));
+}
+
+Ensure(BinaryTree, when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
+  BTree *tree = btree_init(10);
+  btree_insert(tree, -5);
+
+  assert_that(tree->left, is_not_equal_to(NULL));
+  assert_that(tree->left->data, is_equal_to(-5));
+}
+
+Ensure(BinaryTree, when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side) {
+  BTree *tree = btree_init(10);
+
+  btree_insert(tree, 16);
+
+  assert_that(tree->right, is_not_equal_to(NULL));
+  assert_that(tree->right->data, is_equal_to(16));
+}
+
+Ensure(BinaryTree, when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
+  BTree *tree = btree_init(10);
+
+  btree_insert(tree, 10);
+
+  assert_that(tree->left, is_not_equal_to(NULL));
+  assert_that(tree->left->data, is_equal_to(10));
+}
+
+TestSuite *binary_search_tree_tests() {
+  TestSuite *suite = create_test_suite();
+
+  add_test_with_context(suite, BinaryTree, when_the_tree_is_NULL);
+  add_test_with_context(suite, BinaryTree, when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
+  add_test_with_context(suite, BinaryTree, when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side);
+  add_test_with_context(suite, BinaryTree, when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
+  return suite;
+}
+
+int main(int argc, char **argv) {
+  TestSuite *suite = create_test_suite();
+  add_suite(suite, binary_search_tree_tests());
+  return run_test_suite(suite, create_text_reporter());
+}
diff --git a/src/02/03/main.c b/src/02/03/main.c
new file mode 100644
index 0000000..25927f5
--- /dev/null
+++ b/src/02/03/main.c
@@ -0,0 +1,4 @@
+int main(int argc, char *argv[])
+{
+  return 0;
+}