Newer
Older
import cse332.interfaces.worklists.PriorityWorkList;
import cse332.interfaces.worklists.WorkList;
import datastructures.worklists.MinFourHeap;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.Timeout;
import java.lang.reflect.Field;
import java.util.*;
import java.util.concurrent.TimeUnit;
import static org.junit.jupiter.api.Assertions.*;
public class MinFourHeapTests {
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
public void test_hasWork_empty_noWork() {
WorkList<Integer> STUDENT_INT = new MinFourHeap<>(Integer::compareTo);
assertFalse(STUDENT_INT.hasWork());
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
public void test_hasWork_oneElement_hasWork() {
WorkList<Integer> STUDENT_INT = new MinFourHeap<>(Integer::compareTo);
STUDENT_INT.add(1);
assertTrue(STUDENT_INT.hasWork());
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
public void test_addNextHasWork_manyElements_noWork() {
WorkList<Double> STUDENT_DOUBLE = new MinFourHeap<>(Double::compareTo);
for (int i = 0; i < 1000; i++) {
STUDENT_DOUBLE.add(Math.random());
}
for (int i = 0; i < 1000; i++) {
STUDENT_DOUBLE.next();
}
assertFalse(STUDENT_DOUBLE.hasWork());
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
public void test_peek_fewElements_throwsException() {
WorkList<Integer> STUDENT_INT = new MinFourHeap<>(Integer::compareTo);
assertThrows(NoSuchElementException.class, () -> {
STUDENT_INT.peek();
});
assertThrows(NoSuchElementException.class, () -> {
STUDENT_INT.peek();
});
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
public void test_next_fewElements_throwsException() {
WorkList<Integer> STUDENT_INT = new MinFourHeap<>(Integer::compareTo);
assertThrows(NoSuchElementException.class, () -> {
STUDENT_INT.next();
});
assertThrows(NoSuchElementException.class, () -> {
STUDENT_INT.next();
});
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
public void test_clear_fewElements_empty() {
WorkList<String> STUDENT_STR = new MinFourHeap<>(String::compareTo);
addAll(STUDENT_STR, new String[]{"Beware", "the", "Jabberwock", "my", "son!"});
assertTrue(STUDENT_STR.hasWork());
assertEquals(5, STUDENT_STR.size());
STUDENT_STR.clear();
assertFalse(STUDENT_STR.hasWork());
assertEquals(0, STUDENT_STR.size());
assertThrows(NoSuchElementException.class, () -> {
STUDENT_STR.peek();
});
assertThrows(NoSuchElementException.class, () -> {
STUDENT_STR.next();
});
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
PriorityWorkList<String> heap = new MinFourHeap<>(String::compareTo);
String[] tests = { "a", "b", "c", "d", "e" };
for (int i = 0; i < 5; i++) {
String str = tests[i] + "a";
heap.add(str);
}
for (int i = 0; i < 5; i++) {
String str_heap = heap.next();
String str = (char) ('a' + i) + "a";
assertEquals(str, str_heap);
}
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
public void test_addPeekNext_differentOrderings_correctStructure() {
PriorityWorkList<String> ordered = new MinFourHeap<>(String::compareTo);
PriorityWorkList<String> reversed = new MinFourHeap<>(String::compareTo);
PriorityWorkList<String> random = new MinFourHeap<>(String::compareTo);
addAll(ordered, new String[]{"a", "b", "c", "d", "e"});
addAll(reversed, new String[]{"e", "d", "c", "b", "a"});
addAll(random, new String[]{"d", "b", "c", "e", "a"});
assertTrue(isSame("a", ordered.peek(), reversed.peek(), random.peek()));
assertTrue(isSame("a", ordered.next(), reversed.next(), random.next()));
assertTrue(isSame("b", ordered.next(), reversed.next(), random.next()));
addAll(ordered, new String[] {"a", "a", "b", "c", "z"});
addAll(reversed, new String[] {"z", "c", "b", "a", "a"});
addAll(random, new String[] {"c", "z", "a", "b", "a"});
String[] expected = new String[] {"a", "a", "b", "c", "c", "d", "e", "z"};
for (String e : expected) {
assertTrue(isSame(e, ordered.peek(), reversed.peek(), random.peek()));
assertTrue(isSame(e, ordered.next(), reversed.next(), random.next()));
}
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
PriorityWorkList<String> heap = new MinFourHeap<>(String::compareTo);
int n = 10000;
// Add them
for (int i = 0; i < n; i++) {
String str = String.format("%05d", i * 37 % n);
heap.add(str);
}
// Delete them all
for (int i = 0; i < n; i++) {
String s = heap.next();
assertEquals(i , Integer.parseInt(s));
}
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
public void test_customComparator_manyElements_correctStructure() {
Random RAND = new Random(SEED);
PriorityWorkList<Coordinate> student = new MinFourHeap<>(Coordinate::compareTo);
Queue<Coordinate> reference = new PriorityQueue<>();
for (int i = 0; i < 10000; i++) {
Coordinate coord = new Coordinate(RAND.nextInt(10000) - 5000, RAND.nextInt(10000) - 5000);
student.add(coord);
reference.add(coord);
}
assertEquals(reference.size(), student.size());
while (!reference.isEmpty()) {
assertEquals(reference.peek() , student.peek());
assertEquals(reference.remove() , student.next());
}
}
@Test()
@Timeout(value = 3000, unit = TimeUnit.MILLISECONDS)
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
PriorityWorkList<Integer> heap = new MinFourHeap<>(Integer::compareTo);
addAll(heap, new Integer[] {10, 10, 15, 1, 17, 16, 100, 101, 102, 103, 105, 106, 107, 108});
Object[] heapData = getField(heap, "data");
String heapStr = Arrays.toString(heapData);
String heapExp = "[1, 10, 15, 10, 17, 16, 100, 101, 102, 103, 105, 106, 107, 108";
heap.next();
heap.next();
heap.next();
Object[] heapData2 = getField(heap, "data");
String heapStr2 = Arrays.toString(heapData2);
String heapExp2 = "[15, 16, 103, 107, 17, 108, 100, 101, 102, 106, 105,";
assertTrue(heapStr.contains(heapExp));
assertTrue(heapStr2.contains(heapExp2));
}
public static class Coordinate implements Comparable<Coordinate> {
private final int x;
private final int y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
// What exactly this comparable method is doing is somewhat arbitrary.
public int compareTo(Coordinate other) {
if (this.x != other.x) {
return this.x - other.x;
} else {
return this.y - other.y;
}
}
}
private boolean isSame(String... args) {
String first = args[0];
for (String arg : args) {
if (!first.equals(arg)) {
return false;
}
}
return true;
}
protected static <E> void addAll(WorkList<E> worklist, E[] values) {
for (E value : values) {
worklist.add(value);
}
}
protected static <E> void addAndRemove(WorkList<E> worklist, E value, int amount) {
for (int i = 0; i < amount; i++) {
worklist.add(value);
}
for (int i = 0; i < amount; i++) {
worklist.next();
}
}
protected <T> T getField(Object o, String fieldName) {
try {
Field field = o.getClass().getSuperclass().getDeclaredField(fieldName);
field.setAccessible(true);
Object f = field.get(o);
return (T) f;
} catch (Exception var6) {
try {
Field field = o.getClass().getDeclaredField(fieldName);
field.setAccessible(true);
Object f = field.get(o);
return (T) f;
} catch (Exception var5) {
return null;
}
}
}
}