CSE 12 PA2: Generics & ArrayLists
Due Date: Thursday, January 25, 2024, 11:59pm PST
There is an FAQ post on Piazza. Please read that post first if you have any questions.
Learning goals:
Implement a data structure similar to Java’s ArrayLists with generic types
Write JUnit tests to verify proper implementation
Testing and Implementation of ArrayList [95 points]
In this part of the assignment, you will implement a data structure similar to Java's ArrayList and write JUnit tests to ensure that your implementation functions correctly.
Make sure to read the entire write-up before you start coding.
Download the starter code and put it in a directory in your working environment.
You will find the following files:
+-- PA2/starter
| +-- MyList.java
| +-- MyArrayListPublicTester.java
| +-- MyArrayListHiddenTester.java Edit this file
| +-- MyArrayList.java (create this file) Edit this file
How to run and compile the testers:
Running the tester on UNIX based systems (including a mac):
Compile: javac -cp ../libs/junit-4.13.2.jar:../libs/hamcrest-2.2.jar:. MyArrayListPublicTester.java
Execute: java -cp ../libs/junit-4.13.2.jar:../libs/hamcrest-2.2.jar:. org.junit.runner.JUnitCore MyArrayListPublicTester
Running the tester on Windows systems:
Compile: javac -cp ".;..\libs\junit-4.13.2.jar;..\libs\hamcrest-2.2.jar" MyArrayListPublicTester.java
Execute: java -cp ".;..\libs\junit-4.13.2.jar;..\libs\hamcrest-2.2.jar" org.junit.runner.JUnitCore MyArrayListPublicTester
To run the hidden tester, replace references to MyArrayListPublicTester with MyArrayListHiddenTester in the above commands.
Part 1: JUnit Testing (20 points)
We provide two test files:
MyArrayListPublicTester.java
Contains all the public test cases we will use to grade your MyArrayList implementation (visible on Gradescope)
MyArrayListHiddenTester.java
Contains only the headers and description to the hidden test cases we will use to grade your MyArrayList implementation (hidden until the PA is graded)
Your task: Implement the missing unit tests in MyArrayListHiddenTester.java based on the description in ‘hidden tests’ column in the Tests tab below.
Your tests will be graded to check if they pass/ fail correctly
NOTE: DO NOT CHANGE THE TEST HEADERS!
Tests Table: List of various test cases and their description
Part 2: Implementation of ArrayList (75 points)
In this part of the assignment, you will create your own implementation of ArrayList called MyArrayList.
Important Note
DO NOT IMPORT AND USE JAVA'S BUILT IN ARRAYLIST or any other imports!!! If we see that you do use these functions, you will receive a zero. You must implement the ArrayList from scratch to earn credit for this assignment.
Edit the file named MyArrayList.java. Make sure the MyArrayList class implements MyList. MyArrayList is a generic class. This class will only be a subset of the Java Collection’s Framework ArrayList.
Your task is to implement the instance variables, constructors and public methods stubbed out in the interface and described in the table below.
There are various ways to implement an ArrayList. In PA2, you will follow these:
Instance Variables
Note: Do not make these instance variables private, they should have the default access modifier (i.e. do not declare them as public or private). Do not add any other instance variables and static variables other than private static final variables to be used as constants. There are two instance variables.
Object[] values :
The underlying data structure of the ArrayList. The index of an element in this array should correspond to the index of the element in the ArrayList.
You don't need to check if values is null in any of your code. You can assume values will never be null .
null can be a valid element in your ArrayList. The only way of knowing if an element is valid or not is by checking the length variable, defined below. All invalid elements in the array should be null . Check the Example with nulls for more clarity.
Note: In some of the methods you will write, you will need to return an object of type E , but our values array is of type Object , so we will need to cast whatever we return to type E (e.g., (E) values[0] ). If you compile with code that does this, you will see the following warning.
The code will still work exactly the same, but if you want to hide this warning, add @SuppressWarnings("unchecked") above any method that does this cast
int length :
This variable should be equal to the number of valid elements in your values array. A valid element in values is an element in your ArrayList.
Note: You may assume that nothing (other than possibly your own code) would change length to be something out of bounds of values (i.e., length >= 0 && length <= values.length will always evaluate to true , unless your code manually sets it to be something else).
Constructors
There are three constructors.
public MyArrayList() :
Initialize the Object array with the default length of 5. The capacity of the ArrayList is the length of the array.
Note: the capacity (length of values : values.length ) is ==not== the same as the length (number of elements in the ArrayList, i.e., the number of valid elements in the array)
public MyArrayList(int initialCapacity) : Initialize the Object array with the length of initialCapacity . If the initialCapacity is invalid (i.e. any value of initialCapacity strictly less than 0), throw an IllegalArgumentException .
public MyArrayList (E[] arr) :
Initialize the instance variables with the input array (shallow copy) of capacity equal to the length of arr . All elements in arr are valid (even the null s), so set length accordingly. If arr is null , fall back to the behavior of the no-arg constructor (construct an ArrayList with the default capacity).
Public Methods
Note: Do not make these functions private, they should all remain public (for testing and grading purposes). There are eleven methods.
The following table includes all the methods you need to implement in MyArrayList.java
Example using append and remove on list with nulls
As stated earlier, null can be a valid element in your ArrayList. In this example, bolded elements are elements in the ArrayList (valid elements of values ) and non-bolded null represent unoccupied spots in values .
Statements on the left-hand side of the array should evaluate to expressions on the right-hand side.
...
list.values -> [3, 1, null, 5, null, null, null] // capacity is 7
list.size() -> 5
list.append(20);
list.size() -> 6
list.values -> [3, 1, null, 5, null, 20, null]
list.append(null);
list.size() -> 7
list.values -> [3, 1, null, 5, null, 20, null] // capacity is still 7
list.remove(6) -> null
list.size() -> 6
list.values -> [3, 1, null, 5, null, 20, null]
list.remove(5) -> 20
list.size() -> 5
list.values -> [3, 1, null, 5, null, null, null]
list.remove(4) -> null
list.size() -> 4
list.values -> [3, 1, null, 5, null, null, null]
list.remove(3) -> 5
list.size() -> 3
list.values -> [3, 1, null, null, null, null, null]
list.remove(2) -> null
list.size() -> 2
list.values -> [3, 1, null, null, null, null, null]
list.remove(1) -> 1
list.size() -> 1
list.values -> [3, null, null, null, null, null, null]
list.remove(0) -> 3
list.size() -> 0
list.values -> [null, null, null, null, null, null, null]
Example using rotate on list with nulls
...
list.values -> [null, 1, null, null, 2, 3, null, null] // capacity is 8
list.size() -> 6
list.rotate(1)
list.values -> [1, null, null, 2, 3, null, null, null]
list.rotate(2)
list.values -> [null, 2, 3, null, 1, null, null, null]
Part 3: Coding Style (5 points)
Coding style is an important part of ensuring readability and maintainability of your code. We will grade your code style in all submitted code files according to the style guidelines. Namely, there are a few things you must have in each file/class/method:
File header
Class header
Method header(s)
Inline comments
Proper indentation
Descriptive variable names
No magic numbers (Exception: Magic numbers can be used for testing.)
Reasonably short methods (if you have implemented each method according to the specification in this write-up, you’re fine). This is not enforced as strictly.
Lines shorter than 80 characters
Javadoc conventions ( @param , @return tags, /** comments */ , etc.)
A full style guide can be found here and a sample styled file can be found here. If you need any clarifications, feel free to ask on Piazza.
Submission Instructions:
Please follow ALL of the instructions below to completely submit your assignment.
Submit all of the following files to Gradescope.
MyArrayListHiddenTester.java
MyArrayList.java
Coding Style (5 points)
Correctness (95 points) You will earn points based on the autograder tests that your code passes. If the autograder tests are not able to ru (e.g., your code does not compile or it does not match the specifications in this writeup), you may not earn credit.
Tester (20 points)
The autograder will test your implementation of the Junit tests. Your unit tests are expected to fail or pass based on the test cases table’s hidden tests column in Part 1.