Class Chain<T>

java.lang.Object
java.util.AbstractCollection<T>
java.util.AbstractList<T>
com.google.mu.collect.Chain<T>
All Implemented Interfaces:
Iterable<T>, Collection<T>, List<T>, SequencedCollection<T>
public final class Chain<T> extends AbstractList<T>
Immutable List implementation that supports O(1) concatenation.

At high level, this class provides similar behavior as Stream.concat() or Guava Iterables.concat(), except it's not recursive. That is, if your Chain is the result of 1 million concatenations, you won't run into stack overflow error because under the hood, it's a heap-allocated immutable tree structure.

The expected use case is to concatenate lots of smaller Chains using the concat() methods to create the final Chain. O(n) materialization cost will be (lazily) incurred upon the first time accessing the elements of the final Chain through the List interface such as List.get(int), List.equals(java.lang.Object), AbstractCollection.toString() etc. You may also want to copy the final Chain into a more conventional List such as Guava ImmutableList.

On the other hand, it's inefficient to materialize, concatenate then materialize the concatenated Chain...

Unless explicitly documented as lazy or an O(1) operation, all List methods will materialize the elements eagerly if not already.

Null elements are not allowed.

While bearing a bit of similarity, this class isn't a persistent data structure. Besides the O(1) concatenation, it's a traditional immutable List supporting no other functional updates. Concatenation is O(1) as opposed to O(logn) in persistent lists; and random access is also O(1) (after one-time lazy materialization).

Since:
8.1