The record contains () for the general collection

Question

I am writing a skiplist class in java as an exercise. I wrote a class called SkipListInternal<E> that contains the actual skipist. I also created a SkipListSet<E> wrapper class that implements the SortedSet<E> interface and contains an instance of SkipListInternal<E> .

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

When writing the boolean contains(Object o) method (inherited from Collection<E> via SortedSet<E> ), I noticed that its argument is Object, not E. I intended to do something similar, but this is impossible due to Erase Type:

 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 is impossible to do, how can I do it?

Answer 1

Strictly speaking, such an implementation would be wrong.

The reason for this is that even if the object is not of type E , it can still return true when calling equals() .

Suppose you have 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 will print true :

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

And just to clarify: this behavior is intended , and that is why contains() accepts Object instead of E The same is true for remove() .

Answer 2

Since contains() from java.util.Collection , we must follow the Collection.contains() contract . Since throwing a ClassCastException is an optional behavior, it will correctly return false in your code if it crashes on failure. Therefore, I believe that your implementation complies 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); 

Answer 3

@Joaschim's comment is suitable for standard collections, however, if you want the verified collection to offer you to check what can be added, and not optimized for searching for invalid types (if you do not 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 built-in stream safe ConcurrentSkipListSet and ConcurrentSkipListMap You might be interested to read the source of this.;)

Answer 4

In order for the sorted set to work, the elements of the set must be in order. It can be either "natural" (i.e., Elements implement Comparable ), or "imposed" (using an explicit Comparator for a given construction).

So, firstly, you would rather use the order defined for the given elements (after all, you use SortedSet !) Instead of equals in contains for efficiency. I assume that you are already using ordering in your inner SkipListInternal<E> - how do you support Sorted in a SortedSet for equals only?

The fact that contains actually declared as contains(Object key) in the interface is really unsuccessful. I would do what the TreeMap implementation does (which is the base 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; 

ie, cast, assuming the client application using your collection is behaving reasonably.