Lab 2 - MyArrayList

CSCI 151
Fall, 2018
Due:  11:59 pm, Sunday, September 30

In this assignment, you will create your first Java class, an implementation of the ArrayList data structure from the Java Collections Framework. You will also learn how to use Generics and get some practice writing test cases for your program. The purpose of this lab is to:

Part 1:  Writing the MyArrayList class

You'll be constructing your very own implementation of the ArrayList data structure so that you understand its inner workings. You should use the prefix My in the class name so that you don't accidentally use the standard ArrayList in your testing. However, you will be matching its behavior, 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.  The List interface contains more than 20 methods.  Your class will contain a subset of these methods.

Write MyArrayList as a generic class.  That means that the type of objects to be stored in the list is specified when the list is declared or instantiated.  Use the header line

public class MyArrayList<E> extends AbstractList<E>

Note that you are extending AbstractList instead of implementing List.  AbstractList is an abstract class contained in the java.util package.  It contains stub routines for most of the List methods, so you don't have to implement the entire List interface, only the methods indicated in parts 2 and 3 of the lab below.  (Two methods which remain abstract in AbstractList are get and size.  You won't be able to compile your class successfully until you write implementations for these two methods.)  Since AbstractList implements List, your class will, too.

AbstractList is in the java.util package, so you need to write  "import java.util.*;" at the beginning of your class file.

Note:  Don't use any of the methods from the Arrays class in your implementation, with the exception of Arrays.toString, which you may use for testing if you like.

Private data

Define the following member variables in your MyArrayList class:

int size
the number of items currently stored in the list (which may differ from the list's current capacity)
E[] data
the array where the items in the list will actually be stored
The list items should be stored in consecutive array positions, starting with position 0.  For example, if the list contains 4 elements, they should be stored in array positions 0, 1, 2, and 3.  (There should not be any gaps.)

Note the difference between the length of the array (data.length) and the size of the list.  The array may not always be completely filled up; we allow some extra space for future additions.

Constructors

Recall that the purpose of a constructor is to initialize an object's instance variables.  In this case, your constructors must initialize size and data.  Write the following constructors in your MyArrayList class:

MyArrayList(int startLength)
startLength is the initial capacity of the data array.
MyArrayList()
Use a default initial capacity of 5.  NOTE:  Avoid duplicating code from your other constructor in this one, by having this constructor call the other with an appropriate argument (that is, use this(5)).

Note:  Java does not permit the instantiation of an array of a generic type.  To create an array of E objects, you need to create an array of type Object, then cast it into an array of type E.  For example, to create an E array with 5 elements, you would write:

E[] someArray = (E[]) new Object[5];

This code will generate a warning message from the compiler.  You can (and should) suppress the message by writing the following statement immediately before the method in which the cast operation occurs:

@SuppressWarnings("unchecked")

A private method

Write a private method called resize that doubles the length of the array by creating a new array of twice the current length, copying the data from the current array to the new one, and then resetting the data pointer to point to the new array.  (The old array will eventually be garbage collected.)

private void resize()
Create a new array that is twice the size of the current one (use data.length)
Copy all of the old data into the new array
Set this.data to be your new array

While you are testing the class, it's a good idea to have the resize method print a message indicating the old and new lengths.  You can remove the print statement when it seems to be working.

Some public methods (more to follow)

Implement the following methods in your MyArrayList class

int size();
Return the number of items stored in the list, not the maximum capacity of the underlying array (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, with a statement like this:
throw new IndexOutOfBoundsException();
or even better:
throw new IndexOutOfBoundsException("Index Out of Bounds! You tried to get " +
index + " but the size is " + size );
or something to that effect.
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().

Part 2 - Testing with JUnit

We've noted in class that today's software is extremely large and complex.  Object-oriented programming deals with this size and complexity by breaking down large programs into small modules (i.e., objects).  Software engineers have found that it is not only wise to write their software in small chunks, but also to test it that way.  That is, as each class is written, a set of tests is written to verify that it is working properly.  This is sometimes called "unit testing."  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 people take this even further, 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:

The JUnit framework addresses these issues, and more.

JUnit

JUnit is a unit testing framework for Java that is supported in Eclipse.  It enables developers to easily create Java test cases.  It provides a comprehensive assertion facility to verify expected versus actual results.  We will use it in this lab to develop tests for the MyArrayList class.  You'll be strongly encouraged to continue using it as we write other classes in future assignments.

It is simple to write a JUnit test case in Eclipse:

It is also simple to run your tests:
So what can you actually do in these tests?  Let's walk through some examples:

JUnit methods

The JUnit framework contains many useful methods that you can call in your tests.  Here is a list of some of them:
assertTrue([message], boolean condition)
assertFalse([message], boolean condition)
Checks that the boolean condition is true (or false), if not, displays the message.
assertEquals([message], expected, actual)
assertEquals([message], expected, actual, tolerance)
Tests that float or double values match. The tolerance is the number of decimals which must be the same.
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 (you may need to click on the Assert class in the left lower pane).

You can even test that the correct exceptions are thrown by changing the @Test tag before your test method.  For example, to test the exception that should be thrown by the add method when adding "off the left" of the list, we could use this code:
@Test(expected=IndexOutOfBoundsException.class)
public void testForAddLeftException() throws Exception {
    MyArrayList<Integer> test = new MyArrayList<Integer>();
    test.add(-1, 5);
}

To test the exception that should be thrown by the add method when adding "off the right" of the list, we would use a second method:

@Test(expected=IndexOutOfBoundsException.class)
public void testForAddRightException() throws Exception {
    MyArrayList<Integer> test = new MyArrayList<Integer>();
    test.add(test.size()+1, 5);
}


Writing your own tests

Now it's your turn.  In each of the following test methods, implement the recommended test.

NOTE:  Some of the these tests ask you to read some input data from a file.  You can do this by using a Scanner created to read from a File, as follows:

Scanner scanner = new Scanner(new File("test1.txt"));

Then just use the Scanner in the usual way.

There you go, your very first JUnit tests!  As you implement the rest of your arraylist methods, please write the accompanying JUnit test, and add to any previous ones.

Part 3 - Completing MyArrayList

Now, finish writing the public methods of your MyArrayList class.  Don't forget to write (and run!) the indicated tests as you go along.

More 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 item that is being replaced.
Throw an IndexOutOfBoundsException if the index is not within the allowed range.  Note that this range is smaller than the range allowed for add().
In testSet(): Create a MyArrayList of Strings and an ArrayList of Strings.  Read the file test1.txt and insert each line of the file, one at a time, into both lists.  Use the add(element) method for your MyArrayList, but insert the lines into the ArrayList using add(0,element). (The effect is that the two lists are in the opposite order.)  Now use use get() and set() to reverse the order of the elements in your MyArrayList.  The two lists should now be in the same order. 
Assert that the sizes of the two lists are the same. Then loop through the two lists element-by-element and assert that the ith elements should be equal for each i.
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().

In testRemove(): Read in test1.txt, then remove every even-indexed entry, starting at 0 (that is, entries 0, 2, 4,... in the original list; keep in mind that positions change as items are removed) and add them into a second MyArrayList.  Check against a standard Java ArrayList.
boolean isEmpty();
Return true if there are no items stored, false otherwise.

Write your own unit test for this method..
void clear();
Empty the list.  Be sure to allow garbage collection to take place by setting array entries to null.

Write your own unit test for this method.

Efficiency Checking

Great! You are done your implementation, and you have written some JUnit tests to make sure that each method works. Hopefully everything is being added, set, and removed correctly. The last thing we want to quickly check is that your program is working efficiently. Add the following two tests to your test file (precede the method header with the @Test tag):

Please put your answers to the above questions in a plain text file named README file, and submit it with your lab.

***** After you have completed the efficiency tests, please put @Ignore in front of the @Test to disable them. *****

Comments

For this assignment, you only need to include a block comment at the beginning of each of your java files, with a description of of the contents of the file and your name.  If you're familiar with javadoc, it would be a good idea to write your comments in javadoc style.  We'll be covering javadoc later in the course.

handin

Look through your programs and make sure you've included your name at the top of all of them.  If you know that there is a problem in one of your programs, document that at the top.  If you adhered to the honor code in this assignment, add the following statement as a comment at the top of your README, MyArrayList.java and MyArrayListTest.java files:

I have adhered to the Honor Code in this assignment.

Quit Eclipse, and then go through and delete any *.class files and backup files.  (If you don't quit Eclipse first, it will keep regenerating your class files when it autocompiles!)

You now just need to electronically handin all your files.

    % cd          # changes to your home directory
    % cd cs151    # goes to your cs151 folder
    % handin      # starts the handin program
                            # class is 151
                            # assignment is 2
                            # file/directory is lab2

    % lshand      # should show that you've handed in something

You can also specify the options to handin from the command line

    % cd ~/cs151                 # goes to your cs151 folder
    % handin -c 151 -a 2 lab2

    % lshand      # should show that you've handed in something