# Thread: bug? list and treeSet

1. Join Date
Apr 2011
Posts
18
Rep Power
0

## 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...!

2. Originally Posted by Fubarable
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

3. 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

4. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,565
Rep Power
12
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;
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;
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.)

5. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18
Originally Posted by pbrockway2
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...:)

6. Join Date
Apr 2011
Posts
18
Rep Power
0
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).

7. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,565
Rep Power
12
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...

8. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,565
Rep Power
12
... 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.

9. Join Date
Apr 2011
Posts
18
Rep Power
0
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.

10. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18
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.

11. Originally Posted by douglas.nelson@oracle.com
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

12. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18
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.

13. Join Date
Apr 2011
Posts
18
Rep Power
0
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.

14. Originally Posted by douglas.nelson@oracle.com
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

15. Join Date
Apr 2011
Posts
18
Rep Power
0
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

16. Join Date
Apr 2011
Posts
18
Rep Power
0
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 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

17. Join Date
Apr 2011
Posts
18
Rep Power
0
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 to you all Doug

18. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,565
Rep Power
12
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 02:36 AM.

19. Join Date
Apr 2011
Posts
18
Rep Power
0
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 Last

#### Posting Permissions

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