Sorry, all paragraphs were in disorder ; looks like my mail app is not wysiwyg
at all.
I hope this time content doesn't get messed up, else I'll just give up.
----- Message transféré ----
De : Jeff Hain <jeffh...@rocketmail.com>
À : core-libs-dev@openjdk.java.net
Envoyé le : Mer 13 juillet 2011, 1h 13min 51s
Objet : AbstractCollection.removeAll(Collection) and
AbstractSet.removeAll(Collection)
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.
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:
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;
}
Regards,
Jeff
