CSCI 151 - MyArrayList CSCI 151 Lab 2: MyArrayList This should be handed in by 6PM on Sunday March 13 In this lab, you will create your first implementation of a data structure from the Java Collections Framework. You will also learn how to use Generics and get some practice writing test cases for you program. The purpose of this lab is to: Learn about the ArrayList structure Learn to create classes using Generics, Use an Abstract class to jumpstart an implementation, Introduce JUnit for proper testing, Part 1 - MyArrayList Basics You'll be constructing your own implementation of the ArrayList data structure so that you understand its inner workings. You should use the prefix "My" in your class names so that you don't accidentally use the standard ArrayList in your testing. However, you will be matching its behaviour, so when in doubt, you can refer back to the ArrayList documentation for clarification and/or use an ArrayList as a working reference solution. Your MyArrayList class will implement the Java List interface. That is, you will need to provide implementation for all of the (abstract) methods contained in List. There are more than 20 such methods, however, and that could take you a while to get through. Fortunately, the folks at Java have provided a lovely abstract class AbstractList that provides some very basic and default behavior for a List. Some of the methods still aren't implemented (that is, they are abstract) and some of them may have inefficient implementation (that is, you'll want to override them), but it's useful nonetheless. Thus your MyArrayList class should extend AbstractList. Because AbstractList itself implements the List interface, your code will do that as well when it extends AbstractList. You'll be using generics for your implementation, and taking advantage of the fact that List and AbstractList are similarly parameterized. To get started, make a project folder Lab2 (for example, I would use Lab2Geitz), Create this in your csci151 folder. In Eclipse make a new Java project that uses this folder; you can call the project Lab2 or Lab2, as you wish. Make a new class in this project in package lab2 called MyArrayList. Below the class name is a box asking for the Superclass; type AbstractList and hit the Browse button; Eclipse will provide the correct superclass java.util.AbstractList, Check the boxes offering stubs for a constructor and any inherited abstract methods, then click Finish. You should see the following class:
public class MyArrayList extends AbstractList
If you get something else, just change the class declaration to this. AbstractList gives you all methods except for get(int index) and size(), however, you'll need to override some of its methods to get your ArrayList in shape to be usable. Basic Design As you might expect from the name, the backing storage for an ArrayList is an array. That is, an ArrayList is really just an array with the extra functionality of dynamic resizing. The MyArrayList's array will not always be full; therefore, your class will need to keep track of the number of items that are currently in the list. Also, you need to keep the data in the array packed to the front so there are no gaps. Private data Add the following members to your MyArrayList class. private int size number of items currently stored in the list (which may differ from the list's current capacity) private E[] data backing storage for MyArrayList Constructors Implement the following constructors in your MyArrayList class. MyArrayList(int startSize) startSize is the initial size you will make your data array. MyArrayList() Use an initial capacity of 2. NOTE: you should not be duplicating code from your other constructor in this one. Have this constructor call the other with appropriate arguments (that is, use this(2)). You may get an error message about allocating an array of a generic type. This can be solved by using casting and a special marker in the source code to suppress the warning. Allocate in a manner similar to:
E[] someArray=(E [])new Object[numElements];
and have a line
@SuppressWarnings("unchecked")
directly above the method header. This doesn't remove the warning in 1.5, but does in 1.6, and it will get rid of the error message in Eclipse. Private Methods You will need to implement a private resize method that doubles the size of the array ( Do not just increase its length by one!) by creating a new array of twice the current size, copying the data over, then resetting the data pointer to point to the new array. private void resize() Create a new array that is twice the size of the previous (use data.length to get the size of the data array) Copy all of the old data into the new array Set this.data to be your new array Feel free to write more private methods if you think they will help with the required public methods. Public Methods (part 1. More to follow.) Implement the following methods in your MyArrayList class int size(); Return the number of items stored in the array, not the maximum capacity (i.e, not the size of the data array that you get from data.length) void add(int index, E element); Adds the element at the specified index, shifting everything else right one space.You are allowed to add at any index location up to and including the current size. (index==size is the first unused location) Resize the array if necessary. Throw an IndexOutOfBoundsException if the index is not within the allowed range. Remember, an Exception is just an Object, so you create it just like you do a regular object. For example, you may use the following:
throw new IndexOutOfBoundsException(); or even better:
throw new IndexOutOfBoundsException("Index Out of Bounds! You tried to access " + index + " but the size is " + size ); boolean add(E element); Adds an item to the end of the array. (Hint: you can use the previous method -- don't just copy the code from there.) This method returns true if the item was added. Since you will always be adding the item specified, you should always return true. E get(int index); Return the value stored at the given index. Throw an IndexOutOfBoundsException if the index is not within the allowed range. Note that this range is smaller than the range allowed for add(). Good programming style suggestions Take advantage of your existing methods and don't duplicate logic. You've got two constructors and two add() methods. Only one needs to do the real work, the second should just figure out a way to call the first. You should include a meaningful message when you construct the IndexOutOfBoundsException. (For example, when Java's ArrayList throws an IndexOutOfBounds exception, it tells you which index was accessed and the size of the arraylist. This seems like good information.) Part 2 - Testing with JUnit The programs you will write in this course get increasingly complex, and increasingly difficult to debug. We want to strongly encourage you to get into good testing habits. Many of you have survived thus far by writing all your code for a lab in one swoop and then testing (if that) as an afterthought at the end. This is no longer a feasible approach. Your life will be much simpler if you "write a little, test a little, write a little more, test a little more ...." So before you proceed to the rest of your MyArrayList implementation, you will test the code you have written thus far, using a Java testing framework called JUnit. As a side note, some of our alums take this to the extreme, and practice "Test Driven Development." As the name suggests, instead of designing your program to fit some guidelines and THEN deciding what tests are adequate, test driven development FIRST decides on a set of tests that you want your program to "pass", and only then do you design the program to pass those tests. You can read more about this software development technique in many places, including Wikipedia. The "old" way of testing was to write test cases in a main method somewhere. Although this approach is convenient and simple, it can be ineffective: There is no explicit concept of a test passing or failing. Typically, the program outputs messages simply with System.out.println; the user has to look at this and decide if it is correct. There is no mechanism to collect results in a structured fashion. There is no replicability. After each test run, a person has to examine and interpret the results. The JUnit framework addresses these issues, and more. JUnit JUnit is a widely-used API that enables developers to easily create Java test cases. It provides a comprehensive assertion facility to verify expected versus actual results. It is simple to create a JUnit test case, especially in Eclipse: Highlight your MyArrayList.java file in the Eclipse Project Eplorer, and select and select New > JUnit Test Case from the File menu Select the radio button at the top: New JUnit Jupiter test You should be able to accept the default options. Explipse will name your test class MyArrayListTest Do not select anything in theWhich method stubs would you like to create? section. The Class under test: textbox should specify lab2.MyArrayList. If it doesn't, use the Browse button to select this class. Click the Next button at the bottom of the window. Select the checkbox to the left of size() and the checkbox to the left of add(E)under MyArrayList. This gives two tests; you will create more later by copying this syntax. Click Finish at the bottom of the window. Eclipse may ask if you want to add JUnit5 to the build path. If it does click Perform the following action: Add Junit 5 library to the build path. You should now have another class file, named MyArrayListTest.java. Check it out. Some things to notice: Each test method is preceded by the tag @Test. You can add your own test methods provided you use this tag. JUnit's default test method names start with the word test, followed by the name of the method that is to be tested. For example, testSize will test the size method. If a method has multiple method signatures (with different parameters) then the test method name will also list the types of the parameters. For example, testAddE() and testAddIntE() test the add(E element) and add(int index, E element) methods, respectively. This naming convention is handy but not required. You can use any name for a test as long as you preceed it with the @Test tag. You can use the @Disabled tag (immediately above the @Test tag) to direct JUnit to ignore the test method that follows. This allows you to write tests before you have written the code to test. Note that JUnit will run the test methods in an arbitrary order, so each one should be self-contained. T It is also simple to run your tests: Right-click your new test class in the Project Explorer and select Run As > JUnit Test. The results of the tests are displayed in the "JUnit View". The stubs JUnit gives for tests automatically fail, so if you run your newly-made tests you should get two fails, no passes. You run the initial test from the Project Explorer. After running a test Eclipse leaves you in the JUnit Explorer; from this window you can run subsequent tests by clicking on the small triangular Run icon at the top of the window. To help you see what to do with the tests we will walk through several examples: Since we selected size() as one of the methods to test, let's think about how to test it. We want the size of a new list to be 0, we want it to increase every time we add to the list, and we want it to return to 0 when we clear the list. The following test method will do that:
@Test
void testSize() {
MyArrayList mine = new MyArrayList();
assertEquals(0, mine.size() );
mine.add(23);
assertEquals(1, mine.size() );
mine.add(34);
assertEquals(2, mine.size() );
}
Type this into your test code and replace the @Test tag over the testAddE() method with @Disabled. You could go back to the Project Explorer and run your test by right-clicking on it, but after running ibe test you should already be in Eclipse's JUnit view. Click on the small green run icon just under the menu bar. Since you disabled one test, Eclipse should report that you ran one test. If you correctly implemented size() it will give you a green bar for a successful run, with no errors and no failures. Now change the middle assertion to incorrectdly say the size should be 0 after adding an element to the list, and rerun the test. This time you get a red bar for a failed test. It tells you that testSize is the name of the failed test, and if you look carefully it even says the line number where the test failed. If you have multiple assertions, as this example does, Eclipse only reports the first failed assertion in a test. Patch up testSize() so it runs correctly (or @Disable it) and change testAddE() to this:
@Test
void testAddE() {
MyArrayList mine = new MyArrayList();
mine.add(23);
int result = mine.get(0);
assertEquals(23, result);
}
This tests the add() method by doing an add and a get, making sure we are retrieving the same value we added. To thoroughly test the method you need to do more than this one example, but this should give you the idea of how JUnit works. Spend a few minutes playing with these two test methods so you can tell the difference between tests succeeding and failing and when tests fail you can find the point in the test code where the failure occurs. Note that you can add a third argument to assertEquals and to other JUnit assertions. This is a string to be printed if the assertion fails; you might have a assesrtion such as
assertEquals(23, result, "get should haves returned 23"). I find Eclipse's output for a failed test sufficient without this. In general, JUnit tests work by creating situations in code and making assertions about the values this code should produce. assertEquals is the most commonly used assertion, but there are others: assertTrue(boolean condition) assertFalse(boolean condition) Checks that the boolean condition is true (or false). assertNull([message], object) Checks that the object is null. assertNotNull([message], object) Checks that the object is not null. assertSame([String], expected, actual) Checks that both variables refer to the same object. assertNotSame([String], expected, actual) Checks that both variables refer to different objects. For a full list of assert methods, go here . One common testing technique for a sitation lilke this where we are making our own implementation of a standard Java class is to build two objects: a standard ArrayList and our MyArrayList. Put t hem through various situations and assert that they do the same thing. For example:
@Test
void testDoTheSame() {
MyArrayListmine = new MyArrayList();
ArrayListstandard = new ArrayList();
for (int i = 0; i < 10; i++) {
mine.add(2*i+3);
standard.add(2*i+3);
}
for (int i=0; i < 10; i++)
assertEquals(mine.get(i), standard.get(i) );
}
You can even test that the correct exceptions are thrown by changing the assertThrows assertion. The syntx for this is a bit convoluted. Here is an example:
@Tes<
void testAddThrows() {
MyArrayList mine = new MyArrayList();
assertThrows( IndexOutOfBoundsException.class, () -> mine.add(5, 23) );
}
The notation ( ) -> mine.add(5, 23) is Java's syntax for a lambda expression, which creates an inline function. You will see and write many lambda expressions in CSCI 275, but we won't make much use of them this semester. You can put a method at the top of the class preceeded by the tag @BeforeEach. This will be run before each of the tests. If every one of your tests needs a new MyArrayList list that contains specific data, you can declare the list as a class variable, initialize it in the BeforeEach method and then use it in each of the tests. This leads to a test class such as:
class MyArrayListTest {
MyArrayList mine;
@BeforeEach
void init() {
mine = new MyArrayList();
}
@est
void testSize2() {
mine.add(23);
assertEquals(1, mine.size(), "size should have been 1");
}
Now it is your turn. So far you have implemented the size() method, two add() methods and a get() method. Write enough tests to convince yourself that any code that passes all of these tests must be correct. As you implement the rest of your arraylist methods, please write the accompanying JUnit test, and at each step run all of your tests. It is easy to add code to an existing class that breaks functionality that previously worked. JUnit is your friend; it will help you maintain a working base of code and avoid the many frustrations of debugging. Part 3 - Completing MyArrayList Now finish your implementation of the MyArrayList class with the following methods. Don't forget to write (and run!) your tests as you go along. Public Methods Implement the following methods in your MyArrayList class E set(int index, E element); Change the value at the specified index to element. Return the previous value. Throw an IndexOutOfBoundsException if the index is not within the allowed range. Note that this range is smaller than the range allowed for add(). Here is an optional idea for testSet(): Read and store the Strings in test1.txt, then use get() and set() to reverse the order of the elements. Print them out to make sure it worked. E remove(int index); Remove the item at the specified index, shifting all other elements to the left. Return the value that was removed. Throw an IndexOutOfBoundsException if the index is not within the allowed range. Note that this range is smaller than the range allowed for add(). Here is an optional thought for testRemove(): Read in the test2.txt, then remove every even-indexed entry, starting at 0 (so, entries 0, 2, 4,...) boolean isEmpty(); Return true if there are no items stored, false otherwise. Test this method appropriately. void clear(); Empty out the list. Be sure to allow garbage collection to take place by setting array entries to null. Test this method appropriately. Part 4 - More Testing Notice that there is no main method here. For this lab you have created a data structure, not a program. To grade your work we will make a program that imports MyArrayList and does things with it. I suggest that you do the same before you hand it in. Handing In Your Work You should hand in a zipped copy of the project folder for this lab. That should contain your README file, MyArrayList.java, and MyArrayListTest.java. If you adhered to the honor code in this assignment, add a README text file to your project folder with the text: I have adhered to the Honor Code in this assignment. You want to keep the graders happy. If there are portions of these programs that you know are not working correctly, it would be helful if you included information about what does and what doesn't work in your README file. Go to your csci151 folder and make a compressed version of your Lab2 project folder. On a Mac select this folder and select Compress from the File menu. On Windows right-click on the project folder and select Send to -> Compressed (zipped) folder In either case you should get a zip file. Open the Blackboard course 202202 Data Structures 01. Click onthe Course Material link, then on the Lab 2 link. In the Assignment Submission section click on the Browse My Computer button. this will bring up the usual navigation controls that should allow you to select your zipped project f ile for this assignment. Last Modified: March 2022 - Bob Geitz.
