net.sf.saxon.tinytree

Class TinyTree

public final class TinyTree extends Object

A data structure to hold the contents of a tree. As the name implies, this implementation of the data model is optimized for size, and for speed of creation: it minimizes the number of Java objects used.

It can be used to represent a tree that is rooted at a document node, or one that is rooted at an element node.

Field Summary
protected int[]alpha
protected int[]attCode
protected int[]attParent
protected int[]attTypeCode
protected Value[]attTypedValue
protected CharSequence[]attValue
protected int[]beta
protected LargeStringBuffercharBuffer
protected FastStringBuffercommentBuffer
protected short[]depth
protected longdocumentNumber
protected int[]nameCode
protected int[]namespaceCode
protected int[]namespaceParent
protected int[]next
byte[]nodeKind
protected intnumberOfAttributes
protected intnumberOfNamespaces
protected intnumberOfNodes
protected int[]prior
protected introotIndexUsed
protected int[]typeCodeArray
protected Value[]typedValueArray
protected booleanusesNamespaces
Constructor Summary
TinyTree()
Create a TinyTree.
TinyTree(int nodes, int attributes, int namespaces, int characters)
Create a tree with a specified initial size
Method Summary
voidaddAttribute(NodeInfo root, int parent, int nameCode, int typeCode, CharSequence attValue, int properties)
Add an attribute node to the tree
intaddDocumentNode(TinyDocumentImpl doc)
Add a document node to the tree.
voidaddNamespace(int parent, int nscode)
Add a namespace node to the current element
intaddNode(short kind, int depth, int alpha, int beta, int nameCode)
Add a node to the tree
intaddTextNodeCopy(int depth, int existingNodeNr)
Create a new text node that is a copy of an existing text node
voidappendChars(CharSequence chars)
Append character data to the current text node
voidcondense()
Condense the tree: release unused memory.
voiddiagnosticDump()
Produce diagnostic print of main tree arrays
static voiddiagnosticDump(NodeInfo node)
Create diagnostic dump of the tree containing a particular node.
voidensurePriorIndex()
On demand, make an index for quick access to preceding-sibling nodes
int[]getAlphaArray()
Get the array holding alpha information
AtomicValuegetAtomizedValueOfUntypedNode(int nodeNr)
Get the typed value of a node whose type is known to be untypedAtomic.
intgetAttributeAnnotation(int nr)
Get the type annotation of an attribute node.
int[]getAttributeNameCodeArray()
Get the array used to hold the name codes of all attributes
TinyAttributeImplgetAttributeNode(int nr)
Make a (transient) attribute node from the array of attributes
int[]getAttributeParentArray()
Get the array used to hold the parent pointers of all attributes
int[]getAttributeTypeCodeArray()
Get the array used to hold the type codes of all attributes
CharSequence[]getAttributeValueArray()
Get the array used to hold the name codes of all attributes
int[]getBetaArray()
Get the array holding beta information
CharSequencegetCharacterBuffer()
Get the character buffer used to hold all the text data of the document
intgetColumnNumber(int sequence)
Get the column number for a node.
CharSequencegetCommentBuffer()
Get the character buffer used to hold all the comment data of the document
ConfigurationgetConfiguration()
Get the configuration previously set using setConfiguration
longgetDocumentNumber()
Get the document number (actually, the tree number)
intgetLineNumber(int sequence)
Get the line number for a node.
intgetNameCode(int nodeNr)
Get the nameCode for a given node, which must be a document, element, text, comment, or processing instruction node
int[]getNameCodeArray()
Get the array holding node name information
NamePoolgetNamePool()
Get the name pool used for the names in this document
int[]getNamespaceCodeArray()
Get the array used to hold the namespace codes of namespace declarations
int[]getNamespaceParentArray()
Get the array used to hold the parent pointers of all namespace declarations
int[]getNextPointerArray()
Get the array holding next-sibling pointers
TinyNodeImplgetNode(int nr)
Get the node at a given position in the tree
short[]getNodeDepthArray()
Get the array holding node depth information
intgetNodeKind(int nodeNr)
Get the node kind of a given node, which must be a document, element, text, comment, or processing instruction node
byte[]getNodeKindArray()
Get the array holding node kind information
intgetNumberOfAttributes()
Get the number of attributes in the tree
intgetNumberOfNamespaces()
Get the number of namespace declarations in the tree
intgetNumberOfNodes()
Get the number of nodes in the tree, excluding attributes and namespace nodes
intgetRootNode(int nodeNr)
Get the root node for a given node
StringgetSystemId(int seq)
Get the system id of an element in the document
intgetTypeAnnotation(int nodeNr)
Get the type annotation of a node.
int[]getTypeCodeArray()
Get the array holding node type information
ValuegetTypedValueOfAttribute(TinyAttributeImpl att)
Get the type value of an attribute node.
ValuegetTypedValueOfAttribute(int nodeNr)
Get the type value of an attribute node, given only the node number.
ValuegetTypedValueOfElement(TinyElementImpl element)
Get the type value of an element node.
ValuegetTypedValueOfElement(int nodeNr)
Get the type value of an element node, given only the node number
voidindexIDElement(NodeInfo root, int nodeNr, NameChecker checker)
Index an element of type xs:ID
booleanisIdAttribute(int nr)
Determine whether an attribute is an IDREF/IDREFS attribute.
booleanisIdElement(int nr)
Ask whether an element is an ID element.
booleanisIdrefAttribute(int nr)
Determine whether an attribute is an IDREF/IDREFS attribute.
booleanisIdrefElement(int nr)
Ask whether an element is an IDREF/IDREFS element.
booleanisNilled(int nodeNr)
Ask whether a given node is nilled
voidsetConfiguration(Configuration config)
Set the Configuration that contains this document
voidsetElementAnnotation(int nodeNr, int typeCode)
Set the type annotation of an element node
voidsetLineNumber(int sequence, int line, int column)
Set the line number for a node.
voidsetLineNumbering()
Set line numbering on
voidsetSystemId(int seq, String uri)
Set the system id of an element in the document.
voidshowSize()
Output a statistical summary to System.err

Field Detail

alpha

protected int[] alpha

attCode

protected int[] attCode

attParent

protected int[] attParent

attTypeCode

protected int[] attTypeCode

attTypedValue

protected Value[] attTypedValue

attValue

protected CharSequence[] attValue

beta

protected int[] beta

charBuffer

protected LargeStringBuffer charBuffer

commentBuffer

protected FastStringBuffer commentBuffer

depth

protected short[] depth

documentNumber

protected long documentNumber

nameCode

protected int[] nameCode

namespaceCode

protected int[] namespaceCode

namespaceParent

protected int[] namespaceParent

protected int[] next

nodeKind

public byte[] nodeKind

numberOfAttributes

protected int numberOfAttributes

numberOfNamespaces

protected int numberOfNamespaces

numberOfNodes

protected int numberOfNodes

prior

protected int[] prior

rootIndexUsed

protected int rootIndexUsed

typeCodeArray

protected int[] typeCodeArray

typedValueArray

protected Value[] typedValueArray

usesNamespaces

protected boolean usesNamespaces

Constructor Detail

TinyTree

public TinyTree()
Create a TinyTree. The initial size is based on the average size of trees previously built in this session

TinyTree

public TinyTree(int nodes, int attributes, int namespaces, int characters)
Create a tree with a specified initial size

Parameters: nodes the expected number of (non attribute or namespace) nodes attributes the expected number of attributes namespaces the expected number of namespace declarations characters the expected number of characters in the document (in text nodes)

Method Detail

addAttribute

void addAttribute(NodeInfo root, int parent, int nameCode, int typeCode, CharSequence attValue, int properties)
Add an attribute node to the tree

Parameters: root the root of the tree to contain the attribute parent the parent element of the new attribute nameCode the name code of the attribute typeCode the type annotation of the attribute attValue the string value of the attribute properties any special properties of the attribute (bit-significant)

addDocumentNode

int addDocumentNode(TinyDocumentImpl doc)
Add a document node to the tree. The data structure can contain any number of document (or element) nodes as top-level nodes. The document node is retained in the documentList list, and its offset in that list is held in the alpha array for the relevant node number.

Parameters: doc the document node to be added

Returns: the number of the node that was added

addNamespace

void addNamespace(int parent, int nscode)
Add a namespace node to the current element

Parameters: parent the node number of the element nscode namespace code identifying the prefix and uri

addNode

int addNode(short kind, int depth, int alpha, int beta, int nameCode)
Add a node to the tree

Parameters: kind The kind of the node. This must be a document, element, text, comment, or processing-instruction node (not an attribute or namespace) depth The depth in the tree alpha Pointer to attributes or text beta Pointer to namespaces or text nameCode The name of the node

Returns: the node number of the node that was added

addTextNodeCopy

public int addTextNodeCopy(int depth, int existingNodeNr)
Create a new text node that is a copy of an existing text node

Parameters: depth the depth of the new node existingNodeNr the node to be copied

Returns: the node number of the new node

appendChars

void appendChars(CharSequence chars)
Append character data to the current text node

Parameters: chars the character data to be appended

condense

void condense()
Condense the tree: release unused memory. This is done after the full tree has been built. The method makes a pragmatic judgement as to whether it is worth reclaiming space; this is only done when the constructed tree is very small compared with the space allocated.

diagnosticDump

public void diagnosticDump()
Produce diagnostic print of main tree arrays

diagnosticDump

public static void diagnosticDump(NodeInfo node)
Create diagnostic dump of the tree containing a particular node. Designed to be called as an extension function for diagnostics.

Parameters: node the node in question

ensurePriorIndex

void ensurePriorIndex()
On demand, make an index for quick access to preceding-sibling nodes

getAlphaArray

public int[] getAlphaArray()
Get the array holding alpha information

Returns: an array of integers, whose meaning depends on the node kind. For elements it is a pointer to the first attribute, for text, comment, and processing instruction nodes it is a pointer to the content

getAtomizedValueOfUntypedNode

AtomicValue getAtomizedValueOfUntypedNode(int nodeNr)
Get the typed value of a node whose type is known to be untypedAtomic. The node must be a document, element, text, comment, or processing-instruction node, and it must have no type annotation. This method gets the typed value of a numbered node without actually instantiating the NodeInfo object, as a performance optimization.

Parameters: nodeNr the node whose typed value is required

Returns: the atomic value of the node

getAttributeAnnotation

int getAttributeAnnotation(int nr)
Get the type annotation of an attribute node. The bit IS_DTD_TYPE (1<<30) will be set in the case of an attribute node if the type annotation is one of ID, IDREF, or IDREFS and this is derived from DTD rather than schema validation.

Parameters: nr the node number of the attribute

Returns: Type.UNTYPED_ATOMIC if there is no annotation

getAttributeNameCodeArray

public int[] getAttributeNameCodeArray()
Get the array used to hold the name codes of all attributes

Returns: an integer array; the Nth integer holds the attribute name code of attribute N

getAttributeNode

TinyAttributeImpl getAttributeNode(int nr)
Make a (transient) attribute node from the array of attributes

Parameters: nr the node number of the attribute

Returns: an attribute node

getAttributeParentArray

public int[] getAttributeParentArray()
Get the array used to hold the parent pointers of all attributes

Returns: an integer array; the Nth integer holds the pointer to the parent element of attribute N

getAttributeTypeCodeArray

public int[] getAttributeTypeCodeArray()
Get the array used to hold the type codes of all attributes

Returns: an integer array; the Nth integer holds the attribute type code of attribute N

getAttributeValueArray

public CharSequence[] getAttributeValueArray()
Get the array used to hold the name codes of all attributes

Returns: an array of strings; the Nth string holds the string value of attribute N

getBetaArray

public int[] getBetaArray()
Get the array holding beta information

Returns: an array of integers, whose meaning depends on the node kind. For elements it is a pointer to the first namespace declaration

getCharacterBuffer

public CharSequence getCharacterBuffer()
Get the character buffer used to hold all the text data of the document

Returns: the character buffer

getColumnNumber

int getColumnNumber(int sequence)
Get the column number for a node.

Parameters: sequence the node number

Returns: the line number of the node. Return -1 if line numbering is off.

getCommentBuffer

public CharSequence getCommentBuffer()
Get the character buffer used to hold all the comment data of the document

Returns: the character buffer used for comments

getConfiguration

public Configuration getConfiguration()
Get the configuration previously set using setConfiguration

Returns: the Saxon configuration

getDocumentNumber

public long getDocumentNumber()
Get the document number (actually, the tree number)

Returns: the unique number of this TinyTree structure

getLineNumber

public int getLineNumber(int sequence)
Get the line number for a node.

Parameters: sequence the node number

Returns: the line number of the node. Return -1 if line numbering is off.

getNameCode

public int getNameCode(int nodeNr)
Get the nameCode for a given node, which must be a document, element, text, comment, or processing instruction node

Parameters: nodeNr the node number

Returns: the name code

getNameCodeArray

public int[] getNameCodeArray()
Get the array holding node name information

Returns: an array of integers, integer N is the name code of node number N

getNamePool

public NamePool getNamePool()
Get the name pool used for the names in this document

Returns: the name pool

getNamespaceCodeArray

public int[] getNamespaceCodeArray()
Get the array used to hold the namespace codes of namespace declarations

Returns: an array of integer namespace codes

getNamespaceParentArray

public int[] getNamespaceParentArray()
Get the array used to hold the parent pointers of all namespace declarations

Returns: an integer array; the Nth integer holds the pointer to the parent element of namespace N

getNextPointerArray

public int[] getNextPointerArray()
Get the array holding next-sibling pointers

Returns: an array of integers, integer N is the next-sibling pointer for node number N

getNode

public final TinyNodeImpl getNode(int nr)
Get the node at a given position in the tree

Parameters: nr the node number

Returns: the node at the given position

getNodeDepthArray

public short[] getNodeDepthArray()
Get the array holding node depth information

Returns: an array of shorts, byte N is the node depth of node number N

getNodeKind

public int getNodeKind(int nodeNr)
Get the node kind of a given node, which must be a document, element, text, comment, or processing instruction node

Parameters: nodeNr the node number

Returns: the node kind

getNodeKindArray

public byte[] getNodeKindArray()
Get the array holding node kind information

Returns: an array of bytes, byte N is the node kind of node number N

getNumberOfAttributes

public int getNumberOfAttributes()
Get the number of attributes in the tree

Returns: the number of attributes

getNumberOfNamespaces

public int getNumberOfNamespaces()
Get the number of namespace declarations in the tree

Returns: the number of namespace declarations

getNumberOfNodes

public int getNumberOfNodes()
Get the number of nodes in the tree, excluding attributes and namespace nodes

Returns: the number of nodes.

getRootNode

int getRootNode(int nodeNr)
Get the root node for a given node

Parameters: nodeNr the node number of the given node

Returns: the node number of the root of the tree containing the given node

getSystemId

public String getSystemId(int seq)
Get the system id of an element in the document

Parameters: seq the node number of the element node

Returns: the system id (base URI) of the element

getTypeAnnotation

public int getTypeAnnotation(int nodeNr)
Get the type annotation of a node. Applies only to document, element, text, processing instruction, and comment nodes.

Parameters: nodeNr the node whose type annotation is required

Returns: the fingerprint of the type annotation for elements and attributes, otherwise undefined.

getTypeCodeArray

public int[] getTypeCodeArray()
Get the array holding node type information

Returns: an array of integers, integer N is the type code of node number N

getTypedValueOfAttribute

public Value getTypedValueOfAttribute(TinyAttributeImpl att)
Get the type value of an attribute node.

Parameters: att the attribute node

Returns: the typed value of the node

getTypedValueOfAttribute

public Value getTypedValueOfAttribute(int nodeNr)
Get the type value of an attribute node, given only the node number. This method avoids materializing the attribute node if possible

Parameters: nodeNr the node number of the attribute node

Returns: the typed value of the node

getTypedValueOfElement

public Value getTypedValueOfElement(TinyElementImpl element)
Get the type value of an element node.

Parameters: element the element node

Returns: the typed value of the node

getTypedValueOfElement

public Value getTypedValueOfElement(int nodeNr)
Get the type value of an element node, given only the node number

Parameters: nodeNr the node number of the element node

Returns: the typed value of the node

indexIDElement

public void indexIDElement(NodeInfo root, int nodeNr, NameChecker checker)
Index an element of type xs:ID

Parameters: root the root node of the document nodeNr the element of type xs:ID checker checks names against XML 1.0 or XML 1.1 rules

isIdAttribute

public boolean isIdAttribute(int nr)
Determine whether an attribute is an IDREF/IDREFS attribute. (The represents the is-idref property in the data model)

Parameters: nr the node number of the attribute

Returns: true if this is an IDREF/IDREFS attribute

isIdElement

public boolean isIdElement(int nr)
Ask whether an element is an ID element. (The represents the is-id property in the data model)

Parameters: nr the element node whose is-idref property is required

Returns: true if the node has the is-idref property

isIdrefAttribute

public boolean isIdrefAttribute(int nr)
Determine whether an attribute is an IDREF/IDREFS attribute. (The represents the is-idref property in the data model)

Parameters: nr the node number of the attribute

Returns: true if this is an IDREF/IDREFS attribute

isIdrefElement

public boolean isIdrefElement(int nr)
Ask whether an element is an IDREF/IDREFS element. (The represents the is-idref property in the data model)

Parameters: nr the element node whose is-idref property is required

Returns: true if the node has the is-idref property

isNilled

public boolean isNilled(int nodeNr)
Ask whether a given node is nilled

Parameters: nodeNr the node in question (which must be an element node)

Returns: true if the node has the nilled property

setConfiguration

public void setConfiguration(Configuration config)
Set the Configuration that contains this document

Parameters: config the Saxon configuration

setElementAnnotation

void setElementAnnotation(int nodeNr, int typeCode)
Set the type annotation of an element node

Parameters: nodeNr the node whose type annotation is to be set typeCode the type annotation

setLineNumber

void setLineNumber(int sequence, int line, int column)
Set the line number for a node. Ignored if line numbering is off.

Parameters: sequence the node number line the line number to be set for the node column the column number for the node

setLineNumbering

public void setLineNumbering()
Set line numbering on

setSystemId

void setSystemId(int seq, String uri)
Set the system id of an element in the document. This identifies the external entity containing the node - this is not necessarily the same as the base URI.

Parameters: seq the node number uri the system ID

showSize

public void showSize()
Output a statistical summary to System.err