Re: Generics, extending LinkedList<T>, and unchecked casts
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.
Daniel Dyer wrote:
On Wed, 27 Dec 2006 23:29:29 -0000, Mark Maloof <maloof@cs.georgetown.edu>
wrote:
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
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.
--
Daniel Dyer
https://watchmaker.dev.java.net - Evolutionary Algorithm Framework for Java