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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
package edu.caltech.cs2.datastructures;
import edu.caltech.cs2.helpers.Inspection;
import edu.caltech.cs2.helpers.Reflection;
import edu.caltech.cs2.helpers.RuntimeInstrumentation;
import edu.caltech.cs2.interfaces.IFixedSizeQueue;
import edu.caltech.cs2.interfaces.IQueue;
import org.junit.jupiter.api.*;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;
import org.junit.jupiter.params.provider.ValueSource;
import java.lang.reflect.Constructor;
import java.util.*;
import java.util.function.Consumer;
import java.util.function.Function;
import static edu.caltech.cs2.project03.Project03TestOrdering.*;
import static java.util.concurrent.TimeUnit.SECONDS;
import static org.junit.jupiter.api.Assertions.*;
@Tag("B")
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
public class CircularArrayFixedSizeQueueTests implements FixedSizeQueueTests {
private static String FIXED_QUEUE_SOURCE = "src/edu/caltech/cs2/datastructures/CircularArrayFixedSizeQueue.java";
private Constructor circFixedSizeQueueConstructor = Reflection.getConstructor(CircularArrayFixedSizeQueue.class,
int.class);
private int DEFAULT_CAPACITY = 10;
public IQueue<Object> newQueue() {
return Reflection.newInstance(circFixedSizeQueueConstructor, DEFAULT_CAPACITY);
}
public IQueue<Object> newQueue(int capacity) {
return Reflection.newInstance(circFixedSizeQueueConstructor, capacity);
}
public IFixedSizeQueue<Object> newFixedSizeQueue(int capacity) {
return Reflection.newInstance(circFixedSizeQueueConstructor, capacity);
}
// FIXED QUEUE-SPECIFIC TESTS ----------------------------------------
@Order(classSpecificTestLevel)
@DisplayName("Does not use or import disallowed classes")
@Test
public void testForInvalidClasses() {
List<String> regexps = List.of("java\\.util\\.(?!Iterator)", "java\\.lang\\.reflect", "java\\.io");
Inspection.assertNoImportsOf(FIXED_QUEUE_SOURCE, regexps);
Inspection.assertNoUsageOf(FIXED_QUEUE_SOURCE, regexps);
}
@Order(classSpecificTestLevel)
@DisplayName("There are no static fields")
@Test
public void testConstantFields() {
Reflection.assertFieldsEqualTo(CircularArrayFixedSizeQueue.class, "static", 0);
}
@Order(classSpecificTestLevel)
@DisplayName("The overall number of fields is small")
@Test
public void testSmallNumberOfFields() {
Reflection.assertFieldsLessThan(CircularArrayFixedSizeQueue.class, "private", 4);
}
@Order(classSpecificTestLevel)
@DisplayName("There are no public fields")
@Test
public void testNoPublicFields() {
Reflection.assertNoPublicFields(CircularArrayFixedSizeQueue.class);
}
@Order(classSpecificTestLevel)
@DisplayName("There are no protected fields")
@Test
public void testNoProtectedFields() {
Reflection.assertNoProtectedFields(CircularArrayFixedSizeQueue.class);
}
@Order(classSpecificTestLevel)
@DisplayName("All fields in CircularArrayFixedSizeQueue have modifiers")
@Test
public void testFieldModifiers() {
Reflection.assertFieldModifiers(CircularArrayFixedSizeQueue.class);
}
@Order(classSpecificTestLevel)
@DisplayName("The public interface is correct")
@Test
public void testPublicInterface() {
Reflection.assertPublicInterface(CircularArrayFixedSizeQueue.class,
List.of("enqueue", "dequeue", "peek", "iterator", "size", "isFull", "capacity", "toString"));
}
@Order(classSpecificTestLevel)
@DisplayName("Uses this(...) notation in all but one constructor")
@Test
public void testForThisConstructors() {
Inspection.assertConstructorHygiene(FIXED_QUEUE_SOURCE);
}
// TOSTRING TESTS ---------------------------------------------------
@Order(toStringTestLevel)
@DisplayName("toString is correctly overridden")
@Test
public void testToStringOverride() {
Reflection.assertMethodCorrectlyOverridden(ArrayDeque.class, "toString");
}
@Order(toStringTestLevel)
@DisplayName("toString() matches java.util.ArrayDeque")
@ParameterizedTest(name = "Test toString() on [{arguments}]")
@ValueSource(strings = { "0, 1, 2, 3", "5, 4, 3, 2, 1", "8, 3, 5, 7, 4, 3, 12, 12, 1" })
public void testToString(String inputs) {
java.util.ArrayDeque<String> reference = new java.util.ArrayDeque<String>();
Constructor c = Reflection.getConstructor(CircularArrayFixedSizeQueue.class, int.class);
IFixedSizeQueue<String> me = Reflection.newInstance(c, inputs.length());
for (String value : inputs.trim().split(", ")) {
assertEquals(reference.toString(), me.toString(), "toString outputs should be the same");
reference.addLast(value);
me.enqueue(value);
}
}
// TIME COMPLEXITY TESTS ------------------------------------------------
@Order(complexityTestLevel)
@DisplayName("enqueue() and dequeue() take constant time")
@Timeout(value = 10, unit = SECONDS)
@Test()
public void testQueueOperationComplexity() {
Function<Integer, IFixedSizeQueue<Integer>> provide = (Integer numElements) -> {
Constructor c = Reflection.getConstructor(CircularArrayFixedSizeQueue.class, int.class);
IFixedSizeQueue<Integer> q = Reflection.newInstance(c, numElements * 2);
for (int i = 0; i < numElements; i++) {
q.enqueue(i);
}
return q;
};
Consumer<IFixedSizeQueue<Integer>> enqueue = (IFixedSizeQueue<Integer> q) -> q.enqueue(0);
Consumer<IFixedSizeQueue<Integer>> dequeue = (IFixedSizeQueue<Integer> q) -> q.dequeue();
RuntimeInstrumentation.assertAtMost("enqueue", RuntimeInstrumentation.ComplexityType.CONSTANT, provide, enqueue, 8);
RuntimeInstrumentation.assertAtMost("dequeue", RuntimeInstrumentation.ComplexityType.CONSTANT, provide, dequeue, 8);
}
@Order(complexityTestLevel)
@DisplayName("peek() takes constant time")
@Timeout(value = 10, unit = SECONDS)
@Test()
public void testPeekComplexity() {
Function<Integer, IFixedSizeQueue<Integer>> provide = (Integer numElements) -> {
Constructor c = Reflection.getConstructor(CircularArrayFixedSizeQueue.class, int.class);
IFixedSizeQueue<Integer> q = Reflection.newInstance(c, numElements * 2);
for (int i = 0; i < numElements; i++) {
q.enqueue(i);
}
return q;
};
Consumer<IFixedSizeQueue<Integer>> peek = (IFixedSizeQueue<Integer> q) -> q.peek();
RuntimeInstrumentation.assertAtMost("peek", RuntimeInstrumentation.ComplexityType.CONSTANT, provide, peek, 8);
}
@Order(fixedSizeQueueLevel)
@DisplayName("Test iterator matches reference for wraparound values")
@ParameterizedTest(name = "Test iterator and wraparound behavior with {1} random values with seed = {0} and fixed array size = {2}")
@CsvSource({ "69, 200, 20", "21, 300, 200" })
public void testWrapAround(int seed, int numVals, int queueSize) {
Random r = new Random(seed);
IFixedSizeQueue<Object> me = newFixedSizeQueue(queueSize);
Queue<Object> reference = new java.util.ArrayDeque<>();
assertEquals(queueSize, me.capacity(), "capacity does not match expected value");
for (int i = 0; i < queueSize; i++) {
int num = r.nextInt();
assertFalse(me.isFull(), "queue should not be full");
assertTrue(me.enqueue(num), "enqueue should be successful");
reference.add(num);
}
for (int i = 0; i < numVals; i++) {
me.enqueue(me.dequeue());
reference.add(reference.remove());
assertEquals(reference.peek(), me.peek(), "return values of peek()s are not equal");
assertEquals(reference.size(), me.size(), "size()s are not equal");
assertEquals(queueSize, me.capacity(), "capacity of a fixed size queue should not change");
assertIterableEquals(reference, me, "Reference and implemented queues are not equal");
}
}
}