You want a set data structure, but you have decided that the
HashSet and the
TreeSet are not suitable for
your purposes, and so you have decided to write your own
implementation. The collection is represented as an
ArrayList and fast access is assured by keeping the
elements sorted and using binary-search.
You will have to implement most of the methods required by the
Set interface. Fortunately, inheriting from
AbstractSet will save you writing a couple of methods.
Further you have decided to include test scaffolding as part of the
main method, since otherwise a set doesn't do anything.
$ java BinSet constructor 1 success add 1 success contains 1 success contains 2 success contains 3 success contains 4 success size 1 success clear/size success clear/isEmpty success addAll 1 success containsAll 1 success containsAll 2 success remove 1 success iterator 1 success iterator 3 success retainAll 1 success toArray(array) 1 success
You will work in groups for this portion of the lab.
containsmethod, which given an object determines whether or not that object is in the set.
addmethod, which, given an element, either puts the element in the set and returns true, or determines that the element is already there and returns false.
addAllmethod, which, given a collection of elements, modifies the set if necessary to add any new elements. If the set was modified return true, but if not return false.
You will complete this portion of the lab on your own.
You will implement a set based on binary search. To get you started,
skeleton code is provided. However, in addition to the stubs
provided, you must also write one more test scaffolding function using
some type other than
You can find the JavaDoc for the
Set interface here.
You will find it quite useful. Here is the JavaDoc
The following code skeleton is provided for you to complete the implementation.
There are a number of methods to be written. Take care that the
contains method is O(log(n)). Otherwise you may
implement the other methods as you see fit. Make sure to write
another test scaffolding method.
Be sure to fully comment your implementation. This includes:
You should zip all your java files together, both the ones that you wrote as well as the ones that we provided (you should not modify the provided classes, however). Submit the zip to the dropbox on MyCourses. (See MyCourses for deadlines for on-time and late submissions. The syllabus describes the penalty for submitting to a late drop box. No submissions are accepted after the late deadline passes.)
The grade breakdown for this lab is as follows: