T
- the type of the items in the listpublic class ZenoChain<T>
extends java.lang.Object
implements java.lang.Iterable<T>
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 and Description |
---|
ZenoChain()
Create an empty sequence
|
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
|
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.
|
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.
|
public ZenoChain<T> add(T item)
item
- the item to be appendedpublic ZenoChain<T> prepend(T item)
item
- the item to be added at the start of the sequencepublic ZenoChain<T> addAll(java.lang.Iterable<? extends T> items)
items
- the sequence of items to be appendedpublic ZenoChain<T> concat(ZenoChain<T> other)
other
- the ZenoChain to be concatenated after this onepublic T get(int n)
n
- the requested indexjava.lang.IndexOutOfBoundsException
- if n is negative or beyond the end of the listpublic ZenoChain<T> subList(int start, int end)
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).
start
- the zero-based start position of the required sublist, inclusiveend
- the zero-based end position of the required sublist, exclusivejava.lang.IndexOutOfBoundsException
- under the same conditions as for List.subList(int, int)
:
(start < 0 || end > size || start > end)public int size()
public boolean isEmpty()
public boolean isSingleton()
public java.util.Iterator<T> iterator()
iterator
in interface java.lang.Iterable<T>
public java.lang.String toString()
toString
in class java.lang.Object
(X,Y,Z,...)
where X
,
Y
, and Z
are the string representations of the elements of the sequencepublic java.lang.String showMetrics()
ZenoChain
, exposing its internal structureZenoChain
of length 100.Copyright (c) 2004-2022 Saxonica Limited. All rights reserved.