This question won't take you more than 15 mins, and junit test provided.

In past terms, the biggest struggle students have had is in understanding how/when indexes work. This question is asking you to write the add(), remove(), and get() methods which use indices. To keep the focus on using (arrays and) indices correctly, this class does not (and should not) implement the List interface. Your only focus should be on using indices correctly.

----------------------------------

package edu.buffalo.cse116;

import java.util.Arrays;

/** * This could represents an array-based conceptualization of a list. For the sake of simplicity, * I did not have this implement the List interface (and the many methods we will not bother with). * This can (hopefully) allow students to focus on how we use indices in the list. * * @author Lewis and Chase * @author Matthew Hertz * @version 4.0 * @param Type of data held in this collection */ public class ArrayList { /** First index in the array at which elements cannot be found. Only indices LESS THAN this value are valid. */ private int _size;

/** Array in which the elements are stored. */ private E[] _store;

/** * Creates an empty list with a backing store of length 32. */ @SuppressWarnings("unchecked") public ArrayList() { _size = 0; _store = (E[]) (new Object[32]); }

/** * This method is used to insert the given element at the specified index. It must first check if the index is legal * and throw an exception if it is not. It then will check if space exists in the backing store (and double the array * length when necessary). It must then shift all of the data up to create the "hole" in which the element can be * inserted. The last step will be to actually add the element to the backing store. * * @param element Data to be added to this list * @param index Location in the array to add the element. */ public void add(int index, E element) { }

/** * Remove the element that was at the specified index. To fill any "hole" created, the remaining elements should be * shifted down from the end. It will returns the element that was removed from the list. * * @param index Index in the list for the element to be removed. * @return The element that was been removed from the list. */ public E remove(int index) {

} /** * Retrieve the element that was at the specified index. This will not change the elements in any way. * * @param index Index in the list for the element to be retrieved. * @return The element at the specified index */ public E get(int index) {

} }

------------------------------------

test file

package edu.buffalo.cse116;

import static org.junit.Assert.*; import static org.junit.Assert.fail;

import java.lang.reflect.Field; import java.util.Random;

import org.junit.Before; import org.junit.Test;

public class ArrayListTest {

@Test public void testAddIllegal() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", null, "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "fkj388snaz", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ", "deDP0VeFMa", "dTy8GMqlL9", "FoHx9J7VbI", "xe8hDIvU7S" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } Random rnd = new Random(); for (int i = 0; i < data.length; i++) { setSize(i); try { theList.add(-1, data[i]); fail("Need to throw an IndexOutOfBoundsException when given an illegal index."); } catch (IndexOutOfBoundsException e) { // This is expected; allow it. } catch (Exception e) { fail( "Need to throw an IndexOutOfBoundsException when given an illegal index. Your code threw: " + e.toString()); } try { theList.add(i + 1 + rnd.nextInt(6), data[i]); fail("Need to throw an IndexOutOfBoundsException when given an illegal index."); } catch (IndexOutOfBoundsException e) { // This is expected; allow it. } catch (Exception e) { fail( "Need to throw an IndexOutOfBoundsException when given an illegal index. Your code threw: " + e.toString()); } } }

@Test public void testAddAtLast() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", "n074hPafSH", "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { theList.add(i, data[i]); assertSame("Do not reassign _store unless the elements fill the array!", store, getStore()); assertEquals("Size field after " + (i + 1) + " calls to add() to add to end of the list is incorrect.", i + 1, getSize()); for (int j = 0; j <= i; j++) { assertEquals("Found incorrect element in the array at index " + j + " after " + (i + 1) + " calls to add() for the end of the list", data[j], store[j]); } } }

@Test public void testAddAtFirst() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", "n074hPafSH" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { theList.add(0, data[i]); assertSame("Do not reassign _store unless the elements fill the array!", store, getStore()); assertEquals("Size field after " + (i + 1) + " calls to add() to add at the head of the list is incorrect.", i + 1, getSize()); for (int j = 0; j <= i; j++) { assertEquals("Found incorrect element in the array at index " + j + " after " + (i + 1) + " calls to add() for the head of the list", data[j], store[i - j]); } } }

@Test public void testAddAtGrow() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", null, "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "fkj388snaz", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ", "deDP0VeFMa", "dTy8GMqlL9", "FoHx9J7VbI", "xe8hDIvU7S" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } setSize(32); theList.add(0, "Bob"); assertEquals("Size field after 33 calls to add() to add to start of the list is incorrect. Expected 33, but was " + getSize(), 33, getSize()); Object[] newStore = getStore(); assertNotSame("Need to reassign _store when the size of the ArrayList is larger than _store's length", store, newStore); assertEquals("Should be doubling the array length when it is needed", 64, getStore().length); assertEquals("Found incorrect element in the array at index 0 when the array grew", "Bob", newStore[0]); for (int j = 0; j < data.length; j++) { if (data[j] != null) { assertEquals("Found incorrect element in the array at index " + j + " after growing array", data[j], newStore[j + 1]); } } }

@Test public void testAddAtMid() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", "n074hPafSH", "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed" }; sizeField.setInt(theList, data.length); Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } theList.add(data.length / 2, "Mommy"); assertEquals(data.length + 1, getSize()); assertSame("Do not reassign _store unless the elements fill the array!", store, getStore()); for (int i = 0; i < (data.length / 2); i++) { assertEquals(data[i], store[i]); } assertEquals("Mommy", getStore()[data.length / 2]); for (int i = data.length / 2; i < data.length; i++) { assertEquals(data[i], store[i + 1]); } }

@Test public void testRemoveIllegal() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", null, "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "fkj388snaz", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ", "deDP0VeFMa", "dTy8GMqlL9", "FoHx9J7VbI", "xe8hDIvU7S" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } Random rnd = new Random(); for (int i = 0; i < data.length; i++) { setSize(i); try { theList.remove(-1); fail("Need to throw an IndexOutOfBoundsException when given an illegal index."); } catch (IndexOutOfBoundsException e) { // This is expected; allow it. } catch (Exception e) { fail( "Need to throw an IndexOutOfBoundsException when given an illegal index. Your code threw: " + e.toString()); } try { theList.remove(i + rnd.nextInt(6)); fail("Need to throw an IndexOutOfBoundsException when given an illegal index."); } catch (IndexOutOfBoundsException e) { // This is expected; allow it. } catch (Exception e) { fail( "Need to throw an IndexOutOfBoundsException when given an illegal index. Your code threw: " + e.toString()); } } }

@Test public void testRemoveAtLast() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", "n074hPafSH", "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } setSize(13); String retVal = theList.remove(12); assertEquals("remove() should return the element that was removed.", data[12], retVal); assertSame("Do not reassign _store in remove()!", store, getStore()); assertEquals("Size field after calling remove() is incorrect.", 12, getSize()); for (int j = 0; j < 12; j++) { assertEquals("Found incorrect element in the array at index " + j + " after removing the end element", data[j], store[j]); } assertNull("remove() should use null at the end of the list", store[12]); for (int j = 13; j < data.length; j++) { assertEquals("remove() should not touch entries in _store above _size", data[j], store[j]); } }

@Test public void testRemoveAtFirst() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", "n074hPafSH", "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } setSize(22); String retVal = theList.remove(0); assertEquals("remove() should return the element that was removed.", data[0], retVal); assertSame("Do not reassign _store in remove()!", store, getStore()); assertEquals("Size field after calling remove() is incorrect.", 21, getSize()); for (int j = 0; j < 21; j++) { assertEquals("Found incorrect element in the array at index " + j + " after removing the first element", data[j + 1], store[j]); } assertNull("remove() should use null at the end of the list", store[21]); for (int j = 22; j < data.length; j++) { assertEquals("remove() should not touch entries in _store above _size", data[j], store[j]); } }

@Test public void testRemoveAtMid() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", "n074hPafSH", "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } setSize(data.length); String retVal = theList.remove(12); assertEquals("remove() should return the element that was removed.", data[12], retVal); assertSame("Do not reassign _store in remove()!", store, getStore()); assertEquals("Size field after calling remove() is incorrect.", data.length - 1, getSize()); for (int j = 0; j < 12; j++) { assertEquals("Found incorrect element in the array at index " + j + " after removing the end element", data[j], store[j]); } for (int j = 13; j < data.length; j++) { assertEquals("remove() should not touch entries in _store above _size", data[j], store[j - 1]); } assertNull("remove() should use null at the end of the list", store[data.length - 1]); }

@Test public void testGetIllegal() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", null, "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "fkj388snaz", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ", "deDP0VeFMa", "dTy8GMqlL9", "FoHx9J7VbI", "xe8hDIvU7S" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } Random rnd = new Random(); for (int i = 0; i < data.length; i++) { setSize(i); try { theList.get(-1); fail("Need to throw an IndexOutOfBoundsException when given an illegal index."); } catch (IndexOutOfBoundsException e) { // This is expected; allow it. } catch (Exception e) { fail( "Need to throw an IndexOutOfBoundsException when given an illegal index. Your code threw: " + e.toString()); } try { theList.get(i + rnd.nextInt(6)); fail("Need to throw an IndexOutOfBoundsException when given an illegal index."); } catch (IndexOutOfBoundsException e) { // This is expected; allow it. } catch (Exception e) { fail( "Need to throw an IndexOutOfBoundsException when given an illegal index. Your code threw: " + e.toString()); } } }

@Test public void testGetLast() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", "n074hPafSH", "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } setSize(13); String retVal = theList.get(12); assertEquals("get() should return the element that was at that index.", data[12], retVal); assertSame("Do not reassign _store in get()!", store, getStore()); assertEquals("Size field after calling get() is incorrect.", 13, getSize()); for (int j = 0; j < data.length; j++) { assertEquals("Found incorrect element in the array at index " + j + ". get() should not change any elements!", data[j], store[j]); } }

@Test public void testGetNull() throws Exception { String[] data = { null, "tul81cghCm", "n074hPafSH", "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } setSize(22); String retVal = theList.get(0); assertNull("get() should return the element that was at the specified index even if it was null.", retVal); assertSame("Do not reassign _store in get()!", store, getStore()); assertEquals("Size field after calling get() is incorrect.", 22, getSize()); assertNull("Found incorrect element in the array at index " + 0 + ". get() should not change any elements!", store[0]); for (int j = 1; j < data.length; j++) { assertEquals("Found incorrect element in the array at index " + j + ". get() should not change any elements!", data[j], store[j]); } }

@Test public void testGetNonLast() throws Exception { String[] data = { "i2kN1pFjcv", "tul81cghCm", null, "vy8umsWsPA", "PowltMb2Dz", "BWfLuRzluo", "b3RVEBqVNN", "x9t3XGmra5", "Uj9dCnqxrI", "Gmrad3W6WK", "hVD0RKVgrs", "hB5OlayVed", "vMktHBhjde", "EqWgpmoOwe", "gee00MC6Xm", "j4QQ6CJZnI", "ffRRS73QI0", "jOHQr8aiYi", "Fg1EY3ymcB", "LVNU6Rk6NF", "p6cOw2py8L", "Eh0C0lEShV", "1dvrCgPKrg", "y67e0V9Avz", "UjjsWAV5Ml", "kOFZ9mLPqG", "INaSyDkMlJ" }; Object[] store = getStore(); for (int i = 0; i < data.length; i++) { store[i] = data[i]; } setSize(data.length); for (int i = 0; i < data.length / 2; i++) { String retVal = theList.get(i); if (data[i] == null) { assertNull("get() should return the element that was at the specified index even if it was null.", retVal); } else { assertEquals("get() should return the element that was removed.", data[i], retVal); } assertSame("Do not reassign _store in get()!", store, getStore()); assertEquals("Size field after calling get() is incorrect.", data.length, getSize()); for (int j = 0; j < data.length; j++) { if (data[i] == null) { assertNull("get() should not change any element in the _store array.", store[i]); } else { assertEquals("get() should not change any element in the _store array.", data[i], store[i]); } } } }

/** List instance used to test all our code. */ private ArrayList theList; private Field sizeField; private Field storeField;

@Before public final void checkFieldsUnchanged() { Class al = ArrayList.class; Field[] fields = al.getDeclaredFields(); assertEquals( "You should not add any fields to the ArrayList class beyond the two provided. This class's field count:" + fields.length, 2, fields.length); try { sizeField = al.getDeclaredField("_size"); assertEquals("The _size field should be of type int", Integer.TYPE, sizeField.getType()); sizeField.setAccessible(true); } catch (Exception e) { fail("Your ArrayList class should still define a field named \"_size\""); } try { storeField = al.getDeclaredField("_store"); assertTrue("The _store field should be an array of generic type", storeField.getType().isArray()); assertEquals("The _store field should be an array of generic type", Object.class, storeField.getType().getComponentType()); storeField.setAccessible(true); } catch (Exception e) { fail("Your ArrayList class should still define a field named \"_store\""); } theList = new ArrayList(); }

public int getSize() throws IllegalArgumentException, IllegalAccessException { return sizeField.getInt(theList); }

public void setSize(int newSize) throws IllegalArgumentException, IllegalAccessException { sizeField.setInt(theList, newSize); }

public Object[] getStore() throws IllegalArgumentException, IllegalAccessException { return (Object[]) storeField.get(theList); } }