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.
Iterableis mutable? all I see in it isiterator()– AbaseImmutableList? Would it be acceptable for it to be aListthat cannot be mutated? – CollectorImmutableList. In practice when used with small number of underlying lists, performance will not be a concern. – ComrasConcatenatedListthat uses many small lists and therefore approaches O(n) time. Hiding that behavior from the caller leads to performance problems. – Collector