Package gnu.lists
Class TreeList
- All Implemented Interfaces:
Consumable
,Consumer
,PositionConsumer
,XConsumer
,Appendable
,Consumer<Object>
,DoubleConsumer
,IntConsumer
,LongConsumer
- Direct Known Subclasses:
NodeTree
public class TreeList
extends AbstractSequence<Object>
implements Appendable, XConsumer, PositionConsumer, Consumable
A compact representation of a tree, that is a nested list structure.
The data structure can store anything that can be emitted to a Consumer.
This data structure is optimized for efficient forwards traversal
through the data structure, not random access.
It does have an "insertion point"; insertions and deletions are
efficient through the use of a buffer gap.
It is a reasonable choice for a "DOM" for XML data.
-
Field Summary
FieldsModifier and TypeFieldDescriptionint
If non-zero, gap is in an attribute starting (1 less than) here.protected static final int
The beginning of an attribute.static final int
protected static final int
Beginning of a document (or top-level value).protected static final int
Begin of an element, non-compact form.protected static final int
Beginning of an element, compact form.protected static final int
static final int
Start of an entity (typically a file, possibly included).static final int
char[]
int
If non-zero, gap is in an document starting (1 less than) here.protected static final int
The document-uri property of a node.static final int
protected static final int
End of a document.protected static final int
End of n element, non-compact form.protected static final int
End of an element, compact form.protected static final int
int
int
static final int
A 32-bit integer, non-compact form.static final int
The largest Unicode character that can be encoded in one char.Object[]
int
protected static final char
A position triple referencing some other "nodes".protected static final int
A processing-instruction node follows.Fields inherited from class gnu.lists.AbstractSequence
noInts
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionappend
(char c) append
(CharSequence csq) append
(CharSequence csq, int start, int end) void
beginEntity
(Object base) void
clear()
int
compare
(int ipos1, int ipos2) Compare two positions, and indicate their relative order.void
int
consumeIRange
(int startPosition, int endPosition, Consumer out) boolean
consumeNext
(int ipos, Consumer out) Copy an element specified by a position pair to a Consumer.void
consumePosRange
(int startPos, int endPos, Consumer out) int
createPos
(int index, boolean isAfter) Generate a position at a given index.int
createRelativePos
(int istart, int offset, boolean isAfter) documentUriOfPos
(int pos) void
dump()
void
dump
(PrintWriter out) void
dump
(PrintWriter out, int start, int limit) void
End of an attribute or end of an actual parameter.void
void
void
void
ensureSpace
(int needed) int
int
firstAttributePos
(int ipos) Like firstChildPos.int
firstChildPos
(int ipos) Get position before first child (of the element following position).get
(int index) int
getAttributeCount
(int parent) protected int
getIndexDifference
(int ipos1, int ipos0) Get offset of (ipos1) relative to (ipos0).protected final int
getIntN
(int index) Get a 32-bit int from the data array.protected final long
getLongN
(int index) Get a 64-bit long from the data array.int
getNextKind
(int ipos) int
getNextKindI
(int index) getNextTypeObject
(int ipos) getPosNext
(int ipos) Get the element following the specified position.int
getPosNextInt
(int ipos) Return following value (like getPosNext), as an integer.getPosPrevious
(int ipos) Get the element before the specified position.int
gotoAttributesStart
(int index) boolean
final int
gotoChildrenStart
(int index) int
hashCode()
boolean
hasNext
(int ipos) boolean
ignoring()
True if consumer is ignoring rest of element.boolean
isEmpty()
final int
nextDataIndex
(int pos) int
nextIndex
(int ipos) Get the offset from the beginning corresponding to a position cookie.int
nextMatching
(int startPos, ItemPredicate predicate, int endPos, boolean descend) Get next matching child or descendent (ignoring attributes).final int
nextNodeIndex
(int pos, int limit) Skip all primitive content nodes.int
nextPos
(int position) Return the next position following the argument.int
parentOrEntityI
(int index) int
parentOrEntityPos
(int ipos) int
parentPos
(int ipos) Get position of parent.final int
posToDataIndex
(int ipos) final void
reserveObjects
(int needed) void
setAttributeName
(int attrIndex, int nameIndex) void
setElementName
(int elementIndex, int nameIndex) final void
setIntN
(int index, int i) int
size()
void
startAttribute
(int index) void
startAttribute
(Object attrType) Write a attribute for the current element.void
void
startElement
(int index) void
startElement
(Object type) void
void
statistics
(PrintWriter out) int
stringValue
(boolean inElement, int index, StringBuffer sbuf) void
stringValue
(int startIndex, int endIndex, StringBuffer sbuf) int
stringValue
(int index, StringBuffer sbuf) void
toString
(String sep, StringBuffer sbuf) void
write
(char[] buf, int off, int len) void
write
(int c) void
write
(CharSequence str, int start, int length) void
void
writeBoolean
(boolean v) void
writeByte
(int v) void
writeCDATA
(char[] chars, int offset, int length) void
writeComment
(char[] chars, int offset, int length) void
writeComment
(String comment, int offset, int length) void
writeDocumentUri
(Object uri) Write/set the document-uri property of the current document.void
writeDouble
(double v) void
writeFloat
(float v) void
writeInt
(int v) void
writeIntForce32
(int v) void
void
writeLong
(long v) void
void
writePosition
(AbstractSequence seq, int ipos) Consume a single position pair.void
writePosition
(SeqPosition position) Consume node at current position.void
writeProcessingInstruction
(String target, char[] content, int offset, int length) void
writeProcessingInstruction
(String target, String content, int offset, int length) Methods inherited from class gnu.lists.AbstractSequence
add, add, addAll, addAll, addPos, asImmutable, badRank, boundedHash, checkCanWrite, checkRank, compare, compare, consume, contains, containsAll, copyPos, effectiveIndex, effectiveIndex, effectiveIndex, effectiveIndex, effectiveIndex, elements, endPos, equals, equals, fill, fill, fillPosRange, firstChildPos, fromEndIndex, get, get, get, get, getAttribute, getAttributeLength, getBooleanRaw, getByteRaw, getCharRaw, getContainingSequenceSize, getDoubleRaw, getElementKind, getFloatRaw, getInt, getInt, getInt, getInt, getInt, getIntRaw, getIterator, getIterator, getIteratorAtPos, getLongRaw, getLowBound, getNextTypeName, getRaw, getRowMajor, getShortRaw, getSize, getSize, gotoChildrenStart, gotoParent, hasPrevious, indexOf, isAfterPos, iterator, lastIndexOf, listIterator, listIterator, nextIndex, previousPos, rank, releasePos, remove, remove, removeAll, removePos, removePosRange, retainAll, set, set, setAt, setBuffer, setPosNext, setPosPrevious, setRaw, stableCompare, startPos, subList, subSequence, subSequencePos, toArray, toArray, toString, unsupported, unsupportedException
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.function.DoubleConsumer
andThen
Methods inherited from interface java.util.function.IntConsumer
andThen
Methods inherited from interface java.util.function.LongConsumer
andThen
-
Field Details
-
objects
-
oindex
public int oindex -
data
public char[] data -
gapStart
public int gapStart -
gapEnd
public int gapEnd -
attrStart
public int attrStartIf non-zero, gap is in an attribute starting (1 less than) here. -
docStart
public int docStartIf non-zero, gap is in an document starting (1 less than) here. -
MAX_CHAR_SHORT
public static final int MAX_CHAR_SHORTThe largest Unicode character that can be encoded in one char.- See Also:
-
POSITION_PAIR_FOLLOWS
protected static final char POSITION_PAIR_FOLLOWSA position triple referencing some other "nodes". Followed by index of sequence (2 chars), and ipos (2 chars).- See Also:
-
INT_FOLLOWS
public static final int INT_FOLLOWSA 32-bit integer, non-compact form. [INT_FOLLOWS] [word1], [word2]: The big-endian bits of the integer.- See Also:
-
PROCESSING_INSTRUCTION
protected static final int PROCESSING_INSTRUCTIONA processing-instruction node follows. [PROCESSING_INSTRUCTION] [target] 2 shorts, where objects[target] is the target as a String. [length] 2 shorts. [comment text], (length) number of characters.- See Also:
-
BEGIN_ATTRIBUTE_LONG
protected static final int BEGIN_ATTRIBUTE_LONGThe beginning of an attribute. [BEGIN_ATTRIBUTE_LONG] [index], 2 shorts, where objects[index] is the attribute type name and objects[index+1] is the attribute type object. [end_offset], 2 shorts, giving the location of the following END_ATTRIBUTE. If the attribute straddles the gap, then end_offset is a negative offset relative to data.length. (Therefore allocating more space for the gap does not require adjusting end_offset.) Otherwise, the end_offset is relative to the BEGIN_ATTRIBUTE_LONG word.- See Also:
-
BEGIN_ATTRIBUTE_LONG_SIZE
public static final int BEGIN_ATTRIBUTE_LONG_SIZE- See Also:
-
END_ATTRIBUTE_SIZE
public static final int END_ATTRIBUTE_SIZE- See Also:
-
BEGIN_DOCUMENT
protected static final int BEGIN_DOCUMENTBeginning of a document (or top-level value). Used to distinguish a document from its element node. [end_offset], 2 shorts, giving the location of the following END_DOCUMENT. If the attribute straddles the gap, then end_offset is a negative offset relative to data.length. (Therefore allocating more space for the gap does not require adjusting end_offset.) Otherwise, the end_offset is relative to the BEGIN_DOCUMENT word. [parent_offset], in 2 shorts. The parent node, or -1 if no parent. Otherwise, a negative value is a relative offset, while a non-negative value is absolute. (Use the latter when gap is between this node and its parent. The parent would normally be a BEGIN_ENTITY.- See Also:
-
END_DOCUMENT
protected static final int END_DOCUMENTEnd of a document.- See Also:
-
BEGIN_ENTITY
public static final int BEGIN_ENTITYStart of an entity (typically a file, possibly included). [base_uri], 2 shorts, given an index of a base-uri object [parent_offset], in 2 shorts, encoded as for BEGIN_DOCUMENT.- See Also:
-
BEGIN_ENTITY_SIZE
public static final int BEGIN_ENTITY_SIZE- See Also:
-
END_ENTITY
protected static final int END_ENTITY- See Also:
-
DOCUMENT_URI
protected static final int DOCUMENT_URIThe document-uri property of a node. This is not an actual value, but it is a property of the previous document node, or the surrounding node just after a BEGIN_XXX entry. [DOCUMENT_URI] [index]. 2 shorts, where objects[index] is the document-uri value.- See Also:
-
BEGIN_ELEMENT_SHORT
protected static final int BEGIN_ELEMENT_SHORTBeginning of an element, compact form. [BEGIN_ELEMENT_SHORT + index], where objects[index] is the element's type name and objects[index+1] is the type object. [end_offset], the unsigned offset (from the initial word) to the corresponding END_ELEMENT_SHORT. [parent_offset], the (unsigned absolute value of the) offset to the outer BEGIN_ELEMENT_SHORT/BEGIN_ELEMENT_LONG/BEGIN_DOCUMENT. . (If these is no parent, then parent_offset==0.) This should is used whenindex < BEGIN_ELEMENT_SHORT_INDEX_MAX
, both end_offset and parent_offset fit in 16 bits, and the element does not straddle the gap.- See Also:
-
BEGIN_ELEMENT_SHORT_INDEX_MAX
protected static final int BEGIN_ELEMENT_SHORT_INDEX_MAX- See Also:
-
END_ELEMENT_SHORT
protected static final int END_ELEMENT_SHORTEnd of an element, compact form. [END_ELEMENT_SHORT] [begin_offset], the unsigned absolute value of the offset to the matching BEGIN. (This is the same as the matching end_offset.)- See Also:
-
BEGIN_ELEMENT_LONG
protected static final int BEGIN_ELEMENT_LONGBegin of an element, non-compact form. [BEGIN_ELEMENT_LONG] [end_offset], in 2 shorts. The position of the matching END_ELEMENT_LONG. If the element straddles the gap, then end_offset is a negative offset relative to data.length. (Therefore allocating more space for the gap does not require adjusting any end_offset.) If the element and and its children are all on the same side of the gap, then end_offset is a positive offset relative to the BEGIN_ELEMENT_LONG word. (Hence shifting an entire element when the gap is moved does not require changing its end_offset.) Note that the space taken by a BEGIN_ELEMENT_LONG is the same that needed for a BEGIN_ELEMENT_SHORT (but a END_ELEMENT_LONG takes much more space than a END_ELEMENT_SHORT). This is to make it easier to convert a BEGIN_ELEMENT_LONG to a BEGIN_ELEMENT_SHORT or vice versa, as needed.- See Also:
-
END_ELEMENT_LONG
protected static final int END_ELEMENT_LONGEnd of n element, non-compact form. [END_ELEMENT_LONG] [index], 2 shorts where objects[index] is the element's type name and objects[index+1] is the type object. [begin_offset], in 2 shorts. The position of the matching BEGIN_ELEMENT_LONG. If the element straddles the gap, then begin_offset is the actual index (i.e. relative to the start of data) of the matching BEGIN_ELEMENT_LONG. (Therefore allocating more space for the gap does not require adjusting begin_offset.) If the element does not straddle the gap, then begin_offset is a negative offset relative to the END_ELEMENT_LONG word. (Hence shifting an entire element when the gap is moved does not require changing its begin_offset.) relative to data.length. [parent_offset], in 2 shorts. The position of the outer BEGIN_ELEMENT_LONG, BEGIN_ELEMENT_SHORT or BEGIN_DOCUMENT. If the difference straddles the gap (i.e. either this element straddles the gap or the parent element does and the gap precedes this element), then parent_offset is the actual index of the parent element. Otherwise, then parent_offset is a negative offset relative to the END_ELEMENT_LONG word.- See Also:
-
-
Constructor Details
-
TreeList
public TreeList() -
TreeList
Make a copy of a sub-range of a TreeList.- Parameters:
list
- the TreeList to copystartPosition
- start of range, as a raw index in dataendPosition
- end of range, as a raw index in data
-
TreeList
-
-
Method Details
-
clear
public void clear()- Overrides:
clear
in classAbstractSequence<Object>
-
ensureSpace
public void ensureSpace(int needed) -
reserveObjects
public final void reserveObjects(int needed) -
find
-
getIntN
protected final int getIntN(int index) Get a 32-bit int from the data array. -
getLongN
protected final long getLongN(int index) Get a 64-bit long from the data array. -
setIntN
public final void setIntN(int index, int i) -
writePosition
Description copied from interface:PositionConsumer
Consume node at current position. The caller may invalidate or change the position after consume returns, so if the consumer wants to save it, it needs to copy it.- Specified by:
writePosition
in interfacePositionConsumer
-
writePosition
Description copied from interface:PositionConsumer
Consume a single position pair. This PositionConsumer may assume the sequence does no reference management; i.e. that copyPos is trivial and releasePos is a no-op. If that is not the case, use consume(TreePosition) instead.- Specified by:
writePosition
in interfacePositionConsumer
-
writeObject
- Specified by:
writeObject
in interfaceConsumer
-
writeDocumentUri
Write/set the document-uri property of the current document. Only allowed immediately following startDocument. -
writeComment
public void writeComment(char[] chars, int offset, int length) - Specified by:
writeComment
in interfaceXConsumer
-
writeComment
-
writeProcessingInstruction
- Specified by:
writeProcessingInstruction
in interfaceXConsumer
-
writeProcessingInstruction
-
startElement
- Specified by:
startElement
in interfaceConsumer
-
startDocument
public void startDocument()- Specified by:
startDocument
in interfaceConsumer
-
endDocument
public void endDocument()- Specified by:
endDocument
in interfaceConsumer
-
beginEntity
- Specified by:
beginEntity
in interfaceXConsumer
-
endEntity
public void endEntity() -
startElement
public void startElement(int index) -
setElementName
public void setElementName(int elementIndex, int nameIndex) -
endElement
public void endElement()- Specified by:
endElement
in interfaceConsumer
-
startAttribute
Description copied from interface:Consumer
Write a attribute for the current element. This is only allowed immediately after a startElement.- Specified by:
startAttribute
in interfaceConsumer
-
startAttribute
public void startAttribute(int index) -
setAttributeName
public void setAttributeName(int attrIndex, int nameIndex) -
endAttribute
public void endAttribute()Description copied from interface:Consumer
End of an attribute or end of an actual parameter. The former use matches a startAttribute; the latter may not, and can be used to separate parameters in a parameter list. This double duty suggsts the method should at least be re-named.- Specified by:
endAttribute
in interfaceConsumer
-
append
- Specified by:
append
in interfaceAppendable
- Specified by:
append
in interfaceConsumer
-
write
public void write(int c) -
writeBoolean
public void writeBoolean(boolean v) - Specified by:
writeBoolean
in interfaceConsumer
-
writeByte
public void writeByte(int v) -
writeInt
public void writeInt(int v) -
writeIntForce32
public void writeIntForce32(int v) -
writeLong
public void writeLong(long v) -
writeFloat
public void writeFloat(float v) - Specified by:
writeFloat
in interfaceConsumer
-
writeDouble
public void writeDouble(double v) - Specified by:
writeDouble
in interfaceConsumer
-
ignoring
public boolean ignoring()Description copied from interface:Consumer
True if consumer is ignoring rest of element. The producer can use this information to skip ahead. -
writeJoiner
public void writeJoiner() -
write
public void write(char[] buf, int off, int len) -
write
-
write
-
writeCDATA
public void writeCDATA(char[] chars, int offset, int length) - Specified by:
writeCDATA
in interfaceXConsumer
-
append
- Specified by:
append
in interfaceAppendable
- Specified by:
append
in interfaceConsumer
-
append
- Specified by:
append
in interfaceAppendable
- Specified by:
append
in interfaceConsumer
-
isEmpty
public boolean isEmpty()- Overrides:
isEmpty
in classAbstractSequence<Object>
-
size
public int size()- Overrides:
size
in classAbstractSequence<Object>
-
createPos
public int createPos(int index, boolean isAfter) Description copied from class:AbstractSequence
Generate a position at a given index. The result is a position cookie that must be free'd with releasePos.- Overrides:
createPos
in classAbstractSequence<Object>
- Parameters:
index
- offset from beginning of desired positionisAfter
- should the position have the isAfter property
-
posToDataIndex
public final int posToDataIndex(int ipos) -
firstChildPos
public int firstChildPos(int ipos) Description copied from class:AbstractSequence
Get position before first child (of the element following position).- Overrides:
firstChildPos
in classAbstractSequence<Object>
- Parameters:
ipos
- parent position. It is not released by this method.- Returns:
- non-zero position cookie if there is a child sequence (which might be empty); zero if current position is end of sequence or following element is atomic (cannot have children).
-
gotoChildrenStart
public final int gotoChildrenStart(int index) -
parentPos
public int parentPos(int ipos) Description copied from class:AbstractSequence
Get position of parent.- Overrides:
parentPos
in classAbstractSequence<Object>
- Parameters:
ipos
- child position. It is not released by this method.- Returns:
- the p os of the parent, or endPos() is there is no known parent.
-
parentOrEntityPos
public int parentOrEntityPos(int ipos) -
parentOrEntityI
public int parentOrEntityI(int index) -
getAttributeCount
public int getAttributeCount(int parent) -
gotoAttributesStart
- Overrides:
gotoAttributesStart
in classAbstractSequence<Object>
-
firstAttributePos
public int firstAttributePos(int ipos) Description copied from class:AbstractSequence
Like firstChildPos. Problem: Should this stop before we get to children? I think so, but that requires changes to TreeList.- Overrides:
firstAttributePos
in classAbstractSequence<Object>
-
gotoAttributesStart
public int gotoAttributesStart(int index) -
get
- Overrides:
get
in classAbstractSequence<Object>
-
consumeNext
Description copied from class:AbstractSequence
Copy an element specified by a position pair to a Consumer.- Overrides:
consumeNext
in classAbstractSequence<Object>
- Returns:
- if hasNext(ipos).
-
consumePosRange
- Overrides:
consumePosRange
in classAbstractSequence<Object>
-
consumeIRange
-
toString
- Overrides:
toString
in classAbstractSequence<Object>
-
hasNext
public boolean hasNext(int ipos) - Overrides:
hasNext
in classAbstractSequence<Object>
-
getNextKind
public int getNextKind(int ipos) - Overrides:
getNextKind
in classAbstractSequence<Object>
-
getNextKindI
public int getNextKindI(int index) -
getNextTypeObject
- Overrides:
getNextTypeObject
in classAbstractSequence<Object>
-
getPosPrevious
Description copied from class:AbstractSequence
Get the element before the specified position.- Overrides:
getPosPrevious
in classAbstractSequence<Object>
- Parameters:
ipos
- the specified position.- Returns:
- the following element, or eofValue if there is none. FIXME Should change eof handling so return type can be E.
-
getPosNextInt
public int getPosNextInt(int ipos) Return following value (like getPosNext), as an integer. -
getPosNext
Description copied from class:AbstractSequence
Get the element following the specified position.- Overrides:
getPosNext
in classAbstractSequence<Object>
- Parameters:
ipos
- the specified position.- Returns:
- the following element, or eofValue if there is none. Called by SeqPosition.getNext. FIXME Should change eof handling so return type can be E.
-
stringValue
-
stringValue
-
stringValue
-
createRelativePos
public int createRelativePos(int istart, int offset, boolean isAfter) - Overrides:
createRelativePos
in classAbstractSequence<Object>
-
nextNodeIndex
public final int nextNodeIndex(int pos, int limit) Skip all primitive content nodes. -
nextMatching
Description copied from class:AbstractSequence
Get next matching child or descendent (ignoring attributes).- Overrides:
nextMatching
in classAbstractSequence<Object>
- Parameters:
startPos
- starting positionpredicate
- a test (predicate) to apply to selected elementsendPos
- stop before endPosdescend
- if true do depth-first traversal.- Returns:
- poistion of next match or 0 if none found
-
nextPos
public int nextPos(int position) Description copied from class:AbstractSequence
Return the next position following the argument. The new position has the isAfter property. The argument is implicitly released (as in releasePos). Returns 0 if we are already at end of file.- Overrides:
nextPos
in classAbstractSequence<Object>
-
nextDataIndex
public final int nextDataIndex(int pos) -
documentUriOfPos
-
compare
public int compare(int ipos1, int ipos2) Compare two positions, and indicate their relative order.- Overrides:
compare
in classAbstractSequence<Object>
-
getIndexDifference
protected int getIndexDifference(int ipos1, int ipos0) Description copied from class:AbstractSequence
Get offset of (ipos1) relative to (ipos0).- Overrides:
getIndexDifference
in classAbstractSequence<Object>
-
nextIndex
public int nextIndex(int ipos) Description copied from class:AbstractSequence
Get the offset from the beginning corresponding to a position cookie.- Overrides:
nextIndex
in classAbstractSequence<Object>
-
hashCode
public int hashCode()- Overrides:
hashCode
in classAbstractSequence<Object>
-
consume
- Specified by:
consume
in interfaceConsumable
- Overrides:
consume
in classAbstractSequence<Object>
-
statistics
public void statistics() -
statistics
-
dump
public void dump() -
dump
-
dump
-