Java Generics Causing Class Cast Error

Question

So I'm coding up a generic adjacency list and my code has no compile errors, but when I run my tests I get the same runtime error across the board:

java.lang.ClassCastException: [[Ljava.lang.Object; cannot be cast to [[Lds.Graph.Edge;
    at ds.TheAdjacencyMatrix.AdjacencyMatrix.<init>(AdjacencyMatrix.java:86)
    at ds.TheAdjacencyMatrix.AdjacencyMatrix.<init>(AdjacencyMatrix.java:63)
    at ds.TheAdjacencyMatrix.AdjacencyMatrix.<init>(AdjacencyMatrix.java:73)
    at ds.Graph.Test.TheAdjacencyMatrixTest.testAddVertex(TheAdjacencyMatrixTest.java:33)

The error is in the constructor on the line where I cast the 2d object array to E[][] type

The relevant code for the adjacency matrix is::

public class AdjacencyMatrix<T, E extends Edge> 
        implements AdjacencyMatrixInterface<T, E>, Graph<T, E> {

    //~Constants----------------------------------------------
    private static final int DEFAULT_SIZE = 10;

    //~Data Fields--------------------------------------------
    /**
     * Int matrix that holds edge weights in weighted graphs. 
     * A 1 in a directed graph indicates an edge, a 0 indicates no edge.
     */
    private E[][] matrix;

    /**
     * Array of elements contained in the graph.
     * Elements correspond to the same indices as they do in the adjacency matrix of edges.
     * 
     * i.e. matrix[4][5] is an edge from 4 to 5, 
     *  elements[4] is the element at 4, elements[5] is the element at 5
     */
    private T[] elements;

    /**
     * The maximum number of vertices in the adjacency matrix.
     */
    private int size;

    /**
     * The current number of vertices in the graph.
     */
    private int numVertices;

    /**
     * Indicates whether the graph is directed or not. True if directed, false otherwise.
     */
    private boolean directed;

    //~Constructors--------------------------------------------
    /**
     * Initializes the adjacency matrix to a size of 10.
     * Which means there are 10 vertices in the graph.
     */
    public AdjacencyMatrix() {

        this(DEFAULT_SIZE);
    }

    /**
     * Initializes the adjacency matrix to a size of 10. There will be 10 vertices in the graph.
     * 
     * @param directed true if the graph is to be a directed graph, false otherwise.
     */
    public AdjacencyMatrix(boolean directed) {

        this();
        this.directed = directed;
    }

    /**
     * Initializes the adjacency matrix to a size of size.
     * There will be a maximum size of *size* vertices in the graph
     * 
     * @param size the size of the adjacency matrix.
     */
    @SuppressWarnings("unchecked")
    public AdjacencyMatrix(int size) {

        matrix = (E[][]) new Object[size][size];
        elements = (T[]) new Object[size];

        this.size = size;
        numVertices = 0;
        directed = false;
    }

And the Edge class is an abstract class whose code is here:

package ds.Graph;

/**
 * An abstract Edge class which has methods
 * getWeight()
 * and
 * setWeight(int weight).
 * Used for a Graph data structure to abstract
 * out the edges.
 * 
 *
 *
 */
public abstract class Edge implements Comparable<Edge> {

    /**
     * Sets the weight of the edge to the passed in weight.
     * 
     * @param weight the weight of the edge.
     */
    public abstract void setWeight(int weight);

    /**
     * Gets the weight of the edge.
     * 
     * @return the edge weight.
     */
    public abstract int getWeight();
}

EDIT::

So this is the line of code that sets of the error at runtime. IntEdge is just an object inheriting from Edge that holds an integer.

AdjacencyMatrixInterface<String, IntEdge> matrix = new AdjacencyMatrix<String, IntEdge>(false);

Answer 1

The reason is because even though E is a subclass of Object, E[] is not a subclass of Object[]. Arrays have a flat class hierarchy and thus can't be cast into each other.

[Edit]

I was wrong (thx for the comment). Actually there is a type hierarchy for arrays (see http://etutorials.org/cert/java+certification/Chapter+6.+Object-oriented+Programming/6.5+Completing+the+Type+Hierarchy/ ). As correctly pointed out, you are thus trying to cast a supertype instance to a subtype, which won't work for any other Java Objects as well.

Answer 2

Simple change that line to

matrix = (E[][]) new Edge[size][size];

E is erased to its upper bound inside the class. E's upper bound is Edge in this case. So it will try to cast to Edge[][].

Also, you have to make sure that matrix and elements is not exposed to the outside as E[][] and T[] respectively, since they are not really of those types. But as long as you only use them within the class, there is no problem.

Answer 3

The issue is that Object[][] is not an instance of Edge[][]. You can't cast your objects like that.

new Object[][] {} instanceof Edge[][] // => false

Its the other way around Object[][] is in fact superclass of Edge[][]

new Edge[][] {} instanceof Object[][] // => true

Also, According to Java Language Specification

The direct superclass of an array type is Object. Every array type implements the interfaces Cloneable and java.io.Serializable.

Edit:

Also, as Rahul Bobhate pointed out, its better to use Java Collections Framework since it was designed to utilize generics. All array-based workarounds are are pretty ugly.

Answer 4

You cannot cast an array of Object to an E. Although it will compile, it will cause ClassCastException at runtime. You can cast only compatible reference types. Since an array of E and array of Object are not related in any way, JVM won't be able to cast the array of Object to array of E.

You can use List instead of array. You could define matrix as a List of List as follows:

private List<List<E>> matrix;
private List<T> elements;

You can then initialize matrix in the constructor easily:

public AdjacencyMatrix(int size) {

    matrix = new ArrayList<List<E>>(size);
    for(int i=0; i<size; i++)
    {
        t.add(new ArrayList<E>());
    }

    elements = new ArrayList<T>(size);

    this.size = size;
    numVertices = 0;
    directed = false;
}

You can then access the elements inside the list as follows:

E e = matrix.get(0).get(1);

This will fetch you the 2nd element in the 1st list.

Answer 5

This is not right, you must be getting unchecked cast warning:

matrix = (E[][]) new Object[size][size];
        elements = (T[]) new Object[size];

You need to explicitly pass array instances since generic information is erased at runtime (which means at runtime code under execution would be matrix = new Object[][])

You can have constructor like:

public class AdjacencyMatrix<T, E extends Edge> 
        implements AdjacencyMatrixInterface<T, E>, Graph<T, E> {
E[][] matrix;
T[] elements;
public AdjacencyMatrix(int size, E[][] matrix, T[] elements) {
        this.matrix = matrix;
        this.elements = elements;
   }
}