Java Immutable List

Question

I am currently building an LRU cache where I need to store the last N inserted items. Items will be inserted frequently (i.e. many write operations) and read operations will typically return a large number of events always strictly in sequence albeit starting at an arbitrary point in the cache. For example, suppose the cache contains events:

[1, 2, 3, 4, 5, 6]

A legal read operation would be to return an iterator over events [2, 3, 4].

Due to read operations potentially being long-lived I'd like to use a data structure where I can safely iterate over a logical copy of the sequence for each read attempt, thus preventing a cache read from holding up any subsequent writes. However, using a vanilla Java ArrayList or LinkedList implies a large overhead in making a full copy.

My question: Are there any 3rd party Java libraries that provide immutable data structures similar to Scala, whereby attempts to modify the data structure return a new immutable copy (which is in fact based on the original data structure and hence the copy operation is very fast)? Obviously the data structure could not conform to the Java Collections API as operations like add(T) would need to return the new collection (rather than void).

(Please no comments / answers citing this as a case of premature optimisation.)

Thanks in advance.

Note

Guava's ImmutableList nearly achieves what I need: It allows to you call copyOf where the copy typically references the original (avoiding performing an actual copy). Unfortunately you can't go the other way and add an item to the list and get back a copy that includes the new element.

Answer 1

Functional Java comes in the form of a library (not a different language) and provides immutable collections. Not sure if it'll fit your needs but worth a try. The List Sort example of Functional Java is also available here.

Answer 2

JDK 9 has new of() method factories. E.g. you can have an immutable Set as

Set<Integer> intSet = Set.of(1, 2, 3);

You can do the same with a List, e.g.

List<String> stringList = List.of("A", "B", "C");

and a Map:

Map<String, String> doubleMap = Map.of("key1", "val1", 
                                       "key2", "val2");

Answer 3

Pure4J

Provides immutable collections via copies of the Clojure persistent collections classes. It might not be exactly what you are after, as it is about enforcing pure functional semantics on (subsets of) java programs.

On the other hand, it has immutability guarantees for both elements and collections. When you add/remove an element from a collection you get back a new collection and the original remains unchanged.

Answer 4

Guava

Google Guava can meet your needs.

When you want to update the cache, use Guava's builder pattern to create a new cache from the old one, then delete the old cache.

To update the cache, create an ImmutableList.Builder() and initialize it with your existing ImmutableList. Modify the list through the Builder interface. Then call .build() to get a new ImmutableList, and delete the old cache. The new cache will reuse all the old objects, so this is a very lightweight operation.

When someone wants an immutable copy of the cache (or one of its items), return copyOf(), and they'll get access to an immutable snapshot.

Caveat, if you're working with threads, make sure you wrap the list in an object and synchronize it's get() & insert() methods.

You can read more at the Guava site.

Answer 5

It looks like you want to implement a singly-linked list here, which can then be shared by different wrapper objects. Do you ever want to remove elements, or do you only append new ones?

If there is only adding and no removal, I suppose a simpler variant of CopyOnWriteArrayList, which only makes the copy whenever the old array is full, could do. The sublist() methods then would simply create a new wrapper object.

/**
 * A list which only supports appending objects.
 */
public class OnlyAppendingList<E> extends AbstractList<E> {

    private Object[] data;
    private int len;

    public int size() {
        return this.len;
    }

    public E get(int index) {
        if(index >= this.len)
           throw new IndexOutOfBoundsException(index + " >= " + this.len);
        @SuppressWarnings("unchecked")
        E res = this.data[index];
        return res;
    }

    public boolean add(E element) {
        if(len == data.length) {
             this.resize();
        }
        this.data[this.len] = element;
        this.len++;
        return true;
    }

    private void resize() {
        this.data = Arrays.copyOf(data, data.length * 2 +2);
    }

    public void add(int index, E element) {
       if(index > this.len) {
          throw new IndexOutOfBoundsException(index + " > " + len);
       }
       if(index < this.len) {
           throw new UnsupportedOperationException("we only support appending, not insertion!");
       }
       this.add(element);
    }


    /**
     * Returns an immutable sublist of this list.
     */
    public List<E> subList(final int fromIndex, final int toIndex) {
        // TODO: bounds checks
        return new SubList<E>(this.data, fromIndex, fromIndex - toIndex);
    }

    private static class SubList<E> extends AbstractList<E> {
        private Object[] data;
        private int start;
        private int len;

        SubList(Object[] data, int start, int len) {
            this.data = data; this.start = start; this.len = len;
        }

        public int size() {
            return this.len;
        }

        public E get(int index) {
            if(index >= this.len)
               throw new IndexOutOfBoundsException(index + " >= " + this.len);
            if(index < 0)
               throw new IndexOutOfBoundsException(index + " < 0");

            @SuppressWarnings("unchecked")
            E res = this.data[index + start];
            return res;
        }
        public List<E> subList(int from, int to) {
            // TODO: bounds check
            return new SubList(data, start + from, to - from);
        }
    }
}

If this is modified by multiple threads, you should make the add method synchronized and the len variable volatile, I think. (I did not completely check that it then is threadsafe.)

Answer 6

Have you looked at the CopyOnWriteArrrayList? Each mutation to the list will copy all contents to a new backing array leaving the current array you may be iterating on uneffected.

Answer 7

Google Guava has immutable collections.