Integer Set in Java

In this assignment, you will produce two implementations of an integer set with the same public interface, as given by the IntSet.java interface type. The set method adds an element to the set. The clear method removes an element from the set. The test method tests whether an element is in the set. The min and max methods give the smallest and largest element of the set. Thus, one way of looking at all elements of the set is:

 

for (int i = set.min(); i <= set.max(); i++)

   if (set.test(i))

      i is an element of set

 

The ArraySet class stores its elements in an array starting out with an array of length 10, and doubling the length whenever the array runs out of space. Append elements in the order in which they are set. When clearing an element, replace it with the last element in the array. Don't shrink the array.

 

The BitSet class stores a sequence of bits to indicate whether a particular element is present or not. Pack 32 bits to an int. Start out with an array of length 10, which represents a set of up to 320 elements starting from the initially set element. If an element is set that is outside the representable range, allocate a larger array that is at least twice the length of the existing array. For example, consider the statements:

 

IntSet set = new BitSet();

set.set(100);

 

Now set.elements has length 10 and can represent numbers 100 ... 419.

 

set.set(500);

Now set.elements has length 20 and can represent numbers 100...739.

 

set.set(4000);

Now set.elements has length 122 and can represent numbers 100...4003.

 

If the array needs to grow to hold values that are less than the current start position, then also grow to at least twice the current length. For example, consider

 

IntSet set = new BitSet();

set.set(100);

set.set(-1);

Now set.elements has size 20 and can represent elements -220...419.

 

After

 

set.set(-1000);

set.elements has size 45 and can represent elements -1020...419.

 

The clear operation simply clears a bit without shrinking the array.

 

Add test cases of your choice to the JUnit test class SetTest.java.

Need a custom answer at your budget?

This assignment has been answered 4 times in private sessions.

© 2020 Codify Tutor. All rights reserved