Creating and array of E in Generic SortedSet

Question

As a sample, I am developing a simple MySortedSet<E> in java which implements SortedSet<E> interface. It is backed up with a simple array which is E[] array.

I have several questions regarding that:

This is the class: (I am not writing entire code, instead of related parts)

public class MySortedSet<E> implements SortedSet<E>, Iterator<E> {

 private E[] array;
 private Comparator<? super E> _comparator;
 private int size = 0;
 private int capacity;

 @SuppressWarnings("unchecked")
 public MySortedSet() {
    this.capacity = 10;
    this.array = (E[]) new Object[this.capacity];
    // this.array = Array.newInstance(Class<E> var,int size);
    // We have to get Class<E> from outside caller.
 }
}

Question 1: Can somebody please tell me whether there is a better solution to create a new array in constructor instead of this this.array = (E[]) new Object[this.capacity];

Answer 1

ArrayList<E> stores the elements in a plain Object[], primitive values are autoboxed, and it assigns null to holes left by removed elements.

Classes that implement Comparable<E> must implement int compareTo(E other) which works similarly to compare(E o1, E o2) from Comparator. You could either check your internal comparator for null and fall back on the natural ordering of the objects, or you could define an internal "use the natural ordering" comparator implementation.

Binary search is a method of minimizing the number of comparisons needed to locate an item or the spot where an item should be inserted into a sorted list. Instead of checking each element starting with the first, you start at the midpoint of the list. If the sought item should come before the found element, shift halfway toward the front and repeat; otherwise shift halfway to the end and repeat. Each time you repeat, you use the previous lower/upper bound and the midpoint as the new sublist, halving the number of elements in each step.

Think of trying to guess a number between 1 and 100 where each time you are told whether you guessed too high or too low.

• 50 - too high
• 25 - too low
• 37 - too high
• 31 - too low
• 34 - too low
• 35 - correct!

Answer 2

Either you should keep doing what you're doing here, or you should keep it as an Object[] and cast the values when you're outputting them. (The ArrayList implementation, for example, does the latter.)

Answer 3

You can change your code to remove the unsafe cast:

public MySortedSet(Class<E> clazz) {
    capacity = 10;
    array = Array.newInstance(clazz, capacity);
}

Although it forces the client code to provide a Class<E> object, this is a very common code pattern used to work around this class of problem (where you need a typed Class object in a constructor).