8000 Remove added ds tests · DontFearAlgorithms/Algorithms-1@fcde92a · GitHub
[go: up one dir, main page]
Skip to content

Commit fcde92a

Browse files
williamfisetwilliamfiset
committed
Remove added ds tests
1 parent c9b102e commit fcde92a

30 files changed

+6164
-7
lines changed

‎README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,15 @@
11

22
[![Travis](https://img.shields.io/travis/williamfiset/Algorithms.svg)](https://travis-ci.org/williamfiset/Algorithms) [![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
33

4-
# Algorithms & Data Structures project
4+
# Algorithms & data structures project
55

66
Algorithms and data structures are amongst the most fundamental ingredients in the recipe for efficient code and good software design; knowledge of how to create and design excellent algorithms is an essential skill required in becoming an exemplary programmer. The goal of this repository is to provide a complete and thorough explanation of the most common data structures and algorithms in the clearest possible way.
77

88
# Data Structures
99
* [:movie_camera:](https://www.youtube.com/watch?v=q4fnJZr8ztY)[Balanced Trees](https://github.com/williamfiset/algorithms/tree/master/com/williamfiset/algorithms/datastructures/balancedtree)
1010
* [Avl Tree (recursive)](https://github.com/williamfiset/algorithms/blob/master/com/williamfiset/algorithms/datastructures/balancedtree/AVLTreeRecursive.java)
1111
* [Avl Tree (recursive, mildly optimized)](https://github.com/williamfiset/algorithms/blob/master/com/williamfiset/algorithms/datastructures/balancedtree/AVLTreeRecursiveOptimized.java)
12-
* [Red Black Tree(recursive)](https://github.com/williamfiset/algorithms/blob/master/com/williamfiset/algorithms/datastructures/balancedtree/RedBlackTree.java)
12+
* [Red Black Tree (recursive)](https://github.com/williamfiset/algorithms/blob/master/com/williamfiset/algorithms/datastructures/balancedtree/RedBlackTree.java)
1313
* [:movie_camera:](https://www.youtube.com/watch?v=JfSdGQdAzq8)[Binary Search Tree](https://github.com/williamfiset/algorithms/blob/master/com/williamfiset/algorithms/datastructures/binarysearchtree/BinarySearchTree.java)
1414
* [Splay Tree](https://github.com/williamfiset/algorithms/blob/master/com/williamfiset/algorithms/datastructures/binarysearchtree/SplayTree.java)
1515
* [Bloom Filter](https://github.com/williamfiset/algorithms/tree/master/com/williamfiset/algorithms/datastructures/bloomfilter)

‎build.gradle

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,10 @@ dependencies {
2828
// JUnit framework
2929
testCompile 'junit:junit:4.+'
3030
compile 'junit:junit:4.+'
31+
32+
// JUnit 5 / Jupiter
33+
testImplementation('org.junit.jupiter:junit-jupiter-api:5.4.2')
34+
testRuntime('org.junit.jupiter:junit-jupiter-engine:5.4.2')
3135

3236
// Test mocking framework
3337
testCompile "org.mockito:mockito-core:1.+"
@@ -40,8 +44,6 @@ dependencies {
4044

4145
// Apache commons lang
4246
compile 'org.apache.commons:commons-lang3:3.6'
43-
44-
4547
}
4648

4749
test {
@@ -58,6 +60,7 @@ sourceSets {
5860
srcDirs = [
5961
javaAlgorithmsPackage + '/ai',
6062
javaAlgorithmsPackage + '/dp',
63+
javaAlgorithmsPackage + '/datastructures',
6164
javaAlgorithmsPackage + '/geometry',
6265
javaAlgorithmsPackage + '/graphtheory',
6366
javaAlgorithmsPackage + '/linearalgebra',
@@ -74,6 +77,7 @@ sourceSets {
7477
java {
7578
srcDirs = [
7679
javatestsAlgorithmsPackage + '/ai',
80+
javatestsAlgorithmsPackage + '/datastructures',
7781
javatestsAlgorithmsPackage + '/dp',
7882
javatestsAlgorithmsPackage + '/geometry',
7983
javatestsAlgorithmsPackage + '/graphtheory',

‎com/williamfiset/algorithms/datastructures/balancedtree/AVLTreeRecursive.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,8 +6,8 @@
66
*/
77
package com.williamfiset.algorithms.datastructures.balancedtree;
88

9-
import com.williamfiset.datastructures.utils.TreePrinter;
10-
import com.williamfiset.datastructures.utils.TreePrinter.PrintableNode;
9+
import com.williamfiset.algorithms.datastructures.utils.TreePrinter;
10+
import com.williamfiset.algorithms.datastructures.utils.TreePrinter.PrintableNode;
1111

1212
public class AVLTreeRecursive<T extends Comparable<T>> implements Iterable<T> {
1313

‎com/williamfiset/algorithms/datastructures/binarysearchtree/SplayTree.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
package com.williamfiset.algorithms.datastructures.binarysearchtree;
22

3-
import com.williamfiset.datastructures.utils.TreePrinter;
3+
import com.williamfiset.algorithms.datastructures.utils.TreePrinter;
44
import java.util.ArrayList;
55
import java.util.Scanner;
66

‎javatests/com/williamfiset/algorithms/datastructures/balancedtree/AVLTreeTest.java

Lines changed: 192 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,192 @@
1+
package javatests.com.williamfiset.algorithms.datastructures.balancedtree;
2+
3+
import static org.junit.Assert.*;
4+
5+
import com.williamfiset.algorithms.datastructures.balancedtree.AVLTreeRecursive;
6+
import java.util.ArrayList;
7+
import java.util.Collections;
8+
import java.util.List;
9+
import java.util.TreeSet;
10+
import org.junit.Before;
11+
import org.junit.Test;
12+
13+
public class AVLTreeTest {
14+
15+
static final int MAX_RAND_NUM = +100000;
16+
static final int MIN_RAND_NUM = -100000;
17+
18+
static final int TEST_SZ = 2500;
19+
20+
private AVLTreeRecursive<Integer> tree;
21+
22+
@Before
23+
public void setup() {
24+
tree = new AVLTreeRecursive<>();
25+
}
26+
27+
@Test
28+
public void testNullInsertion() {
29+
assertFalse(tree.insert(null));
30+
}
31+
32+
@Test
33+
public void testNullRemoval() {
34+
assertFalse(tree.remove(null));
35+
}
36+
37+
@Test
38+
public void testTreeContainsNull() {
39+
assertFalse(tree.contains(null));
40+
}
41+
42+
@Test
43+
public void testLeftLeftCase() {
44+
45+
tree.insert(3);
46+
tree.insert(2);
47+
tree.insert(1);
48+
49+
assertEquals(2, tree.root.value.intValue());
50+
assertEquals(1, tree.root.left.value.intValue());
51+
assertEquals(3, tree.root.right.value.intValue());
52+
53+
assertNull(tree.root.left.left);
54+
assertNull(tree.root.left.right);
55+
assertNull(tree.root.right.left);
56+
assertNull(tree.root.right.right);
57+
}
58+
59+
@Test
60+
public void testLeftRightCase() {
61+
62+
tree.insert(3);
63+
tree.insert(1);
64+
tree.insert(2);
65+
66+
assertEquals(2, tree.root.value.intValue());
67+
assertEquals(1, tree.root.left.value.intValue());
68+
assertEquals(3, tree.root.right.value.intValue());
69+
70+
assertNull(tree.root.left.left);
71+
assertNull(tree.root.left.right);
72+
assertNull(tree.root.right.left);
73+
assertNull(tree.root.right.right);
74+
}
75+
76+
@Test
77+
public void testRightRightCase() {
78+
79+
tree.insert(1);
80+
tree.insert(2);
81+
tree.insert(3);
82+
83+
assertEquals(2, tree.root.value.intValue());
84+
assertEquals(1, tree.root.left.value.intValue());
85+
assertEquals(3, tree.root.right.value.intValue());
86+
87+
assertNull(tree.root.left.left);
88+
assertNull(tree.root.left.right);
89+
assertNull(tree.root.right.left);
90+
assertNull(tree.root.right.right);
91+
}
92+
93+
@Test
94+
public void testRightLeftCase() {
95+
96+
tree.insert(1);
97+
tree.insert(3);
98+
tree.insert(2);
99+
100+
assertEquals(2, tree.root.value.intValue());
101+
assertEquals(1, tree.root.left.value.intValue());
102+
assertEquals(3, tree.root.right.value.intValue());
103+
104+
assertNull(tree.root.left.left);
105+
assertNull(tree.root.left.right);
106+
assertNull(tree.root.right.left);
107+
assertNull(tree.root.right.right);
108+
}
109+
110+
@Test
111+
public void testRandomizedBalanceFactorTest() {
112+
for (int i = 0; i < TEST_SZ; i++) {
113+
tree.insert(randValue());
114+
assertTrue(validateBalanceFactorValues(tree.root));
115+
}
116+
}
117+
118+
// Make sure all balance factor values are either -1, 0 or +1
119+
static boolean validateBalanceFactorValues(AVLTreeRecursive.Node node) {
120+
if (node == null) return true;
121+
if (node.bf > +1 || node.bf < -1) return false;
122+
return validateBalanceFactorValues(node.left) && validateBalanceFactorValues(node.right);
123+
}
124+
125+
@Test
126+
public void testRandomizedValueInsertionsAgainstTreeSet() {
127+
128+
TreeSet<Integer> set = new TreeSet<>();
129+
for (int i = 0; i < TEST_SZ; i++) {
130+
int v = randValue();
131+
assertEquals(set.add(v), tree.insert(v));
132+
assertEquals(set.size(), tree.size());
133+
assertTrue(tree.validateBSTInvarient(tree.root));
134+
}
135+
}
136+
137+
@Test
138+
public void testTreeHeight() {
139+
for (int n = 1; n <= TEST_SZ; n++) {
140+
141+
tree.insert(randValue());
142+
int height = tree.height();
143+
144+
// Get an upper bound on what the maximum height of
145+
// an AVL tree should be. Values were taken from:
146+
// https://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures
147+
double c = 1.441;
148+
double b = -0.329;
149+
double upperBound = c * (Math.log(n + 2.0) / Math.log(2)) + b;
150+
151+
assertTrue(height < upperBound);
152+
}
153+
}
154+
155+
@Test
156+
public void randomRemoveTests() {
157+
TreeSet<Integer> ts = new TreeSet<>();
158+
for (int i = 0; i < TEST_SZ; i++) {
159+
160+
int size = i;
161+
List<Integer> lst = genRandList(size);
162+
for (Integer value : lst) {
163+
tree.insert(value);
164+
ts.add(value);
165+
}
166+
Collections.shuffle(lst);
167+
168+
// Remove all the elements we just placed in the tree.
169+
for (int j = 0; j < size; j++) {
170+
171+
Integer value = lst.get(j);
172+
173+
assertEquals(ts.remove(value), tree.remove(value));
174+
assertFalse(tree.contains(value));
175+
assertEquals(size - j - 1, tree.size());
176+
}
177+
178+
assertTrue(tree.isEmpty());
179+
}
180+
}
181+
182+
static List<Integer> genRandList(int sz) {
183+
List<Integer> lst = new ArrayList<>(sz);
184+
for (int i = 0; i < sz; i++) lst.add(i); // unique values.
185+
Collections.shuffle(lst);
186+
return lst;
187+
}
188+
189+
public static int randValue() {
190+
return (int) (Math.random() * MAX_RAND_NUM * 2) + MIN_RAND_NUM;
191+
}
192+
}

0 commit comments

Comments
 (0)
0