bug? list and treeSet

[douglas.nelson@oracle.com]

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

[Fubarable]

I think I speak for all in wishing you much luck in solving this!

[JosAH]

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

[DarrylBurke]

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

[pbrockway2]

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

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

[Tolls]

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...:)

[douglas.nelson@oracle.com]

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

[pbrockway2]

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

[pbrockway2]

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

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

[Tolls]

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.

[JosAH]

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

[Tolls]

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.

[douglas.nelson@oracle.com]

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.

[JosAH]

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

[douglas.nelson@oracle.com]

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

[douglas.nelson@oracle.com]

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

[douglas.nelson@oracle.com]

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

[pbrockway2]

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

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

[douglas.nelson@oracle.com]

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

thanks Doug