Generics Lab

Why?

You have been using generics for some time; whenever you make an ArrayList where T is some type, type T is a generic type. You also need to know how to create your own classes with generic parameters. This lab is for practicing this skill.

Success Criteria

Be able to write a class with a generic parameter.

Design

You know what sets are from grade school (and also from reviewing them in your discrete math course). Like lists (for example, ArrayLists), sets are very convenient object containers to have around. There are many ways to implement sets. One way that works well for sets drawn from a small universe (for example, sets that contain various collections of twenty or thirty strings, or sets of enumeration values) is to use arrays to keep track of their contents.

Suppose we have some small collection of values v₀, v₁, … v_n-1 of type T. Call this our universe. Suppose we record these values in an array of type T (called universe, of course), so that v₀ is stored at universe[0], v₁ at universe[1], and so forth up to v_n-1 stored at universe[n-1]. Suppose we also have a boolean array contains of size n. We can represent any set of elements from the universe by setting to true the elements of contains that correspond to the values in the set, and all other elements of contains to false. For example, the set {v₁, v₅, v₁₂} can be represented by the a contains array with contains[1] == contains[5] == contains[12] == true, and all other elements of contains set to false. This is the idea behind our implementation of an ArraySet.

UML Diagram

Consider the UML diagram below.

classDiagram
class ArraySet~T~ {
  -universe : T[*]
  -contains : boolean[*]
  -int size
  +ArraySet(elements T[*])
  +add(value T) boolean
  +remove(value T)
  +contains(value T) boolean
  +size() int
  +clear()
  +equals(otherSet ArraySet~T~) boolean
}

This class has a generic parameter T, which in UML is typically represented in a dashed box at the upper-right corner of the class symbol. However in this case it is represented beside the class name within angle brackets. Instances of this class are sets of values of a universe of values of type T, as just explained. The count attribute keeps track of how many elements are in the set. Besides the diagram, this class has the following specifications.

Specifications

ArraySet(T[] elements) — This constructor accepts an array of values in the universe and makes an empty set of those values. It copies the values from the elements array into a newly created universe array.

boolean add(T value) — This method adds value to the set, provided it is in universe. If value is in universe, it returns true; otherwise it returns false. Note that adding a value to a set that already contains it does nothing (in particular, it does not alter the size of the set).

void remove(T value) — This method removes value from the set, if it is there; otherwise it does nothing. Note that values outside the universe cannot be in the set, so if such a value is passed to this method, the method does nothing.

boolean contains(T value) — This is the membership method; it returns true just in the case that value is in the set.

int size() — This method returns count.

void clear() — This method makes the set empty.

boolean equals(ArraySet<T> other) — This method return true iff otherSet has the same size and contains the same elements as this set.

Plan

1. Open Eclipse and make a new project. Download the ZArraySetTest.java class and place it in the default package.
2. Look over the tests in ZArrayTest.java class to see how the ArraySet class can be used if you are still a little puzzled by how it is supposed to behave.
3. Create the ArraySet class. Start implementing it in a test-driven development manner. You may find it useful to comment out a lot of the tests in ZArraySetTest.java class until you are ready to implement the code for them (just so you get green bars as you go along). Remember that you can comment out blocks of code in Java using the /* and */ comment delimiters (or highlight several lines and press ctrl + / to toggle single-line comments in most IDES, macOS crew: you typically have to use cmd where the rest of the world uses ctrl).
4. When you finish, show your successful complete test run to the instructor. If you cannot finish before the end of the class, show what you have got.
5. If you finish early you might write the following methods (along with tests for them). boolean isSubset(ArraySet<T> otherSet) — returns true iff every element of this set is also a member of the otherSet. ArraySet<T> complement() returns a new ArraySet<T> with the same universe as this set, containing all the values of the universe that are not in this set.

Submitting

Submit your completed file to Gradescope. You may submit as many times as you like.

Acknowledgements

This lab was originally authored by Dr. Chris Fox.