In this part of the lab, we will add functionality to our MyArrayList class to insert and retrieve items from our data structure. We will also practice using unit tests to debug and validate our implementation.
The first main operation we will work on programming is adding items to our data structure since we cannot do anything unless it is storing data. Given how array lists store data, we need to first create a private helper method that will make sure our add methods for inserting data always work.
Recall that an array list can theoretically store a near infinite number of items (depending only on the amount of memory your computer has). However, we are using an array inside the array list to physically store that data, and arrays always have a fixed length. To avoid ever running into a situation where the size of the array list (i.e., the number of items actually in the collection) becomes larger than its length (i.e., the number of items it can physically store, given its underlying array), we need an ability to resize the underlying array to make it larger so it can store enough items.
To do so, create a new private void resize() method that takes no arguments and:
T[] array whose length is double the length of the this.items array.this.items array to our new array created in Step 1. Make sure those items all keep the same order (a for loop over indices of the items is really helpful here).this.items instance variable.Hint
Since we need to create a new T[] array, we should follow the same process we used in the first constructor in Part 1, including adding the @SuppressWarnings(“unchecked”) annotation to this method.
Our next method public void add(int index, T item) will be responsible for adding a given T item into a desired index in the array list. This method should:
index makes sense given the current number of items in the array list. That is, the index should be a number in the range [0, this.size] inclusive (otherwise there would be a gap between the current items and the new one). If the index is not in that range, we should throw an IndexOutOfBoundsException with an error message that makes sense – something like (feel free to change the text):throw new IndexOutOfBoundsException("Tried to add an item to a MyArrayList with too large of an index. Index:" + index + " but size is " + this.size);
this.size < this.items.length. If so, we can proceed to Step 3. Otherwise, we need to resize the underlying array by calling our resize() method we created above.index < this.size, then we need to move all of the items starting at index through the end of the array up one index.
Save the item argument into the index position of the this.items array.
Increase the size count by 1Our second approach for adding items to the array list is the method public boolean add(T item) that always adds an item to the end of the list. Because we already did all of the necessary work in the previous method, our second add method can simply call the first add method with the appropriate index. Question: what is the appropriate index to pass into the first add method in order to add a new item to the current end of the array list?
The only other instruction needed in the second add method is to always return true since we successfully added the item to the array list.
We will only have one method for retrieving items from the array list: public T get(int index). Recall that we created a stub of this method while testing our code so far at the end of Part 1. We should change this method to:
index argument is valid, given the current number of items in the array list. That is, index should be a value in the range [0, this.size - 1]. If index is not in this range, once again throw an IndexOutOfBoundsExeception with an appropriate error message.index in the this.items array.Now that we have more methods that work together implemented, we can once again test our progress. Rather than adding more code to our public static void main method, we will instead use unit tests like in the Warmup.
In MyArrayList.java, right click anywhere in the file, and select “Source Action” from the right click menu. Then, select “Generate Tests”. Again, use the default name proposed by the IDE of MyArrayListTest. Next, it will prompt you with what methods you want to create tests for. Select just the size method for now (we will manually add other tests later).
You should now see a new java file named MyArrayListTest.java that contains a class named MyArrayListTest with one empty test method. Following a similar process to what we used in Warmup Part 1, we will create all the unit tests that we need to debug any mistakes in our implementation.
Even though the IDE created an empty test testSize for our size method, we should start by testing our methods for inserting items into the MyArrayList, otherwise it is difficult to check whether the size method works for non-empty array lists.
In your MyArrayListTest.java file, create a new test called testAddGet by copying the following code:
@Test
public void testAddGet() {
// create a MyArrayList that stores Integers
MyArrayList<Integer> array = new MyArrayList<Integer>();
// add a couple items
// afterwards, the array should be [10, 11, 12]
array.add(0, 10);
array.add(1, 11);
array.add(2, 12);
// get the items back out of the MyArrayList
int item0 = array.get(0);
int item1 = array.get(1);
int item2 = array.get(2);
// check whether the items were in the correct order
assertEquals(10, item0);
assertEquals(11, item1);
assertEquals(12, item2);
}
This test verifies that:
Run this test to make sure everything works! If any line of the test does not pass, hopefully where it fails and what is stored in item0 and item1 will give you a hint of where to find any bugs in your implementation of MyArrayList. Don’t forget to use the Debugger from Part 2 of the Warmup to help you debug.
While the above test is useful for checking whether we can add an item to the end of a MyArrayList object, we also need to test whether we can correctly add to an index where there is already an item in the list. We split this into a second, separate unit test so that our unit tests do not get too complicated, but instead each test verifies a different use case of our data structure.
Create another test called testAddMiddle that:
MyArrayList objectitems to the array listitem to index = 0 of the array listitem from index = 0 (assigned to a local variable as in our test above) and then asserts that the value of that local variable is equal to the item added in Step 3item to index = 2 of the array listitem from index = 2 and asserts that it is equal to the unique item added in Step 5Use the test results to help you debug your add(index, item) method, if needed.
Similar to the test we just used to verify the add(index, item) and get methods, write another test called testAdd in your MyArrayListTest.java file that tests the add(item) method. You could even duplicate the code from our first test, only replacing which add function is called. Use the test results to help you debug your add(item) method, if needed.
Next, we can test our size method from the MyArrayList class using the testSize test automatically created by the IDE for us., since a stub for that test has already been created for us. Your test could:
MyArrayList object, then assert that its size method returns 0 (since the array list is empty)size method returns 1size method returns 3Use the test results to help you debug your size method, if needed. Hint: if the size isn’t increasing properly, the problem might actually be in your add(index, item) method, which is responsible for increasing the value of the this.size instance variable.
Last but certainly not least, we also want to make sure that our implementation can handle what are called edge cases, which are special cases that are different from the general use case of a method and could cause unexpected behavior.
Additional edge cases for our MyArrayList class so far involve passing in an invalid index parameter into the add(index, item) and get methods. Write two more tests testAddException and testGetException that both:
MyArrayList object and fill it with a small number (e.g., 2-5) of itemsMyArrayList parameter (e.g., 1000) to the add or get method and make sure that an IndexOutOfBoundsException is thrown. You can check whether an exception is thrown by using the assertThrows function used in Part 4 of the Warmup.index parameter that should throw an IndexOutOfBoundsException. (Question: what value should we use here based on the current size of the array list? It will be different for add and get).index parameter and make sure that an IndexOutOfBoundsException is thrown.ReadMe
Most programming languages, including Java, only allow for positive indexing starting at the beginning of the list. So negative indices are never allowed in Java. Some programming languages, such as Python, do allow for negative indexing (where a negative index starts at the end of the list).
Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.