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

[Sebastian Sickelmann]

Jeff Hain wrote:
> 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;
> }

look good to me. 

>    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.

The overriden equals method should be no problem if the Implementation is an set. So it should be possible to exit in this case in the AbstractSet Implementation, isn't it?

>  
>  
> 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
> 

-- 
NEU: FreePhone - kostenlos mobil telefonieren!			
Jetzt informieren: http://www.gmx.net/de/go/freephone