Espresso: Laboratory: Dynamic Arrays

Summary: In today's laboratory, you will explore two new concepts: expandable arrays, and generic classes in Java. These are initial steps in our study of complex structures for storing collections of data.

Exercises

Exercise 0: Preparation

a. In Eclipse, create a new package entitled username.dynArray in your Code project.

Exercise 1: An Expanding int Array

Create a new class DynamicArray in the package username.dynArray. The purpose of this class will be to create a more "object-like" array that automatically expands to accommodate the number of values stored in it.

Fields.
a. Add a field that is a standard one-dimensional array of int values. You might call it data.

b. Add a second field, perhaps called n, that will store the effective size of the array (i.e., the number of positions in the array that are currently in use). Note that this number will frequently be fewer than the array's capacity (i.e., the length of the underlying array).

Constructor.
c. Write a constructor that generates a new array with a small number of (empty) positions. A reasonable default capacity might be 16, whereas n will be 0.

Exercise 2: Adding get and set

a. Add a method set(int position, int val) that sets the value stored at position to val.

Note that if position is greater than or equal to n, then the call to set will effectively have inserted a new value into the array. Thus, the effective size of the array, n, should also be increased.

Moreover, if position is beyond the capacity of the underlying array, the array will need to be expanded. To do this, you will want to follow these steps:

b. Add a method to your class, get(int position), that returns the value indexed by position.

Note that if position is within the effective size of the array, all is well. However, the method should throw an exception if the input parameter position is not valid, given the array's effective size. An appropriate exception for this circumstance would be java.lang.ArrayIndexOutOfBoundsException.

Test your code carefully. It is easy to get an "off-by-one" error, which could make the array behave as if it is one element smaller, or larger, than it should be.

Exercise 4: Making it Generic

A generic class in Java is a class that can store data of any object type. This is a powerful way to make code re-usable, and it is particularly appropriate for classes which store data collections. Moreover, it is surprisingly easy to make a generic class in Java. In this exercise, you will upgrade your DynamicArray class to make it generic. To do so, make the following revisions.

a. Modify your class header to read: public class DynamicArray<T>. Here the <T> implies that the class will be generic, and declares T to be shorthand for whatever object type the client chooses to store in the array.

b. Modify the declaration of the array field, such that it becomes an array of Objects. For example,

   Object[] data;

Make the corresponding change in each place that you instantiate the array. (This should happen in two places: once in your constructor, and again in the method set).

c. Modify the header for the method set to indicate that it accepts a value of type T.

   public void set(int pos, T val)

d. Finally, modify the header for the method get to indicate that it will return a value of type T.

   public T get(int pos)

You will also need to cast the value returned by get to type T. For example,

   return (T)this.data[pos];

Note that the syntax for making arrays generic is unusual. If we were writing a class that stored individual data items (not items in an array), we would simply declare those data items to have type T, and we would not need to cast the value before returning it.

Exercise 5: Using a Generic Array

The code below makes use of the generic dynamic array to store strings. Note the syntax used to declare the array and to specify that it will store data of type String.

   public static void main(String[] args) {      
      DynamicArray<String> a = new DynamicArray<String>();

      //load more than the default number of values
      for (int i=0; i < 24; i++) {
         a.put("hello " + i);
      }

      //set one value specifically
      a.set(23, "goodbye");

      //print out all the values
      int size = a.size();
      for (int i=0; i<size; i++) {
         System.out.println(a.get(i));
      }
   }// main(String[])