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
package edu.caltech.cs2.datastructures;
import edu.caltech.cs2.helpers.*;
import edu.caltech.cs2.helpers.ArrayFuncs;
import org.junit.jupiter.api.*;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static java.util.concurrent.TimeUnit.SECONDS;
import java.util.List;
import java.util.function.Consumer;
import java.util.function.Function;
public class InsertionSortTests {
@Order(0)
@Tag("D")
@DisplayName("Test sort() edge cases")
@ParameterizedTest(name = "Correctly sorted {0}")
@CsvSource(value = {
"[]| []",
"[0]| [0]",
"[-90210]| [-90210]",
"[1, 1, 1, 2]| [1, 1, 1, 2]",
"[3, 2]| [2, 3]",
"[1, 2, 1, 2]| [1, 1, 2, 2]",
"[5, 4, 4, -4]| [-4, 4, 4, 5]"
},
delimiter = '|')
public void testSortEdge(String input, String output) {
Integer[] arrInput = ArrayFuncs.stringToArray(input);
Integer[] arrOutput = ArrayFuncs.stringToArray(output);
InsertionSort.sort(arrInput);
assertEquals(ArrayFuncs.arrayToString(arrOutput), ArrayFuncs.arrayToString(arrInput));
}
@Order(1)
@Tag("D")
@DisplayName("Test sort() longer arrays")
@ParameterizedTest(name = "Correctly sorted {0}")
@CsvSource(value = {
"[19, 7, -4, 16, 20, 8, 2, 10, 1, 17, 14, 22, -13, 5, 14, 23, 9, 20, 12, 15, 18, 14, 21, 4, 17, 19, -7, -4, 11, 0, 25, 24, 3, 14, 6]| [-13, -7, -4, -4, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 14, 14, 14, 15, 16, 17, 17, 18, 19, 19, 20, 20, 21, 22, 23, 24, 25]",
"[18, 15, 4, 11, 0, 1, 14, 17, 11, 4, 21, 8, 18, 4, 19, 18, 15, 4, 21, 8, 13, 20, 12, 6, 17, 0, 21, 8, 18]| [0, 0, 1, 4, 4, 4, 4, 6, 8, 8, 8, 11, 11, 12, 13, 14, 15, 15, 17, 17, 18, 18, 18, 18, 19, 20, 21, 21, 21]",
"[0, 8, 3, 4, 13, 3, 8, 2, 0, 17, 11, 14, 22, 0, 18, 7, 4, 17, 4]| [0, 0, 0, 2, 3, 3, 4, 4, 4, 7, 8, 8, 11, 13, 14, 17, 17, 18, 22]",
"[15, 7, 8, 11, 8, 15, 15, 4, 3, 4, 18, 1, 14, 18, 2, 18, 8, 18, 19, 14, 14, 5, 17, 4, 13, 2, 7]| [1, 2, 2, 3, 4, 4, 4, 5, 7, 7, 8, 8, 8, 11, 13, 14, 14, 14, 15, 15, 15, 17, 18, 18, 18, 18, 19]",
"[18, 16, 20, 0, 1, 1, 11, 4, 20, 15, 1, 24, 10, 4, 13, 3, 17, 8, 2, 10, 11, 0, 12, 0, 17]| [0, 0, 0, 1, 1, 1, 2, 3, 4, 4, 8, 10, 10, 11, 11, 12, 13, 15, 16, 17, 17, 18, 20, 20, 24]"
},
delimiter = '|')
public void testSort(String input, String output) {
Integer[] arrInput = ArrayFuncs.stringToArray(input);
Integer[] arrOutput = ArrayFuncs.stringToArray(output);
InsertionSort.sort(arrInput);
assertEquals(ArrayFuncs.arrayToString(arrOutput), ArrayFuncs.arrayToString(arrInput));
}
@Order(2)
@Tag("D")
@DisplayName("sort() takes linear time on a sorted array")
@Timeout(value = 10, unit = SECONDS)
@Test()
public void testSortedComplexity() {
Function<Integer, Integer[]> provide = ArrayFuncs::genSortedArray;
Consumer<Integer[]> sorted = InsertionSort::sort;
RuntimeInstrumentation.assertAtMost("sort()", RuntimeInstrumentation.ComplexityType.LINEAR, provide, sorted, 8);
}
@Order(3)
@Tag("D")
@DisplayName("sort() takes quadratic time on a random array")
@Timeout(value = 10, unit = SECONDS)
@Test()
public void testRandomComplexity() {
Function<Integer, Integer[]> provide = ArrayFuncs::genRandomArray;
Consumer<Integer[]> sorted = InsertionSort::sort;
RuntimeInstrumentation.assertAtMost("sort()", RuntimeInstrumentation.ComplexityType.QUADRATIC, provide, sorted, 8);
}
@Order(4)
@Tag("D")
@DisplayName("Does not use or import disallowed classes")
@Test()
public void testForInvalidClasses() {
List<String> regexps = List.of("java.util.Iterator",
"java.util.function.Function",
"java.util.HashMap",
"java.util.TreeMap",
"java.util.LinkedHashMap",
"java.util.ConcurrentHashMap",
"java.util.Map",
"java.util.SortedMap",
"java.util.Arrays",
"java.util.*",
"java.util.ArrayList",
"java.util.LinkedList",
"java.util.List",
"java\\.lang\\.reflect",
"java\\.io\\.(?!File|FileNotFoundException)");
Inspection.assertNoImportsOf("src/edu/caltech/cs2/datastructures/InsertionSort.java", regexps);
Inspection.assertNoUsageOf("src/edu/caltech/cs2/datastructures/InsertionSort.java", regexps);
}
}