Class ZenoChain<T>

  • Type Parameters:
    T - the type of the items in the list
    All Implemented Interfaces:
    java.lang.Iterable<T>

    public class ZenoChain<T>
    extends java.lang.Object
    implements java.lang.Iterable<T>
    An implementation of sequences as a list-of-lists, where the sublists at the end of the master list tend to be small, and the sublists at the start tend to be larger (or the other way around if the list is built by prepending items rather than appending them). The number of sublists is of the order log(N) where N is the length of the sequence, giving logarithmic performance or better for appending items to either end of the sequence, or for getting the Nth item.

    This is an immutable data structure; updating operations create a new ZenoChain leaving the original unchanged.

    In effect the ZenoChain is a tree with a constant depth of 3, implemented as a list of lists.

    For a list built by appending to the end, the size of sublists goes as follows as the list grows: (1).. (32).. (32,1).. (32,32).. (64,1).. (64,32).. (64,32,1).. (64,32,32).. (64,64,1).. (64,64,32).. (128,32,1).. (128,64,1).. (128,64,32,1).. For a list of 20,000 items we get 10 sublists with sizes (8192, 4096, 4096, 2048, 1024, 256, 128, 64, 64, 32). The exact numbers don't matter, the important thing is that the number of sublists is log(N) with shorter sublists at the end of the sequence where append/prepend operations take place.

    When two lists are concatenated, the two master lists are first concatenated, followed by a consolidation to combine short lists now appearing near the middle of the structure, to reduce the number of sublists.

    • Constructor Summary

      Constructors 
      Constructor Description
      ZenoChain()
      Create an empty sequence
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      ZenoChain<T> add​(T item)
      Append an item to this list.
      ZenoChain<T> addAll​(java.lang.Iterable<? extends T> items)
      Append a sequence of items.
      ZenoChain<T> concat​(ZenoChain<T> other)
      Concatenate two ZenoChains to form a new ZenoChain, leaving the original operands unchanged
      T get​(int n)
      Get the item at position n, zero-based
      ZenoChain<T> insert​(int n, T value)
      Insert an item at position n, zero-based
      boolean isEmpty()
      Ask if the list is empty
      boolean isSingleton()
      Ask if the list is a singleton
      java.util.Iterator<T> iterator()
      Iterate over the items
      ZenoChain<T> prepend​(T item)
      Prepend an item.
      ZenoChain<T> remove​(int n)
      Remove the item at position n, zero-based
      ZenoChain<T> replace​(int n, T value)
      Replace the item at position n, zero-based
      java.lang.String showMetrics()
      Diagnostic display of a ZenoChain, exposing its internal structure
      int size()
      Get the size of the list
      ZenoChain<T> subList​(int start, int end)
      Get a sublist of this list.
      java.lang.String toString()
      Get a string representation of the ZenoChain.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.lang.Iterable

        forEach, spliterator
    • Constructor Detail

      • ZenoChain

        public ZenoChain()
        Create an empty sequence
    • Method Detail

      • add

        public ZenoChain<T> add​(T item)
        Append an item to this list. This is an immutable operation; the original list is unchanged
        Parameters:
        item - the item to be appended
        Returns:
        the list that results from the append operation
      • prepend

        public ZenoChain<T> prepend​(T item)
        Prepend an item. This is an immutable operation; the original list is unchanged.
        Parameters:
        item - the item to be added at the start of the sequence
        Returns:
        the list resulting from the prepend operation
      • addAll

        public ZenoChain<T> addAll​(java.lang.Iterable<? extends T> items)
        Append a sequence of items. This is an immutable operation; the original list is unchanged.
        Parameters:
        items - the sequence of items to be appended
        Returns:
        the concatenated sequence
      • concat

        public ZenoChain<T> concat​(ZenoChain<T> other)
        Concatenate two ZenoChains to form a new ZenoChain, leaving the original operands unchanged
        Parameters:
        other - the ZenoChain to be concatenated after this one
        Returns:
        a new ZenoChain whose elements are the elements of this ZenoChain followed by the elements of the other ZenoChain.
      • replace

        public ZenoChain<T> replace​(int n,
                                    T value)
        Replace the item at position n, zero-based
        Parameters:
        n - the requested index
        value - the replacement value
        Returns:
        the new ZenoChain
        Throws:
        java.lang.IndexOutOfBoundsException - if n is negative or beyond the end of the list
      • remove

        public ZenoChain<T> remove​(int n)
        Remove the item at position n, zero-based
        Parameters:
        n - the requested index
        Returns:
        the new ZenoChain
        Throws:
        java.lang.IndexOutOfBoundsException - if n is negative or beyond the end of the list
      • insert

        public ZenoChain<T> insert​(int n,
                                   T value)
        Insert an item at position n, zero-based
        Parameters:
        n - the requested index
        value - the replacement value
        Returns:
        the new ZenoChain
        Throws:
        java.lang.IndexOutOfBoundsException - if n is negative or beyond the end of the list
      • get

        public T get​(int n)
        Get the item at position n, zero-based
        Parameters:
        n - the requested index
        Returns:
        the item at position n
        Throws:
        java.lang.IndexOutOfBoundsException - if n is negative or beyond the end of the list
      • subList

        public ZenoChain<T> subList​(int start,
                                    int end)
        Get a sublist of this list.

        Note that unlike List.subList(int, int), the returned list is not "backed" by the original list; changes to the returned list will not affect the original list in any way. (This is inevitable, since both lists are immutable).

        Parameters:
        start - the zero-based start position of the required sublist, inclusive
        end - the zero-based end position of the required sublist, exclusive
        Returns:
        the sublist, as a new ZenoChain
        Throws:
        java.lang.IndexOutOfBoundsException - under the same conditions as for List.subList(int, int): (start < 0 || end > size || start > end)
      • size

        public int size()
        Get the size of the list
        Returns:
        the size of the list
      • isEmpty

        public boolean isEmpty()
        Ask if the list is empty
        Returns:
        true if the size is zero
      • isSingleton

        public boolean isSingleton()
        Ask if the list is a singleton
        Returns:
        true if the size is one
      • iterator

        public java.util.Iterator<T> iterator()
        Iterate over the items
        Specified by:
        iterator in interface java.lang.Iterable<T>
        Returns:
        a Java-style iterator over the items
      • toString

        public java.lang.String toString()
        Get a string representation of the ZenoChain.
        Overrides:
        toString in class java.lang.Object
        Returns:
        the string representation in the form (X,Y,Z,...) where X, Y, and Z are the string representations of the elements of the sequence
      • showMetrics

        public java.lang.String showMetrics()
        Diagnostic display of a ZenoChain, exposing its internal structure
        Returns:
        a string that shows the sizes of the segments, for example (64,32,4) for a ZenoChain of length 100.