CSci 2101: Priority Queue

JUnit Test code for PriorityQueue


import static org.junit.Assert.*;
import java.util.NoSuchElementException;
import org.junit.Test;

public class TestPriorityQueue {
	@Test
	public void TestEmptyQueue() {
		OurQueue<String> queue = new OurPriorityQueue<String>();
		assertTrue(queue.isEmpty());
		assertEquals(0,queue.size());
	}
	
	@Test
	public void TestNonEmptyQueue() {
		OurQueue<String> queue = new OurPriorityQueue<String>();
		queue.add("kiwi");
		assertFalse(queue.isEmpty());
		assertEquals(1,queue.size());
	}	
	
	@Test(expected=NoSuchElementException.class)
	public void TestElementEmptyQueue(){
		OurQueue<String> queue = new OurPriorityQueue<String>();
		queue.element();
	}
	
	@Test(expected=NoSuchElementException.class)
	public void TestRemoveFromEmptyQueue(){
		OurQueue<String> queue = new OurPriorityQueue<String>();
		queue.remove();
	}	
	
}

OurQueue interface



/**
 * A collection that typically stores its elements in a FIFO
 * (first-in-first-out) manner
 * Modeled after JCF Queue interface
 *
 * @author Elena Machkasova for CSCi 2101 summer 2010
 *
 * @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();
	
}

OurPriorityQueue class


import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 
 * 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>
 */
public class OurPriorityQueue<E extends Comparable<E>> implements OurQueue<E>{
	private Node firstNode;
	
    /**
     * Returns true if this list contains no elements, 
     * false otherwise
     * @return true if this list contains no elements, 
     * false otherwise
     */
    public boolean isEmpty(){
        return false;
    }
    
    /**
     * Returns the number of elements in this queue. 
     * @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. 
	 * 
	 * @param e - the element to be added to the queue
	 */
	public void add(E e) {
	}
	
	/**
	 * Retrieves and removes the firstNode of this queue. 
	 * Throws:
	 * NoSuchElementException - if this queue is empty
	 * 
	 * @return - the head of the queue
	 * @throws NoSuchElementException - if this queue is empty
	 */
	public E remove() {
		return null;
	}
	
	/**
	 * Retrieves but does not remove the head of this queue. 
	 * Throws:
	 * NoSuchElementException - if this queue is empty
	 * 
	 * @return - the head element of the queue
	 * @throws NoSuchElementException - if this queue is empty
	 */
	public E element() {
		return null;
	}
	
    /**
     * Removes all elements from the queue. 
     * This queue will be empty after this call returns.
     * @return
     */
    public void clear() {
    	
    }
	
    private class Node {
        public E item;
        public Node next;
        
        public Node(E newItem, Node nextNode) {
                item = newItem;
                next = nextNode;
        }       
        
    }
    
	public Iterator<E> iterator() {
		return new PriorityQueueIterator();
	}
	
	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
			
		}
		
		
	}
}

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.