Review for CR 6728865 : Improved heuristics for Collections.disjoint() [updated]

[Mike Duigou]

Here's another try that tries to use similar wording to Collection:
     * 
     * <p>Care must also be exercised when using collections that have 
     * restrictions on the elements that they may contain. Collection
     * implementations are allowed to throw exceptions for any operation
     * involving elements they deem ineligible. For absolute safety the 
     * specified collections should contain only elements which are 
     * eligible elements for both collections. 

And for the throws:

     * @throws NullPointerException if either collection is {@code null}. 
     * @throws NullPointerException if one collection contains a {@code null}
     * element and {@code null} is not an eligible element for the other collection.
     * (optional)
     * @throws ClassCastException if one collection contains an element that is
     * of a type which is ineligible for the other collection. (optional)


On Dec 22 2010, at 05:45 , Chris Hegarty wrote:

> My concern with this revised wording is that you are now specifying that the implementation must use contains() ( and not be implemented using a different strategy ). I guess an alternative implementation is unlikely, but this does appear overly restricting.

At least four alternate (though impractical) implementations are possible which don't directly use contains() :

Collection<?> clone = c1.clone();
for(Object e : c2) {
  if(clone.remove(e)) { 
    return false;
  }
}

and

Collection<?> clone = c1.clone();
clone.retainAll(c2);
return !clone.isEmpty();

and

Collection<?> clone = c1.clone();
clone.removeAll(c2);
return clone.size() == c1.size();

and

for(Object e : c1) {
  if(null == e) {
    for(Object o : c2) {
      if(null == o) {
        return false;
      }
    }
  } else {
    for(Object o : c2) {
      if((e == o) || ((e.hashCode() == o.hashCode()) && e.equals(o))) {
        return false;
      }
    }
  }
}
return true;

All but the last use optional operations. The last actually avoids the problem with ineligible elements altogether at a very likely performance cost. I won't suggest we switch to this implementation. ;-) It could also be improved by calculating the hashCodes of all c2 elements, and sorting them into an array to be binary searched for each e. For largish non-Set collections this would actually be faster than the current contains() based impl.

> 
> I wonder if its really necessary to add text to the NPE. A cautionary note may be sufficient. We could also throw ClassCastException, but there is no mention of it in the spec.
> 
> Sorry for being a pain about this, I'm just concerned with adding overly restricting spec.

I think your concern is correct. Specifying contains() is too restrictive.

> Have we thought about catching/swallowing these exceptions?

I'm uncomfortable turning the NPE into a "false" because there may be unknown circumstances such as concurrent modification which could cause the same effect.

Mike