Class Vector<E>

All Implemented Interfaces:
IndexedList<E>, Iterable<E>, List<E>, Traversable<E>, Iterable<E>

public class Vector<E> extends AbstractIndexedList<E>
Vector is a general-purpose, immutable data structure.

It provides random access and updates in effectively constant time, as well as very fast append and prepend.

It is backed by a little endian bit-mapped vector trie with a branching factor of 32. Locality is very good, but not contiguous, which is good for very large sequences.

See Scala's documentation for more information on the implementation.

  • Field Details

    • EMPTY

      private static final Vector EMPTY
    • pointer

      protected final VectorPointer<E> pointer
    • startIndex

      private final int startIndex
    • endIndex

      private final int endIndex
    • focus

      private final int focus
    • dirty

      private boolean dirty
  • Constructor Details

    • Vector

      Vector(int startIndex, int endIndex, int focus)
  • Method Details

    • factory

      @NotNull public static <E> @NotNull BuilderFactory<E,Vector<E>> factory()
    • empty

      @NotNull public static <E> @NotNull Vector<E> empty()
    • size

      public int size()
      Description copied from interface: Traversable
      Returns the size of the collection.

      Warning: infinite collections are possible, as are collections that require traversal to calculate the size.

      Specified by:
      size in interface Traversable<E>
      Overrides:
      size in class AbstractTraversable<E>
    • initIterator

      private void initIterator(VectorIterator<E> s)
    • iterator

      @NotNull public @NotNull Iterator<E> iterator()
    • get

      public E get(int index)
      Description copied from interface: List
      Returns the element at the specified index in this list (zero-based).
    • checkRangeConvert

      private int checkRangeConvert(int index)
    • take

      @NotNull public @NotNull Vector<E> take(int n)
      Description copied from interface: List
      Returns a list containing the first number of elements from this list.
    • drop

      @NotNull public @NotNull Vector<E> drop(int n)
      Description copied from interface: List
      Returns a list containing all elements in this list, excluding the first number of elements.
    • isEmpty

      public boolean isEmpty()
      Description copied from interface: Traversable
      Returns true if this collection is empty.
      Specified by:
      isEmpty in interface Traversable<E>
      Overrides:
      isEmpty in class AbstractTraversable<E>
    • first

      @Nullable public E first()
      Description copied from interface: List
      Returns first element in the list or null if the list is empty.
    • tail

      @NotNull public @NotNull Vector<E> tail()
      Description copied from interface: List
      Returns a list containing all elements in the list, excluding the first element. An empty list is returned if the list is empty.
    • last

      @Nullable public E last()
      Description copied from interface: List
      Returns last element in the list or null if the list is empty.
    • range

      @NotNull public @NotNull Vector<E> range(int from, boolean fromInclusive, int to, boolean toInclusive)
      Description copied from interface: List
      Returns a list containing a contiguous range of elements from this list.
      Parameters:
      from - starting index for the range (zero-based)
      fromInclusive - if true, the element at the from index will be included
      to - end index for the range (zero-based)
      toInclusive - if true, the element at the to index will be included
    • slice

      @NotNull private @NotNull Vector<E> slice(int from, int until)
    • splitAt

      @NotNull protected @NotNull Pair<Vector<E>,Vector<E>> splitAt(int n)
    • set

      @NotNull public @NotNull Vector<E> set(int index, E elem)
      Description copied from interface: List
      Returns a list with the element set to the value specified at the index (zero-based).
    • gotoPosWritable

      private void gotoPosWritable(int oldIndex, int newIndex, int xor)
    • gotoFreshPosWritable

      private void gotoFreshPosWritable(int oldIndex, int newIndex, int xor)
    • prepend

      @NotNull public @NotNull Vector<E> prepend(E value)
      Description copied from interface: List
      Returns a list with the specified element prepended to the top of the list.
    • append

      @NotNull public @NotNull Vector<E> append(E value)
      Description copied from interface: List
      Returns a list with the specified element appended to the bottom of the list.
    • shiftTopLevel

      private void shiftTopLevel(int oldLeft, int newLeft)
    • zeroLeft

      private void zeroLeft(Object[] array, int index)
    • zeroRight

      private void zeroRight(Object[] array, int index)
    • copyLeft

      private Object[] copyLeft(Object[] array, int right)
    • copyRight

      private Object[] copyRight(Object[] array, int left)
    • preClean

      private void preClean(int depth)
    • cleanLeftEdge

      private void cleanLeftEdge(int cutIndex)
    • cleanRightEdge

      private void cleanRightEdge(int cutIndex)
    • requiredDepth

      private int requiredDepth(int xor)
    • dropFront0

      private Vector<E> dropFront0(int cutIndex)
    • dropBack0

      private Vector<E> dropBack0(int cutIndex)