Lab 2 - MyArrayList
CSCI 151
Spring, 2018
Due: 11:59 pm, Sunday, February 25
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:
- Learn how to write your own Java class,
- Begin learning about Java Collections,
- Learn how to write a generic class,
- Learn how to use JUnit to do proper testing of a class.
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:
- 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.
- main has access to protected and private
members and methods. While you may want to test the inner
workings of a class, many tests are really about testing an
object's interface to the outside world.
- 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 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:
- Right click on your MyArrayList class file in the package view
in the left pane, and select New > JUnit Test Case.
- Select the radio button New JUnit 4 test and click Next.
- Name your test MyArrayListTest
- Do not select anything in the Which method stubs
would you like to create? section.
- Click Browse... in the Class under test: section.
- Type MyArrayList in the text field in the dialog that
came up. Select MyArrayList in the list below.
- Select Next.
- Select the checkbox to the left of MyArrayList<E>.
This should select all the methods that we will test initially.
You will be adding tests by hand later.
- Select Finish
- When it asks if you want to add JUnit4 to the build path,
click Perform the following action.
- You should now have another class file, named something like
MyArrayListTest.java. Check it out. Some things to notice:
- All test methods are preceded by @Test. You can
add your own test method provided you use this tag.
- All test methods start with 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.
- You can use the @Ignore tag (instead of the @Test
tag) to specify JUnit to ignore the test method that follows.
Otherwise, JUnit will run the test methods in an arbitrary
order (so each one should be self-contained.)
It is also simple to run your tests:
- Right-click your new test class and select Run As >
JUnit Test.
- The results of the tests are displayed in the "JUnit
View". Right now all your tests should be failing, as we
haven't implemented any yet.
So what can you actually do in these tests? Let's walk through
some examples:
- To test that your empty constructor is working correctly,
replace the fail(...) method call with the following
code in the testMyArrayList() method:
MyArrayList<Integer> test = new MyArrayList<Integer>();
ArrayList<Integer> standard = new ArrayList<Integer>();
assertEquals("Size after construction", standard.size(), test.size());
Basically, we construct an arraylist with our implementation,
and compare it to that of Java's. Ideally the size of our new
arraylist is 0, which should be the same as
standard.size(). Observe that this is a stand-alone test;
it constructs the array lists it needs, and is disjoint from the
other tests.
- To see what would happen if your test failed, change the last
line of code to
assertEquals("Size after construction", 2, test.size());
Rerun the test (press the green play-button icon with the yellow
arrow), and see how the test fails. Notice that the failure
trace conveniently tells you what value you were expecting (2),
and what value you actually got (0). Nice! Change it
back before proceeding.
- To test that your size method is working correctly, replace
the fail(...) method call with the following code in
the testSize method:
MyArrayList<Integer> test = new MyArrayList<Integer>();
ArrayList<Integer> standard = new ArrayList<Integer>();
assertEquals( "Size after construction", standard.size(), test.size());
test.add(0,5);
standard.add(0,5);
assertEquals( "Size after add", standard.size(), test.size());
Now run the test to verify that your size method is working
properly.
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.
- testAddE(): Tests your constructor, the
single-parameter add method (which should call the two-parameter
add method), and the get method. Under the covers, it will
also test your private resize method. This also tests adds to
the end of the list and adds when the list is at capacity.
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
listsusing their
respective add(element) methods. Assert that
the sizes of the two lists are the same. Then loop
through your two lists element-by-element and assert that the
ith elements should be equal for each i.
- testAddIntEFront(): Tests adding to the
beginning of the list.
Again, read Strings from test1.txt,
but insert each line at the front of both lists using add(index,
element). Then verify that the lists are
identical.
- testAddIntEMiddle(): Tests adding to the middle
of the list.
Once more, read Strings from test1.txt. This time
insert each line at the current midpoint (position size/2) of
the list.
- Write methods to test the IndexOutOfBounds exceptions on both
borders (index -1 and index size or size+1, depending on the
method) for the parameterized add method and the get method.
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):
- testAddEfficiency(): Create a test program that
inserts 1,000,000 Integers starting at 1 onto the end of the
list (using the single-parameter add). Every
10,000 adds, print out the value. Note the speed with
which the program completes. Now insert the same Integers
but onto the front of the list. Does the speed
change? Why or why not?
You may want to change this method's @Test tag to
an @Ignore tag before proceeding. This will
indicate to JUnit to ignore this test for the time being
(which is good, because it takes a while to run.)
- testRemoveEfficiency(): As with the previous test,
insert 1,000,000 Integers starting at 1 onto the end of the list
(using the single-parameter add). Now remove all
the elements from the back of the list (printing out the value
every 10,000 removes). This should run quickly (and if not, take
another look at your remove method).
- testMemory(): Finally, create a test program that
stores Integers and have it store values starting with 1 until
it runs out of memory or throws an exception (use an infinite
loop). Every 10,000 adds, print out the value. Note
what the last value printed was. Now run it again telling
it to use more memory and notice if the value changes or
not. You can tell Eclipse to use more memory by clicking Run
> Run Configurations..., clicking on the Arguments
tab, and inserting -Xmx500m in the VM arguments
textbox. Or, you can run java from the command line:
% java -Xmx500m Test8
Also, pay attention to the rate at which it prints out
numbers. Do you notice any changes? Run it again. Does it
behave the same? Why do you think this is happening?
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