Package com.google.mu.collect

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

  • Method Details

    • of

      public static <T> Chain<T> of(T element)
      Returns a Chain with a single element.

    • of

      @SafeVarargs public static <T> Chain<T> of(T first, T... remaining)
      Returns a Chain with first followed by remaining.

    • concat

      public static <T> Chain<T> concat(Chain<? extends T> left, Chain<? extends T> right)
      Returns a new Chain concatenating elements from the left Chain and the right Chain, in O(1) time.

      Encounter order of elements is preserved. That is, concat([1, 2], [3, 4]) returns [1, 2, 3, 4].

    • concat

      public Chain<T> concat(T lastElement)
      Returns a new Chain concatenating elements from this Chain followed by lastElement, in O(1) time.

    • size

      public int size()
      Returns the size of the chain. O(1) operation.
      Specified by:
      size in interface Collection<T>
      Specified by:
      size in interface List<T>
      Specified by:
      size in class AbstractCollection<T>

    • isEmpty

      public boolean isEmpty()
      Always false. O(1) operation.
      Specified by:
      isEmpty in interface Collection<T>
      Specified by:
      isEmpty in interface List<T>
      Overrides:
      isEmpty in class AbstractCollection<T>

    • stream

      public Stream<T> stream()
      Returns a lazy stream of the elements in this list. The returned stream is lazy in that concatenated chains aren't consumed until the stream reaches their elements.

    • getFirst

      public T getFirst()
      Returns the first element. Will override the SequencedCollection method. Takes O(1) time.

    • get

      public T get(int i)
      Specified by:
      get in interface List<T>
      Specified by:
      get in class AbstractList<T>

    • iterator

      public Iterator<T> iterator()
      Specified by:
      iterator in interface Collection<T>
      Specified by:
      iterator in interface Iterable<T>
      Specified by:
      iterator in interface List<T>
      Overrides:
      iterator in class AbstractList<T>

    • spliterator

      public Spliterator<T> spliterator()

    • listIterator

      public ListIterator<T> listIterator()
      Specified by:
      listIterator in interface List<T>
      Overrides:
      listIterator in class AbstractList<T>

    • listIterator

      public ListIterator<T> listIterator(int index)
      Specified by:
      listIterator in interface List<T>
      Overrides:
      listIterator in class AbstractList<T>

    • subList

      public List<T> subList(int fromIndex, int toIndex)
      Specified by:
      subList in interface List<T>
      Overrides:
      subList in class AbstractList<T>