CODEWITHSUNDEEP
javacomparatortreeset
jan
jan

Reputation: 55

Comparator for TreeSet doesn't work as wanted

My idea was to sort some entities (which are just some integers) by their layers. I found someone who seemed to have the same problem (I think) but I didn't understand the solution. The layers of each entity is stored in an array. I used a an enumaration for the layers.

public enum Layer {
DEFAULT,
BACKGROUND,
FOREGROUND,
HUD_0,
HUD_1
}

So I don't know if I misunderstood the way a comparator works or if i just have problems because the entities are Integers...

final Layer[] layers = {Layer.BACKGROUND, Layer.HUD_1, Layer.DEFAULT, Layer.DEFAULT, Layer.HUD_0, Layer.HUD_1};
    TreeSet<Integer> sorted = new TreeSet<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer entity1, Integer entity2) {
            //Integer layer1 = layers[entity1].ordinal();
            //Integer layer2 = layers[entity2].ordinal();
            //return layer1 < layer2 ? -1 : (layer1 > layer2 ? 1 : 0);
            return layers[entity1].compareTo(layers[entity2]);
        }
    });
    sorted.add(0);//bg
    System.out.println(sorted.toString());
    sorted.add(4);//hud0
    System.out.println(sorted.toString());
    sorted.add(2);//def
    System.out.println(sorted.toString());
    sorted.add(3);//def
    System.out.println(sorted.toString());
    sorted.add(1);//hud1
    System.out.println(sorted.toString());
    sorted.add(5);//hud1
    System.out.println(sorted.toString());

This is the output:

[0]
[0, 4]
[2, 0, 4]
[2, 0, 4]
[2, 0, 4, 1]
[2, 0, 4, 1]

the last should actually be [2, 3, 0, 4, 1, 5]

I read that a TreeSet stores every element just once since it is a Set but I don't know why its using the layer for that and not the entities which i actually want insert.

Upvotes: 0

Views: 1908

Answers (3)

Billy Mailman
Billy Mailman

Reputation: 272

The problem is ultimately that the TreeSet will (being a set) only hold elements once, and it needs a way to know if it already contains an element, and it uses the Comparator you provided to do that. Since your comparator was using the enums for ordering, the Treeset saw two entries as equal if the enums matched.

For details, see http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html, particularly the paragraph

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

Ultimately, if you want to use a TreeSet to sort on the enum, you'll need to expand the comparison logic to fall back on something else when the enums match. Something like

public int compare(Integer entity1, Integer entity2) {
    int returnValue = layers[entity1].compareTo(layers[entity2]);
    if(returnValue == 0){
        returnValue = entity1.compareTo(entity2);
    }
}

Which then makes the entities not match (and fail to add to the TreeSet) just because the enums match.

Upvotes: 0

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

It happens that way because that is how TreeSet is defined: "a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal." java.util.TreeSet

You could introduce a tie breaker that will impose an order among different objects in the same layer - it could just be an arbitrary sequence number if there is nothing more meaningful you could use. Objects in different layers would still be ordered by layer.

Upvotes: 2

assylias
assylias

Reputation: 328598

From a TreeSet's perspective, two elements are equal if item1.compareTo(item2) == 0. In your case, Layer.HUB_1 appears twice in your array and both items will be deemed equal so only one will be added.

Upvotes: 3

Related Questions