Programming Project PriorityList<E> Twice
Two Collection Classes implement the same ADT using two different Data Structures
1. 1D Array
2. Singly-Linked Structure
Collaboration Solo: Complete this by yourself with help from TAs and any code from our course.
Preview: This project asks you to implement an interface PriorityList<E> using an array instance variable and then a singly linked structure. This project has the following goals:
· Implement a collection class using an array data structure: ArrayPriorityList<E>
· Implement a collection class using the singly linked structure: LinkedPriorityList<E>
· Observe the same interface implemented using two different data structures
· Understand how generic classes store collections of the same type element safely
· Use exceptions to handle invalid arguments
· More practice testing
· Testing to make sure exceptions are in fact thrown when they are supposed to
These two new types will store a collection of elements as a zero-based indexed list where the element at index 0 is considered to have higher priority than the element at index 1. The element at index size()-1 has the lowest priority. An instance of this collection class will be able to store just one type of element such as String> or <Integer. The required methods are described in interface PriorityList<E> http://www.cs.arizona.edu/~mercer/Projects/PriorityList.java
1) ArrayPriorityList<E> implements PriorityList<E>
ArrayPriorityList<E> must use a 1D array instance variable to store elements. Since you cannot have an array of E, the type of array elements will be Object to allow this class to store any type of element, which requires a cast in the get method. It begins like this:
/**
* This class implements a generic collection to store elements where
* indexes represent priorities and the priorities can change in several ways.
*
* @author Your Name
* @param <E> The type of all elements stored in this collection
*/
public class ArrayPriorityList<E> implements PriorityList<E> {
private Object[] data; // The data structure storing elements
private int n; // The number of meaningful elements
// Create an empty list with zero elements
public ArrayPriorityList() {
data = new Object[20];
n = 0;
}
// . . . Complete the methods not shown here to save space . . .
}
You must have a unit test for ArrayPriorityList<E>. The following start of a unit test reviews how to ensure your methods throw exceptions when expected. Pay careful attention to those methods as to when the IllegalArgumentException should be thrown.
import static org.junit.Assert.*;
import org.junit.Test;
public class ArrayPriorityListTest {
@Test
public void testInsertToLeft() {
PriorityList<String> list = new ArrayPriorityList<String>();
list.insertElementAt(0, "First");
// Must shift array elements in this case
list.insertElementAt(0, "New First");
assertEquals("New First", list.getElementAt(0));
assertEquals("First", list.getElementAt(1));
}
// Write short test methods to ensure methods throw exceptions
// when they are supposed to throw new IllegalArgumentException();
@Test(expected = IllegalArgumentException.class)
public void testExceptionGetElementAtZeroWhenSizeIsZero() {
PriorityList<String> list = new ArrayPriorityList<String>();
list.getElementAt(0);
}
}
2) LinkedPriorityList<E> implements PriorityList<E>
ArrayPriorityList<E> must use the private inner class Node to ensure your Node objects to store a reference to the element in data and also a reference to the next element next (or null in the last node). Your LinkedPriorityList<E> class must begin like this:
/**
* This class implements a generic collection to store elements where
* indexes represent priorities and the priorities can change in several ways.
*
* @author Your Name
* @param <E> The type of all elements stored in this collection
*/
public class LinkedPriorityList<E> implements PriorityList<E> {
// This private inner class saves lots of typing and is hidden from outsiders
private class Node {
// These instance variables can be accessed from the enclosing class
private E data;
private Node next;
public Node(E element) {
data = element;
next = null;
}
public Node(E element, Node link) {
data = element;
next = link;
}
}
// These instance variables belong to the enclosing class LinkedPriorityList
private Node first;
private int size;
// Create an empty list with zero elements
public LinkedPriorityList() {
first = null;
size = 0;
}
// . . . Add the methods of interface PriorityList<E>
}
You must have a unit test for LinkedPriorityList<E>. The following start of a unit test reviews how to ensure your methods throw exceptions when expected. Pay careful attention to those methods as to when the IllegalArgumentException should be thrown.
import static org.junit.Assert.*;
import org.junit.Test;
public class LinkedPriorityListTest {
@Test
public void testInsertToLeft() {
PriorityList<String> list = new LinkedPriorityList<String>();
list.insertElementAt(0, "First");
// Must shift array elements in this case
list.insertElementAt(0, "New First");
assertEquals("New First", list.getElementAt(0));
assertEquals("First", list.getElementAt(1));
}
// Write short test methods to ensure methods throw exceptions
// when they are supposed to throw new IllegalArgumentException();
@Test(expected = IllegalArgumentException.class)
public void testExceptionGetElementAtZeroWhenSizeIsZero() {
PriorityList<String> list = new LinkedPriorityList<String>();
list.getElementAt(0);
}
}
Grading Criteria (100 points max), Turn in to Web-Cat
____/ +16 pts Style/Readability
· +2 You included your name as a comment in both files
· +2 You have a 1 or 2 sentence description of the purpose of each class
· +2 The source code is formatted nicely (in Eclipse use Source > Format)
· +2 Used meaningful identifiers
· +4 All methods are commented with an accurate description in ArrayPriorityList<E>
· +4 All methods are commented with an accurate description in LinkedPriorityList<E>
____ / +84 Web-Cat correctness and code coverage: To get 100% for these 84 points, you will need 100% problem coverage only, which means Rick's tests pass and you exercised all methods). You can get a score of 0 even though all of your tests passed in your workspace because
· WebCat reports a compile time error (look for Unknown symbol)
· One of Rick's test cases placed your loop into an infinite loop (look for Timeout Error)
· One of your assertions failed on WebCat (even though it passed for you locally)
Please note other ways to lose points when graded by your TA:
-50 You did not use a singly-subscripted array for ArrayPriortyList<E>
-50 You did not a singly-linked structure of Node objects for LinkedPriortyList<E>