programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Some overlaps in the game map? even with same x and z coordinates

Jacky Luk
Ranch Hand
Posts: 634

I've added some nodes to the SortedSet, in theory, the SortedSet shouldn't contain duplicate nodes
on my map, but the result isn't it. Why? There are still duplicate nodes on the map.
From each iteration of the function where it starts to add nodes to this SortedSet,
it even has been cleared as well. But I don't think I will make a difference.
Just wondering why are there duplicate nodes in my map?
Could anyone please lend me a hand?
Thanks
Jack

Paweł Baczyński
Bartender
Posts: 2083
44
• 1
I believe your comparator is not transitive.

If you have three Nodes:
1. id = 1, x = 0, z = 0, g = 2
2. id = 2, x = 0, z = 1, g = 1
3. id = 3, x = 0, z = 0, g = 0

Then according to your comparator:
node1 > node2 (because node1.g > node2.g)
and
node2 > node3 (because node2.g > node3.g)

but
node1 = node3 (because node1.x = node3.x and node1.z = node3.z)

Not being transitive violates the contract of compare method and as the result you should not expect sorting to work properly.

Jacky Luk
Ranch Hand
Posts: 634
Hi Pawel,

I haven't got this working yet like this.

There are still repeated nodes....
Thanks
Jack

Paweł Baczyński
Bartender
Posts: 2083
44
Your new comparator can never return a negative value.

So it violates this rule:
The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

What do you mean by repeated node? A node with the same coordinates as some other node?

Jacky Luk
Ranch Hand
Posts: 634
Paweł Baczyński wrote:Your new comparator can never return a negative value.

So it violates this rule:
The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

What do you mean by repeated node? A node with the same coordinates as some other node?

Yes, not sure why there can be 2 nodes in the SortedSet with the same x and z coordinates.
the g values can be don't-care
Thanks
Jack

Paweł Baczyński
Bartender
Posts: 2083
44
As long as you are breaking the contract of the Comparator interface you can not be sure of anything.

Please post some code that shows how you are populating your set.

Jacky Luk
Ranch Hand
Posts: 634

Thanks Pawel for your kindred help
Jack

Paweł Baczyński
Bartender
Posts: 2083
44
Well, that is too much code.

Can you post a SSCCE?

=============
This compare method is still not transitive.
id = 1, x = 1, z = 1
id = 2, x = 1, z = 2
id = 3, x = 1, z = 1

node1 < node2 (because node1.id < node2.id)
node2 < node3 (because node2.id < node3.id)

but

node1 = node3 (because node1.x = node3.x and node1.z = node3.z)

You need to fix that before you look for possible causes elsewhere.

Jacky Luk
Ranch Hand
Posts: 634
Okay, I've solved that

Campbell Ritchie
Marshal
Posts: 56536
172
Jacky Luk wrote:Okay, I've solved that . . .
O good grief! I won't even read such code!