Java Collection For Ensuring Uniqueness While Providing References

Question

I have a structure like this:

public class Foo
{
    public int A ;
    public int B ;
    public int C ;
}

I need to add these to a collection one-by-one in such a way that I end up with no more than one copy where A, B, and C are all equal. I also need references to the objects for another class, like this:

public class Bar
{
    public Foo A ;
    public Foo B ;
    public Foo C ;
}

I tried using a TreeSet < Foo >, which worked to ensure uniqueness, but I cannot get a reference back out of a TreeSet (only a boolean of whether or not it is/was in the set), so I can't pass that reference on to Bar. I tried using a TreeMap < Foo , Integer > along with an ArrayList < Foo >, and that works to ensure uniqueness and to allow me to get references to the objects, but it wastes a massive amount of time and memory to maintain the ArrayList and the Integers.

I need a way to say "If this Foo is not yet in the collection, add it; Otherwise, give me the Foo already in the collection instead of the one I created to check for its presence in the collection.".

(It just occurred to me that I could do something like TreeMap < Foo , Foo >, and that would do what I want, but it still seems like a waste, even though it's nowhere near as much of one, so I'll continue with this question in hope of enlightenment.)

(And yes, I did implement Comparable to do the uniqueness-check in the trees; That part works already.)

Answer 1

I would use e.g. a TreeMap<Foo, Foo> object. When you put a new Foo in the map, specify it as both the key and the value. This lets you use get to return the Foo already in the collection. Note that you have to handle the case of a Foo already being in the map yourself.

Answer 2

A solution in Sorted collection in Java by Neil Coffey gave what I need, which is using ArrayList < Foo > and always doing Collections . binarySearch to get either the index of the element already in the list, or the point at which the element should be inserted into the list.

This maintains a constantly-sorted list at O(log n) time like a tree, but allows retrieval of existing instances at the same time. Unfortunately, it has O(n) insertion time, but that isn't the end of the world in this case, though it's still suboptimal.

Answer 3

To ensure uniqueness in a Set, you need to over-ride equals() and hashcode() so that two instances of Foo with the same A,B,C are .equals().

Ideally, anything you put in a Set should be immutable (i.e. your three ints should be final. From the documentation:

Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set.

Unfortunately, Set doesn't provide any method that allows you to get the actual instance - you would need a Map or another collection as you have already tried.

Update another approach would be to create your own modified version of TreeSet based on the JDK source code to add a method to obtain the instance you need (extending the standard TreeSet won't do what you need because the relevant fields are private, unless you use reflection to access them).

Answer 4

Apparently a TreeList is based on a TreeMap thus making this approach redundant, but I thought I'd just comment on it anyway for completeness.

If a copy of a Foo object exists in the TreeList (e.g. as returned by contains) then you can retrieve the copy using the tailSet and first methods.