Name: nt126004 Date: 08/12/2002


FULL PRODUCT VERSION :
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1-beta-b14)
Java HotSpot(TM)
Client VM (build 1.4.1-beta-b14, mixed mode)

FULL OPERATING SYSTEM VERSION :
Microsoft Windows 2000 [Version
5.00.2195]

A DESCRIPTION OF THE PROBLEM :
If you construct a
TreeSet with a Comparator, you would expect all the set methods to use it.
However, while addAll() calls the comparator, removeAll() and
retainAll() don't (they use equals() instead).
This can be very
awkward if you want to compare on some arbitrary attribute of a class since
the only way removeAll() can be made to work properly is to override
equals() which is often undesirable. The corollary of this is that you
will not be able to create two different orderings on a class in a TreeSet
without extending the class and overriding the equals() method.

If
you look at the code, the problem lies in AbstractSet.removeAll(). The
behaviour changes depending on whether "if (size() > c.size())". In some
cases, it delegates the contains() call to the passed in Collection which
won't necessarily use a comparator. addAll() has been overridden in
TreeSet to fix the problem but removeAll() and retainAll() haven't.

I see that your documentation does actually cover
this behaviour. It seems to me though that this restriction makes the use of
comparators almost completely pointless. The whole point of comparators is to
enable different orderings on the underlying object. I _can_ imagine certain
trivial examples where you can have different comparators which still obey the
equals() contract (for example, two comparators which implement exactly reverse
orderings). However, in the general case, it is not possible to have multiple
comparators which all obey the equals() contract. This means that the use of
comparators with this class is fairly pointless and in fact it would be safer
not to include them since they have more pitfalls than benefits.
It's also not clear to me why addAll() behaves in a compeletely different way to removeAll() and retainAll().
So I think that a full comparator implementation for this class would improve the class considerably.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1. Construct a tree set with a comparator
2. create two objects in a class
which uses Object.equals() and which are equal as far as the comparator is
concerned.
3. Insert one of the objects into the set
4. Insert the
other object into a List.
5. call set.removeAll(list);
6. set is
still of size 1.

EXPECTED VERSUS ACTUAL BEHAVIOR :
Expected : Set should be of size zero
Actual : Set is of size one

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------

import java.util.*;



public class TestRemoveAll
{

    static class TestObject
    
{
        final int a;

        public TestObject(int a)
        {
            this.a = a;
        }

        public int getA()
        {
            return a;
        }
    }

    static class CompareTestObject implements Comparator
    {
        public CompareTestObject()
        {
        }

        public int compare(Object o1, Object o2)
        {
            TestObject lhs = (TestObject) o1;
            TestObject rhs = (TestObject) o2;
            Integer int1 = new Integer(lhs.getA());
            Integer int2 = new Integer(rhs.getA());
            return int1.compareTo(int2);
        }
    }

    public TestRemoveAll(String s)
    {
    }

    public static void main(String[] args)
    {
        TestObject obj1 = new TestObject(1);
        TestObject obj2 = new TestObject(1);

        // This uses comparator and works as you'd expect
        TreeSet set = new TreeSet(new CompareTestObject());
        LinkedList list = new LinkedList();
        
        set.add(obj1);
        list.add(obj2);
        set.addAll(list);
        assert(set.size() == 1);

        // This doesn't use comparator (uses equals()) and fails
        set = new TreeSet(new CompareTestObject());
        list = new LinkedList();
        set.add(obj1);
        list.add(obj2);
        
        set.removeAll(list);
        assert(set.size() == 0);

        // This doesn't use comparator (uses equals()) and fails
        set = new TreeSet(new CompareTestObject());
        list = new LinkedList();
        set.add(obj1);
        list.add(obj2);
        set.retainAll(list);
        
assert(set.size() == 1);
    }
}




---------- END SOURCE ----------

CUSTOMER WORKAROUND :
Extend the class you have in the set to have a new equals() operator which is
consistent with your comparator.
(Review ID: 160016)
======================================================================