Generic method with Comparable does not accept Integer[]

Question

Problem

I have a class called

public class HeapClass <E extends Comparable <E>>

There is a method in there called

public void heapSort(E[] arr)

I have a small main method to test it out and want to call the method with a simple array:

Integer[] arr = {3, 2, 1, 4};
        
HeapClass h = new HeapClass();
        
h.heapSort(arr);

However, for some reason I receive an error:

Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;
    at HeapClass.heapSort(HeapClass.java:11)
    at Test.main(Test.java:9)

---

Full Code

Here is the full code for both files:

public class HeapClass <E extends Comparable <E>>
{
    private int lastposition;
    
    private E[] array;
    
    public void heapSort(E[] arr)
    {
        lastposition = arr.length - 1;
        
        array = (E[]) new Object[arr.length * 2];
        
        for (int i = 0; i < arr.length; i++)
            add(arr[i]);
        
        for (int i = 0; i < arr.length; i++)
            array[arr.length - i - 1] = remove();
        
        arr = array;
    }
    
    public void add (E obj)
    {
        lastposition++;
        array[lastposition] = obj;
        trickleUp(lastposition);
    }
    
    public void swap (int from, int to)
    {
        E temp = array[from];
        array[from] = array[to];
        array[to] = temp;
    }
    
    public void trickleUp(int position)
    {
        if (position == 0)
            return;
        
        int parent = (int) Math.floor((position - 1) / 2);
        
        if (((Comparable <E>) array[position]).compareTo(array[parent]) > 0)
        {
            swap(position, parent);
            trickleUp(parent);
        }
    }
    
    public E remove()
    {
        E temp = array[0];
        swap(0, lastposition--);
        trickleDown(0);
        return temp;
    }
    
    public void trickleDown(int parent)
    {
        int left = 2 * parent + 1;
        int right = 2 * parent + 2;
        
        if (left == lastposition && ((Comparable <E>) array[parent]).compareTo(array[left]) < 0)
        {
            swap(parent, left);
            return;
        }
        if (left == lastposition)
            return;
        if (right == lastposition)
        {
            E max;
            int pos;
            if (((Comparable <E>) array[left]).compareTo(array[right]) < 0)
            {
                max = array[right];
                pos = 1;
            }
            else
            {
                max = array[left];
                pos = 0;
            }
            
            if(((Comparable <E>) array[parent]).compareTo(max) < 0)
            {
                if (pos == 0)
                {
                    swap(parent, left);
                    return;
                }
                else
                {
                    swap(parent, right);
                    return;
                }
            }
            return;
        }
        if (left >= lastposition || right >= lastposition)
            return;
        if (((Comparable <E>) array[left]).compareTo(array[right]) > 0 && ((Comparable <E>) array[parent]).compareTo(array[left]) < 0)
        {
            swap(parent, left);
            trickleDown(left);
        }
        if (((Comparable <E>) array[parent]).compareTo(array[right]) < 0)
        {
            swap(parent, right);
            trickleDown(right);
        }
    }

}

public class Test
{
    public static void main (String[] args)
    {
        Integer[] arr = {3, 2, 1, 4};
        
        HeapClass h = new HeapClass();
        
        h.heapSort(arr);
        
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i]);
        
    }
}

Answer 1

If we take the algorithm you posted and the initial java.lang.ClassCastException error, it is because of a subtle thing:

array = (E[]) new Object[arr.length * 2];

In your class, you asked for E to be an instance of Comparable<E> and declared array to be a E[] and that's the trick: the type of E is bound to Comparable.

So, when you erase type - at least with this online compiler - the type of E, and array, is Comparable.

The JLS 4.6 says:

The erasure of a type variable (§4.4) is the erasure of its leftmost bound.

In your case, the leftmost bound is Comparable and you need to use it to create your array:

array = (E[]) new Comparable[arr.length * 2];

You can view the result here: https://onlinegdb.com/fA_B7xZYD

The resulting NullPointerException is however due to your code not handling the fact that some values may not be set:

• ArrayList use an array of some length and also use a size: you could mimic that.
• You could fill in default non null values... which works only for some type (eg: 0 for Integer, "" for String, ...).
• You could also ignore the null using a Comparator ignoring nulls or wrap your compareTo calls so to avoid nulls.

With a Comparator:

Comparator<E> comparator = Comparator.nullsLast(Comparator.naturalOrder());

And rather than doing:

array[index].compareTo(array[otherIndex])

Do:

comparator.compare(array[index], array[otherIndex])

Or by ignoring nulls, and simplifying the array index access:

int compareIndex(int ia, int ib) {
  E va = array[ia];
  E vb = array[ib];
  if (va == null) {
    if (vb == null) return 0;
    return 1; // a should be after b (nullsLast)
  }
  if (vb == null) return -1; // a should be before a
  return a.compareTo(b);
}

But as I pointed to BadZen, this depends on your assignment: if you are learning, such exercise may help understand the differences between various kind of List (ArrayList, LinkedList, ...) and more generally common structural type found in algorithm.

And given your code, you are doing something that mostly resemble to what a TreeSet provides: a sorted container.

Your code is simply doing it using a sort which I don't know the name in English (bubble sort?) while TreeSet use a B-tree.