Generics and Comparable

[Krep Lock]

I'm not quite "getting" generic usage yet.

I have a custom container class and I'd like to pull out the smallest element from the list. Seems pretty straightforward, but I've been working on it for hours now. Here's my best try so far:

public class MyArrayList<T extends Comparable> extends MyListADT<T>
{
    //  lots of stuff

    public static <T extends Comparable<T> > T smaller(T x, T y)
    {
        if(x.compareTo(y) <= 0)
            return x;
        else
            return y;
    }

    public int min()
    {
        int smallest = 0;

        for(int i = 1; i < length; i++)
        {
            if(list[i] == smaller(list[smallest], list[i]))
                smallest = i;
        }

        return smallest;
    }
}

It compiles with a warning, then fails to execute:

E:\practice>javac -Xlint MyArrayList.java
MyArrayList.java:154: warning: [unchecked] unchecked method invocation: <T>smaller(T,T) in MyArrayList is applied to (T,T)
if(list[i] == smaller(list[smallest], list[i]))
^
1 warning

E:\practice>javac TestProg.java

E:\practice>java TestProg
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;
at MyListADT.<init>(MyListADT.java:39)
at MyArrayList.<init>(MyArrayList.java:12)
at TestProg.main(TestProg.java:11)

I think the problem is in the constructor, line 39 in MyListADT.java:
list = (T[]) new Object[maxSize];

I'm not sure how the syntax would work there for limiting T[] to only those classes that implement Comparable. Otoh, am I going about this right with trying to exclude non-comparables from my container class?

Thanks for any tips on this.

[Janeice DelVecchio]

The problem is you should never be EXTENDING Comparable, you should be IMPLEMENTING Comparable. They're 2 separate actions.

excuse my pseudocode.....

public class Dog extends Animal 
     // a Dog IS A Animal, but no dog can be compared  :wink:
public class Student extends Person implements Comparable 
     // a Student IS A Person and implements the Comparable interface    

Remember you can only extend one class, but you can implement more than one (pretty sure how that works)

Oh, and check this out:
http://www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.html

EDIT: And don't forget you'll need a CompareTo method if you're implementing Comparable. I don't see it in your code sample.

[Janeice DelVecchio]

And if you want to get the smallest item in the list you might find an easier way to sort the List then return the item in the first index.... Check out the Collections class.... there might be something that will do this for you.

[Krep Lock]

Well, I confess I am working on homework, so using the library is not an option for this feature. The test program for the assignment uses a collection of Integers, so I could avoid a lot of trouble by comparing primitive values and get an 'A' but I'd like to figure out how to do it the "right" way and compare actual classes with a compareTo() implementation.

The class declaration reads:

public class MyArrayList<T extends Comparable> extends MyListADT<T> 

So I am not extending (or implementing) Comparable with my collection class, I am just telling it to accept any class, T, that implements Comparable and substitute that for T within the class code. I'm not sure why it's "extends Comparable" though I expect it's for a similar reason that interfaces do not implement each other, but rather extend each other.

So Comparable is to be implemented in any class that this container will hold. I feel pretty close on this but the project is a train wreck all the same.

[Rob Spoor]

Comparable is generic too. The declaration should be

public class MyArrayList<T extends Comparable<? super T>> extends MyListADT<T>

That "? super T" is to ensure that T can also be java.sql.Timestamp which is a Comparable<java.util.Date>.

That should solve the warning, but the ClassCastException will still exist. Can you show us the relevant parts of MyListADT? Especially the related fields and its constructor, since that's where the exception is coming from.

[Campbell Ritchie]

Janeice is correct that you extend classes and implement interfaces, but inside generics brackets <> you write extends regardless.

[Istvan Kovacs]

Krep Lock wrote:

public class MyArrayList<T extends Comparable> extends MyListADT<T>
{
   T[] list = (T[]) new Object[maxSize];
}

Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;
at MyListADT.<init>(MyListADT.java:39)
at MyArrayList.<init>(MyArrayList.java:12)
at TestProg.main(TestProg.java:11)

The problem is that you create an Object[], which cannot be cast to T[]. Object[] is the superclass of T[]. You can cast a reference of the superclass type to the subclass if and only if the reference actually points to an instance of the the subclass, but in your case, the reference points to an actual superclass instance.

However, you cannot directly instantiate T[], the following does not compile (as you have probably found out already):

    T[] list = new T[maxSize];

The only way to get around this is reflection. That's why the toArray method in Collection requires you to pass an array - it reads the actual type of the array using reflection, and if needed, creates another array to hold the contents of the collection.

    public <T> T[] toArray(T[] a) {
        // Estimate size of array; be prepared to see more or fewer elements
        int size = size();
        T[] r = a.length >= size ? a :
                  (T[])java.lang.reflect.Array
                  .newInstance(a.getClass().getComponentType(), size);

	// copy and return, omitted from this listing
    } 

Generics are a difficult beast. You could check how Collections.min is implemented, but its signature will be frightening.

public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)

For a thorough explanation, I recommend Java Generics and Collections by Maurice Naftalin Maurice and Philip Wadler.

[Rob Spoor]

Istvan Kovacs wrote:The problem is that you create an Object[], which cannot be cast to T[].

Actually you can (it's a warning after all, not an error), but only if the rest of the code ensures that every interaction with the array respects the T type. For instance, a very simple stack implementation (no bounds checking):

public class Stack<T>
{
    T[] array;
    int index;

    public Stack(int size)
    {
        array = (T[])new Object[size];
        index = 0;
    }

    public void push(T element)
    {
        array[index++] = element; // only a T is added to the array
    }

    public T pop()
    {
        T element = array[--index];
        array[index] = null; // to prevent a memory leak
        return element;
    }
}

It's essential to hide the array from any outside code because otherwise you can cast the T[] to Object[] and then add anything.

That said, the safest choice for the created array type is what T extends. With my stack that is Object, but in Krep's case using "new Comparable[...]" is probably better. After all, you know that every T is a Comparable. Type erasure also turns every occurrence of T into Comparable so why not use Comparable[]?

[Istvan Kovacs]

Rob Prime wrote:

Istvan Kovacs wrote:The problem is that you create an Object[], which cannot be cast to T[].

Actually you can (it's a warning after all, not an error), but only if the rest of the code ensures that every interaction with the array respects the T type

OK, I worded it wrong. You cannot cast an array of the supertype into an array of the subtype. You can cast an Object[] into an Object[], as T will be erased into Object (or, if T extends Comparable, then into Comparable).

Your code works; inserting the following main method into your code prints the expected result:

    public static void main(String[] args) {
		Stack<String> stack = new Stack<String>(10);
		stack.push("text");
                String popped = stack.pop();
		System.out.println(popped);
	}

However, don't forget that at runtime, erasure will have removed the type. At runtime, you simply have

public class Stack
{
    Object[] array;
    int index;

    public Stack(int size)
    {
        array = new Object[size];
        index = 0;
    }

    public void push(Object element)
    {
        array[index++] = element;
    }

    public Object pop()
    {
        Object element = array[--index];
        array[index] = null; // to prevent a memory leak
        return element;
    }
    
    public static void main(String[] args) {
		Stack stack = new Stack(10);
		stack.push("text");
                String popped = (String) stack.pop();
		System.out.println(popped);
	}
}

So your code does not actually attempt to cast the Object[] array into a String[].

Now add this method to your stack, and modify main:

    public T[] toArray()
    {
        T[] destination = (T[])new Object[array.length];
        System.arraycopy(array, 0, destination, 0, array.length);
        return destination;
    }
    
    public static void main(String[] args) {
		Stack<String> stack = new Stack<String>(10);
                String[] asArray = stack.toArray();
		for (String s:asArray) {
			System.out.println(s);
		}
    }

This results in a ClassCastException, because here you really are casting an Object[] returned by toArray into a String[]. At runtime:

    public Object[] toArray()
    {
        Object[] destination = new Object[array.length];
        System.arraycopy(array, 0, destination, 0, array.length);
        return destination;
    }
    
    public static void main(String[] args) {
		Stack stack = new Stack(10);
                String[] asArray = (String[]) stack.toArray(); // <-- cast fails!
		for (String s:asArray) {
			System.out.println(s);
		}
    }

That said, the safest choice for the created array type is what T extends. With my stack that is Object, but in Krep's case using "new Comparable[...]" is probably better. After all, you know that every T is a Comparable. Type erasure also turns every occurrence of T into Comparable so why not use Comparable[]?

Even if you do that, it will fail if the array is passed to the outside world (you cannot cast Comparable[] into String[]). This fails, too:

public class Stack<T extends Comparable><? super T>>
{
    T[] array;

    public Stack(int size)
    {
        array = (T[])new Comparable[size];
    }

    public T[] toArray()
    {
        T[] destination = (T[])new Comparable[array.length];
        System.arraycopy(array, 0, destination, 0, array.length);
        return destination;
    }
    
    public static void main(String[] args) {
		Stack<String> stack = new Stack<String>(10);
		String[] asArray = stack.toArray();
		for (String s:asArray) {
			System.out.println(s);
		}
    }
}

[Rob Spoor]

Istvan Kovacs wrote:Even if you do that, it will fail if the array is passed to the outside world (you cannot cast Comparable[] into String[]).

Hence my

Rob Prime wrote:It's essential to hide the array from any outside code because otherwise you can cast the T[] to Object[] and then add anything.

[Istvan Kovacs]

Rob Prime wrote:It's essential to hide the array from any outside code because otherwise you can cast the T[] to Object[] and then add anything.

Maybe it's nitpicking, but I don't agree with the underlined reasoning: you cannot "add anything", as the cast will fail. You can even expose the Object[], but you have to claim its true type - Object[].

public Object[] honestToArray() {
	Object[] destination = new Object[array.length];
	System.arraycopy(array, 0, destination, 0, array.length);
	return destination;
}
	
private static void test2() {
	Stack<String> stack = new Stack<String>(10);
	Object[] asArray = stack.honestToArray();
	for (Object o : asArray) {
		String s = (String) o;
		System.out.println(s);
	}
}

Given the original toArray example, you cannot cast the Object[] returned by the method to String[] or Number[] or anything. It's an Object[] and the cast will fail. This has nothing to do with generics. This code fails at runtime (the Object[] reference points to an actual Object[] instance):

Object[] objects = new Object[10];
String[] strings = (String[]) objects;

On the other hand, this runs OK (the Object[] reference points to a subtype, String[]):

Object[] objects = new String[10];
String[] strings = (String[]) objects;

Finally, here we make a mistake after casting (no compile-time warnings). The cast succeeds because Number[], just like Object[], is a supertype of the actual Integer[] value. But when we access the array, type checking kicks in, and adding a Double (which is a subtype of Number) fails.

Object[] objects = new Integer[10];
Number[] numbers = (Number[]) objects;
numbers[0] = Integer.valueOf(0); // OK
numbers[1] = 1; // OK
numbers[2] = Double.valueOf(2.2d); // fails

[Rob Spoor]

Istvan Kovacs wrote:

Rob Prime wrote:It's essential to hide the array from any outside code because otherwise you can cast the T[] to Object[] and then add anything.

Maybe it's nitpicking, but I don't agree with the underlined reasoning: you cannot "add anything", as the cast will fail.

Of course not. You can cast any non-primitive array to Object[]. Since my T[] was actually created as an Object[] you can add any object to it. Your example goes the other way around - casting the Object[] back to T[] outside the class. That's indeed not possible, but I never said it was.

What I meant was this:

Stack<String> stack = new Stack<String>(10);
stack.push("Hello World");
T[] array = stack.array; // called from inside class Stack itself ;)
Object[] objects = array; // allowed since T[] is a sub type of Object[]
objects[0] = Integer.valueOf(42); // will work since array is in fact an Object[]
String s = stack.pop(); // oops! the stack is now broken!

By exposing the array directly to the outside world all guarantees about it are void.

[Krep Lock]

Thanks for all the input, everyone.

Rob Prime wrote:Comparable is generic too. The declaration should be

public class MyArrayList<T extends Comparable<? super T>> extends MyListADT<T>

That "? super T" is to ensure that T can also be java.sql.Timestamp which is a Comparable<java.util.Date>.

That should solve the warning, but the ClassCastException will still exist. Can you show us the relevant parts of MyListADT? Especially the related fields and its constructor, since that's where the exception is coming from.

Here is the relevent portion of MyListADT:

public abstract class MyListADT<T extends Comparable> implements Cloneable
{
    protected int length;
    protected int maxSize;
    protected T[] list;

    public MyListADT(int size)
    {
		maxSize = size;
        length = 0;
        list = (T[]) new Object[maxSize];
    }

    //  more stuff here
}

...and TestProg's attempt to instantiate a list:

public class TestProg
{
    public static void main(String[] args)
    {
        MyArrayList<Integer> list = new MyArrayList<Integer>(25);

        list.insertEnd(23);
        list.insertEnd(7);
        list.insertEnd(47);
        list.insertEnd(30);
        list.insertEnd(102);

        System.out.println();
        System.out.println("Listing:");
        list.print();
        System.out.println();

        System.out.println("Minimum element in list is " + list.min());
    }
}

Generics is new to me and what Istvan says about

        list = (T[]) new Object[maxSize];

makes sense to me, but I'm surprised it compiles at all if that is the problem.

[Rob Spoor]

Rob Prime wrote:That said, the safest choice for the created array type is what T extends. With my stack that is Object, but in Krep's case using "new Comparable[...]" is probably better. After all, you know that every T is a Comparable. Type erasure also turns every occurrence of T into Comparable so why not use Comparable[]?

I so love it when I'm right. I ran your little piece of code through JAD and got this:

// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3) 
// Source File Name:   MyListADT.java


public abstract class MyListADT
    implements Cloneable
{

    public MyListADT(int i)
    {
        maxSize = i;
        length = 0;
        list = (Comparable[])new Object[maxSize];
    }

    protected int length;
    protected int maxSize;
    protected Comparable list[];
}

As you see, type erasure turns T into Comparable. Change the array creating into "new Comparable[maxSize]", possibly "new Comparable<?>[maxSize]" if your IDE gives a raw-type warning, and your code will work.

[Istvan Kovacs]

You have T extends Comparable. When the compiler processes this, a process called erasure is performed: generic type information is 'erased'. If you have a simple type variable, it'll be 'erased' into Object (there's no information that can be kept). With T extends Comparable, the compiler will figure out that whatever type T is, it will be a subtype of Comparable, and will use that as the runtime type.
Thus, at run time we have:

public abstract class MyListADT implements Cloneable  
{  
     protected int length;  
     protected int maxSize;  
     protected Comparable[] list;  
   
     public MyListADT(int size)  
     {  
         maxSize = size;  
         length = 0;  
         list = (Comparable[]) new Object[maxSize];  
     }  
}  

(Comparable[]) new Object[maxSize]; is an illegal cast, as new Object[] results in creating an instance of Object[], not Comparable[]. Replace this with

list = (T[]) new Comparable[maxSize];  

That should make the problem go away.

Edit: removed wrong comment aimed at Rob. :-)

[Krep Lock]

Thanks a lot, people. I got it to work with the regular test program and a custom Rocket object I made for testing. I also realized I was making way too big a production of comparing list objects and tightened that up.