Re: Collection of distinc objects

D?ejm wrote:


There's always:

public class IdentityHashSet<T> extends AbstractSet<T> {
    private IdentityHashMap<T, T> map = new IdentityHashMap<T, T>();

    public boolean add (T object) {
        boolean result = map.containsKey(object);
        map.put(object, object);
        return result;
    }

    public int size () {
        return map.size();
    }

    public Iterator<T> iterator () {
        return map.keySet().iterator();
    }
}

AIUI, this should work, and support adding and removing objects from the
set, including removing objects through the iterator. Since it's only
fourteen lines of code (excluding blank lines, comments, Javadoc...)
it's surprising it's absent from java.util!

And of course there's the

public class Holder<T> {
    public final T contents;
    public Holder<T> (T contents) { this.contents = contents; }
    @SuppressWarnings("unchecked")
    public boolean equals (Object o) {
        return this == o ||
            (o instanceof Holder &&
                ((Holder)o).contents == contents);
    }
    public int hashCode () {
        return System.identityHashCode(contents);
    }
}

Some Holder<T>s put into a HashSet will behave as the Ts put into the
IdentityHashSet. (Separate Holders with the same T compare equal, but
distinct T instances, even if those compare equal, produce
unequal-comparing holders.)

Read the caveats in Sun's API docs regarding IdentityHashMap<K, V>;
they'll apply also to IdentityHashSet<T> and HashSet<Holder<T>>.

See an earlier posting of mine to this same thread for a way to get this
behavior with TreeSet (distinct instances behaving distinctly). It
requires being able to give each distinct object a distinct "instance
number" to compare with a comparator. That's easy to do if you can make
the objects of a class you create, as I demonstrated there. If not, you
can use:

public class InstanceComparator<T> implements Comparator<T> {
    private int next = 0;
    public int compare (T t1, T t2) {
        int i = getID(t1);
        int j = getID(t2);
        return (i < j)?-1:((i > j)?1:0);
    }
    private WeakHashMap<Holder<T>, Integer> map = new
        WeakHashMap<Holder<T>, Integer>();
    private int getID (T t) {
        Holder<T> h = new Holder<T>(t);
        Integer i = map.get(h);
        if (i != null) return i.intValue();
        map.put(h, Integer.valueOf(next));
        return next++;
    }
}

This uses the earlier Holder<T> class as well as a WeakHashMap of
Integers under the hood and an incremented "next id" number to generate
id numbers and associate these with distinct instances of T (even if
they compare equal). The WeakHashMap of Holder<T> gives us a
"WeakIdentityHashMap", so the mappings for objects that are no longer
used go away instead of eating up memory, while keeping the
IdentityHashMap semantics. Different instances of the comparator have
their own mappings. This works with any object of reference type,
including boxed integers, one-element arrays, and so forth.

Note that the above class depends on the semantics that even distinct
Holders may compare equal, but that Holders compare equal iff the held
objects are identity-equal. This is true for the Holder implementation
in this posting but not for the one in the earlier posting.

Implementing an actual WeakIdentityHashMap<K, V> class is left as an
exercise for the reader but shouldn't be too difficult since 90% of the
work is already done with Holder<K> and WeakHashMap<K, V>. :)

And of course the Holder<T> class is just begging for expanding to
implement Comparable<T> and use a static instance of
InstanceComparator<T> under the hood...not to mention maybe a renaming
to make it's exact purpose clearer, which is to totally subvert the
normal object-comparison semantics. ;)

All of the code above modulo typos and "Organize Imports" (ctrl+O in
Eclipse).