Writing contains() for a generic collection

Question

I'm writing a skiplist class in java as an excercise. I've written a class called SkipListInternal<E> which contains the actual skiplist. I've also made a wrapper class called SkipListSet<E> which implement the SortedSet<E> interface and contains an instance of SkipListInternal<E>.

Among other things, SkipListInternal<E> contains a method E find(E e) which returns the element equal to e if it is present, and otherwise returns null.

When writing the boolean contains(Object o) (inherited from Collection<E> via SortedSet<E>) method I noticed that its argument is an Object and not an E. I intended to do something like this, but is not possible due to type erasure:

public class SkipListSet<E> implements SortedSet<E>{
   private SkipListInternal<E> skiplist;

   ...

   public boolean contains(Object o){
       if (!(o instanceof E)) return false;
       return skiplist.find((E) o) != null;
   }

   ...

}

Since it can't be done this way, how should I do it?

Answer 1

Strictly speaking such an implementation would be wrong.

The reason for this is that even if an object is not of type E, it could still return true on an equals() call.

Assume for a second, that you've got a class like this:

public class FakeString {
  private final String value;

  public FakeString(String value) {
    if (value == null) {
      throw new IllegalArgumentException();
    }
    this.value = value;
  }

  public int hashCode() {
    return value.hashCode();
  }

  public boolean equals(Object o) {
    return value.equals(o);
  }
}

Then this code would print true:

List<String> strings = Arrays.asList("foo", "bar", "baz");
System.out.println(strings.contains(new FakeString("bar")));

And just to clarify: this behaviour is intended and is the reason why contains() takes an Object instead of E. The same is true for remove(), by the way.