Inserting and Retrieving Items

Overview

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.

Adding Items to MyArrayList

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.

private void resize Method

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:

1. Creates a new T[] array whose length is double the length of the this.items array.
2. Copy all of the existing items from the 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).
3. Assign your new array to the this.items instance variable.

public void add(int index, T item) 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:

1. First check whether 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);

2. Next, we need to ensure that there is room for the new item by checking whether 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.
3. If index < this.size, then we need to move all of the items starting at index through the end of the array up one index.
4. Save the item argument into the index position of the this.items array.
5. Increase the size count by 1

public boolean add(T item) Method

Our 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.

Retrieving Items from MyArrayList

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:

1. First verify that the 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.
2. Return the item at the given index in the this.items array.

Testing Our Progress

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.

Testing add(int index, T item) and get(int index)

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:

1. We can insert new items to the end of the list (first 10, then 11, then 12)
2. The underlying array is resized when needed (when we try to add the third item)
3. We can retrieve items back out of the list
4. The items are inserted and retrieved in the correct order

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.

More Testing for add(int index, T item)

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:

1. Creates a new MyArrayList object
2. Adds two items to the array list
3. Adds a new unique item to index = 0 of the array list
4. Gets the unique item 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 3
5. Adds a final unique item to index = 2 of the array list
6. Gets the item from index = 2 and asserts that it is equal to the unique item added in Step 5

Use the test results to help you debug your add(index, item) method, if needed.

Testing add(T item)

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.

Testing size()

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:

1. Create a new MyArrayList object, then assert that its size method returns 0 (since the array list is empty)
2. Add an item to the object, then assert that its size method returns 1
3. Add two more items to the object, then assert that its size method returns 3

Use 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.

Testing “Edge Cases”

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:

1. Create a MyArrayList object and fill it with a small number (e.g., 2-5) of items
2. Try to use way too high of an MyArrayList 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.
3. Repeat Step 2 but use the smallest 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).
4. Repeat step 3, but use a negative index parameter and make sure that an IndexOutOfBoundsException is thrown.

Committing Your Progress

Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.