CODEWITHSUNDEEP
javacollectionsimmutability
Bober02
Bober02

Reputation: 15341

immutable collections implementation

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.

Upvotes: 3

Views: 1387

Answers (4)

Rob Moffat
Rob Moffat

Reputation: 475

Clojure contains such immutable (or persistent) collections.

It provides all the collections you are after, and supports mutation-via-construction: Put simply, adding or removing new elements returns a new collection, which in general does reuse large parts of the old collection through clever use of Trie-type data structures.

On their own, these are a poor fit for using in straight Java - they're designed to use in Clojure.

Pure4j is an attempt to port these (and the immutable/value based style advocated by Clojure) to the Java language. It might be what you're after.

Disclaimer: I am the developer of Pure4J

Upvotes: 0

Java Drinker
Java Drinker

Reputation: 3167

I'm assuming that you're intention is to understand how immutable collections work within the framework of functional languages (like haskell etc.). The idea being that all collections are immutable and final, thereby avoiding all the multi-threading gotchas with regards to mutability, synchronization etc., but still allow you to add and remove and modify as though they were mutable

The best examples I have seen for this have been in the source code for Clojure. It is a language that is lisp-like and therefore deals with immutable collections as a core feature. I would highly recommend looking at how collections are implememnted in clojure, as they are bound to answer many of your questions. Likely some things will be just too complicated (I still barely understand tries). See here and good luck

Upvotes: 0

daveb
daveb

Reputation: 76211

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.

Upvotes: 6

TechTrip
TechTrip

Reputation: 4537

In terms of Java the Collections utility class is your friend. Rather than do these operations manually I would suggest working through the API given. In particular look at the immutable and unmodifiable methods.

For instance, in terms of immutable there is:

<T> List<T>
emptyList() 
          Returns the empty list (immutable).
static
<K,V> Map<K,V>
emptyMap() 
          Returns the empty map (immutable).
static
<T> Set<T>
emptySet() 
          Returns the empty set (immutable).

For unmodifiable you have:

static
<T> Collection<T>
unmodifiableCollection(Collection<? extends T> c) 
          Returns an unmodifiable view of the specified collection.
static
<T> List<T>
unmodifiableList(List<? extends T> list) 
          Returns an unmodifiable view of the specified list.
static
<K,V> Map<K,V>
unmodifiableMap(Map<? extends K,? extends V> m) 
          Returns an unmodifiable view of the specified map.
static
<T> Set<T>
unmodifiableSet(Set<? extends T> s) 
          Returns an unmodifiable view of the specified set.
static
<K,V> SortedMap<K,V>
unmodifiableSortedMap(SortedMap<K,? extends V> m) 
          Returns an unmodifiable view of the specified sorted map.
static
<T> SortedSet<T>
unmodifiableSortedSet(SortedSet<T> s)

There are others and some strategies you can implement underneath but I would start there.

Upvotes: 2

Related Questions