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
