Testing & ADTs

This lab will help you learn how to use a simple test harness for Java programs, and you will also practice designing various representations for an abstract datatype (ADT). Part I walks through some sample code to show you how to use a simple testing framework. Parts II and III leave you to your own devices to design the code for a general implementation of Lists and various implementations of a Set datatype.

Part I: A Simple Test Harness

Begin by creating a new Eclipse project (called Lab7). Then download the following two libraries:

Add them to your Eclipse project:
  1. Right click on Lab7 in the left-hand pane.
  2. Go down to Build Path and then choose Add External Archives
  3. Navigate to wherever you downloaded the above libraries and add both of them.
These libraries automatically provide two things of interest for this assignment. The first is the ISame interface:
public interface ISame {
  // is this object the same as the given object?
  public boolean same(Object obj);
The second is the class SimpleTestHarness. SimpleTestHarness objects contain methods that run test cases, keep track of success and failure, and print out detailed reports. Let's look at a simple class to learn how to use the test harness.

Part II: Lists of Comparable Objects

Now build a list data structure that can contain any comparable object. Use the test harness to write your examples and tests (this of course requires you to implement the ISame interface). Your list implementation should support at least four methods: Also, you may want to save this code. It is a very general implementation of lists since it works with any objects that implement IComparable. It might prove useful to have this code already written and tested to use in future assignments.

Part III: An ADT for Sets

Now we will build three different implementations of Sets and compare the tradeoffs in the representations. Start by designing the ISet interface. Your interface should support at least the following operations:

Again, you will also have to implement the ISame interface in order to build and run test cases. Be prepared to design helper methods in your List data structure from Part II.

You should build three implementations of ISet. They differ in the way that the elements are represented:

  1. Represent the elements as a list of objects (using the code from Part II).
  2. Represent the elements as a sorted list of objects.
  3. Represent the elements as a binary search tree.

You should consider the relative merits of each representation. Consider how much "work" it would take to: By "work", we mean how long it would take the computer to compute the answer when the method is called on a large Set. Your answer to each question should rank the representations from fastest to slowest and include a few words to justify your expectations. Later in the course, we will pin down precisely how to carry out such an analysis, but it will help for you to have considered such questions on your own before then.

Part IV Challenge Problem: Remove

Design a method to remove a given item from a Set. This should be easy for the list and sorted-list representations, but you might find it tricky to perform on the binary search tree representation!