immutable collections implementation

Question

I have a general question with regards to immutable collections. I will use Java as a reference labguage as I know it best.

Firstly, is there a general approach to assuring immutability? By that I mean whether one should copy the entire collection, make changes and then return the new object? Is there any more complex, general approach?

Taking this a bit further, what about "obvious" (to me) mutable collections, such as trees? Usually they are implemented as Nodes with N children nodes. How would you assure immutability in this case? Clone and Copy all references recursively?

Following from the above, I was wondering whether what would be best approach to these collections:

1. List - array-based which we would copy before making changes?
2. Queues - two arrays for front and back, cloned before returning? What about bode based implementation?
3. Trees
4. Hashmap - copy the bucket array, as well as all collision lists?
5. Set

Thank you very much for your responses.

Answer 1

Happily, much of this has already been done for you, check out google guava which has ImmutableCollection, ImmutableList, ImmutableSet, ImmutableMap etc etc.

Immutability is ensured by preventing subclasses of these classes (by either making them final, or making their constructors private).

When you make an immutable collection from a mutable one, the data in the mutable collection is copied, then all mutation operations are disallowed - they will throw an exception (UnsupportedOperationException for example).

For performance reasons, the guava libraries will do their best not to copy data if they don't need to. For example, if you already have an ImmutableMap, and create a new one with ImmutableMap.copyOf(theOtherImmutableMap), then no data is copied, since we already know the other map is immutable, it's ok to have two references to the same data.