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

public BinarySearchSet(Comparator super E> 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.