The purpose of this assignment is to practice Java-programming with
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 the course book. However, the implementation is actually not quite correct, and it returns an index rather than a boolean.
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.
You can use the Scanner class to read the file. You are allowed to use an ArrayList in the main program. Since the interface only contains a member method, there is no requirement to implement an add method. A simpler solution is to just pass the array to the constructor. However, you are allowed to implement an add method, in which case you should use a dynamic 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 extends Comparable<? super E>> implements MySet<E>
(Note that the Lab1B class, containing main, should not be generic.)
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. One way of achieving this in Java is to compare the elements using their "natural ordering", i.e. the one provided by the Comparable interface. This is the method you should use in this assignment. The somewhat cryptic declaration <E extends Comparable<? super E>> is explained in the course book (section 1.5.5).
Follow the instructions for reporting lab assignments carefully. Include a discussion of the time complexity of your methods.
Submissions which do not pass certain tests may be summarily rejected.
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.
Comment: When we implement the above interface using sorted arrays, we encounter a difficulty when we take the union of the sorted array and an arbitrary object of MySet, since we don't know that the latter is also implemented as a sorted array. A natural solution is to assume that it is, and use a cast to convert it to the type of sorted arrays. However, one could argue that this is not very elegant.
However, if we add the requirement that MySet has an iterator which can iterate through the elements of the sorted sets, then 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:
public interface MySet<E> extends Iterable<E> { public boolean member(E element); public void union(MySet<E> set); public void intersection(MySet<E> set); }