CSCI 151 - Lab 1 - Spring 2008 MyArrayList - Testing, testing, 1, 2, 3...

11:59.59pm, Sunday, February 17

Assignment Description

In this lab you'll be creating your first implementation of a data structure from the Java Collections Framework. You'll also be learning how to use Generics and getting some practice writing test cases for you program.

If you've not done so, I suggest you do Lab 0 first.

Part 1 - MyArrayList

We'll be constructing an implementation of the ArrayList data structure. We'll be using the prefix "My" in our class names so that you don't accidentally use the standard ArrayList in your testing. However, we 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.

MyArrayList implements the Java List interface. It contains more that 20 methods, however, we don't have to implement them all if we extend the existing class AbstractList.

We'll be using generics for our implementation, and taking advantage of the fact that List and AbstractList are similarly parameterized. Just declare your class like the following: 

    public class MyArrayList<AnyType> extends AbstractList<AnyType>

AbstractList gives you all methods except for get(int index) and size(), however, you'll need to override many other methods to get this working.

You should be using Javadoc style comments in your programs. 

javadoc -d docs -link http://cs.oberlin.edu/~kuperman/csci151/jdk1.5/docs/api *.java

Basic Design

As you'd expect, the backing storage for an ArrayList is an array. However, you'll need to keep track of the number of items that are currently in the array you may not have something in every slot. Also, you need to keep the data in the array packed to the front so there are no gaps.

When the array is full, and a user tries to add something in, you should double the size of the array. You'll need to copy the previous items into the same slots in the new array.

Private data

int size
number of items currently stored in the list
AnyType[] data
backing storage for MyArrayList

Constructors

MyArrayList(int size)
size is the initial guess as to the number of items in the list. You should just round this up to the nearest power of 2 and use that as the initial max capacity. (You can just start with the value of 2 and keep doubling that until it is no smaller than the requested size.)
MyArrayList()
Use an initial capacity of 2. NOTE: you should not be duplicating code from your other constructor in this one.

You may get a compiler warning 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: 

    AnyType[] data=(AnyType [])new Object[size];

and have a line 

    @SuppressWarnings("unchecked")

between your JavaDoc comments and 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.

Public Methods

boolean add(AnyType element);
Adds an item to the end of the array.
This method returns true if the item was added. Since you will always be adding the item specified, you should always return true.
void add(int index, AnyType 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.
AnyType 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().
AnyType set(int index, AnyType 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().
AnyType 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().
int size();
Return the number of items stored in the array, not the maximum capacity.
boolean isEmpty();
Return true if there are no items stored, false otherwise.
void clear();
Empty out the list. Be sure to allow garbage collection to take place.

Good programming style suggestions

You'll probably want a private method to handle the array resizing. I'd suggest printing yourself a message when it is called at first indicating what size it is and what size it becomes. Just be sure to remove it after doing some testing.

Also, 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.

Part 2 - Testing

Next you'll be creating a set of programs that exercise your MyArrayList class. Each should be a separate file named Test1.java, Test2.java, etc.

  1. Take an array of Strings from the command line and insert them one at a time into a MyArrayList<String> using the add(element) method. Then print the contents of the list. (AbstractList has a toString() method that will do the work of actually creating the output you need.)
  2. Same as #1, but after displaying the contents of the list, use get() and set() and reverse the order of the elements. Then print the list again.
  3. Same as #1, but insert each command line argument at the front of the list using add(index, element).
  4. Same as the previous, but insert the String in the midpoint (size/2) of the list.
  5. This time, the command line arguments will be Integers. Insert them as in #1 and print out the list. Then, remove every Integer from an even index starting at 0 (0,2,4,...) and add them into a second MyArrayList. Then print out each list and the sum of the Integers they contain.

  6. Create a class that tests out the exceptions you should be generating by using try/catch blocks. You should focus on the border cases. For example, try to add to position 0, then try position -1.

    Keep your output short and tidy, maybe just passed/failed messages. You can just use the exception's toString method if you want to see the type of exception you caught.

    Trying to add to position 0: passed.
Trying to add to position -1: passed! java.lang.IndexOutOfBoundsException: Index: -1, Size: 1
  7. Finally, create a test program that stores Integers and have it store values starting with 1 until it runs out of memory (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. 
    java -Xmx500m Test7

    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?

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 MyArrayList.java file:

I affirm that I have adhered to the Honor Code in this assignment.

Go through and delete any *.class files and backup files.

handin

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 1
                            # file/directory is lab1

    % 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 1 lab1

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

Lab Goals

This lab is intended to:

Last Modified: February 12, 2008 - Benjamin A. KupermanVI Powered