In Java a common collection class is the ArrayList, which is a list structure implemented using arrays. Arrays are a natural choice because lists require preserving insertion order of the elements, and can have duplicate elements in the list.

Sets, on the other hand, do not preserve insertion order and do not allow duplicate elements. But what if we want insertion order to be preserved? Enter the elusive ArraySet, a set structure implemented using arrays. An ArraySet preserves insertion order while not allowing duplicate elements to be present in the set.

• create an ArraySet class specifically for storing numbers. Your ArraySet, which will be named ArrayNumSet, must conform to the following specification:
• Must be generic, and must be bounded by the Number type. This means that your class will only support storing numbers.
• Must implement the NumSet interface, which is given to you as NumSet.java. This implies that all abstract methods must be implemented in your ArrayNumSet class. The NumSet class contains comments which further describe what each implemented method should do.
• Some methods in the NumSet interface throw exceptions. Make sure to implement code in your methods to throw the appropriate exceptions if needed. For example, your set does not support adding null elements, and should throw a NullPointerException if such an element is passed to add().
• The constructor of your ArrayNumSet class has one parameter, an int called initialCapacity. This is the length of the array that will hold your elements. When this array becomes full and a new element is added, increase the array to be double the length it was before. This should work if the array fills up multiple times. For example, if the initialCapacity = 2, then when a third element is added, the array should become large enough to hold 4 elements, and if a 5th element is added, then the array should become large enough to hold 8 elements, etc. The capacity() method you will implement returns the current length of the array.

You cannot use ArrayList or any other collection class / method in this program. Only arrays are allowed. Remember, arrays and ArrayLists are different data structures.

ArrayNumSet class must utilize code comments. Javadoc-specific comments are not required.

A main method is not required, as your ArrayNumSet class will be instantiated in the unit tests. A main method is very useful though for testing your code before submitting to zylabs.

Detailed instructions

This program is not really a standalone program, in the sense that you do not need a main() method. Here, we will look at this as a series of tasks. First thing, lets define the class itself. We know the class needs to be called ArrayNumSet, needs to be generic and bounded by Number, and needs to implement the NumSet interface.

• To find the NumSet interface, look at the filename above where the code (in orange) is located. Notice that this is a dropdown box. Click on the name, and you'll find that you can switch between ArrayNumSet.java and NumSet.java.

The NumSet interface is defined for you, and looking at its class declaration (public interface ....) we see exactly how the bound is written. So we will write our class declaration (Hint: it starts with public class) which looks about the same, but we are writing a class instead of an interface. Also we need to implement the NumSet interface. We use the implements keyword for that (remember, we extends a class, but implements interfaces).

Notice that the NumSet interface contains abstract methods. We will be 'implementing' (hence the keyword implements) these methods in our ArrayNumSet class. You can copy/paste these method declarations into your ArrayNumSet class when ready to implement them. For now, lets take a look at the array.

• In Java, arrays do not support generic types. But we need our array to support generics :-(

Here we are out of luck, we need to think of a way around this. Well, what are all the possible types we could instantiate our generic type to? As we are bounded by Number our generic type has to be something that inherits Number. Since every type then will also be of type Number, lets just have our array be of type Number.

When writing object oriented code, we now need to think about how to represent the array. The array should be a field in our class. Should the array be visible directly outside the class? Probably not, as we want our class to control all the additions and removals of elements to/from the array. So maybe something like this:

private Number[] arr;

Notice here that we have not instantiated arr yet. To do that, we need the length of the array, but we do not know that yet, as the length (called capacity) is passed into the constructor as initialCapacity. So we can instantiate (create) the array in the constructor, then assign it to this.arr.

What else should we have as a field? Maybe the size of the array. Here, the size is not the length. The length is our array capacity. The size is the current number of elements in the array. So this size will be initially zero.

Now we can start to implement the methods we need to implement from the NumSet interface. Some of these methods may be a bit tricky. For the E get(int index) method, where index is an array index of the element we want to get, and it returns that element of type E. Because our array stores elements of type Number, we have to manually cast the element we get from type Number to type E before returning it. This produces a compiler warning, which can be ignored. You can also suppress the warning by typing @SuppressWarnings("unchecked") right above your method.

• Java's ArrayList class manually casts elements it returns in the same way. This is due to type erasure.

One last thing to note, you can have more methods than just those in the interface, for example a method to double the capacity of the array. This should probably be a private method. Remember that an array cannot be expanded, so if you need to increase its capacity, you may want to create a new array first that is 2x the capacity of the old one. this.arr can always be assigned a new array.

When implementing boolean remove(E e), you need to shift the array elements after 'removing' the element e. Otherwise you end up with 'holes' in the array, where operations like E get(int index) may fail if the indices in the array are off. Basically what you are doing is moving all elements to the right of the `removed' element, by 1 to the left. For example, suppose you remove the first element. If you are removing the element by replacing it with null, the index of the element still exists (ie, the element at index 1 is still at index 1, when it should have shifted to be index 0 after removal of the element at index 0). So shift the element at index 1 to index 0. Now do the same thing for the element at index 2, shift it to index 1, etc, until all elements are shifted. Remember to adjust your array's size accordingly.

Example input / output

Your program is really a class, ArrayNumSet, which will be instantiated once per test case and various methods called to check how your program is performing. For example, suppose your ArrayNumSet class is instantiated as an object called numSet holding type Integer and with initialCapacity = 2:

NumSet numSet = new ArrayNumSet(2); 

Three integers are added to your set:

numSet.add(5); numSet.add(3); numSet.add(7); 

Then your size() method is called:

numSet.size(); 

It should return 3. Your capacity() method is called:

numSet.capacity(); 

It should return 4. Your get() method is called with an index of 2:

numSet.get(2); 

It should return integer 7. The test cases each have a description of what each one will be testing.