CSci 2101 Lab 7: priority queue, introduction to jUnit

Tuesday March 21st

30 points

Your goal is to write jUnit tests for priority queue and implement its functionality to pass the tests. Specifically, you need to implement:

  1. Finish the add method
  2. Test and implement the iterator. Note: testing iterators is tricky!
  3. Test and implement remove in the priority queue. Make sure to test it not just in isolation, but also with other methods. Make sure to test for necessary exceptions.

Work in pairs, use Eclipse.

jUnit resources: jUnit API (find the Assert class)

Starting code from Monday class:

jUnit tests

Our queue interface:


/**
 * A collection that typically stores its elements in a FIFO
 * (first-in-first-out) manner
 * Modeled after Queue interface in the Java Collections Framework
 *
 * @author Elena Machkasova for CSCi 2101 
 *
 * @param <E> - the type of elements it holds
 */
public interface OurQueue<E> extends Iterable<E> {
	/**
	 * Returns the number of elements in this queue.
	 * 
	 * @return the size of the queue
	 */
	public int size();
	
	/**
	 * Returns true if this collection contains no elements, false 
	 * otherwise.
	 * 
	 * @return true if this collection contains no elements, false 
	 * otherwise.
	 */
	public boolean isEmpty();
	
	/**
	 * Retrieves, but does not remove, the head of this queue. 
	 * Throws an exception if this queue is empty. 
	 * 
	 * @return the head of this queue. 
	 * @throws NoSuchElementException - if this queue is empty.
	 */
	public E element();
	
	/**
	 * Adds an element to the end of the queue
	 * 
	 * @param element - the element to be added to the queue
	 */
	public void add(E element);
	
	/**
	 * Retrieves and removes the head of this queue. 
	 * Throws an exception if this queue is empty. 
	 * 
	 * @return the head of this queue
	 * @throws NoSuchElementException - if this queue is empty.
	 */
	public E remove();
	
	/**
	 * Removes all of the elements from this queue making it empty.
	 */
	public void clear();
	
}
  

Priority queue class:


/**
 * 
 * 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. 
 *
 * @param <E> - type of elements in the queue. Must implement Comparable<E>
 */
import java.util.Iterator;
import java.util.NoSuchElementException;

public class OurPriorityQueue<E extends Comparable<E>> implements OurQueue<E> {
    private Node first;
    private int size;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return (first == null);
    }

    @Override
    public E element() {
        if (isEmpty()){
            throw new NoSuchElementException();
        } 
        return first.item;
    }

    @Override
    public void add(E item) {
        Node current = first;
        boolean running = true;

        if (current == null) {
            first = new Node(item, null);
            size = 1;
            
        } else {
            while (running) {
                if ((item.compareTo(current.item)) > 0) {
                    running = false;
                } else {
                    current = current.next;
                }

            }
            Node temp = current.next;
            current.next = new Node(item, temp);
            size++;
        }

    }

    @Override
    public E remove() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public void clear() {
        first = null;
        size = 0;
    }

    @Override
    public Iterator<E> iterator() {
        return new PriorityQueueIterator();
    }

    private class Node {
        public E item;
        public Node next;

        public Node(E newItem, Node nextNode) {
            item = newItem;
            next = nextNode;
        }

    }

    private class PriorityQueueIterator implements Iterator<E> {

        @Override
        public boolean hasNext() {
            // TODO Auto-generated method stub
            return false;
        }

        @Override
        public E next() {
            // TODO Auto-generated method stub
            return null;
        }

        @Override
        public void remove() {
            // TODO Auto-generated method stub

        }

    }

}
  

How to submit:

Send me all of the code you worked on at the end of the lab (CC your group). The lab grade is based on in-class activities and the code sent to me at the end of the lab (or, if final, incorporated into the solution).

Add at least one of your own tests.


CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.