- Formal Specifications Mypriorityqueue Type Extends Comparable Type Heap Myarraylist Type Insert Item Type Remov 1 (29.88 KiB) Viewed 58 times
Use this code to test if it's working:
public class MyPriorityQueueTest{private MyPriorityQueue<Integer> queue;@Beforepublic final void setup(){queue = new MyPriorityQueue<Integer>();}@Testpublic final void insert_0(){insert_ten_items_asc(queue);assertEquals("insert_0 failed", "[0, 1, 2, 3, 4, 5, 6, 7, 8,9]",queue.toString());}@Testpublic final void insert_1(){insert_ten_items_des(queue);assertEquals("insert_1 failed", "[0, 1, 4, 3, 2, 8, 5, 9, 6,7]",queue.toString());}@Testpublic final void insert_2(){insert_ten_items_ran(queue);assertEquals("insert_2 failed", "[0, 1, 6, 2, 4, 7, 8, 5, 3,9]",queue.toString());}@Testpublic final void insert_3(){insert_ten_items_ran(queue);insert_ten_items_ran(queue);assertEquals("insert_3 failed", "[0, 0, 1, 1, 4, 6, 3, 5, 2, 9, 5,7,7, 8, 4, 6, 8, 3, 2, 9]", queue.toString());}@Testpublic final void size_0(){assertEquals("size_0 failed", 0, queue.size());}@Testpublic final void size_1(){queue.insert(0);assertEquals("size_1 failed", 1, queue.size());
}@Testpublic final void size_2(){insert_ten_items_ran(queue);assertEquals("size_2 failed", 10, queue.size());}@Testpublic final void size_3(){insert_ten_items_ran(queue);insert_ten_items_ran(queue);assertEquals("size_3 failed", 20, queue.size());}@Testpublic final void empty_and_non_empty(){assertEquals("empty failed", true, queue.isEmpty());insert_ten_items_ran(queue);insert_ten_items_ran(queue);assertEquals("non_empty failed", false, queue.isEmpty());}@Testpublic final void min_0(){assertEquals("min_0 failed", null, queue.min());queue.insert(5);assertEquals("min_0 failed", Integer.valueOf(5),queue.min());queue.insert(2);assertEquals("min_0 failed", Integer.valueOf(2),queue.min());queue.insert(1);assertEquals("min_0 failed", Integer.valueOf(1),queue.min());queue.insert(3);assertEquals("min_0 failed", Integer.valueOf(1),queue.min());}@Testpublic final void remove_0(){assertEquals("remove_0 failed", null, queue.removeMin());assertEquals("remove_0 failed", "[]", queue.toString());insert_ten_items_ran(queue);assertEquals("remove_0 failed", Integer.valueOf(0),queue.removeMin());assertEquals("remove_0 failed", "[1, 2, 6, 3, 4, 7, 8, 5,9]",queue.toString());assertEquals("remove_0 failed", Integer.valueOf(1),queue.removeMin());assertEquals("remove_0 failed", "[2, 3, 6, 5, 4, 7, 8, 9]",queue.toString());assertEquals("remove_0 failed", Integer.valueOf(2),queue.removeMin());assertEquals("remove_0 failed", "[3, 4, 6, 5, 9, 7, 8]",queue.toString());assertEquals("remove_0 failed", Integer.valueOf(3),queue.removeMin());assertEquals("remove_0 failed", "[4, 5, 6, 8, 9, 7]",queue.toString());assertEquals("remove_0 failed", Integer.valueOf(4),queue.removeMin());
assertEquals("remove_0 failed", "[5, 7, 6, 8, 9]",queue.toString());assertEquals("remove_0 failed", Integer.valueOf(5),queue.removeMin());assertEquals("remove_0 failed", "[6, 7, 9, 8]",queue.toString());assertEquals("remove_0 failed", Integer.valueOf(6),queue.removeMin());assertEquals("remove_0 failed", "[7, 8, 9]",queue.toString());assertEquals("remove_0 failed", Integer.valueOf(7),queue.removeMin());assertEquals("remove_0 failed", "[8, 9]", queue.toString());assertEquals("remove_0 failed", Integer.valueOf(8),queue.removeMin());assertEquals("remove_0 failed", "[9]", queue.toString());assertEquals("remove_0 failed", Integer.valueOf(9),queue.removeMin());assertEquals("remove_0 failed", "[]", queue.toString());assertEquals("remove_0 failed", null, queue.removeMin());assertEquals("remove_0 failed", "[]", queue.toString());}@Testpublic final void example(){assertEquals("example failed", null, queue.min());assertEquals("example failed", "[]", queue.toString());queue.insert(4);assertEquals("example failed", Integer.valueOf(4),queue.min());assertEquals("example failed", "[4]", queue.toString());queue.insert(7);assertEquals("example failed", Integer.valueOf(4),queue.min());assertEquals("example failed", "[4, 7]", queue.toString());queue.insert(5);assertEquals("example failed", Integer.valueOf(4),queue.min());assertEquals("example failed", "[4, 7, 5]",queue.toString());queue.insert(2);assertEquals("example failed", Integer.valueOf(2),queue.min());assertEquals("example failed", "[2, 4, 5, 7]",queue.toString());queue.insert(3);assertEquals("example failed", Integer.valueOf(2),queue.min());assertEquals("example failed", "[2, 3, 5, 7, 4]",queue.toString());queue.insert(6);assertEquals("example failed", Integer.valueOf(2),queue.min());assertEquals("example failed", "[2, 3, 5, 7, 4, 6]",queue.toString());queue.insert(8);assertEquals("example failed", Integer.valueOf(2),queue.min());assertEquals("example failed", "[2, 3, 5, 7, 4, 6, 8]",queue.toString());queue.insert(9);assertEquals("example failed", Integer.valueOf(2),queue.min());assertEquals("example failed", "[2, 3, 5, 7, 4, 6, 8, 9]",queue.toString());queue.insert(1);assertEquals("example failed", Integer.valueOf(1),queue.min());assertEquals("example failed", "[1, 2, 5, 3, 4, 6, 8, 9, 7]",queue.toString());queue.insert(0);assertEquals("example failed", Integer.valueOf(0),queue.min());assertEquals("example failed", "[0, 1, 5, 3, 2, 6, 8, 9, 7,4]",queue.toString());}// ---------- helper methods ---------public final voidinsert_ten_items_asc(MyPriorityQueue<Integer> queue)
{for (int index = 0; index < 10; index++)queue.insert(index);}public final voidinsert_ten_items_des(MyPriorityQueue<Integer> queue){for (int index = 9; index >= 0; index--)queue.insert(index);}public final voidinsert_ten_items_ran(MyPriorityQueue<Integer> queue){int array[] = { 5, 3, 7, 1, 4, 6, 8, 2, 0, 9 };for (int index = 0; index < array.length; index++)queue.insert(array[index]);}
}
(Code is in java please use code's ive used and the test file iwill thumbs up if right)
Formal Specifications MyPriorityQueue<Type extends Comparable<Type>> #heap MyArrayList<Type> +insert(item : Type) +removeMin(): Type +min() Type +size(): int +isEmpty(): boolean +toString(): String #bubbleUp() #sinkDown () #parent (index : int) : int #right (index: int) : int
#left (index: int) : int Field summary • heap - The values of the heap will be stored in this underlying MyArrayList. Method summary • insert - Inserts the item into the heap and corrects the invariant. • It does so by following these steps: i. ii. • This method should run in O(Ign) time. • removeMin - Removes the first element and corrects the invariant. 0 Inserts the item at the end of the array list. iii. iv. Calls bubbleUp to move the item to the correct location. It does so by following these steps: i. Swaps the first element with the last element. ii. Removes the last element. Calls sinkDown to move the first element to the correct location. Returns the element removed. • This method should run in O(Ign) time. • min - Returns the first element. • This method should run in O(1) time. • size - Returns the number of elements in the heap. • This method should run in O(1) time. isEmpty - Returns true if the heap is empty and false otherwise. • This method should run in O(1) time. • toString - Returns the contents of the heap in String format. This method should run in O(n) time. • bubbleUp - Shifts the last element up to a position where it belongs to correct the heap invariant.
• bubbleUp - Shifts the last element up to a position where it belongs to correct the heap invariant. • It does so by following these steps: i. If the element is less than its parent: • Swap the element with its parent. Repeat with the new parent if it exists. • This method should use the compare To method to compare elements. • This method should run in O(Ign) time. sinkDown - Shifts the first element down to a position where it belongs to correct the heap invariant. • It does so by following these steps: i. If the element is less than at least one of its children: • Swap the element with its smallest child. · Repeat with the new children if they exist.
• Repeat with the new children if they exist. • This method should use the compare To method to compare elements. This method should run in O(Ign) time. • parent - Returns the index of the parent node in the heap. • This method should run in O(1) time. • left - Returns the index of the left child node in the heap of the index passed in. This method should run in O(1) time. • right - Returns the index of the right child node in the heap of the index passed in. • This method should run in O(1) time. Submission You will submit a .zip file containing: • MyArrayList.java MyPriority Queue.java Grading Rubric In order to count as complete your submission must pass all JUnit tests. In order to do that: 1. All class, field and method names must match these specifications exactly. 2. All method signatures must match these specifications exactly. 3. Your methods must function in the way specified and only in this way (do not perform extra functions). 4. Your methods must be free of bugs. If you are struggling to pass the tests, have bugs you can't find or error messages you don't understand then please reach out to me or your learning group.