In class, we implemented an IntArrayList class which internally had an array of integers but made it easy to add new elements to the end. We saw that after improvements, adding elements to an IntArray would only take O() time. It accomplished this by doubling the underlying size of the array and copying the old array every time it ran out of space. If total elements are added to the array, in the worst case, the array might have run out of space and had to copy itself when the very last (th) element was added, when the 2 nd element was added, 4th, 8th, and so on down to the starting size of the array. Every time the array runs out of space, it needs to copy all the elements from the old array to the new array. However, even as becomes very large and this series becomes arbitrarily long, + 2 + 4 + 8 + 16+2. In other words, the total number of elements we need to copy over the lifetime of an IntArrayList is bounded above by a linear function of the total number of elements added to it. (Allocating the array each time we copy is additional work which depends on the memory allocation algorithm used, but it will be efficient enough that it won't change the linear bound.) Your task: Improve IAList by creating an addBefore method. Instead of adding an element to the end, addBefore adds it to the beginning, at position 0, causing all existing elements to move forward (their position increased by 1). However, like add, your addBefore method must also guarantee that only O() time is needed to perform n addBefores and adds. To accomplish this, as with add, most calls to addBefore must execute very quickly, in O(1) constant time, meaning that you can't just shift all the elements forward by 1 each call. The changes you make to IAList should preserve the property that the get and set methods take a constant amount of time (not proportional to the array size) and the above property of add that only a linear number of elements is copied. There are several ways to accomplish this task. Perhaps the easiest: double the array when you hit the beginning, but instead of copying the old array to the beginning of the new array, copy it to the second half (leaving all the unused spaces at the end). You will also need to change the implementation of some other methods (element positions may no longer directly correspond to array indexes) and add an additional instance field (to track extra information). The existing methods should continue to have their existing O runtimes as seen in the comment and they must continue to work along with the new addBefore method. Start with the IAList implementation found on Canvas, which will resemble IntArrayList from class. It will have an empty addBefore method which you will need to fill in. A tester program will be released which will attempt to empirically test that your program takes only O() time to perform n addBefore and adds (after testing that it seems to work, along with verifying that the other methods seem to work). EXTRA CREDIT 3 POINTS: Notice that the above technique will "run out of space" when there is extra room left on the opposite end of the array. Instead, use one whole array before triggering any copying (preserving O(n) performance, starting with length 4). ---------------------------------------------- use this code IAList.java public class IAList { private int[] a; // Underlying array private int length; // Number of added elements in a // YOU WILL NEED TO ADD AT LEAST ONE NEW DATA FIELD HERE. public IAList() { length = 0; // Start with no added elements in a a = new int[4]; // A little room to grow // YOU MAY NEED TO INITIALIZE YOUR NEW DATA FIELD(S). } public int get(int i) { // Retrieve an added element, O(1) // THE NEW DATA FIELD(S) MAY CHANGE THE WAY GET WORKS. if (i < 0 || i >= length) { throw new IndexOutOfBoundsException(i+""); } return a[i]; // Retrieve the element at position i } public int size() { // Number of added elements, O(1) // THE NEW DATA FIELD(S) MAY CHANGE THE WAY SIZE WORKS. return length; // The number of added elements } public void set(int i, int x) { // Modify an existing element, O(1) // THE NEW DATA FIELD(S) MAY CHANGE THE WAY SET WORKS. if (i < 0 || i >= length) { throw new IndexOutOfBoundsException(i+""); } a[i] = x; // Change the existing element at position i to x } public void add(int x) { // Add an element to the end, O(n) for n // THE NEW DATA FIELD(S) MAY CHANGE THE WAY ADD WORKS. if (length >= a.length) { // Create new array of double the length int[] b = new int[a.length * 2]; // Copy the elements of a to the corresponding indexes of b for (int i = 0; i < a.length; i++) { b[i] = a[i]; } // Reassign a reference to b a = b; } // Place x at the end of the IAList a[length] = x; // Increase length by 1 length = length + 1; } public void addBefore(int x) { /* FILL THIS IN!! */ } } -------------------------- use test code file (IAListTest) to check score public class IAListTest { public static void main(String[] args) { System.out.println("Now starting tests. You'll see an 'Everything looks OK!' message if everything is ok!"); System.out.println("Creating two IALists, a and b."); System.out.println("Adding the numbers 1 through 10 to a by calling a.add(1); a.add(2); etc."); IAList a = new IAList(); IAList b = new IAList(); int score = 0; try { for (int i = 0; i < 10; i++) { a.add(i + 1); for (int j = 0; j <= i; j++) { int aget = a.get(j); if (aget != j + 1) { throw new RuntimeException("After adding " + (i + 1) + " to IAList a, calling a.get("+j+") should get "+(j+1)+ " but got "+aget+"!"); } } } if (a.size() != 10) { throw new RuntimeException("Size should be 10 after adding 10 things"); } checkBounds(a); for (int i = 0; i < a.size(); i++) { if (a.get(i) != i + 1) { throw new RuntimeException("After adding 10 things and tried to a.get(" + i + ") I expected to see " + (i + 1) + " but saw " + a.get(i) + "!"); } a.set(i, i + 1 + 10); if (a.get(i) != i + 1 + 10) { throw new RuntimeException("After setting I tried to a.get(" + i + ") I expected to see " + (i + 1 + 10) + " but saw " + a.get(i) + "!"); } } for (int i = 100; i < 200; i++) { b.add(100); } for (int i = 0; i < 100; i++) { if (b.get(i) != 100) { throw new RuntimeException("Bad value in new IAList"); } } for (int i = 0; i < a.size(); i++) { if (a.get(i) != i + 1 + 10) { throw new RuntimeException("After creating another IAList I tried (again) to a.get(" + i + ") I expected to see " + (i + 1 + 10) + " but saw " + a.get(i) + "!"); } } System.out.println("Initial functionality looks OK. Now testing addBefore with a single value."); a.addBefore(10); score += 9; if (a.size() != 11) { throw new RuntimeException( "Size should be 11 after adding 10 things and addBefore-ing 1 but instead it's " + a.size()); } score += 9; for (int i = 0; i < a.size(); i++) { if (a.get(i) != i + 10) { throw new RuntimeException( "Index " + i + " should have value " + (i + 10) + " but instead has " + a.get(i)); } } score += 9; System.out.println("OK. Now addBefore-ing 90 more values."); for (int i = 0; i < 90; i++) { a.addBefore(9 - i); int get0 = a.get(0); if (get0 != 9 - i) { throw new RuntimeException("After calling a.addBefore(" + (9 - i) + "), when I called get(0), instead of getting it I saw "+get0); } if (a.get(0) != get0) { throw new RuntimeException("Calling a.get(0) twice in a row got different results!"); } int size = a.size(); if (a.size() != 12+i) { throw new RuntimeException("After addBefore-ing "+ (i+2)+" values, there should be "+(12+i)+" things but your size method says "+size); } for (int j = 1; j < a.size(); j++) { if (a.get(j) != 9-i+j) { throw new RuntimeException("After addBefore-ing "+(i+2)+" values, calling a.get("+j+") did not retrieve the correct value!"); } } checkBounds(a); } if (a.size() != 101) { throw new RuntimeException("Size should be 101, instead I got " + a.size()); } for (int i = 0; i < a.size(); i++) { if (a.get(i) != i-80) throw new RuntimeException("Index " + i + " should have value " + (i - 80) + " but instead has " + a.get(i));; } score += 8; System.out.println("OK. Now adding 200 values."); for (int i = 0; i < 200; i++) { a.add(i+21); int size = a.size(); if (a.size() != 102+i) { throw new RuntimeException("After adding "+(i+1)+" out of 200, there should be "+(102+i)+" things but your size method says "+size); } for (int j = 0; j < a.size(); j++) { if (a.get(j) != j-80) { throw new RuntimeException("After adding "+ (i+1)+" out of 200, calling a.get("+j+") did not retrieve the correct value!"); } } } if (a.size() != 301) { throw new RuntimeException("Size should be 301, instead I got " + a.size()); } for (int i = 0; i < a.size(); i++) { if (a.get(i) != i-80) throw new RuntimeException("Index " + i + " should have value " + (i - 80) + " but instead has " + a.get(i));; } score += 8; System.out.println("OK. Now alternating addBefore and append with a bunch of values."); for (int i = 0; i < 1000; i++) { if (i % 2 == 0) { a.addBefore(-(i + 162) / 2); } else { a.add((i + 1) / 2 + 220); } } for (int i = 0; i < a.size(); i++) { if (a.get(i) != -580 + i) { throw new RuntimeException( "Expected a.get(" + i + ") == " + (-580 + i) + " instead was " + a.get(i)); } } score += 8; System.out.println("OK. Now running a speed test addBefore-ing and adding a million values."); long start = System.currentTimeMillis(); for (int i = 0; i < 1000000; i++) { a.addBefore(-581 - i); } for (int i = 0; i < a.size(); i++) { if (a.get(i) != -1000580 + i) { throw new RuntimeException( "Expected a.get(" + i + ") == " + (- 1000580 + i) + " instead was " + a.get(i)); } } score += 8; for (int i = 0; i < 1000000; i++) { a.add(721 + i); } if (a.size() != 2001301) { throw new RuntimeException("Size should now be 2001301, instead I got " + a.size()); } for (int i = 0; i < a.size(); i++) { if (a.get(i) != -1000580 + i) { throw new RuntimeException( "Expected a.get(" + i + ") == " + (- 1000580 + i) + " instead was " + a.get(i)); } } score += 8; for (int i = 0; i < a.size(); i++) { a.set(i, a.size() - i); } for (int i = 0; i < a.size(); i++) { if (a.get(i) != 2001301 - i) { throw new RuntimeException("After resetting the whole array and calling a.get(i) I expected " + (2001301 - i) + " but got " + a.get(i)); } } long end = System.currentTimeMillis(); System.out.println("OK. Now running a speed test alternating addBefore and append with 100,000 zeros."); long start2 = System.currentTimeMillis(); for (int i = 0; i < 200000; i++) { if (i % 2 == 0) { a.addBefore(0); } else { a.add(0); } } for (int i = 0; i < a.size(); i++) { if (i < 100000 || i > 2101301) { if (a.get(i) != 0) throw new RuntimeException("Index "+i+" should have 0 but instead had "+a.get(i)); } else if (a.get(i) != 2001301 - i+100000) { throw new RuntimeException("After calling a.get(i) I expected " + (2001301 - i+100000) + " but got " + a.get(i)); } } long end2 = System.currentTimeMillis(); score += 8; if (end - start < 1000 && end2 - start2 < 1000) { System.out.println("OK. You took " + (end - start) + " milliseconds and "+(end2-start2)+" milliseconds, not bad!"); System.out.println("****** Everything looks OK! ******"); score += 25; } else { System.out.println("OK, but you took " + (end - start) + " milliseconds, which seems too long (I'm expecting 1000 or less; my laptop takes between 80 and 130 in my implementations). Please let me know if you feel this is in error."); if (end - start < 10000 && end2 - start2 < 10000) score += 10; // At least somewhat fast, partial credit } } catch (Exception e) { e.printStackTrace(System.out); } System.out.println( "Tentative score: " + score + "/100 (Note that any academic misconduct would affect your score.)"); } private static void checkBounds(IAList a) { boolean didExcept = false; try { a.get(-1); } catch (Exception e) { didExcept = true; } if (!didExcept) { throw new RuntimeException("Accessing before the beginning did not cause an exception, but it should!"); } didExcept = false; try { a.get(a.size()); } catch (Exception e) { didExcept = true; } if (!didExcept) { throw new RuntimeException("Accessing after the end did not cause an exception, but it should!"); } } }