Page 1 of 2 12 LastLast
Results 1 to 20 of 35
  1. #1
    Join Date
    Apr 2011
    Posts
    18
    Rep Power
    0

    Arrow bug? list and treeSet

    I have a real world problem where I get a list of retail store location and get the distance from group of starting locations and find the 10 closest location for each starting locations. I get returned from getdata a list of stores loop through each store and calculate the distance and put them in a treeset for sorting. Problem is when the second set of data is added to the treeset the original set is replace with a duplicate set of the second set. a very simple test case for this is in the attachment. Rename to TreeSetExample.java to build it.

    this is the example output:

    Main - Started
    *************** starting test 1 *********************
    list count after loop [1] number of elements = [5] contents:
    save simpleVO name = [1]
    save simpleVO name = [2]
    save simpleVO name = [3]
    save simpleVO name = [4]
    save simpleVO name = [5]

    *************** starting test 2 *********************
    list count after loop [1] number of elements = [5] contents:
    save simpleVO name = [1]
    save simpleVO name = [2]
    save simpleVO name = [3]
    save simpleVO name = [4]
    save simpleVO name = [5]
    list count after loop [2] number of elements = [10] contents:
    save simpleVO name = [6]
    save simpleVO name = [7]
    save simpleVO name = [8]
    save simpleVO name = [9]
    save simpleVO name = [10]
    save simpleVO name = [6]
    save simpleVO name = [7]
    save simpleVO name = [8]
    save simpleVO name = [9]
    save simpleVO name = [10]
    Main - we gone bye-bye...!
    Attached Files Attached Files

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,381
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Fubarable View Post
    I think I speak for all in wishing you much luck in solving this!
    True; while I'm not totally ignorant when it comes to operations research problems I don't even understand what this problem is about.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

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

    Default

    Oh, you can find out what the 'operations research problem' is about on the cross post!
    OTN Discussion Forums : bug using list and treeset ...

    db

  5. #5
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    Probably you are adding the same thing multiple times to the set. Usually that would a neat trick, but you manage it because of the comparator you have at the end of your code.

    I didn't read the rest (because it wasn't easy to read with all the visual noise) but I guess hidden in there you have something like

    Java Code:
    import java.util.Comparator;
    import java.util.TreeSet;
    
    
    public class StrangelyCompared {
    	
    	int value;
    	
    	public static void main(String[] args) {
    		TreeSet<StrangelyCompared> test = new TreeSet<StrangelyCompared>(new StrangeComparator());
    		
    		StrangelyCompared data = new StrangelyCompared();
    		
    		data.value = -1;
    		test.add(data);
    		System.out.printf("Set size is %d.  Values are:%n", test.size());
    		for(StrangelyCompared item :test) {
    			System.out.print(item.value + " ");
    		}
    		System.out.println();
    		
    			// now we alter data's state and add it again
    		data.value = 66;
    		test.add(data);
    		System.out.printf("Set size is %d.  Values are:%n", test.size());
    		for(StrangelyCompared item :test) {
    			System.out.print(item.value + " ");
    		}
    		System.out.println();
    	}
    }
    
    class StrangeComparator implements Comparator<StrangelyCompared> {
    	public int compare(StrangelyCompared first, StrangelyCompared second) {
    		return 1;
    	}
    }

    Have a read of the TreeSet API documentation. Pay attention to the bit about how the comparator must be consistent with equals. (There's a link to what that means.)

  6. #6
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    11,861
    Rep Power
    19

    Default

    Quote Originally Posted by pbrockway2 View Post
    Have a read of the TreeSet API documentation. Pay attention to the bit about how the comparator must be consistent with equals. (There's a link to what that means.)
    This here.
    Having just bumped into it yesterday myself...:)

  7. #7
    Join Date
    Apr 2011
    Posts
    18
    Rep Power
    0

    Default

    I did find a work around for this, move the get data into the for loop and get a fresh set of List pointers from the getData() on each loop through (tried to clone it, didn't work).

  8. #8
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    I did find a work around for this

    You don't work around the published API. You embrace it.

    Guess I'll grab some popcorn and move on over to the Oracle forum...

  9. #9
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    ... only to find my hubris rewarded by being labelled as the foolish author of this technique for sneaking things into a set!

    @OP - My point still stands: read the API and try to understand why the comparator must be defined in a certain way in order for TreeSet to behave properly. When you add something to a set the comparator is evidently used to see if it already there. Specifically read the descriptions of the add() and remove() methods.

  10. #10
    Join Date
    Apr 2011
    Posts
    18
    Rep Power
    0

    Default

    In this example the compare just returns a 1, all elements are kept in the set no real sorting is taking place because it is not the problem I am seeing The issues is loading data in to a treeset with identical pointers from a list into a treeset. If you look at the output there should be no duplicates in the final treeset. If you increase up the loop count the treeset will only be populated by the last set and all the previous elemens are duplicated, if you go to the original source an up the loopcount to 4 and run the test.Then move the getdata method into the for loop above the set iterator and you will see all the element are there in order they ware entered(expected results). See my second post for an example. If someone has a better way of doing this please share the results page and let me know what you did.

  11. #11
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    11,861
    Rep Power
    19

    Default

    It has been explained to you the TreeSet requires that the Comparator supplied returns the same results as equals() for that class.

    If you do not require sorting then do not use TreeSet.

    That you persist in continuing down this road shows you really aren't listening to any of us.

    Quoting from the API:
    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.
    Yours is not, since your Comparator never returns 0.

  12. #12
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,381
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by douglas.nelson@oracle.com View Post
    In this example the compare just returns a 1, all elements are kept in the set no real sorting is taking place because it is not the problem I am seeing The issues is loading data in to a treeset with identical pointers from a list into a treeset. If you look at the output there should be no duplicates in the final treeset. If you increase up the loop count the treeset will only be populated by the last set and all the previous elemens are duplicated, if you go to the original source an up the loopcount to 4 and run the test.Then move the getdata method into the for loop above the set iterator and you will see all the element are there in order they ware entered(expected results). See my second post for an example. If someone has a better way of doing this please share the results page and let me know what you did.
    A Comparator defines a relation R(a, b); your comparator defines the relation R(a, b) == 1, implying that a > b; your relation also defines R(b, a) == 1, implying that b > a; therefor a == b but your relation also defines R(a, a) == 1 which leads to funny, smelly things.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  13. #13
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    11,861
    Rep Power
    19

    Default

    And TreeSet uses the supplied Comparator to determine if the Set contains something you are trying to add into it. Since the Comparator always returns 1 then it always assumes the given element is new.

  14. #14
    Join Date
    Apr 2011
    Posts
    18
    Rep Power
    0

    Default

    my understanding of comparators is that the return values are:

    1 or greater - insert after
    0 - no insert
    -1 or less - insert before

    How the compare method returns this value is of no consequence to the treeset only acts on the value of the return.

    A return value of (1) means insert in the order they were received.

    The comparator does not explain the duplicates, what happen to the first set of data. There is no I can set what will do a change and existing object in the threeset. The initial results would rule out any issues in the comparator.

    Thanks for all you guys help on this.

  15. #15
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,381
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by douglas.nelson@oracle.com View Post
    The comparator does not explain the duplicates
    According to your Comparator none of the objects are ever equal, not even when they are equal, hence the duplicates in your set.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    Join Date
    Apr 2011
    Posts
    18
    Rep Power
    0

    Default

    You are correct they are never equal the treeset should put all 10 simpleVO's in the treeset, the code puts a 5 uniquely name obect in the treeset each for loop iteration, all object are treeset but only the last set is replicated. If you increase the loop counter you will see only duplicates of the last 5 objects added.

    thanks Doug

  17. #17
    Join Date
    Apr 2011
    Posts
    18
    Rep Power
    0

    Default

    I clean up the compare method make it a little easier to understand:

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
    // Class simpleComparator
    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
    /**
    * The SimpleComparator is a comparator object used for sorting simple value objects
    *
    * @version 1.0, 04/08/2011
    * @author Douglas Nelson
    * @author copyright Oracle 2011
    * @author Unauthorized use, duplication or modification is strictly prohibited.
    */
    public class simpleComparator implements Comparator<SimpleVO>, Serializable {
    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
    // start compare
    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
    /**
    * compare - return the value comparison of two objects
    *
    * @param simpleVO_1 - first object to compare
    * @param simpleVO_2 - second object to compare
    * @return int - greater then zero - insert after, less then zero - insert above, equals zero - no insert
    */
    public int compare(SimpleVO simpleVO_1, SimpleVO simpleVO_2) {
    //-----------------------------------------
    // sort first in first out, allow duplicates
    //-----------------------------------------
    return(1);

    } // end compare

    } // end SimpleComparator

  18. #18
    Join Date
    Apr 2011
    Posts
    18
    Rep Power
    0

    Default

    Got to the root of the problems from the JAVA Gods at Oracle:

    Dear Java Developer,

    Thank you for reporting this issue.

    We have determined that this report is a new bug and entered the bug into our internal bug tracking system under Bug Id: 7035120.

    You can monitor this bug on the Java Bug Database at
    Bug Database.


    Thanks everyone for your help and ideas and mostly your time.

    Thanks to you all Doug

  19. #19
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    Congrats, Doug.

    Your employers seem worried that your bug might signal some deeper malaise in the language. They are actually suppressing information on it: when I clicked your link all I got was "This bug is not available". I think we can all see just how important your bug must be to lead to such a response.

    -------------------

    The comparator does not explain the duplicates
    There are a couple of things going on here. First because of how you have written the "comparator" the tree set will quite happily add references to objects that compare equal() to objects to which it already includes references. (The snear quotes are because your "comparator" is a bit like a pair of scales that have rusted up so the LHS is perpetually down. Such a piece of kitchen equipment is junk, not a comparator.)

    Secondly, read the code I posted (and which have cost me a hard earned platinum reputation...). You add references to things, change their state, and add the references again: it's no wonder that you see the changed state repeated when you subsequently print a description of the objects or whatever.

    Try changing

    Java Code:
    //TreeSet<StrangelyCompared> test = new TreeSet<StrangelyCompared>(new StrangeComparator());
    List<StrangelyCompared> test = new ArrayList<StrangelyCompared>();

    Lists don't involve the comparator for their add() behaviour, but you will see the "duplication" in the list's contents. To that extent the repetition problem really is independent of the wonky comparator. Bottom line: if you want distinct collection elements you had better add distinct elements (as created with "new" for example) and not try to reuse existing collection elements by changing their state.
    Last edited by pbrockway2; 04-09-2011 at 01:36 AM.

  20. #20
    Join Date
    Apr 2011
    Posts
    18
    Rep Power
    0

    Default

    Great explanation, thanks for that. I have tried to use multiple linked-list but the same results I try the array idea.

    thanks Doug

Page 1 of 2 12 LastLast

Similar Threads

  1. TreeSet weirdness
    By Bulska in forum New To Java
    Replies: 3
    Last Post: 03-18-2011, 03:29 PM
  2. Please Help - TreeSet
    By Riftara in forum New To Java
    Replies: 1
    Last Post: 10-21-2010, 08:33 PM
  3. TreeSet Demonstration
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-15-2008, 07:34 PM
  4. ClassCastException in TreeSet
    By pHew in forum New To Java
    Replies: 2
    Last Post: 01-16-2008, 12:20 AM

Posting Permissions

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