package edu.caltech.cs2.datastructures; import edu.caltech.cs2.helpers.*; import java.util.*; import java.util.ArrayList; import edu.caltech.cs2.interfaces.IDictionary; import edu.caltech.cs2.interfaces.IPriorityQueue; import edu.caltech.cs2.misc.IntegerComparator; import org.junit.jupiter.api.*; import org.junit.jupiter.api.extension.ExtendWith; import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.CsvSource; import static org.junit.jupiter.api.Assertions.*; @ExtendWith(TestExtension.class) @TestMethodOrder(MethodOrderer.OrderAnnotation.class) public class MinFourHeapTests { private static String STRING_SOURCE = "src/edu/caltech/cs2/datastructures/MinFourHeap.java"; public void checkKeyToIndexMap(MinFourHeap heap) { // Check keyToIndexMap IPriorityQueue.PQElement[] heapData = Reflection.getFieldValue(MinFourHeap.class, "data", heap); IDictionary indexMap = Reflection.getFieldValue(MinFourHeap.class, "keyToIndexMap", heap); assertEquals(heap.size(), indexMap.size(), "Heap size and keyToIndexMap sizes are different"); // Reconstruct data from map Integer[] dataFromMap = new Integer[heap.size()]; for (IDictionary.Entry entry : indexMap.entrySet()) { assertTrue(entry.value < heap.size(), "Index in keyToIndexMap is larger than heap size"); // If not null, then was set prior assertNull(dataFromMap[entry.value], "Index appears multiple times in keyToIndexMap"); dataFromMap[entry.value] = entry.key; } // Only check data that's actually in the heap for (int i = 0; i < heap.size(); i++) { assertEquals(heapData[i].data, dataFromMap[i], "keyToIndexMap does not match heap data at index " + i); } } @Order(0) @DisplayName("Does not use or import disallowed classes") @TestHint("Remember that you're not allowed import any other packages except for java.util") @Test @Tag("C") public void testForInvalidClasses() { List regexps = List.of("java.lang.reflect", "java.io"); Inspection.assertNoImportsOf(STRING_SOURCE, regexps); Inspection.assertNoUsageOf(STRING_SOURCE, regexps); } @Order(1) @DisplayName("Does not use or import disallowed classes from java.util") @TestHint("Remember that you're not allowed import any other class except Iterator from java.util") @Test @Tag("C") public void testForInvalidImportsJavaUtil() { List allowed = List.of("Iterator"); Inspection.assertNoImportsOfExcept(STRING_SOURCE, "java\\.util", allowed); List bannedUsages = List.of("java\\.util\\.(?!" + String.join("|", allowed) + ")"); Inspection.assertNoUsageOf(STRING_SOURCE, bannedUsages); } @Test @Tag("C") @Order(2) @DisplayName("The public interface is correct") @TestDescription("This test checks that you haven't declared any extra public methods.") @TestHint("You are welcome to make any extra methods you want, but they have to be private!") public void testPublicInterface() { Reflection.assertPublicInterface(MinFourHeap.class, List.of("enqueue", "dequeue", "iterator", "decreaseKey", "increaseKey", "peek", "size")); } @Test @Tag("C") @Order(3) @DisplayName("Attempting to enqueue duplicate elements throws an exception") @TestDescription("Checking that the heap implementation does not allow for two elements with the same data") @TestHint("Remember equality of two elements is tests by their data fields. Additionally, the heap should have only have elements with unique data") @DependsOn({"enqueue"}) public void testDuplicateThrows() { MinFourHeap heap = new MinFourHeap<>(); heap.enqueue(new IPriorityQueue.PQElement<>(10, 10)); assertThrows(IllegalArgumentException.class, () -> { heap.enqueue(new IPriorityQueue.PQElement<>(10, 10)); }); } @Test @Tag("C") @Order(3) @DisplayName("Attempting to modify the priority of a nonexistent element throws an exception") @TestDescription("This test checks that if an element doesn't exist in the heap, your implementation " + "should not be able to call increaseKey and decreaseKey on such element.") @TestHint("Make sure you are throwing an exception for nonexistent elements in increaseKey and decreaseKey") @DependsOn({"increaseKey", "decreaseKey"}) public void testChangeKeyNonexistentElem() { MinFourHeap heap = new MinFourHeap<>(); heap.enqueue(new IPriorityQueue.PQElement<>(10, 10)); assertThrows(IllegalArgumentException.class, () -> { heap.increaseKey(new IPriorityQueue.PQElement<>(11, 11)); }); assertThrows(IllegalArgumentException.class, () -> { heap.decreaseKey(new IPriorityQueue.PQElement<>(11, 11)); }); } @Test @Tag("C") @Order(3) @DisplayName("Calling increaseKey with a lower priority or decreaseKey with a higher priority throws an exception") @TestDescription("This test checks that increaseKey and decreaseKey only accept the arguments they should.") @TestHint("Make sure you are throwing an exception when increaseKey is asked to decrease a key's priority, " + "and vice versa for decreaseKey.") @DependsOn({"increaseKey", "decreaseKey"}) public void testChangeKeyWrongWay() { MinFourHeap heap = new MinFourHeap<>(); heap.enqueue(new IPriorityQueue.PQElement<>(10, 10)); assertThrows(IllegalArgumentException.class, () -> { heap.increaseKey(new IPriorityQueue.PQElement<>(10, 9)); }); assertThrows(IllegalArgumentException.class, () -> { heap.decreaseKey(new IPriorityQueue.PQElement<>(10, 11)); }); } @Test @Tag("C") @Order(4) @DisplayName("Smoke test enqueue while checking internal state of heap") @TestDescription("This test makes sure the enqueue functions as intended") @TestHint("Make sure to sift up as you enqueue elements into the heap") @DependsOn({"enqueue", "size", "keyToIndexMap (field)", "data (field)"}) public void testEnqueue() { // create heap MinFourHeap heap = new MinFourHeap<>(); List values = new ArrayList<>(Arrays.asList(9, -100, 19, 3, -2, 1, 7, -84, -4, 2, 70)); // step by step look at what heap internal data array should look like List> step_by_step = new ArrayList<>(); step_by_step.add(Arrays.asList(9)); step_by_step.add(Arrays.asList(-100, 9)); step_by_step.add(Arrays.asList(-100, 9, 19)); step_by_step.add(Arrays.asList(-100, 9, 19, 3)); step_by_step.add(Arrays.asList(-100, 9, 19, 3, -2)); step_by_step.add(Arrays.asList(-100, 1, 19, 3, -2, 9)); step_by_step.add(Arrays.asList(-100, 1, 19, 3, -2, 9, 7)); step_by_step.add(Arrays.asList(-100, -84, 19, 3, -2, 9, 7, 1)); step_by_step.add(Arrays.asList(-100, -84, 19, 3, -2, 9, 7, 1, -4)); step_by_step.add(Arrays.asList(-100, -84, 2, 3, -2, 9, 7, 1, -4, 19)); step_by_step.add(Arrays.asList(-100, -84, 2, 3, -2, 9, 7, 1, -4, 19, 70)); // enqueue values while examining internal state for (int i = 0; i < values.size(); i++) { assertTrue(heap.enqueue(new IPriorityQueue.PQElement<>(values.get(i), values.get(i)))); assertEquals(i + 1, heap.size()); IPriorityQueue.PQElement[] heapData = Reflection.getFieldValue(MinFourHeap.class, "data", heap); for (int j = 0; j < heap.size(); j++) { assertEquals(step_by_step.get(i).toArray()[j], heapData[j].data); } checkKeyToIndexMap(heap); } } @Test @Tag("C") @Order(4) @DisplayName("Smoke test dequeue while checking internal state of heap") @TestDescription("This test makes sure the dequeue functions as intended") @TestHint("Make sure to sift down as you dequeue elements into the heap. " + "Double check that in your dequeue() function in MinFourHeap, " + "that you are handling the case where you are attempting to dequeue the last element in the heap. " + "Make sure that you avoid running keyToIndexMap.put((data[0].data, 0)) (as this will throw a null pointer " + "when data[0] is null) - handle this case independently instead. ") @DependsOn({"enqueue", "dequeue", "size", "keyToIndexMap (field)", "data (field)"}) public void testDequeue() { Comparator c = new IntegerComparator(); MinFourHeap heap = new MinFourHeap<>(); PriorityQueue reference = new PriorityQueue<>(c); List values = new ArrayList<>(Arrays.asList(9, -100, 19, 3, -2, 1, 7, -84, -4, 2, 70)); for (int value : values) { assertTrue(heap.enqueue(new IPriorityQueue.PQElement<>(value, value))); reference.add(value); } for (int i = 0; i < reference.size(); i++) { assertEquals(reference.remove(), heap.dequeue().data); checkKeyToIndexMap(heap); assertEquals(reference.size(), heap.size()); } } @Test @Tag("C") @Order(5) @DisplayName("Smoke test increaseKey while checking internal state of heap") @TestDescription("This test makes sure the increaseKey functions as intended") @TestHint("Make sure to sift down when you increase the key of an element") @DependsOn({"enqueue", "increaseKey", "size", "data (field)"}) public void testIncreaseKey() { // Build heap MinFourHeap heap = new MinFourHeap<>(); List values = new ArrayList<>(Arrays.asList(9, -100, 19, 3, -2, 1, 7, -84, -4, 2, 70)); for (Integer value : values) { assertTrue(heap.enqueue(new IPriorityQueue.PQElement<>(value, value))); } // Assert constructed heap is correct Integer[] correctHeapData = {-100, -84, 2, 3, -2, 9, 7, 1, -4, 19, 70}; IPriorityQueue.PQElement[] heapData = Reflection.getFieldValue(MinFourHeap.class, "data", heap); for (int j = 0; j < heap.size(); j++) { assertEquals(correctHeapData[j], heapData[j].data); } // Increase the root's priority heap.increaseKey(new IPriorityQueue.PQElement<>(-100, 100)); // Verify the heap after moving is correct double[] correctHeapPrioritiesAfterIncrease = {-84, -4, 2, 3, -2, 9, 7, 1, 100, 19, 70}; heapData = Reflection.getFieldValue(MinFourHeap.class, "data", heap); checkKeyToIndexMap(heap); for (int i = 0; i < heap.size(); i++) { assertEquals(correctHeapPrioritiesAfterIncrease[i], heapData[i].priority); } } @Test @Tag("C") @Order(5) @DisplayName("Smoke test decreaseKey while checking internal state of heap") @TestDescription("This test makes sure the decreaseKey functions as intended") @TestHint("Make sure to sift up when you decrease the key of an element") @DependsOn({"enqueue", "decreaseKey", "size", "data (field)"}) public void testDecreaseKey() { // Build heap MinFourHeap heap = new MinFourHeap<>(); List values = new ArrayList<>(Arrays.asList(9, -100, 19, 3, -2, 1, 7, -84, -4, 2, 70)); for (Integer value : values) { assertTrue(heap.enqueue(new IPriorityQueue.PQElement<>(value, value))); } // Assert constructed heap is correct Integer[] correctHeapData = {-100, -84, 2, 3, -2, 9, 7, 1, -4, 19, 70}; IPriorityQueue.PQElement[] heapData = Reflection.getFieldValue(MinFourHeap.class, "data", heap); for (int j = 0; j < heap.size(); j++) { assertEquals(correctHeapData[j], heapData[j].data); } // Decrease some node's priority heap.decreaseKey(new IPriorityQueue.PQElement<>(7, -105)); // Verify the heap after moving is correct double[] correctHeapPrioritiesAfterDecrease = {-105, -100, 2, 3, -2, 9, -84, 1, -4, 19, 70}; heapData = Reflection.getFieldValue(MinFourHeap.class, "data", heap); checkKeyToIndexMap(heap); for (int i = 0; i < heap.size(); i++) { assertEquals(correctHeapPrioritiesAfterDecrease[i], heapData[i].priority); } } @Test @Tag("C") @Order(6) @DisplayName("Dequeueing with no further percolation leaves the heap in a consistent state") @TestDescription("This test make sure you do not sift the heap around if the dequeue operation leaves the heap in a valid state") @TestHint("After dequeueing, you should only sift if the heap structure is violated") @DependsOn({"enqueue", "dequeue", "size", "keyToIndexMap (field)", "data (field)"}) public void testDequeueWithNoPercolation() { MinFourHeap heap = new MinFourHeap<>(); List values = new ArrayList<>(Arrays.asList(1, 6, 7, 8, 2)); for (int value : values) { assertTrue(heap.enqueue(new IPriorityQueue.PQElement<>(value, value))); } // Dequeueing 1 won't cause any further percolations, since 2 is in the right place. // There's some edge cases around this for some reason, which is why the test is here... assertEquals(1, heap.dequeue().data); checkKeyToIndexMap(heap); } @Tag("C") @Order(6) @Test @DisplayName("Check that increaseKey that percolates near end of array does not throw") @TestDescription("This test tries to increase the key so that the element gets placed at the end of the heap") @TestHint("Make sure that the indicies in your heap array are not dependent on priority") @DependsOn({"enqueue", "increaseKey", "data (field)"}) public void testDecreaseKeyBeyondArrayBounds() { MinFourHeap heap = new MinFourHeap<>(); // Heap: // 0 => [2 => [5, 6, 7, 8], 1 => [9], 3 => [], 4 => []] List values = new ArrayList<>(Arrays.asList(0, 2, 1, 3, 4, 5, 6, 7, 8, 9)); for (int value : values) { assertTrue(heap.enqueue(new IPriorityQueue.PQElement<>(value, value))); } IPriorityQueue.PQElement[] heapData = Reflection.getFieldValue(MinFourHeap.class, "data", heap); // Make sure our heap data is still "good" for the test assertEquals(10, heapData.length, "Heap data array is not a default size of 10 or was resized prematurely"); // Increase the node at the root. The node gets swapped with 1, then compared against children. // But, 9 is at the last index in the heap array and not the last child. heap.increaseKey(new IPriorityQueue.PQElement<>(0, 100)); // Correctness is checked elsewhere, so don't do anything here. Only thing that matters is that this // executes successfully. // 1 => [2 => [5, 6, 7, 8], 9 => [0 (100)], 3 => [], 4 => []] } @Tag("C") @Order(7) @ParameterizedTest(name = "Stress test increaseKey and decreaseKey with {1} random elements and seed = {0}") @DisplayName("Stress test increaseKey, decreaseKey") @TestDescription("Creates random data to test the stability of increaseKey and decreaseKey") @TestHint("Make sure that all these methods exist (i.e. you have written a percolateDown (or equiv. name) method and findSmallestChild method) and that you are accounting for:\n" + "1. Cases where some or all of the children are null and/or out of bounds\n" + "2. Cases where all children have a higher priority than their parent, so no swapping should occur") @DependsOn({"enqueue", "size", "dequeue", "increaseKey", "decreaseKey", "data (field)"}) @CsvSource({"100, 30000, 15000", "42, 10000, 5000"}) public void stressTestIncreaseDecrease(int seed, int size, int numToReplace) { MinFourHeap heap = new MinFourHeap<>(); Comparator c = new IntegerComparator(); PriorityQueue reference = new PriorityQueue<>(c); Set removed = new TreeSet<>(); Random r = new Random(seed); for (int i = 0; i < size; i++) { int num = r.nextInt(); while (reference.contains(num)) { num = r.nextInt(); } reference.add(num); heap.enqueue(new IPriorityQueue.PQElement<>(num, num)); assertEquals(reference.size(), heap.size()); } for (int j = 0; j < numToReplace; j++) { int newPriority = r.nextInt(); while (reference.contains(newPriority) || removed.contains(newPriority)) { newPriority = r.nextInt(); } IPriorityQueue.PQElement[] heapData = Reflection.getFieldValue(MinFourHeap.class, "data", heap); Integer origKey = heapData[r.nextInt(heap.size())].data; while (removed.contains(origKey)) { origKey = heapData[r.nextInt(heap.size())].data; } if (newPriority < origKey) { heap.decreaseKey(new IPriorityQueue.PQElement<>(origKey, newPriority)); } else { heap.increaseKey(new IPriorityQueue.PQElement<>(origKey, newPriority)); } assertEquals(reference.size(), heap.size()); removed.add(origKey); reference.remove(origKey); reference.add(newPriority); assertEquals(reference.size(), heap.size()); } int i = 0; while (!reference.isEmpty()) { Integer er = reference.remove(); IPriorityQueue.PQElement mr = heap.dequeue(); if (er != mr.priority) { System.err.println(i); System.err.println(reference.size()); System.err.println(heap.size()); } assertEquals((double) er, mr.priority); i++; } } @Tag("C") @Order(7) @ParameterizedTest(name = "Stress test enqueue and dequeue with {1} random elements and seed = {0}") @CsvSource({"100, 10000", "42, 10000"}) @DisplayName("Stress test enqueue, dequeue") @TestDescription("Creates random data to test the stability of enqueue and dequeue") @TestHint("Make sure that all these methods exist (i.e. you have written a percolateDown (or equiv. name) method and findSmallestChild method) and that you are accounting for:\n" + "1. Cases where some or all of the children are null and/or out of bounds\n" + "2. Cases where all children have a higher priority than their parent, so no swapping should occur") @DependsOn({"enqueue", "dequeue", "size", "data (field)", "keyToIndexMap (field)"}) public void stressTestEnqueueDequeue(int seed, int size) { MinFourHeap heap = new MinFourHeap<>(); Comparator c = new IntegerComparator(); PriorityQueue reference = new PriorityQueue<>(c); Random r = new Random(seed); for (int i = 0; i < size; i++) { int num = r.nextInt(); while (reference.contains(num)) { num = r.nextInt(); } reference.add(num); assertTrue(heap.enqueue(new IPriorityQueue.PQElement<>(num, num))); // Check at intervals to save computation if (i % 499 == 0) { checkKeyToIndexMap(heap); } assertEquals(reference.size(), heap.size()); } while (heap.size() != 0) { assertEquals(reference.remove(), heap.dequeue().data); if (heap.size() % 499 == 0) { checkKeyToIndexMap(heap); } } } }