1#include "btree.h"
  2#include <cgreen/cgreen.h>
  3#include <string.h>
  4
  5Describe(BinaryTree);
  6BeforeEach(BinaryTree) {}
  7AfterEach(BinaryTree) {}
  8
  9Ensure(BinaryTree, when_the_tree_is_NULL) {
 10  BTree *tree = btree_insert(NULL, 10);
 11
 12  assert_that(tree, is_not_equal_to(NULL));
 13  assert_that(tree->data, is_equal_to(10));
 14}
 15
 16Ensure(
 17    BinaryTree,
 18    when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
 19  BTree *tree = btree_insert(NULL, 10);
 20  btree_insert(tree, -5);
 21
 22  assert_that(tree->left, is_not_equal_to(NULL));
 23  assert_that(tree->left->data, is_equal_to(-5));
 24}
 25
 26Ensure(
 27    BinaryTree,
 28    when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side) {
 29  BTree *tree = btree_insert(NULL, 10);
 30
 31  btree_insert(tree, 16);
 32
 33  assert_that(tree->right, is_not_equal_to(NULL));
 34  assert_that(tree->right->data, is_equal_to(16));
 35}
 36
 37Ensure(
 38    BinaryTree,
 39    when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
 40  BTree *tree = btree_insert(NULL, 10);
 41
 42  btree_insert(tree, 10);
 43
 44  assert_that(tree->left, is_not_equal_to(NULL));
 45  assert_that(tree->left->data, is_equal_to(10));
 46}
 47
 48Ensure(
 49    BinaryTree,
 50    when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position) {
 51  BTree *tree = btree_insert(NULL, 10);
 52
 53  btree_insert(tree, -5);
 54  btree_insert(tree, 16);
 55
 56  assert_that(tree->data, is_equal_to(10));
 57  assert_that(tree->left->data, is_equal_to(-5));
 58  assert_that(tree->right->data, is_equal_to(16));
 59
 60  btree_insert(tree, -8);
 61
 62  assert_that(tree->left->left, is_not_equal_to(NULL));
 63  assert_that(tree->left->left->data, is_equal_to(-8));
 64
 65  btree_insert(tree, 7);
 66
 67  assert_that(tree->left->right, is_not_equal_to(NULL));
 68  assert_that(tree->left->right->data, is_equal_to(7));
 69
 70  btree_insert(tree, 18);
 71
 72  assert_that(tree->right->right, is_not_equal_to(NULL));
 73  assert_that(tree->right->right->data, is_equal_to(18));
 74
 75  btree_insert(tree, 6);
 76
 77  assert_that(tree->left->right->left, is_not_equal_to(NULL));
 78  assert_that(tree->left->right->left->data, is_equal_to(6));
 79}
 80
 81Ensure(BinaryTree, when_rebalancing_a_tree) {
 82  BTree *tree = btree_insert(NULL, 1);
 83  tree->right = btree_initialize(tree, 5);
 84  tree->right->left = btree_initialize(tree->right, 2);
 85  tree->right->left->right = btree_initialize(tree->right->left, 4);
 86
 87  tree = btree_rebalance(tree->right->left->right);
 88
 89  assert_that(tree, is_not_equal_to(NULL));
 90  assert_that(tree->data, is_equal_to(2));
 91
 92  assert_that(tree->left->data, is_equal_to(1));
 93  assert_that(tree->right->data, is_equal_to(4));
 94  assert_that(tree->right->right->data, is_equal_to(5));
 95}
 96
 97Ensure(
 98    BinaryTree,
 99    when_inserting_items_described_in_the_assignment_it_inserts_in_the_expected_position_in_the_tree) {
100  BTree *tree = btree_insert(NULL, 1);
101  tree = btree_insert(tree, 5);
102  tree = btree_insert(tree, 2);
103  tree = btree_insert(tree, 4);
104  tree = btree_insert(tree, 3);
105
106  assert_that(tree, is_not_equal_to(NULL));
107  assert_that(tree->data, is_equal_to(2));
108  assert_that(tree->left->data, is_equal_to(1));
109  assert_that(tree->right->data, is_equal_to(4));
110  assert_that(tree->right->right->data, is_equal_to(5));
111}
112
113Ensure(BinaryTree, when_calculating_the_size_of_the_tree) {
114  BTree *tree = btree_insert(NULL, 1);
115  tree = btree_insert(tree, 5);
116  tree = btree_insert(tree, 2);
117  tree = btree_insert(tree, 4);
118  tree = btree_insert(tree, 3);
119
120  assert_that(btree_size(tree), is_equal_to(5));
121}
122
123TestSuite *binary_search_tree_tests() {
124  TestSuite *suite = create_test_suite();
125
126  add_test_with_context(suite, BinaryTree, when_the_tree_is_NULL);
127  add_test_with_context(
128      suite, BinaryTree,
129      when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
130  add_test_with_context(
131      suite, BinaryTree,
132      when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side);
133  add_test_with_context(
134      suite, BinaryTree,
135      when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
136  add_test_with_context(
137      suite, BinaryTree,
138      when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position);
139  add_test_with_context(suite, BinaryTree, when_rebalancing_a_tree);
140  add_test_with_context(
141      suite, BinaryTree,
142      when_inserting_items_described_in_the_assignment_it_inserts_in_the_expected_position_in_the_tree);
143
144  add_test_with_context(suite, BinaryTree,
145                        when_calculating_the_size_of_the_tree);
146  return suite;
147}
148
149int main(int argc, char **argv) {
150  TestSuite *suite = create_test_suite();
151  add_suite(suite, binary_search_tree_tests());
152  return run_test_suite(suite, create_text_reporter());
153}