java: copy-on-write data structure?

Question

Is there anything in Java that implements something like the following

interface MSet<T> extends Iterable<T> {
    /**
     * return a new set which consists of this set plus a new element.
     * This set is not changed.
     */
    MSet<T> add(T t);

    /**
     * return a new set which consists of this set minus a designated element.
     * This set is not changed.
     */
    MSet<T> remove(T t);
}

edit: I want something like CopyOnWriteArraySet, except that class is mutable and I want something that is an immutable set that allows creation of a new set. The reason for this is that I need to hand out references to the old set and leave them immutable.

edit 2: how does Scala implement scala.collection.immutable.Set? This is the kind of behavior I need, just that I don't want to suck in all of Scala just for this.

Answer 1

CopyOnWriteArraySet is similar. However, the copying is internal, so it does not return a reference to a new object.

Answer 2

There are copy-on-write data structures in Java, for example the CopyOnWriteArrayList, however the API is slightly different than the one you have suggested; rather than returning a new object, it has the same API as the other collections, but merely creates a separate copy of the array internally.'

There is no type out of the box with the API that you want; however, it should be fairly trivial to implement; simply duplicate the collection, perform the mutating operation on the duplicate, and return it.

Answer 3

No, there isn't such a collection, because it does not implement Collection (neighter List, nor Set). You will have to implement it yourself, perhaps based on ArrayList or on CopyOnWriteArrayList

Answer 4

Use the Google Collections library Immutable* for all your immutable collection needs. I suppose you'll need a light-weight wrapped class - which can be done very easily with a Forwarding* (also in GC) - that spawns new immutable (or mutable, whatever) on add/remove operations. Finally, if your modifications don't need to themselves be allowed to spawn new modifications, you can implement those operations using the various options in the static collection helper libraries in GC (Iterables, Lists, Sets, etc) to get views (re sets : union, intersection, filter).

edit: however, google-code is veeeeery slow at the moment - might have to wait a bit to check it out.