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

Why do you need it to be exactly the same instance? That sounds like a dangerous idea. But you can probably easily extend `TreeSet` with the method you need. — biziclop, Nov 10 '12 at 20:44
So that anything else I add to `Foo` which does not contribute to uniqueness (metadata, basically) will be maintained in `Bar`. — JAKJ, Nov 10 '12 at 20:48
The `Bar` class contains the instances of `Foo` which I first have to check for existence and then store in `Bar`. What you just said makes no sense. — JAKJ, Nov 10 '12 at 20:50
(Nevermind, I see what you're saying now, but that won't work in my case because the same `Foo` could be in multiple `Bar`, and I would have to issue additional equality checks to the `Foo` in the `Bar` to figure out which one was my reference.) — JAKJ, Nov 10 '12 at 20:58

score 1 · Accepted Answer · answered Nov 10 '12 at 20:44

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.

answered Nov 10 '12 at 20:44

Neil

54,642
8
60
72

I posted an answer below as to a way to do what I want with no wasted memory, but at a cost of extra time. I'm going to go ahead and accept this answer, because it is the other way around, wasting a bit of memory in exchange for wasting no time. Both answers work, depending on whether time or memory is more important. – JAKJ Nov 10 '12 at 20:56
Apparently a `TreeList` is based on a `TreeMap` so there's nothing to waste! – Neil Nov 11 '12 at 00:31
No waste here; a `TreeMap` takes exactly as much memory per entry as a `TreeSet`. – Louis Wasserman Nov 11 '12 at 18:02
I've done it again here. I meant to say a `TreeSet` is based on a `TreeMap` of course, so that using a `TreeMap` instead uses up about the same amount of memory (although I'm not exactly convinced by @LouisWasserman's claim that it's exactly the same...) – Neil Nov 11 '12 at 18:07
Sorry, that was wrong. `TreeSet` takes a couple bytes _more_ than `TreeMap`. (Basically, `TreeSet` is just [implemented as a wrapper around a `TreeMap`.](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/TreeSet.java)) Since you're not actually duplicating the object in a `TreeMap` -- you're just storing two references -- the math works out. You might also find http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures helpful. – Louis Wasserman Nov 11 '12 at 18:18

DNA · Answer 2 · 2012-11-10T21:56:02.120

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

score 0 · Answer 3 · edited May 23 '17 at 10:24

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.

score 0 · Answer 4 · answered Nov 11 '12 at 00:35

0

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.

answered Nov 11 '12 at 00:35

Neil

54,642
8
60
72

Java does not have a TreeList that I can find. I assume you mean the one in the Commons API? – JAKJ Nov 11 '12 at 01:29
Sorry, your question was clearly about a `TreeSet`, and this answer was also supposed to be a `TreeSet`. I've no idea how I managed to write `TreeList`. Did you want me to edit my answer? – Neil Nov 11 '12 at 18:05

Java Collection For Ensuring Uniqueness While Providing References

4 Answers4