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:

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 and Description
ZenoChain() Create an empty sequence

Method Summary

Modifier and Type	Method and 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.