AbstractCollection.removeAll(Collection) and AbstractSet.removeAll(Collection)

[Jeff Hain]

Hello.
 
I have some remarks about the methods named in the subject (JDK 6u26, JDK 
7b147).
 
 
1) AbstractCollection.removeAll(Collection)
   This method could return immediately if the specified collection is empty,
not to iterate uselessly over all "this", or if "this" is empty, not to create 
an
iterator for nothing.public boolean removeAll(Collection<?> c) {
   boolean modified = false;
   if (size() > c.size()) {
      for (Iterator<?> i = c.iterator(); i.hasNext(); )
         modified |= remove(i.next());
   } else {
      for (Iterator<?> i = iterator(); i.hasNext(); ) {
         if (c.contains(i.next())) {
            i.remove();
            modified = true;
         }
      }
   }
   return modified;
}
 
# Alternative implementation (not tested):public boolean removeAll(Collection<?> 
c) {
   // Quick check on emptinesses, to make later treatments simpler.
   if (isEmpty() || c.isEmpty()) {
      return false;
   }
   boolean modified = false;
   final int n1 = size();
   final int n2 = c.size();
   // If the "c" is not a set, we are pessimistic about its "contains" method 
complexity.
   final int cContainsAssumedComplexity = (c instanceof Set<?>) ? 1 : n2;
   // If we iterate over "this", assumed complexity is O(n2).
   // If we iterate over "c", assumed complexity is O(n1 * 
cContainsAssumedComplexity).
   // Cast to long to avoid overflow.
   if (n2 < n1 * (long)cContainsAssumedComplexity) {
      for (Iterator<?> i = c.iterator(); i.hasNext(); ) {
         if (remove(i.next())) {
            modified = true;
            if (isEmpty()) {
               break;
            }
         }
      }
   } else {
      for (Iterator<?> i = iterator(); i.hasNext(); ) {
         if (c.contains(i.next())) {
            i.remove();
            modified = true;
         }
      }
   }
   return modified;
}
   I also thought about returning as soon as as many elements as the specified 
collection
contains have been removed, but it would not behave properly with collections 
containing
more than Integer.MAX_VALUE elements, or with some overriden equals methods etc.
 
 
2) AbstractSet.removeAll(Collection)
   Let n1 be the size of "this", and n2 the size of the specified collection.
   This method is in O(n1*n2) if the specified collection has a contains(Object) 
method in O(n2)
(as an ArrayList does), and n1 <= n2.
   I think a better implementation could be done by taking care of the "setness" 
of the specified collection,
and taking care of collections sizes differently.
   Also:
- when iterating on the specified collection, the method could return as soon 
as "this" is empty,
  not to continue useless iterations.
- when iterating on "this", the method could return if the specified collection 
is empty,
  not to iterate over all "this" uselessly.
 
# Current implementation:


Regards,

Jeff