Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-4730113

TreeSet removeAll(), retainAll() don't use comparator; addAll() does

    XMLWordPrintable

    Details

    • Type: Enhancement
    • Status: Closed
    • Priority: P4
    • Resolution: Won't Fix
    • Affects Version/s: 1.4.0
    • Fix Version/s: None
    • Component/s: core-libs
    • Labels:

      Description



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

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              jjb Josh Bloch
              Reporter:
              nthompsosunw Nathanael Thompson (Inactive)
              Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved:
                Imported:
                Indexed: