glazedlists
  1. glazedlists
  2. GLAZEDLISTS-495

SortedList.contains() not working correct?

    Details

    • Type: Bug Bug
    • Status: Open
    • Priority: Major Major
    • Resolution: Unresolved
    • Affects Version/s: current
    • Fix Version/s: milestone 1
    • Component/s: core
    • Labels:
      None
    • Environment:

      Operating System: Windows XP
      Platform: All

    • Issuezilla Id:
      495

      Description

      Hello,

      I have an object, that implements Comparable and overrides equals() &
      hashCode(). If I have a list containing an object and call contains on this
      list, with another object, that is equal to the already contained object, my
      sorted list is returning true AND false... depending on the current comparator.

      Example code
      #################
      import java.util.Comparator;

      import ca.odell.glazedlists.BasicEventList;
      import ca.odell.glazedlists.EventList;
      import ca.odell.glazedlists.SortedList;

      public class Tester {

      private static class DescComparator implements Comparator<MyObject> {
      @Override
      public int compare(MyObject obj1, MyObject obj2)

      { return obj1.getValueTwo().compareTo(obj2.getValueTwo()); }

      }

      private static class MyObject implements Comparable<MyObject> {

      private final String valueOne;

      private final String valueTwo;

      public MyObject(String valueOne, String valueTwo)

      { super(); this.valueOne = valueOne; this.valueTwo = valueTwo; }

      public String getValueOne()

      { return valueOne; }

      public String getValueTwo()

      { return valueTwo; }

      @Override
      public int compareTo(MyObject obj)

      { return valueOne.compareTo(obj.getValueOne()); }

      @Override
      public boolean equals(Object obj) {
      if (obj == null)

      { return false; }
      if (getClass() != obj.getClass()) { return false; }

      final MyObject other = (MyObject) obj;
      if ((this.valueOne == null) ? (other.valueOne != null) :
      !this.valueOne.equals(other.valueOne))

      { return false; }

      return true;
      }

      @Override
      public int hashCode()

      { int hash = 3; hash = 89 * hash + (this.valueOne != null ? this.valueOne.hashCode() : 0); return hash; }

      }

      public static void main(String[] args)

      { // Following objects are equals according to their implemented equals() & hashCode() MyObject myObject = new MyObject("ValueOne", "StringA"); MyObject myObjectCopy = new MyObject("ValueOne", "StringB"); EventList<MyObject> list = new BasicEventList<MyObject>(); list.add(myObject); SortedList<MyObject> sorted = new SortedList<MyObject>(list); // Sort criteria code (MyObject implements Comparable on code) System.out.println(sorted.contains(myObjectCopy)); // Sort criteria desc sorted.setComparator(new DescComparator()); System.out.println(sorted.contains(myObjectCopy)); }

      }
      ###########

      Output is:
      true
      false

      but should be:
      true
      true

      Am I doing something wrong here? Am I missing something? Or is the sorted list
      not working correctly?

      Kind regards
      Kai

        Activity

        Hide
        kameit00 added a comment -

        Created an attachment (id=57)
        Class to test the described behaviour of SortedList.contains()

        Show
        kameit00 added a comment - Created an attachment (id=57) Class to test the described behaviour of SortedList.contains()
        Hide
        jplemieux added a comment -

        This is an interesting case that the implementation of SortedList.indexOf(...)
        fails on... one that wasn't considered when the latest implementation was written.

        SortedList.indexOf(Object o1) uses the Comparator to quickly find a location at
        which to begin a linear search for a matching object (one that is .equals() to
        o1). If we reach a point where the Comparator stops returning 0, then we believe
        the search is futile and return an index of -1 to indicate failure.

        The attached testcase includes an entry in the SortedList that IS .equals() but
        never compares as 0. Since the Comparator is considered first, we never even
        find a location at which to begin a linear search.

        While I think it's probably ok to rely on this "agreement" between .equals() and
        the Comparator in the SortedList, that is NOT something that is documented in
        the API call at all, and really needs to be in order to have a fighting chance
        of understanding this strange behavior.

        While I admit that a Comparator returning 0 does not imply the objects are
        .equals(), and vice-versa, we probably still won't change this method's
        implementation. If we DON'T use the Comparator in the implementation of that
        method, we'll destroy our performance in 98% of all use cases for the benefit of
        just 2% of the cases. Hence, I think it's better to document the assumption and
        move forward.

        Show
        jplemieux added a comment - This is an interesting case that the implementation of SortedList.indexOf(...) fails on... one that wasn't considered when the latest implementation was written. SortedList.indexOf(Object o1) uses the Comparator to quickly find a location at which to begin a linear search for a matching object (one that is .equals() to o1). If we reach a point where the Comparator stops returning 0, then we believe the search is futile and return an index of -1 to indicate failure. The attached testcase includes an entry in the SortedList that IS .equals() but never compares as 0. Since the Comparator is considered first, we never even find a location at which to begin a linear search. While I think it's probably ok to rely on this "agreement" between .equals() and the Comparator in the SortedList, that is NOT something that is documented in the API call at all, and really needs to be in order to have a fighting chance of understanding this strange behavior. While I admit that a Comparator returning 0 does not imply the objects are .equals(), and vice-versa, we probably still won't change this method's implementation. If we DON'T use the Comparator in the implementation of that method, we'll destroy our performance in 98% of all use cases for the benefit of just 2% of the cases. Hence, I think it's better to document the assumption and move forward.
        Hide
        kameit00 added a comment -

        So the only fix in this case would be, to use the underlying list of the sorted list? In this case, using the
        BasicEventList for contains()?

        Show
        kameit00 added a comment - So the only fix in this case would be, to use the underlying list of the sorted list? In this case, using the BasicEventList for contains()?
        Hide
        jplemieux added a comment -

        Either that, or if your application allows it, make your .equals() and
        Comparator agree with each other.

        Show
        jplemieux added a comment - Either that, or if your application allows it, make your .equals() and Comparator agree with each other.
        Hide
        kameit00 added a comment -

        The list is displayed in a JTable, where the user can sort according to his needs. So the comparator is
        different for each column he chooses to sort. The equals() is used, when he wants to add a new object. For
        us, a new object is a duplicate, if the value of one specific column is equal.
        ... does that make sense?

        I think the only solution for us in that case is, to use the underlying list.

        Show
        kameit00 added a comment - The list is displayed in a JTable, where the user can sort according to his needs. So the comparator is different for each column he chooses to sort. The equals() is used, when he wants to add a new object. For us, a new object is a duplicate, if the value of one specific column is equal. ... does that make sense? I think the only solution for us in that case is, to use the underlying list.
        Hide
        jplemieux added a comment -

        There are lots of other solutions to this problem, depending on how far you want
        to go. Others off the top of my head:

        1) Stack 2 SortedLists... one that services your UI, the other for querying.

        2) If you want O(1) reads in order to be able to check for the existence of an
        item in your pipeline (i.e. .contains()), consider using a Map constructed with
        GlazedLists.syncEventListToMap(...)

        Show
        jplemieux added a comment - There are lots of other solutions to this problem, depending on how far you want to go. Others off the top of my head: 1) Stack 2 SortedLists... one that services your UI, the other for querying. 2) If you want O(1) reads in order to be able to check for the existence of an item in your pipeline (i.e. .contains()), consider using a Map constructed with GlazedLists.syncEventListToMap(...)
        Hide
        kameit00 added a comment -

        Solution 2 is interesting for performance reasons. But using our underlying
        observable list will do the job for us with a small change (like solution 1).

        Thanks for the solutions. For performance I did not think of solution 2, so
        that's an interesting information.

        Show
        kameit00 added a comment - Solution 2 is interesting for performance reasons. But using our underlying observable list will do the job for us with a small change (like solution 1). Thanks for the solutions. For performance I did not think of solution 2, so that's an interesting information.

          People

          • Assignee:
            jessewilson
            Reporter:
            kameit00
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated: