Implementing realtime sorting Set (i.e. SortedSet)
I am implementing a class which must maintain a collection of its children. I would like the collection to be sorted and no duplicated. Therefore, it looks like it should be SortedSet.
The children object does not override equals method. The objects is differentiate by it instance reference. For the sorting rules, I define a custom Comparator which has rules according to subset of object attributes.
The problem is that my Comparator is not consistent with equals method of the children objects. The children equality is determined by their instance reference, but the Comparator take only subset of attribute into account - this is intentional.
Therefore, I could not use the SortedSet interface because I could not obey the contract in this interface.
My question is, how could I workaround this limitation or implement the functionality with alternative approaches?
[902 byte] By [
vairoja] at [2007-10-2 20:05:29]
That only holds when none of the classes you use in your set override hashCode(), i.e. the implementation of hashCode() in Object may return distinct integers for distinct objects, but that's not a guarantee the objects you're dealing with do the same. Even Object.hashCode() does not provide absolute certainty that you will get distinct integers: "As much as is reasonably practical,".
If you don't take this into account, things will very likely go wrong at an unexpected and inopportune moment in the future.
In your comparator, if they are found not equal, you are fine. Next check for equality using your equals(). If they are equal, again you are fine. If they are not equal, then you have to do something special. One possibility is to have a private static member uniqueId that you assign to each instance in the constructor and then bump by 1. That unique id would be checked by your comparator if necessary.
With that implementation, your comparator would sort by your initial criteria, and objects with matching criteria would be sorted by order of instanciation.
In my case, the comparator is specific to a class. And according to that class, both equals and hashCode is not overriden and therefore inherit from java.lang.Object.
Thank you for pointing out the "As much as is reasonably practical" phrase, therefore, I might need to find another approach on finding a unique identifier for each object.
I am not very fond of uniqueId field approach. As each object is unique in same way already, there should be a way to determine this uniqueness, right?
> Therefore, I could not use the SortedSet interface
> because I could not obey the contract in this
> interface.
I think if you look at the API for SortedSet you will see that this isn't really a problem. I would avoid all the navel staring and just implement it as you have planned. It is unlikely you will run into issues.
Also note that the problem is with the Set interface, not SortedSet per se as SortedSet is defined with Comparable/Comparator.
