Implementing Sets of Integers in Java

IntSet Interface

In this assessment you are requested to produce a bespoke implementation for sets of integers (that is: integers of type int). A set is a collection of elements that has no particular order, and no concept of multitude of occurrences – two sets are the same if the contain the same elements.

First, here is the specification of how the implementation should be structured The overall type of integer sets should be called IntSet, and this should be an interface.We then distinguish 3 kinds of concrete sets:
• The empty set. We really only need one such thing, but because it behaves differently from any other set it is a class too. So, this gives us the set {}.
• Singleton sets. These are sets containing precisely one number, e.g. {8} or {42}.
• Tree sets. These are sets containing at least two numbers. All tree sets are a tree of two branches which are both integer sets. However, all even numbers go into the left branch, all odd numbers go into the right branch. Insides those branches we forget their last bit, i.e. divide all numbers by 2.

Here is an example: How do we represent the set {2,3,6,8}? It has more than 1 element, so it is a tree set. We put all the even numbers to the left (but halved), so the left branch is the set {1,3,4}. All the odd numbers (well, the 3) go right, but again halved, so the right branch of the tree set is the set

{1}. These two sets in turn are represented using the same principles: {1,3,4} has more than one element, so it is a tree set with

{2} on the left and {0,1} on the right. {2} is a singleton (as is the {1} we had earlier), {0,1} is a tree set with {0} in both branches; and {0} is a singleton. Notice that it can happen in a tree set that one branch is the empty set: for {2,4,64,100} we get an empty right branch, and the left branch is {1,2,32,50}.

All our set objects are (should be) immutable, i.e. you cannot change the content of a set object after construction. So, how do you build up a set? Not entirely unlike you build an arraylist: you initially create an empty set object, and then the ‘add’ method adds elements – but instead of modifying an existing set each call returns the new set as a result. For example, {2,3,6,8} can be built as empty It is sometimes desirable to define classes with so-called smart constructors. This means: we hide the normal constructor(s) from ordinary folk, and supply them instead with a static method that does the constructing and which returns an object of the right type. However, this object will not always be a freshly constructed one, or even use the constructor of this subclass, so this gives us an opportunity to be smart. For certain smart constructors, and that applies here, some data needs to be stored in static variables, so that the smart constructor has access to it.

Criteria for this assessment: is the class design ok? Are the right values represented? Are the sets indeed immutable? Are the requirements for sharing sets implemented? Is the implementation run- time efficient? Generally, you can create more methods than specified if you want to – but no additional fields.
1. Define the 3 classes and the interface as indicated above.
a. The class of empty sets should use a smart constructor which always returns the same object.
b. The class of singleton sets should also use a smart constructor, singleton(n). Note that singletons with small numbers in them are relatively frequent in our representation. So, we require that if 0 ?