The Problem

We have been asked to construct a program that handles lists of strings, integers, library books, and anything else our client can think of. The client requires all of the usual operations for a list, such as the ability to add items, remove items, search for items, and get items (in sorted order). Because the client expects that searching for items will be the most common operation for these lists, we must make our search routine as efficient as possible. Further, we have been informed that the lists may not contain duplicates (ie. it is a set).

At first, we were a little concerned about taking on such a job, since we have yet to learn any algorithms for sorting lists (much less, super efficient sorting algorithms). However, we know that all such lists will begin as empty lists which are already in sorted order, and we can simply insert items in the correct order to ensure that the lists remain sorted.

Requirements

Create a class BinarySearchSet that implements the SortedSet interface. (Do not implement Java's SortedSet, which requires more methods.) Implement every method in the interface according to the functionality described in the comments. Also, provide the following two constructors:

public BinarySearchSet()

If this constructor is used to create the sorted set, it is assumed that the elements are ordered using their natural ordering (i.e., E implements Comparable).

public BinarySearchSet(Comparator comparator)

If this constructor is used to create the sorted set, it is assumed that the elements are ordered using the provided comparator.

Note that E as a generic type placeholder is the same as the T and Type placeholders we have used in lecture. E is often used in the Java API as the generic type for elements of a collection.

Finally, adhere to the following rules for your solution:

Add all new classes to a package called assignment03. Add the SortedSet interface to this package as well.

The data in BinarySearchSet must be backed by a basic array (do not use a Java List). Further more, it is not acceptable for the array to run out of space for new items, nor is it acceptable to create a gigantic array. Start with a modestly-size array and increase the capacity as needed.

The contains and add methods must take advantage of the list being sorted and implement a binary search to determine if an item is in the array and to find the correct position in which to insert a new item, respectively. You may not invoke Java's Arrays.binarySearch routine.

Do not invoke Java's Arrays.sort routine. (Recall that sorting the list is not necessary.)

You are encouraged (but not required) to use lambda expressions when implementing any Comparators. See thelambda expression video (Links to an external site.)Links to an external site.for how to do this.

Unlike previous assignments you are not given any tests as a starting point. You must create your own JUnit tests and submit them with your program.

Finishing up

When preliminary coding is complete and your program compiles without error or warning, test the program thoroughly and systematically.

Your code should be well-commented (Javadoc comments are required) and formatted such that it is clear and easy to read. Be sure to put your name in the header comment of each file -- please make sure your name match what we have in Canvas. You must have at least: comments for every method, describing what the method does, what the arguments are (and what they mean), and what the return value is, as well as any special cases that the method handles or can run in to. You should also have comments on any line or block of code that is not self-explanatory.

Zip your .java source code files (no .class, .java only) and upload the zip file.

Complete your analysis doc (specs below).

GIVEN SORTEDSET.FILE

package assignment03;

import java.util.Collection;

import java.util.Comparator;

import java.util.NoSuchElementException;

/**

* A set that provides a total ordering on its elements. The elements are

* ordered using their natural ordering, or by a Comparator provided at sorted

* set creation time. Thus, all elements inserted into a sorted set must

* implement the Comparable interface or be accepted by the specified

* Comparator. The set's iterator will traverse the set in ascending element

* order.

*

* @author Erin Parker

*

* @param

* -- the type of elements maintained by this set

*/

public interface SortedSet {

/**

* @return The comparator used to order the elements in this set, or null if

* this set uses the natural ordering of its elements (i.e., uses

* Comparable).

*/

public Comparator super E> getComparator();

/**

* @return the first (lowest, smallest) element currently in this set

* @throws NoSuchElementException

* if the set is empty

*/

public E first() throws NoSuchElementException;

/**

* @return the last (highest, largest) element currently in this set

* @throws NoSuchElementException

* if the set is empty

*/

public E last() throws NoSuchElementException;

/**

* Adds the specified element to this set if it is not already present and

* not set to null.

*

* @param o

* -- element to be added to this set

* @return true if this set did not already contain the specified element

*/

public boolean add(E element);

/**

* Adds all of the elements in the specified collection to this set if they

* are not already present and not set to null.

*

* @param c

* -- collection containing elements to be added to this set

* @return true if this set changed as a result of the call

*/

public boolean addAll(Collection extends E> elements);

/**

* Removes all of the elements from this set. The set will be empty after

* this call returns.

*/

public void clear();

/**

* @param o

* -- element whose presence in this set is to be tested

* @return true if this set contains the specified element

*/

public boolean contains(Object element);

/**

* @param c

* -- collection to be checked for containment in this set

* @return true if this set contains all of the elements of the specified

* collection

*/

public boolean containsAll(Collection> elements);

/**

* @return true if this set contains no elements

*/

public boolean isEmpty();

/**

* Removes the specified element from this set if it is present.

*

* @param o

* -- object to be removed from this set, if present

* @return true if this set contained the specified element

*/

public boolean remove(Object element);

/**

* Removes from this set all of its elements that are contained in the

* specified collection.

*

* @param c

* -- collection containing elements to be removed from this set

* @return true if this set changed as a result of the call

*/

public boolean removeAll(Collection> elements);

/**

* @return the number of elements in this set

*/

public int size();

/**

* @return an array containing all of the elements in this set, in sorted

* (ascending) order.

*/

public Object[] toArray();