How to have a TreeSet that is "incompatible with equals"
I have read numerous posts about TreeSets, Comparable / Comparator Interfaces, equals, compareTo, comparison methods, and I know the API says you should make your order "consistent with equals" or strange things might happen.
But in my case, and I think this is a fairly general case, I really need a TreeSet order that is "incompatible with equals".
Suppose we are doing some sort of heuristic lookup and we are expanding (or generating) new states starting from the root (initial) state. And we put the new (extended / generated) states into a TreeSet, which we usually call an open list. We'd like to use the TreeSet container because we don't want to duplicate states in our public list.
Each generated / extended state is estimated by a cost function and yields a heuristic value that indicates the quality of the state. We want the TreeSet (open list) to be ordered by this value. We want to have the best states (which have the best value) at the top of the TreeSet.
Now there is a problem. To place an order by value, we need to give the TreeSet a comparator that compares the value. But two different states can have the same cost / heuristic value. I want both of these states to be on my open list because they are not "equal". But the comparator needs to return 0 from the compare method because they have the same cost. And since it is, different states with the same value will not be inserted into the list.
I want to give a simple example to make it clearer. Let's say our states are strings showing binary data, and the cost function counts the number of "1s" in the string.
Let's assume these are the generated states and their corresponding cost values.
No State Cost
1 01001001 3
2 01101001 4
3 10001001 3
4 01001111 5
As you can see, these 4 states are all different. They are "not equal". But even if state-1 and state-3 are different, they have the same value "3". So when we order our TreeSet at cost, state-3 will not be added to the TreeSet because there is already an item with the same cost value. But we need this state to be added to the list, because it is absolutely correct, different, new state.
How can I solve this problem?
Thank.
source to share
You just need a comparator that does two things:
- Costs are compared first. Lower costs will be ranked first.
- If the costs are equal (and only then), it uses an arbitrary constraint for the rank states. (For example, it compares state identifiers.) It is important that while the link breaker can be arbitrary, it must be deterministic only depending on the fields in the state object, which will remain constant throughout the life of the object in the set.
This is a kind of lexicographic ordering and is fully compliant equals()
. (Because the comparator will return 0 if the if equals()
returns true.)
Put aside: Depending on your specific use case, you might be better off PriorityQueue
than a TreeSet
. Then you don't have to worry about multiple items with the same priority.
source to share
What is meant by "consistent with equals" simply means that for two objects that are equal to each other, the comparator must return 0, or:
obj1.equals(obj2)
must be the same logical value as comparator.compare(obj1, obj2) == 0
;
But you can just use your own comparator, which puts low cost ahead of high cost, if the comparator returns 0 for equal states.
source to share