Lab 1. Sets as sorted arrays

The purpose of this assignment is to practice Java-programming with

recursion,
interfaces,
comparators,
and generics.

A. Implementing a set of integers by a sorted array

A simple way to implement a set of elements is as a sorted array containing these elements. In this way you can write an efficient method for deciding whether a given element is in the set by using binary search.

Your first task is to implement a set of integers as a sorted array of integers. You should implement the following interface with one method

public interface MyIntSet {
    public boolean member(int element);
}

by a class

public class MySortedIntArray implements MyIntSet

Your program should be called with the command

java Lab1A <element> <file>

where <file> is a file containing a sorted list of integers separated by spaces, and <element> is an integer. If <element> is in <file> then the program should print true on standard output, otherwise false.

Binary search is described in section 9.3.3 of Goodrich and Tamassia (4th edition). On p 395 there is an algorithm BinarySearch written in pseudo code. Note however that this algorithm is not exactly adapted to your situation. For example, it has as input an array of entries consisting of keys and elements, and outputs an entry with key equal to a given key k (or null if the element is not in the array). So you first need to simplify this pseudo code so that it works on an array of integers and returns a boolean value true if the integer is in the array and false otherwise. Then you need to code the algorithm in Java. Note. You must implement your own binary search! Use a plain array, not an ArrayList.You are not allowed to use other people's programs or programs from standard libraries.

B. Generics: Implementing a set of elements of arbitrary type by a sorted array

Your second task is to implement sets with elements of an arbitrary type E. Thus you should implement the following generic Java interface:

public interface MySet<E> {
    public boolean member(E element);
}

by a generic class

public class MySortedArray<E> implements MySet<E>

As in part A, you can assume that your input file contains a sorted list, and you should call your program with

java Lab1B <element> <file>

where <file> is a file containing a sorted list of integers separated by spaces, and <element> is an integer. Of course, your generic class must work on other types of input data too!

In order to sort elements of the type E we must have a way to compare them. In Java you achieve this by defining a comparator for E.

Comparators are described in section 8.1.2 in Goodrich and Tamassia. You can follow their example of how to use comparators for implementing a generic class (of priority queues) in section 8.2.2. Note that one of the instance variables is a comparator and that there are two constructors for the class. The first constructor has no argument and uses the "natural ordering" on the type of keys (which is defined for keys which implement the Comparable interface). The other constructor lets you specify your own comparator which you give as an argument to the constructor. See Code Fragments 8.6 and 8.7.

In your case this means that your class MySortedArray<E> would implement one constructor with no arguments

public MySortedArray() {...};

which builds an object with a default comparator and a second constructor

public MySortedArray(Comparator<E> comp) {...};

which builds an object with a given comparator comp.

Reporting the lab

Follow the instructions for reporting lab assignments carefully. In particular you should provide a file Documentation.txt with the following contents:

a short explanation of how your program works including an explanation of all program files (it's usually a good discipline to have one file per class, except in special circumstances);
an explanation of how your program was tested and why you think it has been tested sufficiently;
a discussion of the time complexity of your methods.

C. Optional task

Implement more set operations, for example union and intersection, according to the following extended interface:

public interface MySet<E> {
    public boolean member(E element);
    public void union(MySet<E> set);
    public void intersection(MySet<E> set);
}

These operations can be implemented efficiently by merging sorted arrays. There is a description in Goodrich and Tamassia 11.6, although their code in 11.6.1 can be simplified.

Comment: When we implement the above interface by sorted arrays, we have a difficulty when we take the union of the sorted array and an arbitrary object of MySet, since we don't know yet that the latter is implemented by a sorted array too. The perhaps most natural solution is to assume that it is, and then use a cast to convert it to the type of sorted arrays. However, one could argue that this is not so elegant.

If we however add the requirement that MySet has an iterator which can iterate through the elements of the sorted sets, we can use that for the merge operation and obtain a more abstract (but also more complex) solution. We can express this requirement by stating that MySet extends the interface Iterable, that is, we have the following formulation:

public interface MySet<E> extends Iterable<E> {
    public boolean member(E element);
    public void union(MySet<E> set);
    public void intersection(MySet<E> set);
}