java.lang.Object
- net.sf.saxon.ma.zeno.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.
  - 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
  - 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
  - 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.

Class ZenoChain<T>

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.lang.Iterable

Constructor Detail

ZenoChain

Method Detail

add

prepend

addAll

concat

get

replace

remove

insert

subList

size

isEmpty

isSingleton

iterator

toString

showMetrics