gnu.lists
Class TreeList

java.lang.Object
  gnu.lists.AbstractSequence
      gnu.lists.TreeList

All Implemented Interfaces:

Consumable, Consumer, PositionConsumer, XConsumer, java.lang.Appendable

Direct Known Subclasses:

NodeTree, Values

public class TreeList
extends AbstractSequence
implements java.lang.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

int	attrStart If non-zero, gap is in an attribute starting (1 less than) here.
protected static int	BEGIN_ATTRIBUTE_LONG The beginning of an attribute.
protected static int	BEGIN_DOCUMENT Beginning of a document (or top-level value).
char[]	data
int	docStart If non-zero, gap is in an document starting (1 less than) here.
protected static int	END_DOCUMENT End of a document.
protected static int	END_GROUP_LONG End of a group, non-compact form.
protected static int	END_GROUP_SHORT End of a group, compact form.
int	gapEnd
int	gapStart
static int	INT_FOLLOWS A 32-bit integer, non-compact form.
java.lang.Object[]	objects
int	oindex
protected static char	POSITION_PAIR_FOLLOWS A position triple referenceing some other "nodes".
protected static int	PROCESSING_INSTRUCTION A processing-instruction node follows.

Constructor Summary

TreeList()

TreeList(TreeList list)

TreeList(TreeList list, int startPosition, int endPosition)
Make a copy of a sub-range of a TreeList.

Method Summary

TreeList	append(char c)
TreeList	append(java.lang.CharSequence csq)
TreeList	append(java.lang.CharSequence csq, int start, int end)
java.lang.Object	baseUriOfPos(int pos) Return of the base-uri property, if known, of the node at pos.
void	beginAttribute(int index)
void	beginAttribute(java.lang.String attrName, java.lang.Object attrType) Write a attribute for the current group.
void	beginDocument()
void	beginGroup(int index)
void	beginGroup(java.lang.String typeName, java.lang.Object type)
void	clear()
int	compare(int ipos1, int ipos2) Compare two positions, and indicate their relative order.
void	consume(Consumer out)
void	consume(SeqPosition position) Consume node at current position.
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)
void	dump()
void	dump(java.io.PrintWriter out)
void	endAttribute()
void	endDocument()
void	endGroup(java.lang.String typeName)
void	ensureSpace(int needed)
int	find(java.lang.Object arg1)
int	find(java.lang.Object arg1, java.lang.Object arg2)
int	firstAttributePos(int ipos) Like firstChildPos.
int	firstChildPos(int ipos) Get position before first child (of the element following position).
java.lang.Object	get(int index) See java.util.List.
protected int	getIndexDifference(int ipos1, int ipos0) Get offset of (ipos1) relative to (ipos0).
protected int	getIntN(int index) Get a 32-bit int from the data array.
protected long	getLongN(int index) Get a 64-bit long from the data array.
int	getNextKind(int ipos)
protected int	getNextTypeIndex(int ipos)
java.lang.String	getNextTypeName(int ipos)
java.lang.Object	getNextTypeObject(int ipos)
java.lang.Object	getPosNext(int ipos) Get the element following the specified position.
int	getPosNextInt(int ipos) Return following value (like getPosNext), as an integer.
java.lang.Object	getPosPrevious(int ipos) Get the element before the specified position.
int	gotoAttributesStart(int index)
boolean	gotoAttributesStart(TreePosition pos)
int	gotoChildrenStart(int index)
int	hashCode()
boolean	hasNext(int ipos)
boolean	ignoring() True if consumer is ignoring rest of group.
boolean	isEmpty()
int	nextDataIndex(int pos)
int	nextMatching(int startPos, ElementPredicate predicate, int endPos, boolean descend) Get next matching child or descendent (ignoring attributes).
int	nextNodeIndex(int pos, int limit) Skip all primitive content nodes.
int	nextPos(int position) Return the next position following the argument.
int	parentPos(int ipos) Get position of parent.
int	posToDataIndex(int ipos)
void	resizeObjects()
void	setIntN(int index, int i)
int	size() See java.util.List.
void	statistics()
void	statistics(java.io.PrintWriter out)
int	stringValue(boolean inGroup, int index, java.lang.StringBuffer sbuf)
int	stringValue(int index, java.lang.StringBuffer sbuf)
void	toString(java.lang.String sep, java.lang.StringBuffer sbuf)
void	write(char[] buf, int off, int len)
void	writeBaseUri(java.lang.Object uri) Write/set the base-uri property of the current element or document.
void	writeBoolean(boolean v)
void	writeByte(int v)
void	writeCDATA(char[] chars, int offset, int length)
void	writeChar(int i)
void	writeChars(java.lang.String str)
void	writeComment(char[] chars, int offset, int length)
void	writeDouble(double v)
void	writeFloat(float v)
void	writeInt(int v)
void	writeLong(long v)
void	writeObject(java.lang.Object v)
void	writePosition(AbstractSequence seq, int ipos) Consume a single position pair.
void	writeProcessingInstruction(java.lang.String target, char[] content, int offset, int length)

Methods inherited from class gnu.lists.AbstractSequence

add, add, addAll, addAll, addPos, compare, compare, contains, containsAll, copyPos, elements, endPos, equals, equals, fill, fill, fillPosRange, fromEndIndex, get, getAttribute, getAttributeLength, getContainingSequenceSize, getEffectiveIndex, getIterator, getIterator, getIteratorAtPos, getLowBound, getSize, gotoChildrenStart, gotoParent, hasPrevious, indexOf, isAfterPos, iterator, lastIndexOf, listIterator, listIterator, nextIndex, nextIndex, previousPos, rank, releasePos, remove, remove, removeAll, removePos, removePosRange, retainAll, set, set, setPosNext, setPosPrevious, stableCompare, startPos, subList, subSequence, subSequencePos, toArray, toArray, toString, unsupported

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

objects

public java.lang.Object[] objects

oindex

public int oindex

data

public char[] data

gapStart

public int gapStart

gapEnd

public int gapEnd

attrStart

public int attrStart

If non-zero, gap is in an attribute starting (1 less than) here.

docStart

public int docStart

If non-zero, gap is in an document starting (1 less than) here.

POSITION_PAIR_FOLLOWS

protected static final char POSITION_PAIR_FOLLOWS

A position triple referenceing some other "nodes". Followed by index of sequence (2 chars), and ipos (2 chars).

See Also:

Constant Field Values

INT_FOLLOWS

public static final int INT_FOLLOWS

A 32-bit integer, non-compact form. [INT_FOLLOWS] [word1], [word2]: The big-endian bits of the integer.

See Also:

Constant Field Values

PROCESSING_INSTRUCTION

protected static final int PROCESSING_INSTRUCTION

A 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:

Constant Field Values

BEGIN_ATTRIBUTE_LONG

protected static final int BEGIN_ATTRIBUTE_LONG

The 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. Kludge warning: ParsedXMLToConsumer.endAttributes has hard-wired in the size of BEGIN_ATTRIBUTE_LONG and END_ATTRIBUTE.

See Also:

Constant Field Values

BEGIN_DOCUMENT

protected static final int BEGIN_DOCUMENT

Beginning of a document (or top-level value). [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. Used to distinguish a document from its element node.

See Also:

Constant Field Values

END_DOCUMENT

protected static final int END_DOCUMENT

End of a document.

See Also:

Constant Field Values

END_GROUP_SHORT

protected static final int END_GROUP_SHORT

End of a group, compact form. [END_GROUP_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:

Constant Field Values

END_GROUP_LONG

protected static final int END_GROUP_LONG

End of a group, non-compact form. [END_GROUP_LONG] [index], 2 shorts where objects[index] is the group's type name and objects[index+1] is the type object. [begin_offset], in 2 shorts. The position of the matching BEGIN_GROUP_LONG. If the group straddles the gap, then begin_offset is the actual index (i.e. relative to the start of data) of the matching BEGIN_GROUP_LONG. (Therefore allocating more space for the gap does not require adjusting begin_offset.) If the group does not straddle the gap, then begin_offset is a negative offset relative to the END_GROUP_LONG word. (Hence shifting an entire group 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_GROUP_LONG, BEGIN_GROUP_SHORT or BEGIN_DOCUMENT. If the difference straddles the gap (i.e. either this group straddles the gap or the parent group does and the gap precedes this group), then parent_offset is the actual index of the parent group. Otherwise, then parent_offset is a negative offset relative to the END_GROUP_LONG word.

See Also:

Constant Field Values

Constructor Detail

TreeList

public TreeList()

TreeList

public TreeList(TreeList list,
                int startPosition,
                int endPosition)

Make a copy of a sub-range of a TreeList.

Parameters:

list - the TreeList to copy

startPosition - start of range, as a raw index in data

endPosition - end of range, as a raw index in data

TreeList

public TreeList(TreeList list)

Method Detail

clear

public void clear()

Overrides:

clear in class AbstractSequence

ensureSpace

public void ensureSpace(int needed)

resizeObjects

public final void resizeObjects()

find

public int find(java.lang.Object arg1)

find

public int find(java.lang.Object arg1,
                java.lang.Object arg2)

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)

consume

public void consume(SeqPosition position)

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:

consume in interface PositionConsumer

writePosition

public void writePosition(AbstractSequence seq,
                          int ipos)

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 interface PositionConsumer

writeObject

public void writeObject(java.lang.Object v)

Specified by:

writeObject in interface Consumer

writeBaseUri

public void writeBaseUri(java.lang.Object uri)

Write/set the base-uri property of the current element or document. Only allowed immediately following beginDocument, beginGroup, or writeProcessingInstruction.

Specified by:

writeBaseUri in interface XConsumer

writeComment

public void writeComment(char[] chars,
                         int offset,
                         int length)

Specified by:

writeComment in interface XConsumer

writeProcessingInstruction

public void writeProcessingInstruction(java.lang.String target,
                                       char[] content,
                                       int offset,
                                       int length)

Specified by:

writeProcessingInstruction in interface XConsumer

beginGroup

public void beginGroup(java.lang.String typeName,
                       java.lang.Object type)

Specified by:

beginGroup in interface Consumer

beginDocument

public void beginDocument()

Specified by:

beginDocument in interface Consumer

endDocument

public void endDocument()

Specified by:

endDocument in interface Consumer

beginGroup

public void beginGroup(int index)

endGroup

public void endGroup(java.lang.String typeName)

Specified by:

endGroup in interface Consumer

beginAttribute

public void beginAttribute(java.lang.String attrName,
                           java.lang.Object attrType)

Description copied from interface: Consumer

Write a attribute for the current group. This is only allowed immediately after a beginGroup.

Specified by:

beginAttribute in interface Consumer

beginAttribute

public void beginAttribute(int index)

endAttribute

public void endAttribute()

Specified by:

endAttribute in interface Consumer

writeChar

public void writeChar(int i)

Specified by:

writeChar in interface Consumer

writeBoolean

public void writeBoolean(boolean v)

Specified by:

writeBoolean in interface Consumer

writeByte

public void writeByte(int v)

writeInt

public void writeInt(int v)

Specified by:

writeInt in interface Consumer

writeLong

public void writeLong(long v)

Specified by:

writeLong in interface Consumer

writeFloat

public void writeFloat(float v)

Specified by:

writeFloat in interface Consumer

writeDouble

public void writeDouble(double v)

Specified by:

writeDouble in interface Consumer

ignoring

public boolean ignoring()

Description copied from interface: Consumer

True if consumer is ignoring rest of group. The producer can use this information to skip ahead.

Specified by:

ignoring in interface Consumer

writeChars

public void writeChars(java.lang.String str)

Specified by:

writeChars in interface Consumer

write

public void write(char[] buf,
                  int off,
                  int len)

Specified by:

write in interface Consumer

writeCDATA

public void writeCDATA(char[] chars,
                       int offset,
                       int length)

Specified by:

writeCDATA in interface XConsumer

append

public TreeList append(char c)

Specified by:

append in interface Consumer

Specified by:

append in interface java.lang.Appendable

Overrides:

append in class AbstractSequence

append

public TreeList append(java.lang.CharSequence csq)

Specified by:

append in interface Consumer

Specified by:

append in interface java.lang.Appendable

Overrides:

append in class AbstractSequence

append

public TreeList append(java.lang.CharSequence csq,
                       int start,
                       int end)

Specified by:

append in interface Consumer

Specified by:

append in interface java.lang.Appendable

Overrides:

append in class AbstractSequence

isEmpty

public boolean isEmpty()

Overrides:

isEmpty in class AbstractSequence

size

public int size()

Description copied from class: AbstractSequence

See java.util.List.

Specified by:

size in class AbstractSequence

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.

Specified by:

createPos in class AbstractSequence

Parameters:

index - offset from beginning of desired position

isAfter - 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 class AbstractSequence

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 class AbstractSequence

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.

gotoAttributesStart

public boolean gotoAttributesStart(TreePosition pos)

Overrides:

gotoAttributesStart in class AbstractSequence

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 class AbstractSequence

gotoAttributesStart

public int gotoAttributesStart(int index)

get

public java.lang.Object get(int index)

Description copied from class: AbstractSequence

See java.util.List.

Specified by:

get in class AbstractSequence

consumeNext

public boolean consumeNext(int ipos,
                           Consumer out)

Description copied from class: AbstractSequence

Copy an element specified by a position pair to a Consumer.

Overrides:

consumeNext in class AbstractSequence

Returns:

if hasNext(ipos).

consumePosRange

public void consumePosRange(int startPos,
                            int endPos,
                            Consumer out)

Overrides:

consumePosRange in class AbstractSequence

consumeIRange

public int consumeIRange(int startPosition,
                         int endPosition,
                         Consumer out)

toString

public void toString(java.lang.String sep,
                     java.lang.StringBuffer sbuf)

Overrides:

toString in class AbstractSequence

hasNext

public boolean hasNext(int ipos)

Overrides:

hasNext in class AbstractSequence

getNextKind

public int getNextKind(int ipos)

Overrides:

getNextKind in class AbstractSequence

getNextTypeIndex

protected int getNextTypeIndex(int ipos)

getNextTypeName

public java.lang.String getNextTypeName(int ipos)

Overrides:

getNextTypeName in class AbstractSequence

getNextTypeObject

public java.lang.Object getNextTypeObject(int ipos)

Overrides:

getNextTypeObject in class AbstractSequence

getPosPrevious

public java.lang.Object getPosPrevious(int ipos)

Description copied from class: AbstractSequence

Get the element before the specified position.

Overrides:

getPosPrevious in class AbstractSequence

Parameters:

ipos - the specified position.

Returns:

the following element, or eofValue if there is none.

getPosNextInt

public int getPosNextInt(int ipos)

Return following value (like getPosNext), as an integer.

getPosNext

public java.lang.Object getPosNext(int ipos)

Description copied from class: AbstractSequence

Get the element following the specified position.

Overrides:

getPosNext in class AbstractSequence

Parameters:

ipos - the specified position.

Returns:

the following element, or eofValue if there is none. Called by SeqPosition.getNext.

stringValue

public int stringValue(int index,
                       java.lang.StringBuffer sbuf)

stringValue

public int stringValue(boolean inGroup,
                       int index,
                       java.lang.StringBuffer sbuf)

createRelativePos

public int createRelativePos(int istart,
                             int offset,
                             boolean isAfter)

Overrides:

createRelativePos in class AbstractSequence

nextNodeIndex

public final int nextNodeIndex(int pos,
                               int limit)

Skip all primitive content nodes.

nextMatching

public int nextMatching(int startPos,
                        ElementPredicate predicate,
                        int endPos,
                        boolean descend)

Description copied from class: AbstractSequence

Get next matching child or descendent (ignoring attributes).

Overrides:

nextMatching in class AbstractSequence

Parameters:

startPos - starting position

predicate - a test (predicate) to apply to selected elements

endPos - stop before endPos

descend - 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 class AbstractSequence

nextDataIndex

public final int nextDataIndex(int pos)

baseUriOfPos

public java.lang.Object baseUriOfPos(int pos)

Description copied from class: AbstractSequence

Return of the base-uri property, if known, of the node at pos.

Overrides:

baseUriOfPos in class AbstractSequence

compare

public int compare(int ipos1,
                   int ipos2)

Compare two positions, and indicate their relative order.

Overrides:

compare in class AbstractSequence

getIndexDifference

protected int getIndexDifference(int ipos1,
                                 int ipos0)

Description copied from class: AbstractSequence

Get offset of (ipos1) relative to (ipos0).

Overrides:

getIndexDifference in class AbstractSequence

hashCode

public int hashCode()

Overrides:

hashCode in class AbstractSequence

consume

public void consume(Consumer out)

Specified by:

consume in interface Consumable

Overrides:

consume in class AbstractSequence

statistics

public void statistics()

statistics

public void statistics(java.io.PrintWriter out)

dump

public void dump()

dump

public void dump(java.io.PrintWriter out)