Thread: TreeSet contains(obj) doe not behave as expected

Hello,

I am using the class TreeSet from the java collections library and I have a little problem with the "contains(Object)" method.
I want to use the TreeSet to order a number of Layer-Objects by their Z-Coordinate in a little project of mine.
Sometimes the Z-Coordinate of a layer can change, in that case I
1). remove it from the set
2). change its Z-value
3). add it to the set again
However, my problem is that sometimes a Layer that was added to the set can not be removed anymore since the set doesnt notice, that the Layer is contained within the set.

This is how I construct the TreeSet:

	private final TreeSet<Layer> allLayers = new TreeSet<>(new Comparator<Layer>() {
		public int compare(Layer o1, Layer o2) {
			if (o1.equals(o2)) {
				return 0;
			}
			if (o1.get_z() >= o2.get_z()) {
				return 1;
			}
			return -1;
		}
	});

For adding and removing I just use the standard functions "add(Object)" and "remove(Object)".
The method "equals" in the Layer class is not overwritten. It is still the default inherited from Object.

I have build a little help function to test this behaviour:

	public void containsTest(Layer layer) {
		for (Layer a : allLayers) {
			if (a.equals(layer)) {
				System.out.println(layer+" is contained.");
			}
		}
		System.out.println("Contains " + layer + " = " + allLayers.contains(layer));
	}

The outcome of this is sometimes:

Layer(0) is contained
Contains Layer(0) = false

If I use this class incorrectly please tell me so. Thanks in advance.



Edit:
Here is a small test program with various debug text:

import java.util.Comparator;
import java.util.TreeSet;
 
public class Test {
 
	private static final TreeSet<Layer> layers = new TreeSet<>(new Comparator<Layer>() {
		public int compare(Layer o1, Layer o2) {
			if (o1.equals(o2)) {
				return 0;
			}
			if (o1.get_z() >= o2.get_z()) {
				return 1;
			}
			return -1;
		}
	});
 
	public static void main(String[] args) {
		Layer layer1 = new Layer();
		Layer layer2 = new Layer();
		Layer layer3 = new Layer();
		Layer layer4 = new Layer();
 
		layer1.z = 0;
		layer2.z = 0;
		layer3.z = 1;
		layer4.z = 1;
 
		layer1.interleavedLayer = layer2;
		layer3.interleavedLayer = layer4;
 
		add(layer1);
		add(layer2);
		add(layer3);
		add(layer4);
 
		layer1.set_z(2);
	}
 
	public static void add(Layer l) {
		System.out.println("Add layer "+l+" at "+l.get_z());
		layers.add(l);
		containsTest(l);
	}
 
	public static void remove(Layer l) {
		System.out.println("Remove layer "+l+" at "+l.get_z());
		layers.remove(l);
		containsTest(l);
	}
 
	public static void containsTest(Layer l) {
		boolean contains = false;
		for (Layer a : layers) {
			if (a.equals(l)) {
				contains = true;
				break;
			}
		}
		System.out.println(l+" is contained = "+contains);
		System.out.println("Contains "+l+" = "+layers.contains(l));
		System.out.println();
	}
 
	private static class Layer {
 
		private static int num;
		private String name = getClass().getSimpleName()+num++;
		private int z;
		private Layer interleavedLayer;
 
		public int get_z() {
			return z;
		}
 
		public void set_z(int value) {
			Test.remove(this);
			z = value;
			Test.add(this);
			if (interleavedLayer != null) {
				interleavedLayer.set_z(value);
			}
		}
 
		public String toString() {
			return name;
		}
 
	}
 
}

If I let it run I get the following output:
The important part is underlined.

Add layer Layer0 at 0
Layer0 is contained = true
Contains Layer0 = true

Add layer Layer1 at 0
Layer1 is contained = true
Contains Layer1 = true

Add layer Layer2 at 1
Layer2 is contained = true
Contains Layer2 = true

Add layer Layer3 at 1
Layer3 is contained = true
Contains Layer3 = true

Remove layer Layer0 at 0
Layer0 is contained = true
Contains Layer0 = false

Add layer Layer0 at 2
Layer0 is contained = true
Contains Layer0 = true

Remove layer Layer1 at 0
Layer1 is contained = false
Contains Layer1 = false

Add layer Layer1 at 2
Layer1 is contained = true
Contains Layer1 = true

Can you post a SSCCE that demonstrates the behavior?

You say it happens "sometimes." There must be something special about those times contributing to the behavior. See if you can define what's special about those cases, using prints and comparisons liberally or a debugger.

Here's an SSCCE that cobbles together the code you've posted into something that runs and then tests the scenario you described. All seems to work as advertised. You are welcome to manipulate the example as needed to show the behavior you're experiencing.

// File TreeSetTest.java
// Author: GregBrannon, (c) August 2013
// inspired by the question on JPF:
// [url]http://www.javaprogrammingforums.com/collections-generics/31135-treeset-contains-obj-doe-not-behave-expected.html[/url]
import java.util.Comparator;
import java.util.TreeSet;
 
public class TreeSetTest
{
    // duplicates OP's code but made static and specified TreeSet constructor
    // to be a Layer set
    private static final TreeSet<Layer> allLayers =
        new TreeSet<Layer>(new Comparator<Layer>()
        {
            public int compare(Layer o1, Layer o2)
            {
                if (o1.equals(o2)) {
                    return 0;
                }
                if (o1.get_z() >= o2.get_z()) {
                    return 1;
                }
                return -1;
            }
        } );
 
    public static void main(String[] args)
    {
        Layer layer1 = new Layer( 1 );
        Layer layer2 = new Layer( 2 );
 
        allLayers.add( layer1 );
        allLayers.add( layer2 );
 
        // check that both layer1 and layer2 are in the set
        containsTest( layer1 );
        containsTest( layer2 );
 
        // remove layer1, modify it, return it
        allLayers.remove( layer1 );
        layer1.setZCoord( 3 );
        allLayers.add( layer1 );
 
        // check that both layer1 and layer2 are in the set
        containsTest( layer1 );
        containsTest( layer2 );
 
        // remove both objects
        allLayers.remove( layer1 );
        allLayers.remove( layer2 );
 
        // check that both layer1 and layer2 are no longer in the set
        containsTest( layer1 );
        containsTest( layer2 );
 
    } // end method main()
 
    // duplicates OP's code
    public static void containsTest(Layer layer)
    {
        for (Layer a : allLayers)
        {
            if (a.equals(layer))
            {
                System.out.println(layer+" is contained.");
            }
        }
        System.out.println("Contains " + layer + " = " +
                allLayers.contains(layer));
 
    } // end method containsTest()
 
} // end class TreeSetTest
 
// a minimum Layer class to test tree set functionality
class Layer
{
    int zCoord;
 
    // constructor
    public Layer( int zCoord )
    {
        this.zCoord = zCoord;
 
    } // end constructor
 
    public void setZCoord( int zCoord )
    {
        this.zCoord = zCoord;
    }
 
    public int get_z()
    {
        return zCoord;
    }
 
} // end class Layer

It happens when I change the Z-coordinate of a layer. I remove it, change the Z, and add it again.
Its not arbitrary, it always happens with a given set of layers and always happens to the same layer.
I add 2 layers with Z = 0, and then 2 layers with Z = 1. Then I pick the first layer with Z == 0 and I want to change its Z value to 2 but the error occurs.

Edit: Added the SSCCE that you demanded in the first post.

Well, the comparator returns 0 if 2 elements are equal. As far as I understood thats how its supposed to be, isnt it?

What exactly would be a good choice for a quick sorted data structure? I thought a binary tree (which the treeSet is, isnt it?) would be a good idea.

But wouldnt a tree be faster?

By the way, where am I adding the same element twice to the TreeSet in my example? Every element should only be inserted once by my intention.

But it says the comparator should only return 0 if both elements are equal. In my case the equal Z correlates to a "dont care" in what way they are ordered. After all, my comparator correctly returns 0 if both elements are equal.
At best the documentation is slightly confusing.

But I already have switched to an array list. your argument about the speed is very good though.

Well, thanks for your time.