Lab 5 - Binary Search Based Set


Introduction

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.

Example:

$ 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


Problem Solving Session

You will work in groups for this portion of the lab.

  1. Write pseudo-code for the binary-search algorithm.
  2. Write pseudo-code for the contains method, which given an object determines whether or not that object is in the set.
  3. Write pseudo-code for the add method, 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.
  4. Write pseudo-code for the addAll method, 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.


Implementation

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 Integer.

Java Documentation

You can find the JavaDoc for the Set interface here. You will find it quite useful. Here is the JavaDoc for AbstractSet.

The following code skeleton is provided for you to complete the implementation.

Description

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.

Commenting

Be sure to fully comment your implementation. This includes:


Submission

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.)


Grading

The grade breakdown for this lab is as follows: