Newer
Older
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
/**
*
*/
package search;
import static org.junit.Assert.*;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
/**
* @author HaleyGlavina
*
*/
public class RedBlackTreeTest {
private GeneralCompare<Integer> b1;
private Field<Integer, Integer[]> fld;
/**
* @throws java.lang.Exception
*/
@Before
public void setUp() throws Exception {
b1 = (a1, a2) -> (Integer) a1 - (Integer) a2;
fld = (a1) -> (Integer) a1[0];
}
/**
* @throws java.lang.Exception
*/
@After
public void tearDown() throws Exception {
}
/**
* Test method for {@link search.RedBlackTree#root()}.
*/
@Test
public void testRoot() {
Integer[][] x = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {7, 7}, {8, 8}, {9, 9}};
RedBlackTree<Integer, Integer[]> myTree = new RedBlackTree<Integer, Integer[]>(fld, b1);
// Add first 5 nodes, expected root is 2
for(int i = 0; i < 4; i++){
myTree.put(x[i]);
}
assert((Integer) myTree.root().key() == 2);
// Add remaining nodes, expected root is 4
for(int i = 5; i < x.length; i++){
myTree.put(x[i]);
}
assert((Integer) myTree.root().key() == 4);
}
/**
* Test method for {@link search.RedBlackTree#get(Node<Key, Value> node, Comparable<Key> key)}.
*/
@Test
public void testGet() {
Integer[][] x = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {7, 7}, {8, 8}, {9, 9}};
RedBlackTree<Integer, Integer[]> myTree = new RedBlackTree<Integer, Integer[]>(fld, b1);
// Add first 5 nodes, expected get(6) result is null
for(int i = 0; i < 4; i++){
myTree.put(x[i]);
}
// Add remaining nodes, expected get(6) result is {6, 6}
for(int i = 5; i < x.length; i++){
myTree.put(x[i]);
}
assert(myTree.get(6).key() == 6);
// ==== TESTING WEIRD VALUES ==== //
Integer[][] y = {{100, 1}, {200000, 2}, {-3, 3}, {45, 4}, {-125, 2}};
RedBlackTree<Integer, Integer[]> newTree = new RedBlackTree<Integer, Integer[]>(fld, b1);
for(int i = 0; i < 5; i++){
newTree.put(y[i]);
}
assert(newTree.get(6) == null);
assert(newTree.get(-3).key() == (-3));
assert(newTree.get(100).key() == 100);
assert(newTree.get(-125).key() == (-125));
assert(newTree.get(200000).key() == 200000);
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/**
* Test method for {@link search.RedBlackTree#put(java.lang.Object)}.
*/
@Test
public void testPut() {
Integer[][] x = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {7, 7}, {8, 8}, {9, 9}};
RedBlackTree<Integer, Integer[]> myTree = new RedBlackTree<Integer, Integer[]>(fld, b1);
for(int i = 0; i < x.length; i++){
myTree.put(x[i]);
}
Node h = myTree.root();
// Check if right-most branch of tree matches what is expected
Integer[] expect = {4, 6, 7, 8, 9};
for (int i = 0 ; i < expect.length ; i++) {
assert(expect[i] == h.key());
h = h.right();
}
}
/**
* Test method for {@link search.RedBlackTree#rotateLeft(search.Node)}.
*/
@Test
public void testRotateLeft() {
RedBlackTree<Integer, Integer[]> myTree = new RedBlackTree<Integer, Integer[]>(fld, b1);
Integer[][] x = {{1, 1}, {2, 2}, {3, 3}, {4, 4}};
myTree.put(x[0]);
myTree.put(x[1]);
assert((Integer) myTree.root().key() == 1);
// Check if left rotation changes the root of the tree as expected
myTree.put(x[2]);
myTree.put(x[3]);
assert((Integer) myTree.root().key() == 2);
}
/**
* Test method for {@link search.RedBlackTree#rotateRight(search.Node)}.
*/
@Test
public void testRotateRight() {
RedBlackTree<Integer, Integer[]> myTree = new RedBlackTree<Integer, Integer[]>(fld, b1);
Integer[][] x = {{1, 1}, {2, 2}, {3, 3}, {4, 4}};
myTree.put(x[3]);
myTree.put(x[2]);
assert((Integer) myTree.root().key() == 4);
// Check if right rotation changes the root of the tree as expected
myTree.put(x[1]);
myTree.put(x[0]);
assert((Integer) myTree.root().key() == 3);
}
}