From fb0f63d6a8a87bcfea9d78e67ab9070086871354 Mon Sep 17 00:00:00 2001
From: mo khan <mo.khan@gmail.com>
Date: Sun, 30 Aug 2020 13:18:27 -0600
Subject: feat: add rb_tree_equals function

---
 src/03/rb_tree.c      |  9 +++++++
 src/03/rb_tree.h      |  3 +++
 src/03/rb_tree_test.c | 72 +++++++++++++++++++++++++++++++++++++++++++++++----
 3 files changed, 79 insertions(+), 5 deletions(-)

(limited to 'src')

diff --git a/src/03/rb_tree.c b/src/03/rb_tree.c
index 5bb1017..3b7b8b1 100644
--- a/src/03/rb_tree.c
+++ b/src/03/rb_tree.c
@@ -182,3 +182,12 @@ RBTree *rb_tree_insert(RBTree *tree, int value) {
 void rb_tree_inspect(RBTree *tree) {
   print_tree(tree, 0);
 }
+
+bool rb_equals(RBTree *tree, RBTree *other_tree) {
+  if (!tree || !other_tree)
+    return tree == other_tree;
+
+  return tree->value == other_tree->value
+    && rb_equals(tree->left, other_tree->left)
+    && rb_equals(tree->right, other_tree->right);
+}
diff --git a/src/03/rb_tree.h b/src/03/rb_tree.h
index 484a332..984ad59 100644
--- a/src/03/rb_tree.h
+++ b/src/03/rb_tree.h
@@ -1,3 +1,5 @@
+#include <stdbool.h>
+
 enum Colour {
   black = 0x01,
   red = 0x00,
@@ -14,3 +16,4 @@ typedef struct rb_node {
 RBTree *rb_tree_initialize(int value);
 RBTree *rb_tree_insert(RBTree *tree, int value);
 void rb_tree_inspect(RBTree *tree);
+bool rb_equals(RBTree *tree, RBTree *other_tree);
diff --git a/src/03/rb_tree_test.c b/src/03/rb_tree_test.c
index 807ff76..120f80f 100644
--- a/src/03/rb_tree_test.c
+++ b/src/03/rb_tree_test.c
@@ -24,10 +24,6 @@ height: logn if perfectly balanced.
 (nil) (nil)
  */
 
-Ensure(one_equals_one) {
-  assert_that(1, is_equal_to(1));
-}
-
 Ensure(initialize_returns_a_new_tree) {
   RBTree *tree = rb_tree_initialize(10);
 
@@ -143,15 +139,81 @@ Ensure(rb_tree_insert_repaints_the_new_node) {
   assert_that(tree->right->colour, is_equal_to(black));
 }
 
+Ensure(equals_returns_false_when_tree_is_NULL) {
+  assert_that(rb_equals(NULL, rb_tree_initialize(10)), is_equal_to(false));
+}
+
+Ensure(equals_returns_false_when_other_tree_is_NULL) {
+  assert_that(rb_equals(rb_tree_initialize(10), NULL), is_equal_to(false));
+}
+
+Ensure(equals_returns_true_when_both_trees_are_NULL) {
+  assert_that(rb_equals(NULL, NULL), is_equal_to(true));
+}
+
+Ensure(equals_returns_false_when_tree_has_one_node) {
+  RBTree *tree = rb_tree_initialize(20);
+  RBTree *other_tree = rb_tree_initialize(10);
+
+  assert_that(rb_equals(tree, other_tree), is_equal_to(false));
+}
+
+Ensure(equals_returns_true_when_tree_has_one_node) {
+  RBTree *tree = rb_tree_initialize(20);
+  RBTree *other_tree = rb_tree_initialize(20);
+
+  assert_that(rb_equals(tree, other_tree), is_equal_to(true));
+}
+
+Ensure(equals_returns_true_when_root_and_left_subtree_are_equal) {
+  RBTree *tree = rb_tree_initialize(20);
+  tree = rb_tree_insert(tree, 10);
+
+  RBTree *other_tree = rb_tree_initialize(20);
+  other_tree = rb_tree_insert(other_tree, 10);
+
+  assert_that(rb_equals(tree, other_tree), is_equal_to(true));
+}
+
+Ensure(equals_returns_false_when_root_and_left_subtree_are_not_equal) {
+  RBTree *tree = rb_tree_initialize(20);
+  tree = rb_tree_insert(tree, 10);
+
+  RBTree *other_tree = rb_tree_initialize(20);
+  other_tree = rb_tree_insert(other_tree, 15);
+
+  assert_that(rb_equals(tree, other_tree), is_equal_to(false));
+}
+
+Ensure(equals_returns_false_when_root_and_right_subtree_are_not_equal) {
+  RBTree *tree = rb_tree_initialize(20);
+  tree = rb_tree_insert(tree, 30);
+
+  RBTree *other_tree = rb_tree_initialize(20);
+  other_tree = rb_tree_insert(other_tree, 25);
+
+  assert_that(rb_equals(tree, other_tree), is_equal_to(false));
+}
+
 TestSuite *rb_tree_tests() {
   TestSuite *x = create_test_suite();
-  add_test(x, one_equals_one);
+
   add_test(x, initialize_returns_a_new_tree);
+
   add_test(x, insert_returns_a_new_tree_when_null);
   add_test(x, insert_adds_a_new_item_to_right_subtree);
   add_test(x, insert_adds_a_new_item_to_left_subtree);
   add_test(x, rb_tree_insert_performs_a_right_rotation);
   add_test(x, rb_tree_insert_performs_a_left_rotation);
   add_test(x, rb_tree_insert_repaints_the_new_node);
+
+  add_test(x, equals_returns_false_when_tree_is_NULL);
+  add_test(x, equals_returns_false_when_other_tree_is_NULL);
+  add_test(x, equals_returns_true_when_both_trees_are_NULL);
+  add_test(x, equals_returns_false_when_tree_has_one_node);
+  add_test(x, equals_returns_true_when_tree_has_one_node);
+  add_test(x, equals_returns_true_when_root_and_left_subtree_are_equal);
+  add_test(x, equals_returns_false_when_root_and_left_subtree_are_not_equal);
+  add_test(x, equals_returns_false_when_root_and_right_subtree_are_not_equal);
   return x;
 }
-- 
cgit v1.2.3