Package net.sf.saxon.ma.zeno

Class ZenoChain<T>

java.lang.Object
net.sf.saxon.ma.zeno.ZenoChain<T>
Type Parameters:
T - the type of the items in the list
All Implemented Interfaces:
Iterable<T>
public class ZenoChain<T> extends Object implements 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 Details

    • ZenoChain

      public ZenoChain()
      Create an empty sequence

  • Method Details

    • 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(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:
      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:
      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:
      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:
      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:
      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 Iterator<T> iterator()
      Iterate over the items
      Specified by:
      iterator in interface Iterable<T>
      Returns:
      a Java-style iterator over the items

    • toString

      public String toString()
      Get a string representation of the ZenoChain.
      Overrides:
      toString in class 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 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.