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

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

- Write pseudo-code for the binary-search algorithm.
- Write pseudo-code for the
`contains`

method, which given an object determines whether or not that object is in the set. - 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. - 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.

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`

.

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.

`BinSet`class`BinSet.java`java code

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:

- A file comment block that includes the correct CVS tags (
`$Id$`and`$Log$`). - A class JavaDoc comment block that includes a description and an
`@author`tag (with full name). - A JavaDoc comment block for every field and method (whether public or private) that includes a description and (for methods)
`@param`and`@return`tags. - For any non-trivial method, sufficient comments to explain its implementation.

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:

- Lab attendance and participation: 5%
- Problem Solving Session: 15%
- Implementation: 80%
*Note!*: Zero credit for submissions that do not compile!- Functional Correctness: 70%
- Default constructor: 4%
- Constructor that takes a collection: 4%
- binarySearch: 5%
- add: 4%
- addAll: 4%
- clear: 4%
- contains: 4%
- containsAll: 4%
- isEmpty: 4%
- iterator: 4%
- remove: 4%
- retainAll: 4%
- size: 4%
- toArray with no arguments: 4%
- toArray with array argument: 4%
- toString: 4%
- Additional test method: 5%

- Code Style: 5% (see style guide and example)
- Documentation: 5%