StructuresOfData/test_RBtree.cpp at master · Ksunyy/StructuresOfData · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#pragma once
#include <gtest.h>
#include <vector>
#include <cmath>
#include "Polynomials.h"
#include "RBtree.h"


class RBtreeTest : public::testing::Test {
protected:
	RBtree tree;
	std::string str1 = "x^2y^0z^0+x^0y^0z^0";
	Polynomials poly = Polynomials(str1);

	virtual void SetUp() {
		for (int i = 0; i < 100000; ++i) {
			tree.RB_insert(i, poly);
		}
	}

	virtual void TearDown() {


	}

};


// --------------- POSITIVE TESTS ---------------- //

// SMOKE //

TEST(RBtrees, can_create_RBtree) {
	ASSERT_NO_THROW(RBtree tree);
}

TEST(RBtrees, can_copy_RBtree) {
	RBtree tree1;
	ASSERT_NO_THROW(RBtree(tree1));
}

TEST(RBtrees, can_asing_another_RBtree) {
	RBtree tree1;
	RBtree tree2;
	ASSERT_NO_THROW(tree2 = tree1);

}

TEST(RBtrees, can_print_RBtree) {
	Polynomials p;
	int key = 1;
	RBtree tree1;
	tree1.RB_insert(key, p);

	ASSERT_NO_THROW(tree1.RB_print());
}

// FUNCTIONS //

TEST_F(RBtreeTest, chek_size) {
	EXPECT_EQ(100000, tree.getSize());
}

TEST_F(RBtreeTest, is_root_black_after_insert) {
	EXPECT_EQ(1, tree.getRoot()->col);
}

TEST_F(RBtreeTest, count_rotates_after_insert) {
	bool chek = 1;
	for (int i = 0; i < tree.getInsertRotates().size(); i++) {
		if (tree.getInsertRotates()[i] > 2) chek = 0;

	}
	EXPECT_EQ(1, chek);
}

TEST(RBtree, count_two_rotates_after_insert) {
	RBtree tree1;
	Polynomials p;
	int mx = 0;
	std::vector<int> v = { 10, 30, 20, 40, 15 };
	for (int i = 0; i < 5; i++) {
		tree1.RB_insert(v[i], p);
		if (mx <= tree1.getInsertRotates()[i]) mx = tree1.getInsertRotates()[i];
	}
	EXPECT_EQ(2, mx);

}

TEST_F(RBtreeTest, erase_on_exist_key) {
	tree.RB_erase(2);
	EXPECT_EQ(nullptr, tree.RB_find(2));
}

TEST_F(RBtreeTest, erase_on_unexist_key) {
	tree.RB_erase(-200);
	EXPECT_EQ(nullptr, tree.RB_find(-200));
}

TEST_F(RBtreeTest, is_root_black_after_erase) {
	tree.RB_erase(3);
	EXPECT_EQ(1, tree.getRoot()->col);
}

TEST_F(RBtreeTest, count_rotates_after_erase) {
	bool chek = 1;
	for (int i = 0; i < tree.getSize(); i++) {
		tree.RB_erase(i);
		if (tree.getEraseRotates()[i] > 3) chek = 0;
	}
	EXPECT_EQ(1, chek);
}

TEST_F(RBtreeTest, find_on_exist_key) {
	EXPECT_NE(nullptr, tree.RB_find(10));
}

TEST_F(RBtreeTest, find_on_unexist_key) {
	EXPECT_EQ(nullptr, tree.RB_find(-200));
}