Concatenating ImmutableLists

Question

I have a List<ImmutableList<T>>. I want to flatten it into a single ImmutableList<T> that is a concatenation of all the internal ImmutableLists. These lists can be very long so I do not want this operation to perform a copy of all the elements. The number of ImmutableLists to flatten will be relatively small, so it is fine that lookup will be linear in the number of ImmutableLists. I would strongly prefer that the concatenation will return an Immutable collection. And I need it to return a List that can be accessed in a random location.

Is there a way to do this in Guava?

There is Iterables.concat but that returns an Iterable. To convert this into an ImmutableList again will be linear in the size of the lists IIUC.

Answer 1

By design Guava does not allow you to define your own ImmutableList implementations (if it did, there'd be no way to enforce that it was immutable). Working around this by defining your own class in the com.google.common.collect package is a terrible idea. You break the promises of the Guava library and are running firmly in "undefined behavior" territory, for no benefit.

Looking at your requirements:

• You need to concatenate the elements of n ImmutableList instances in sub-linear time.
• You would like the result to also be immutable.
• You need the result to implement List, and possibly be an ImmutableList.

As you know you can get the first two bullets with a call to Iterables.concat(), but if you need an O(1) random-access List this won't cut it. There isn't a standard List implementation (in Java or Guava) that is backed by a sequence of Lists, but it's straightforward to create one yourself:

/**
 * A constant-time view into several {@link ImmutableList} instances, as if they were
   concatenated together. Since the backing lists are immutable this class is also
   immutable and therefore thread-safe.
 * 
 * More precisely, this class provides O(log n) element access where n is the number of
 * input lists. Assuming the number of lists is small relative to the total number of
 * elements this is effectively constant time.
 */
public class MultiListView<E> extends AbstractList<E> implements RandomAccess {
  private final ImmutableList<ImmutableList<E>> elements;
  private final int size;
  private final int[] startIndexes;

  private MutliListView(Iterable<ImmutableList<E>> elements) {
    this.elements = ImmutableList.copyOf(elements);
    startIndexes = new int[elements.size()];
    int currentSize = 0;
    for (int i = 0; i < this.elements.size(); i++) {
      List<E> ls = this.elements.get(i);
      startIndexes[i] = ls.size();
      currentSize += ls.size();
    }
  }

  @Override
  public E get(int index) {
    checkElementIndex(index, size);
    int location = Arrays.binarySearch(startIndexes, index);
    if (location >= 0) {
      return elements.get(location).get(0);
    }
    location = (~location) - 1;
    return elements.get(location).get(index - startIndexes[location]);
  }

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

  // The default iterator returned by AbstractList.iterator() calls .get()
  // which is likely slower than just concatenating the backing lists' iterators
  @Override
  public Iterator<E> iterator() {
    return Iterables.concat(elements).iterator();
  }

  public static MultiListView<E> of(Iterable<ImmutableList<E>> lists) {
    return new MultiListView<>(lists);
  }

  public static MultiListView<E> of(ImmutableList<E> ... lists) {
    return of(Arrays.asList(lists));
  }
}

This class is immutable even though it doesn't extend ImmutableList or ImmutableCollection, therefore there's no need for it to actually extend ImmutableList.

As to whether such a class should be provided by Guava; you can make your case in the associated issue, but the reason this doesn't already exist is that surprisingly few users actually need it. Be sure there isn't a reasonable way to solve your problem with an Iterable before using MultiListView.