Generics, extending LinkedList<T>, and unchecked casts

Discussion in 'Java' started by Mark Maloof, Dec 27, 2006.

  1. Mark Maloof

    Mark Maloof Guest

    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
     
    Mark Maloof, Dec 27, 2006
    #1
    1. Advertising

  2. Mark Maloof

    Daniel Dyer Guest

    On Wed, 27 Dec 2006 23:29:29 -0000, Mark Maloof <>
    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
     
    Daniel Dyer, Dec 27, 2006
    #2
    1. Advertising

  3. Mark Maloof

    Doug Pardee Guest

    Mark Maloof wrote:
    > 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
    > Comparable<T>.
    > [snip]
    > 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.


    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 ) {
     
    Doug Pardee, Dec 27, 2006
    #3
  4. Mark Maloof

    Mark Rafn Guest

    Mark Maloof <> wrote:
    >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 ) {
    > 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


    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 <http://www.dagon.net/>
     
    Mark Rafn, Dec 28, 2006
    #4
  5. Mark Maloof

    Mark Maloof Guest

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

    Mm.
     
    Mark Maloof, Dec 28, 2006
    #5
  6. Mark Maloof

    Daniel Pitts Guest

    Mark Maloof wrote:
    > 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>
     
    Daniel Pitts, Dec 28, 2006
    #6
  7. Mark Maloof

    Guest

    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 <>
    > 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
     
    , Jan 19, 2007
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    8,968
  2. Eric I.
    Replies:
    6
    Views:
    705
    Eric I.
    Aug 15, 2008
  3. johnmmcparland

    unchecked casts and clone

    johnmmcparland, Dec 10, 2008, in forum: Java
    Replies:
    5
    Views:
    3,882
    Mark Space
    Dec 10, 2008
  4. RVic
    Replies:
    19
    Views:
    1,451
  5. Mayeul
    Replies:
    2
    Views:
    3,493
Loading...

Share This Page