TreeMap problem

[Tolls]

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

First have some 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);
    }
}

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)

{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:

{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?

[JosAH]

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

[DarrylBurke]

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

[Tolls]

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.

[Tolls]

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.

[JosAH]

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

[Tolls]

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.

[JosAH]

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

[Tolls]

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.

[JosAH]

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

[Tolls]

That about sums it up.