Generics, extending LinkedList<T>, and unchecked casts

Thread view:

Mark Maloof - 27 Dec 2006 23:29 GMT

I need an ordered sequence, so I extended LinkedList<T>. Since I'm
implementing an ordered collection, its elements must implement
Comparable<T>. I came up with the following implementation, which
seems to work, but I cannot figure out how to avoid the unchecked cast
at the end of the insert method:

public class OrderedLinkedList<E> extends LinkedList<E> {

public void insert( Comparable<E> element ) {
int i = 0;
while ( i < size() && element.compareTo( this.get( i ) ) >= 0 ) {
i++;
} // while
// add( i, element ); // compiler error
add( i, (E) element ); // unchecked cast
} // OrderedLinkedList::add

public static void main ( String args[] ) {
OrderedLinkedList<String> oll = new OrderedLinkedList<String>();
oll.insert("cat");
oll.insert("pig");
oll.insert("dog");
oll.insert("hog");
System.out.println( oll );
} // OrderedLinkedList::main

} // OrderedLinkedList class

I'm familiar with Bracha's tutorial and Langer's FAQ, and I've spent a
fair amount of time pounding Google, but I haven't found anything that
deals with this particular issue. (Pointers would be appreciated.) My
intuition tells me that I need to indicate somehow that E extends
Comparable (since LinkedList.add takes an E), but I haven't figured out
how to write something that compiles. Any help would be appreciated.

Mark

Reply to this Message

Daniel Dyer - 27 Dec 2006 23:50 GMT

> I need an ordered sequence, so I extended LinkedList<T>. Since I'm
> implementing an ordered collection, its elements must implement
[quoted text clipped - 23 lines]
>
> } // OrderedLinkedList class

A class that implements Comparable<E> is not itself necessarily assignable
to references of type E, it just means it can be compared with instances
of E.

If you don't need duplicates you could just use a SortedSet. If you do
need to deal with duplicates, you could try this:

public class SortedList<E extends Comparable<E>> extends LinkedList<E>

This means you can only use the list with types that are comparable to
themselves.

The other option you have is to follow the TreeSet way of doing things and
drop the requirement for Comparable and allow a Comparator to be specified.

Also, OrderedList is a bad name, lists are, by definition, ordered.
SortedList might be a better name, at least it will be consistent with
java.util.SortedSet then.

Dan.

Signature

Daniel Dyer
https://watchmaker.dev.java.net - Evolutionary Algorithm Framework for Java

Reply to this Message

jflanglois@hotmail.com - 19 Jan 2007 01:38 GMT

public class SortedList<E extends Comparable<E>> extends LinkedList<E>
is not quite enough. Take the following for example:

public class Foo implements Comparable< Foo > {
public int compareTo( final Foo foo ) { ... }
}

public class Bar extends Foo { ... }

Now, SortedList< Foo > will work, but SortedList< Bar > will not
because it is Comparable< Foo >, and the constraint requires an object
to be comparable to itself only. Therefore, we need a "wider" bound:

public class SortedList< E extends Comparable< ? super E > > { ... }

At this point, both Foo and Bar will work, because the constraint
allows an object to compare itself to itself or any of its
superclasses.

That said, I agree on doing it the TreeSort way for a more general
approach. I don't know of a way to enforce the constraint that E is
either Comparable or that there exists a Comparator for it, though
(TreeSort seems to simply throw on add).

jfl.

> > I need an ordered sequence, so I extended LinkedList<T>. Since I'm
> > implementing an ordered collection, its elements must implement
[quoted text clipped - 48 lines]
> Daniel Dyer
> https://watchmaker.dev.java.net - Evolutionary Algorithm Framework for Java

Reply to this Message

Doug Pardee - 27 Dec 2006 23:58 GMT

> public class OrderedLinkedList<E> extends LinkedList<E> {
>
> public void insert( Comparable<E> element ) {

Why insert a Comparable<E>? Don't you want to insert an E?

> // add( i, element ); // compiler error

I'm not surprised that the compiler is annoyed. Just because something
implements Comparable<E> doesn't mean that it is an E. Your unchecked
cast is begging for a ClassCastException.

> I need an ordered sequence, so I extended LinkedList<T>. Since I'm
> implementing an ordered collection, its elements must implement
[quoted text clipped - 3 lines]
> Comparable (since LinkedList.add takes an E), but I haven't figured out
> how to write something that compiles.

Your intuition was correct. I think that what you wanted was:

public class OrderedLinkedList<E extends Comparable<E>>
extends LinkedList<E> {
public void insert( E element ) {

Reply to this Message

Mark Rafn - 28 Dec 2006 00:26 GMT

>I need an ordered sequence, so I extended LinkedList<T>.

Lists are ordered already. You probably mean you need a sorted list.

>Since I'm implementing an ordered collection, its elements must implement
>Comparable<T>. I came up with the following implementation, which
>seems to work, but I cannot figure out how to avoid the unchecked cast
>at the end of the insert method:

>public class OrderedLinkedList<E> extends LinkedList<E> {
> public void insert( Comparable<E> element ) {
[quoted text clipped - 5 lines]
> add( i, (E) element ); // unchecked cast
> } // OrderedLinkedList::add

O(n) for insertion. as expected for search in a linked list. You might
prefer a tree if this list is expected to get big. But that's not your
question, so nevermind :)

Your compiler error indicates that you can't insert element, because it's not
type E. It's type Comparable<E>. Your unchecked cast warning indicates
that there is no runtime checking of this, as E is erased by the compiler.
So it will let you do something broken like using a Comparable<E> in a method
that expects an E.

The problem is that you think that Comparable<E> implies the object is type E.
Not so. Say I declare MyClass extends Object implements Comparable<Foo> and
pass it to your OrderedLinkedList<Foo>. It would happily insert the
MyClass into your LinkedList. You'll get a ClassCastException somewhere
down the road when something expects a Foo and you give them a MyClass.

Try
public class SortedLinkedList<E extends Comparable<E>> {
public void insert( E element ) { ...
Which specifies that it can only be used with homogeneous things that are
Comparable to themselves.
--
Mark Rafn dagon@dagon.net <http://www.dagon.net/>

Reply to this Message

Mark Maloof - 28 Dec 2006 19:31 GMT

Thanks guys. That worked. I could have sworn that I tried what you
suggested, but apparently not.

Mm.

Reply to this Message

Daniel Pitts - 28 Dec 2006 23:14 GMT

> Thanks guys. That worked. I could have sworn that I tried what you
> suggested, but apparently not.
>
> Mm.

A further suggestion...

Don't extends LinkedList<E>, use an existing implementation of
SortedSet<E> or SortedMap<K, V>

Reply to this Message

Generics, extending LinkedList<T>, and unchecked casts

Free Magazines