Results 1 to 11 of 11

Thread: TreeMap problem

  1. #1
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default TreeMap problem

    OK.
    One of my rare threads here, and hopefully it's just me being blind.

    First have some code:

    Java Code:
    package treeset;
    
    import java.util.TreeMap;
    
    /**
     */
    public class TestTreeMap {
    
        private TreeMap<TeamMember, Object> testMap = new TreeMap<TeamMember, Object>(new TeamMember.TeamMemberComparator());
        private static final Object PLACEHOLDER = new Object();
    
        public static void main(String[] args) {
            TestTreeMap ttm = new TestTreeMap();
            ttm.add(new TeamMember(100L, true, "Me"));
            for (long i = 0; i < 4; i++) {
                ttm.add(new TeamMember(i, false, "Addition" + i));
                ttm.printTestSet();
            }
            ttm.add(new TeamMember(100L, false, "Me"));
            ttm.printTestSet();
        }
    
        private void add(TeamMember tm) {
            testMap.put(tm, PLACEHOLDER);
        }
    
        private void printTestSet() {
            System.out.println(testMap);
        }
    }
    Java Code:
    package treeset;
    
    import java.util.Comparator;
    
    /**
     */
    public class TeamMember {
        private boolean isCurrentUser;
        private Long fp;
        private String name;
    
        /**
         * Constructs a new TeamMember
         * @param fp fp
         * @param isCurrentUser If this is current user
         */
        public TeamMember(Long fp, boolean isCurrentUser, String name) {
            this.isCurrentUser = isCurrentUser;
            this.fp = fp;
            this.name = name;
        }
    
        /**
         * Note this equality method <b>only considers fingerprint</b>.
         * @param o The object to test for equality.
         * @return If the TeamMember has the same fingerprint as this TeamMember.
         */
        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
    
            TeamMember that = (TeamMember)o;
    
            return !(fp != null ? !fp.equals(that.fp) : that.fp != null);
    
        }
    
        /**
         * @return the hashcode of the fp (only) of this TeamMember.
         */
        @Override
        public int hashCode() {
            return fp != null ? fp.hashCode() : 0;
        }
    
        @Override
        public String toString() {
            return fp + " " + name + " - " + isCurrentUser;
        }
    
        /**
         * Comparator class for sorting Team Members
         */
        public static class TeamMemberComparator implements Comparator<TeamMember> {
            public int compare(TeamMember thisTeamMember, TeamMember thatTeamMember) {
                if (thisTeamMember.equals(thatTeamMember)) {
                    return 0;
                } else if (thisTeamMember.isCurrentUser) {
                    return -1;
                } else if (thatTeamMember.isCurrentUser) {
                    return 1;
                } else {
                    return thisTeamMember.name.compareTo(thatTeamMember.name);
                }
            }
        }
    }
    The top class is just the testing class for a TreeMap, which contains a placeholder object keyed on by instances of TeamMember.
    As you can see TeamMember has a comparator that order by currentUser on the left, then by name. TeamMembers are equal is the fp (a unique id) is the same, so they should not be added to the map (by the rules of the treemap.

    The above code (on jdk1.6.0_13_x64) gives the following output:
    (excuse the object nonsense)
    Java Code:
    {100 Me - true=java.lang.Object@158b649, 0 Addition0 - false=java.lang.Object@158b649}
    {100 Me - true=java.lang.Object@158b649, 0 Addition0 - false=java.lang.Object@158b649, 1 Addition1 - false=java.lang.Object@158b649}
    {100 Me - true=java.lang.Object@158b649, 0 Addition0 - false=java.lang.Object@158b649, 1 Addition1 - false=java.lang.Object@158b649, 2 Addition2 - false=java.lang.Object@158b649}
    {100 Me - true=java.lang.Object@158b649, 0 Addition0 - false=java.lang.Object@158b649, 1 Addition1 - false=java.lang.Object@158b649, 2 Addition2 - false=java.lang.Object@158b649, 3 Addition3 - false=java.lang.Object@158b649}
    {100 Me - true=java.lang.Object@158b649, 0 Addition0 - false=java.lang.Object@158b649, 1 Addition1 - false=java.lang.Object@158b649, 2 Addition2 - false=java.lang.Object@158b649, 3 Addition3 - false=java.lang.Object@158b649, 100 Me - false=java.lang.Object@158b649}
    As you can see, the second "Me" is still being added, even though the fp values are the same.

    The curious thing is, if you reduce the loop size to 1, you get:
    Java Code:
    {100 Me - true=java.lang.Object@158b649, 0 Addition0 - false=java.lang.Object@158b649}
    {100 Me - true=java.lang.Object@158b649, 0 Addition0 - false=java.lang.Object@158b649}
    which has no extra "Me".

    So...anyone else seen this problem? Anyone else have this problem on other versions of the JDK?

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default

    Your ordering isn't a PTO (Partial Total Ordering), i.e. you shouldn't just compare the fp member for equality, but compare it for > and/or < as well.

    kind regarrds,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    DarrylBurke's Avatar
    DarrylBurke is offline Member
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,193
    Rep Power
    19

    Default

    As you can see TeamMember has a comparator that order by currentUser on the left, then by name. TeamMembers are equal is the fp (a unique id) is the same,
    From the API for Comparator:
    Caution should be exercised when using a comparator capable of imposing an ordering inconsistent with equals to order a sorted set (or sorted map). Suppose a sorted set (or sorted map) with an explicit comparator c is used with elements (or keys) drawn from a set S. If the ordering imposed by c on S is inconsistent with equals, the sorted set (or sorted map) will behave "strangely." In particular the sorted set (or sorted map) will violate the general contract for set (or map), which is defined in terms of equals.
    Does that cover it?

    db

  4. #4
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default

    I thought originally it did, but it is consistent with equals (from the first check in the comparator being a call on equals). We finally figured out what was up (and then I went to lunch).

    The Treemap starts its search for placing an new key on a put() from a "root" element. That root is not the leftmost element (understandably now), it's the middle element.

    Since my comparator is reliant on the leftmost element being checked (that's where the isCurrentUser element is placed), the second "Me" (which has the flag set false) is never actually compared against the original "Me".

    So the order in the set, prior to the attempt to add another "Me" is:
    Me, Addition0, Addition1, Addition2 (say).
    With the root set to Addition0 then the two "Me"'s are never compared.

  5. #5
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default

    Quote Originally Posted by JosAH View Post
    Your ordering isn't a PTO (Partial Total Ordering), i.e. you shouldn't just compare the fp member for equality, but compare it for > and/or < as well.

    kind regarrds,

    Jos
    I'm not ordering on the fp.
    The fp is for equality.
    The name is for ordering.
    The comparator first checks for equality, then for ordering.
    The problem would (and does) still exist if the equality was based on name, or if the ordering was on fp.
    It's the need to stick something with the isCurrentUser set true onto the left that's the problem.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Tolls View Post
    I'm not ordering on the fp.
    The fp is for equality.
    The name is for ordering.
    The comparator first checks for equality, then for ordering.
    The problem would (and does) still exist if the equality was based on name, or if the ordering was on fp.
    It's the need to stick something with the isCurrentUser set true onto the left that's the problem.
    That's the problem: you don't implement a PTO; e.g. a value (100, A) may end up to the left of (1, Z) and may never be compared again against other values.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default

    Ah, I see what you mean now.
    There's no real way around that sadly...well, there would be if I could rip the whole thing out and rewire it.
    "Just change the ordering a bit."
    ...BAH!

    Just need to catch the special case of adding a second Me...which makes me feel slightly unclean, but if people will change their minds at zero hour.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Tolls View Post
    Ah, I see what you mean now.
    There's no real way around that sadly...well, there would be if I could rip the whole thing out and rewire it.
    "Just change the ordering a bit."
    ...BAH!

    Just need to catch the special case of adding a second Me...which makes me feel slightly unclean, but if people will change their minds at zero hour.
    Can't you change your comparator a bit? All you have to do is compare the fp's for <and > (instead of just == and !=)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default

    Wouldn't work would it?
    Since fp determines equality, and name determines ordering (with the exception of isCurrentUser).
    If thisFp < thatFp then what? That doesn't give me any ordering clues.

    The problem lies in the need to check the flag for the lone entry that has to be to the left. The other stuff is then sorted to the right of that. But it would need (going with a Comparator-only solution) to handle the possibility of an entry being added that was equal but the flag was different. That's the problem.
    Last edited by Tolls; 08-31-2011 at 02:32 PM. Reason: typo

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Tolls View Post
    Wouldn't work would it?
    Since fp determines equality, and name determines ordering (with the exception of isCurrentUser).
    If thisFp < thatFp then what? That doesn't give me any ordering clues.

    The problem lies in the need to check the flag for the lone entry that has to be to the left. The other stuff is then sorted to the right of that. But it would need (going with a Comparator-only solution) to handle the possibility of an entry being added that was equal but the flag was different. That's the problem.
    If a PTO can't be defined for your set, the elements can't be stored in a SortedSet; too bad for your customer ;-) (but they want it!)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

Similar Threads

  1. TreeMap vs Map
    By alpdog14 in forum New To Java
    Replies: 5
    Last Post: 03-27-2011, 06:07 PM
  2. [JAVA] TreeMap
    By watle in forum Advanced Java
    Replies: 3
    Last Post: 03-16-2011, 05:39 PM
  3. Treemap question
    By dave120 in forum New To Java
    Replies: 0
    Last Post: 10-13-2009, 02:31 AM
  4. Treemap's
    By Russo in forum New To Java
    Replies: 6
    Last Post: 10-11-2009, 01:13 AM
  5. How to use treemap
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-12-2008, 08:47 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •