Not surprisingly, pretty much a copy of the testing code of priority queue since they have the same behavior, except for the efficiency.
import static org.junit.Assert.*;
import java.util.NoSuchElementException;
import org.junit.Test;
public class TestPriorityHeap {
@Test
public void TestEmptyQueue() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
assertTrue(queue.isEmpty());
assertEquals(0,queue.size());
}
@Test
public void TestNonEmptyQueue() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.add("kiwi");
assertFalse(queue.isEmpty());
assertEquals(1,queue.size());
}
@Test(expected=NoSuchElementException.class)
public void TestElementEmptyQueue(){
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.element();
}
@Test(expected=NoSuchElementException.class)
public void TestRemoveFromEmptyQueue(){
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.remove();
}
@Test
public void TestAdd() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.add("banana");
queue.add("apple");
queue.add("strawberry");
String [] strings = new String[3];
String [] result = {"apple","banana","strawberry"};
int i = 0;
for (String str: queue){
strings[i] = str;
i++;
}
assertArrayEquals(strings, result);
assertEquals(3,queue.size());
}
@Test
public void TestAddAndElement() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.add("banana");
queue.add("apple");
queue.add("strawberry");
assertEquals("apple",queue.element());
assertEquals("apple",queue.element());
assertEquals(3,queue.size());
}
@Test
public void TestRemove() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.add("banana");
queue.add("apple");
queue.add("strawberry");
assertEquals("apple",queue.remove());
assertEquals("banana",queue.remove());
assertEquals(1,queue.size());
}
@Test
public void TestRemoveLast() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.add("banana");
queue.add("apple");
queue.add("strawberry");
queue.remove();
queue.remove();
assertFalse(queue.isEmpty());
assertEquals("strawberry",queue.remove());
assertTrue(queue.isEmpty());
}
@Test
public void TestAddAfterRemove() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.add("banana");
queue.remove();
queue.add("apple");
assertEquals("apple",queue.remove());
assertTrue(queue.isEmpty());
}
@Test (expected=NoSuchElementException.class)
public void TestClear() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.add("banana");
queue.add("strawberry");
queue.add("banana");
queue.clear();
assertTrue(queue.isEmpty());
assertEquals(0,queue.size());
queue.element();
}
@Test
public void TestAddAfterClear() {
OurQueue<String> queue = new PriorityQueueHeap<String>();
queue.add("banana");
queue.add("strawberry");
queue.add("apple");
queue.clear();
queue.add("kiwi");
assertFalse(queue.isEmpty());
assertEquals(1,queue.size());
assertEquals("kiwi",queue.element());
}
}
Starting code for PriorityQueueHeap:
import java.util.ArrayList;
import java.util.Iterator;
/**
*
* The class implements a min-priority queue, i.e. smaller numbers have higher
* priority. For instance, if the queue contains 2, 4, 1, then 1 is returned
* first, then 2, then 4. The smallest element in the queue is called the head
* of the queue. If the queue contains several elements with the same minimal
* value, any one of them may play the role of the head.
*
* Elements inserted in the the queue must implement Comparable interface. They
* are ordered based on the ordering determined by their compareTo method.
*
* The class employs a heap-based implementation, i.e. add and remove are
* guaranteed to work in O(log(n)) time.
*
* The queue is iterable. However, there are no guarantees on the order of the
* elements, i.e. they are in general not sorted.
*
* @param <E>
* - type of elements in the queue. Must implement Comparable<E>
*/
public class PriorityQueueHeap<E extends Comparable<E>> implements OurQueue<E>,
Iterable<E> {
private ArrayList<E> elements = new ArrayList<E>();
/**
* Returns true if this list contains no elements, false otherwise Runs in
* constant time.
*
* @return true if this list contains no elements, false otherwise
*/
public boolean isEmpty() {
return false;
}
/**
* Returns the number of elements in this queue. Runs in constant time.
*
* @return the number of elements in this queue
*/
public int size() {
return 0;
}
/**
* Inserts the specified element at its position in the priority queue. The
* position is determined by compareTo method: the element e is placed after
* all queue elements that are smaller than e based on compareTo and before
* all elements that are >= e. Runs in at most log N time where N is the
* number of elements currently in the queue.
*
* @param e
* - the element to be added to the queue
* @throws NullPointerException
* - if the specified element is null
*/
public void add(E e) {
}
/**
* Retrieves and removes the head of this queue. Runs in at most log N time
* where N is the number of elements currently in the queue. Throws:
* NoSuchElementException - if this queue is empty
*
* @return - the head of the queue
*/
public E remove() {
return null;
}
/**
* Retrieves but does not remove the head of this queue. Runs in constant
* time. Throws: NoSuchElementException - if this queue is empty
*
* @return - the head of the queue
*/
public E element() {
return null;
}
/**
* Removes all elements from the queue. This queue will be empty after this
* call returns.
*
* @return
*/
public void clear() {
}
/**
* Returns an iterator for the queue. There are no guarantees on the order
* of the elements, i.e. they are in general not sorted.
*/
public Iterator<E> iterator() {
return elements.iterator();
}
// swaps elements at indices i and j
// to-do: think about checking error conditions
private void swap(int i, int j) {
}
// returns the index of the parent of this node
// to-do: think about the behavior for the root
private int parent(int i) {
return 0;
}
// returns the index of the left child of this node
// to-do: think about the behavior if no such child
private int leftChild(int i) {
return 0;
}
// returns the index of the right child of this node
// to-do: think about the behavior if no such child
private int rightChild(int i) {
return 0;
}
}