Writing contains() for a generic collection

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 ot开发者_运维知识库herwise 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?

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.

Since the contains() is from java.util.Collection, We are supposed to follow the Collection.contains() contract. Because throwing ClassCastException is an optional behavior, it's correct to return false in your code when cast fails. So I think your implementation comply with the contract.

        /**
         * Returns true if this collection contains the specified element.
         * More formally, returns true if and only if this collection
         * contains at least one element e such that
         * (o==null ? e==null : o.equals(e)).
         *
         * @param o element whose presence in this collection is to be tested
         * @return <tt>true</tt> if this collection contains the specified
         *         element
         * @throws ClassCastException if the type of the specified element
         *         is incompatible with this collection (optional)
         * @throws NullPointerException if the specified element is null and this
         *         collection does not permit null elements (optional)
         */
         boolean contains(Object o);

@Joaschim comment is correct for standard collections, however if you want a checked collection I suggest you check what can be added, and not optimise for the lookups of invalid types (unless you want to throw an Exception) You can do something like.

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

   ...
   public boolean add(Object o) {
       if(!eClass.isInstanceOf(o))
    // OR
       if(eClass != o.getClass())
           throw new IllegalArgumentException("Type "+o.getClass()+" is not a "+eClass);
       skiplist.add(o);
   }

   public boolean contains(Object o){
       // if (!(o instanceof E)) return false; // don't need to optmise for this.
       return skiplist.find((E) o) != null;
   }

   ...

}

BTW: Java has a builtin thread safe ConcurrentSkipListSet and ConcurrentSkipListMap You might find it interesting to read the source for this. ;)

In order for a sorted set implementation to work, the elements of the set have to have an ordering. This may either be "natural" (i.e., the elements implement Comparable) or "imposed" (by using an explicit Comparator during set construction).

So, the first thing is, that you'd probably rather use the ordering defined for the set elements (after all, you are implementing a SortedSet!) instead of equals in contains for efficiency. I assume, that you are already using an ordering in your internal SkipListInternal<E> -- how'd you maintain the Sorted in SortedSet given only equals?

The fact that contains is actually declared as contains(Object key) in the interface is really unfortunate. I'd do, what the TreeMap implementation does (which is the underlying container for TreeSet, the standard SortedSet from the collections framework):

if (comparator != null)
    return getEntryUsingComparator(key);
if (key == null)
    throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;

i.e., cast, assuming the client application using your collection behaves sanely.