CS125 Fall 2008

CS125 Fall 2008

Lab # 4

Implementing an ADT

In this laboratory exercise you will implement an ADT Set. The ADT will be given and a Java interface based upon this ADT will also be supplied to you. You will implement this ADT by creating a class ArraySet. Once you have created this class you will test your implementation using the TestSet program.

Download the starter project

Click here to download the starter files: TestSet.java and Set.java.
Save the files in directory L4.

ADT Set

+add(in element:int):boolean

//adds a new element to a set of integers

//precondition: element is in the universe of input values

//returns true if the precondition is met and operation performed

+remove(in element:int):boolean

//removes the named element from the set

//precondition: element is in the set

//returns true if the precondition is met and operation performed

+union(in otherSet:Set):Set

//returns a set that contains all of the elements of this set and otherSet

+intersection(in otherSet:Set):Set

//returns a set that contains all of the elements that are contained

//in both this set and other set

+contains(in element:int):boolean

//returns true if element is in the set

+isEmpty():boolean

//returns true if set is empty

+size():int

//returns the value of the number of elements in the set

Work to be done

The above ADT specifies and provides the syntax for the operations in an ADT called Set. The Set.java interface provides all the method headers that you are to implement. For this lab, you should create a class ArraySet to implement the interface. ArraySet will use an array of MAX_SIZE = 16 of booleans in this implementation (so you will need an instance variable in this class that is an array of booleans). The universe of integer values is the integers from 0 to 15. The array will initially be empty (all values false). When an integer in the universe is added to the set, the value at its index will be set to true. For example, the set A will contain the elements {2, 5, 7, 8, 15} if its associated array is

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
false	false	true	false	false	true	false	true	true	false	false	false	false	false	false	true

In implementing ArraySet, you should follow the specification in the Set ADT (as further stated in the comments above each operation in the interface.) A possible way to start writing this class is to alter a copy of the Set interface, since all the comments are provided and all you need to do is add the method bodies. In addition to implementing each of these operations in ArraySet, you will add a constructor, instance variables for the boolean array and the size of the set, and a method: public String toString( ) to use for displaying the contents of the set. The display of a the set shown above produced by the toString() method should appear like this:

{2, 5, 7, 8, 15}

Note that the numbers will always be sorted because of the way the set is implemented with an array of Booleans.

Testing

To test each method in your ArraySet class, include a temporary main method in ArraySet that instantiates new objects of type ArraySet, fills the sets with "numbers", prints the contents using the toString() method before and after adding and removing items, and finds the union and intersection of two ArraySet objects (also printing their contents.) Once you are certain your ArraySet works as it should, compile and run the TestSet program you downloaded in the first part of this lab and make sure your final output looks something like the window shown below (the random numbers generated to populate the array will be different each time TestSet is run, so just make sure the union and intersection are accurate for the numbers generated.)

Submitting your work

Show your working program to one of the coaches or your instructor to verify your program is correct. Then, from a terminal window, type the following commands:

cd

        cd cs125

        submit125 L4

Log out

When you are done, logout.