Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 11 of 11

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

  1. #1
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    848
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default 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


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    6,071
    My Mood
    Mellow
    Thanks
    243
    Thanked 752 Times in 738 Posts

    Default Re: TreeSet contains(obj) doe not behave as expected

    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

  3. #3
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    848
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default Re: TreeSet contains(obj) doe not behave as expected

    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.

  4. #4
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,354
    Thanks
    182
    Thanked 832 Times in 775 Posts
    Blog Entries
    5

    Default Re: TreeSet contains(obj) doe not behave as expected

    See the API for TreeSet

    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.
    If all you want is to order the Layers, I'd add them to a List then use Collections.sort to sort the List - a Set should only be used when you want unique elements based upon their equals method - while its tough to tell here this doesn't look to be the case. If you want uniques based upon the z value, then override the hashCode/equals methods to define equality based upon the z value.

  5. #5
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    848
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default Re: TreeSet contains(obj) doe not behave as expected

    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.

  6. #6
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,354
    Thanks
    182
    Thanked 832 Times in 775 Posts
    Blog Entries
    5

    Default Re: TreeSet contains(obj) doe not behave as expected

    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.
    Again I suggest to read the API, as I would say this is a mis-use of a TreeSet (unless I misunderstand the goal at hand). A Set should be used if you want unique elements (based upon the equals/hashCode and in the case of a TreeSet the compareTo/compare methods), which (correct me if I'm wrong) does not seem to be what you are trying to accomplish. It seems to me you just want a way to Sort, which is why other tools such as Collections.sort() or Arrays.sort() exists: to sort other data structures.

  7. #7
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    848
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default Re: TreeSet contains(obj) doe not behave as expected

    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.

  8. #8
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,354
    Thanks
    182
    Thanked 832 Times in 775 Posts
    Blog Entries
    5

    Default Re: TreeSet contains(obj) doe not behave as expected

    But wouldnt a tree be faster?
    Every time you add to a Tree set it takes log(n) time, so to add everthing is n*log(n), the same as Collections.sort takes (the additions to the end of a List in theory take constant time O(1) depending upon the context). Every addition to the TreeSet takes log(n), as opposed to every addition to a List takes constant (or possible linear depending upon context) time. If every addition is crucial time-wise then using a List may be more appropriate.

    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.
    That's the problem. Consider how things are being organized: a self-balancing tree. Suppose you add 1, 2, 3, and 4 (numbers represent your layers, not numerals) and for the sake of argument consider the tree balance as follows:
        3
       / \
      2   4
       \
        1

    When you try to remove 1, it does a comparison against 2, the comparator returns the number 1, so the algorithm starts down the branch of 4. Unable to find 1 it doesn't remove it.

    To correctly implement the TreeSet, your comparator should not return 1 for equal z values (and you should implement the equals/hashCode methods)
    			if (o1.get_z() > o2.get_z()) {
    				return 1;
    			}
    			if ( o1.get_z() == o2.get_z() ){
    				return 0;
    			}

    When you do this and add all layers, the size of the Set will be 2 (as it should be).

    Again, in my opinion this is a mis-use of the Set interface. To get around all of this, use a List

     
    List<Layer> list = new ArrayList<Layer>();
    list.add(layer1);
    list.add(layer2);
    ....
    Collections.sort(list, new Comparator<Layer>(){
    //TODO
    });

  9. #9
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    848
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default Re: TreeSet contains(obj) doe not behave as expected

    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.

  10. #10
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,354
    Thanks
    182
    Thanked 832 Times in 775 Posts
    Blog Entries
    5

    Default Re: TreeSet contains(obj) doe not behave as expected

    But I already have switched to an array list. your argument about the speed is very good though.
    Glad you got it working. Actually, I feel my argument about the way the tree can be organized and why you are encountering your issue was pretty descent as well

    Quote Originally Posted by Cornix View Post
    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.
    Don't mean to belabor the point, but "Don't care" is the problem. In this context, a sorting data structure not meant for duplicate values used to sort on values that have duplicates can run into problems when you try to do such a thing.

  11. #11
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    848
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default Re: TreeSet contains(obj) doe not behave as expected

    Well, thanks for your time.

Similar Threads

  1. paint only paints one obj
    By IHeartProgramming in forum AWT / Java Swing
    Replies: 1
    Last Post: October 11th, 2012, 11:08 AM
  2. class String replaceAll does not behave as i expected
    By Samaras in forum What's Wrong With My Code?
    Replies: 8
    Last Post: August 19th, 2012, 05:41 PM
  3. Save JSON obj via Jfilechooser
    By nautilusz in forum File I/O & Other I/O Streams
    Replies: 0
    Last Post: March 24th, 2012, 07:15 AM
  4. Basic Obj programming help! thanks
    By mclaren93 in forum Object Oriented Programming
    Replies: 1
    Last Post: November 17th, 2011, 07:45 PM
  5. Java applet that can behave like dekstop app?
    By cowcool in forum Java Theory & Questions
    Replies: 5
    Last Post: May 28th, 2011, 02:16 PM