Immutable collections in Java

Question

I have recently started looking at GUAVA's collections, namely ImmutableList and that seems rather cumbersome (with the builder instance etc.) Is there a library that would mimic a more "natural" way of how the collections should behave (scala's http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List is one example). I would like something that allows addition/removal etc. but preserving immutability and, perhaps for the purpose of performance, reuses parts of old list.

Answer 1

Clojure contains such immutable (or persistent) collections.

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.

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

Answer 2

There is an ImmutableArrayList (and other immutable collections) in Goldman Sachs Collection library

See ImmutableArrayList.java, methods newWith(T t) and newWithout(T t)

Answer 3

If I understand you correctly, you want an immutable list that has convenient add/remove methods that return new list instances that reuse as much of the original list structure as possible. You could do something like this:

public abstract class ImmutableList<T> implements Iterable<T> {
    /**
     * Adds an element to the head of the list, returning the new list.
     *
     * @param o The element to be added to the list.
     * @return The list consisting of the element <var>o</var> followed by
     *         this list.
     */
    public final ImmutableList<T> add(final T o) {
        return new Node<>(o, this);
    }

    /**
     * Removes the element <var>o</var> resulting in a new list which
     * is returned to the caller.
     *
     * @param o The object to be removed from the list.
     * @return A list consisting of this list with object <var>o</var> removed.
     */
    public abstract ImmutableList<T> remove(final T o);

    public abstract boolean isEmpty();
    public abstract int size();

    public abstract boolean contains(final T o);

    private ImmutableList() {}

    /**
     * Returns a "standard" enumeration over the elements of the list.
     */
    public Iterator<T> iterator() {
        return new NodeIterator<>(this);
    }

    /**
     * The empty list.  Variables of type ImmutableList should be
     * initialised to this value to create new empty lists.
     */
    private static final ImmutableList<?> EMPTY = new ImmutableList<Object>() {
        @Override
        public ImmutableList<Object> remove(final Object o) {
            return this;
        }

        @Override
        public boolean isEmpty() {
            return true;
        }

        @Override
        public int size() {
            return 0;
        }

        @Override
        public boolean contains(final Object o) {
            return false;
        }
    };

    @SuppressWarnings("unchecked")
    public static <T> ImmutableList<T> empty() {
        return (ImmutableList<T>)EMPTY;
    }

    public static <T> ImmutableList<T> create(final T head) {
        return new Node<>(head, ImmutableList.<T>empty());
    }

    static class Node<T> extends ImmutableList<T> {
        private final int _size;

        private Node(final T element, final ImmutableList<T> next) {
            _element = element;
            _next = ArgumentHelper.verifyNotNull(next, "next");
            _size = next.size() + 1;
        }

        public ImmutableList<T> remove(final T old) {
            if (_element == old) {
                return _next;
            }
            else {
                final ImmutableList<T> n = _next.remove(old);
                if (n == _next) {
                    return this;
                }
                else {
                    return new Node<>(_element, n);
                }
            }
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        @Override
        public int size() {
            return _size;
        }

        @Override
        public boolean contains(final T o) {
            return Objects.equals(_element, o) || _next.contains(o);
        }

        private final T _element;
        private final ImmutableList<T> _next;
    }

    private class NodeIterator<T> implements Iterator<T> {
        private ImmutableList<T> _current;

        private NodeIterator(final ImmutableList<T> head) {
            _current = ArgumentHelper.verifyNotNull(head, "head");
        }

        public boolean hasNext() {
            return !_current.isEmpty();
        }

        public T next() {
            final T result = ((Node<T>)_current)._element;
            _current = ((Node<T>)_current)._next;
            return result;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

For this implementation, a new list is build by adding item(s) to ImmutableList.empty().

Note that this is not a particularly wonderful implementation; new elements are appended to the beginning of the list, as opposed to the end. But perhaps this will give you an idea of where to start.

Answer 4

Immutable means the one that doesn't change, so the answer is no. You can't mutate an immutable list (whoa!). The builder that's shipped with list utilities is good as long as you just want to initialize the list with some content and leave it with them, so I'd suggest you to review your app's architecture.

About the reusing parts of old list - if the list is mutable, than, by mutating it you are risking with the immutability of state of the list from which the current one was derived. But, if the instances are both immutable, you actually do refer to the previous list because you can reuse its parts as long as it doesn't change, and immutable items don't ever change.

Answer 5

Your requirements show you misunderstood the purpose of these tools. An immutable list always needs a builder because it must not change after the constructor has been called. That's the whole purpose of immutables. They don't change, ever. There is no "setup stage."

If you don't need that, simply wrap your existing list in Collections.unmodifiableList().

The drawback is, of course, that someone might keep a reference to the original list and modify it. Or a hacker might peek into the wrapper, get the underlying list and start to mess with it.