CompSci-61B Lab 2a
ADT Classes

Instructor: Prof. Robert Burns

The purpose of this assignment is to develop a CompSci-61B version of the "AList" class that appears in Carrano chapter 5. Features of the Carrano development that we will follow include the use of generics and interfaces. Some minor features are different, including the names of some methods ("getLength" and "display") and having only one constructor.

The classes you will develop in the next lab (2b) can take the place of Java arrays in some applications. These classes are "MyArrayList" and "MyLinkedList", similar to Java's own "ArrayList" and "LinkedList" classes. To prepare for this development, this lab (2a) establishes some preliminary understanding and ground work that will be applied and expanded in the next lab.

Previous labs created the package "compsci61b.intro". Note that the package for the classes to be created in lab 2a is "compsci61b.testing". We will use this package also in future labs for classes meant for development purposes only. In future labs we'll start putting well-developed classes into the package "compsci61b". Still, when you create your jars, files from all of these packages will get included.

Note -- even though "intro" and "testing" are subfolders of "compsci61b", their contents are not part of package "compsci61b". Packages pertain only to the files actually stored in a folder, and have nothing to do with any subfolder structure. Subfolders are only for file organizational purposes, and not for packaging. However, when jarring with wildcards, the contents of subfolders are brought into the jar.

This assignment is worth 40 points, and consists of 4 exercises. Zero points will be awarded for programs with misspelled filenames, or incorrect case. Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader. Be sure to complete both exercises and post the lab2a.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work. Check the course outline for due dates for lab assignments.



EXERCISE 1: The (non-generic) List Interface (10 points)
Write MyIntList.java in package compsci61b.testing similar to the "ListInterface" listing in our Carrano textbook, in chapter 4. But name the interface "MyIntList", and do not use generics -- write it for Integer values instead. That is, the interface is for classes that manage lists of whole numbers only.
// javac compsci61b/testing/MyIntList.java
// jar cf lab2b.jar compsci61b/*   <- should add files from all previous labs

... <- identifying comments go here

package compsci61b.testing;

public interface MyIntList
{
  ... <- method declarations go here
}
Add method declarations as in Carrano, with the following exceptions:

Compile and jar, but do not run the program. Since it is an interface, it cannot be run.

Copy/paste the following test.java program, and save it in the parent folder of your "compsci61b". You do not need to keep this file after you have used it, and you are not supposed to submit it. The purpose of test.java is to validate the public interface, assuring that it meets the specifications. Note the special compile and run commands, which account for the fact that test.java is not in the "compsci61b" package.

// javac -classpath lab2b.jar test.java
// java -cp .;lab2a.jar test     <-- in XP
// java -cp .:lab2a.jar test     <-- in UNIX

import compsci61b.testing.*;

public class test
{
  public static void main(String[] argv)
  {
    System.out.println("Testing MyIntList.");
    MyIntList a;
    System.out.println("Test completed.");
  }
}
Do not post this version of lab2a.jar -- wait until you complete all exercises.

EXERCISE 2: Your First Data Structure Class (10 points)
Write MyIntListClass.java in package compsci61b.testing, using the interface "MyIntList". Data structure classes typically use arrays or linked lists to store values internally, because they allow for multiple values. But to avoid this complication for now, in order to focus on the implementation of an interface, our "MyIntListClass" data structure class will store only one value. Here are the detailed specs:

Here are sample assessor and mutator methods for this class:

  public boolean add(int index, Integer value)
  {
    assert value != null; // do not allow null values to be added
    boolean result = false; // assume it won't work

    if (index <= 0 && index <= nValues) // index validation
    {
      if (!isFull())
      {
        data = value;
        ++nValues;
        result = true; // hey -- it DID work!      
    } }

    return result;
  }

  public String toString()
  {
    String buf = getClass().getName();
    if (isEmpty())
      buf += "is empty";
    else
      buf += "contents: " + data;
    return buf;
  }
Be sure to align your code and indent properly, so that your work has a professional appearance.

Compile, jar, and run the program. When you build the ".jar" file later, it should contain all the files from previous labs.

The following is another test.java program for you to copy/paste, and validate the public interface for "MyIntListClass".

// javac -classpath lab2a.jar test.java
// java -cp .;lab2a.jar test     <-- in XP
// java -cp .:lab2a.jar test     <-- in UNIX

import compsci61b.testing.*;

public class test
{
  public static void main(String[] argv)
  {
    MyIntList a = new MyIntListClass();

    System.out.println("Testing " + a.getClass().getName());
    System.out.println("Should be true: " + (a instanceof compsci61b.testing.MyIntList));
    System.out.println("Should be true: " + (a instanceof compsci61b.testing.MyIntListClass));

    int i;
    Integer value = 0;
    boolean b;

    b = a.add(value);
    b = a.add(0, value);
    value = a.remove(0);
    a.clear();
    b = a.replace(0, value);
    value = a.getEntry(0);
    b = a.contains(value);
    i = a.size();
    b = a.isEmpty();
    b = a.isFull();

    System.out.println("Test completed.");
  }
}
To test the class operation, include a main inside the class. In main, create a "MyIntListClass" object, and exercise all of its methods. Your work will be scored using a separate testing program that is not provided to you. So make sure that your own testing is sufficient to assure yourself that the class works according to the specs. If you have any questions about the specs, ask in lab or use the online discussion group -- don't assume anything.

Do not post this version of lab2a.jar -- wait until you complete all exercises.



EXERCISE 3: Support For Multiple Values (10 points)
Write MyIntegerList.java in package compsci61b.testing, using exercise 2 as a model. It uses an Integer array to store its values. The array size is initially 10, and the data structure automatically doubles the size of the array whenever it needs to do so. Here are the detailed specs:

Here is sample code for expanding an array whose indentifier is data:

Integer[] newData = new Integer[2 * data.length]; // 2nd array with double the size
System.arraycopy(data, 0, newData, 0, data.length); // copy contents into 2nd array
data = newData; // make the exchange      
Here is sample code for creating a gap at index index in an array whose indentifier is data, containing nValues values:
for (int i = nValues; i > index; i--)
  data[i] = data[i - 1]; // move right
Here is sample code for closing a gap at index index in an array whose indentifier is data, containing nValues values:
for (int i = index + 1; i < nValues; i++) data[i - 1] = data[i]; // move left
data[--nValues] = null; // to release object for garbage collection
Use the same test.java program as you did for exercise 2, to validate the public interface. But change all references to "MyIntListClass" to "MyIntegerList", and replace the "should be true"'s like this:
MyIntList a = new MyIntegerList();
...
System.out.println("Should be true: " + (a instanceof compsci61b.testing.MyIntList));
System.out.println("Should be true: " + (a instanceof compsci61b.testing.MyIntegerList));
To test the class operation, include a main inside the class. In main, create a "MyIntegerList" object, and exercise all of its methods. Make sure that the array expansion and shifting code works correctly.

Compile the class, jar it, and run the test program. But do not post this version of lab2a.jar -- wait until you complete all exercises.



EXERCISE 4: Introduction To Java Generics (10 points)
Write the interface MyList.java in package compsci61b.testing, using exercise 1 as a model. Modify it so that it uses Java generics, instead of being exclusively for Integer values. This should be similar to Carrano's "ListInterface" in chapter 4, without "display". (In a future lab, this will be rewritten and saved in package compsci61b.)

Compile and test the interface as you did with "MyIntList" in exercise 1. Use the same test.java, with "MyList" instead of "MyIntList", to validate the public interface.

Write MyListClass.java in package compsci61b.testing, using exercise 2 as a model. The data structure's capacity is one single value, as it was in exercise 2. Modify the class so that the data type of the stored value can be any object data type, and not exclusively Integer. This should be similar to Carrano's "AList" in chapter 5, without the array, without the 2nd constructor, with zero-based indexing, and with "toString" instead of "display".

This new class should implement the new "MyList" interface, instead of "MyIntList". Compile the class, jar it, and test.

For public interface validation, use the same test.java as in exercise 2, but use these statements to create and validate the data structure object:

MyList<Integer> a = new MyListClass<Integer>();
...
System.out.println("Should be true: " + (a instanceof compsci61b.testing.MyList));
System.out.println("Should be true: " + (a instanceof compsci61b.testing.MyListClass));
Create your final version of lab2a.jar, with files from this and all previous labs. Post your lab2a.jar file to your student UNIX account for grading and credit.

[ Home | Contact Prof. Burns ]