1#include "meldable_heap.h"
  2#include <cgreen/cgreen.h>
  3#include <string.h>
  4
  5Ensure(add_inserts_item_into_right_subtree) {
  6  MeldableHeap *heap = meldable_heap_initialize(5);
  7  heap = meldable_heap_add(heap, 3);
  8
  9  assert_that(heap->value, is_equal_to(3));
 10  assert_that(heap->right->value, is_equal_to(5));
 11}
 12
 13Ensure(add_inserts_item_into_left_subtree) {
 14  MeldableHeap *heap = meldable_heap_initialize(5);
 15  heap = meldable_heap_add(heap, 8);
 16
 17  assert_that(heap->value, is_equal_to(5));
 18  assert_that(heap->right->value, is_equal_to(8));
 19}
 20
 21/*
 22          (1)
 23        /      \
 24      (3)      (2)
 25     /  \     /   \
 26  (10)  (6) (7)   (4)
 27           /  \   /
 28         (9)  (8)(5)
 29*/
 30Ensure(add_inserts_multiple_items_into_the_subtree) {
 31  MeldableHeap *heap = NULL;
 32
 33  for (int i = 1; i <= 10; ++i)
 34    heap = meldable_heap_add(heap, i);
 35
 36  assert_that(heap->value, is_equal_to(1));
 37
 38  assert_that(heap->right->value, is_equal_to(2));
 39  assert_that(heap->right->right->value, is_equal_to(4));
 40  assert_that(heap->right->right->left->value, is_equal_to(5));
 41
 42  assert_that(heap->right->left->value, is_equal_to(7));
 43  assert_that(heap->right->left->left->value, is_equal_to(9));
 44  assert_that(heap->right->left->right->value, is_equal_to(8));
 45
 46  assert_that(heap->left->value, is_equal_to(3));
 47  assert_that(heap->left->left->value, is_equal_to(10));
 48  assert_that(heap->left->right->value, is_equal_to(6));
 49}
 50
 51/*
 52          (1)
 53        /      \
 54      (3)      (2)
 55     /  \     /   \
 56  (10)  (6) (7)   (4)
 57           /  \   /
 58         (9)  (8)(5)
 59
 60         to
 61
 62          (1)
 63        /      \
 64      (3)      (2)
 65     /  \     /   \
 66  (10)  (6)       (4)
 67           /  \   /
 68         (9)  (8)(5)
 69*/
 70Ensure(remove_removes_the_node_from_the_tree) {
 71  MeldableHeap *heap = NULL;
 72
 73  for (int i = 1; i <= 10; ++i)
 74    heap = meldable_heap_add(heap, i);
 75
 76  meldable_heap_remove(heap->right->left);
 77
 78  assert_that(heap->value, is_equal_to(1));
 79
 80  assert_that(heap->right->value, is_equal_to(2));
 81  assert_that(heap->right->right->value, is_equal_to(4));
 82  assert_that(heap->right->right->left->value, is_equal_to(5));
 83
 84  assert_that(heap->right->left->value, is_equal_to(8));
 85  assert_that(heap->right->left->left->value, is_equal_to(9));
 86  assert_that(heap->right->left->right, is_equal_to(NULL));
 87
 88  assert_that(heap->left->value, is_equal_to(3));
 89  assert_that(heap->left->left->value, is_equal_to(10));
 90  assert_that(heap->left->right->value, is_equal_to(6));
 91}
 92
 93TestSuite *meldable_heap_tests() {
 94  TestSuite *x = create_test_suite();
 95
 96  add_test(x, add_inserts_item_into_right_subtree);
 97  add_test(x, add_inserts_item_into_left_subtree);
 98  add_test(x, add_inserts_multiple_items_into_the_subtree);
 99  add_test(x, remove_removes_the_node_from_the_tree);
100  return x;
101}