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

[Rémi Forax]

It doesn't work because the complexity of size() can be O(n).
In my opinion, only the checks for emptyness are Ok.

Rémi


On 07/13/2011 05:40 PM, Sebastian Sickelmann wrote:
> 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
>>