• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Generics and Comparable

 
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:



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.
 
Bartender
Posts: 1849
15
Eclipse IDE Spring VI Editor Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The problem is you should never be EXTENDING Comparable, you should be IMPLEMENTING Comparable. They're 2 separate actions.

excuse my pseudocode.....


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
Bartender
Posts: 1849
15
Eclipse IDE Spring VI Editor Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:

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.
 
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Comparable is generic too. The declaration should be 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.
 
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Janeice is correct that you extend classes and implement interfaces, but inside generics brackets <> you write extends regardless.
 
Ranch Hand
Posts: 135
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Krep Lock wrote:




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):


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.



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


For a thorough explanation, I recommend Java Generics and Collections by Maurice Naftalin Maurice and Philip Wadler.
 
Rob Spoor
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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):
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
Ranch Hand
Posts: 135
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:


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


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:


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



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:

 
Rob Spoor
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 135
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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[].




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):


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


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.

 
Rob Spoor
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:
By exposing the array directly to the outside world all guarantees about it are void.
 
Krep Lock
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for all the input, everyone.

Rob Prime wrote:Comparable is generic too. The declaration should be 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:



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



Generics is new to me and what Istvan says about

makes sense to me, but I'm surprised it compiles at all if that is the problem.
 
Rob Spoor
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:
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
Ranch Hand
Posts: 135
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:


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


That should make the problem go away.

Edit: removed wrong comment aimed at Rob. :-)
 
Krep Lock
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic