org.exist.dom
Class ExtArrayNodeSet

java.lang.Object
  org.exist.xquery.value.AbstractSequence
      org.exist.dom.AbstractNodeSet
          org.exist.dom.ExtArrayNodeSet

All Implemented Interfaces:

org.w3c.dom.NodeList, NodeSet, Sequence

public class ExtArrayNodeSet

extends AbstractNodeSet

A fast node set implementation, based on arrays to store nodes and documents. The class uses an array to store all nodes belonging to one document. Another sorted array is used to keep track of the document ids. For each document, we maintain an inner class, Part, which stores the array of nodes. Nodes are just appended to the nodes array. No order is guaranteed and calls to get/contains may fail although a node is present in the array (get/contains do a binary search and thus assume that the set is sorted). Also, duplicates are allowed. If you have to ensure that calls to get/contains return valid results at any time and no duplicates occur, use class AVLTreeNodeSet. Use this class, if you can either ensure that items are added in order, or no calls to contains/get are required during the creation phase. Only after a call to one of the iterator methods, the set will get sorted and duplicates removed.

Since:

0.9.3

Author:

Wolfgang

Field Summary

protected int	initalSize
protected int	lastDoc
protected org.exist.dom.ExtArrayNodeSet.Part	lastPart
protected int	size

Fields inherited from class org.exist.dom.AbstractNodeSet

hasMixedContent, hasTextIndex, indexType, LOG

Fields inherited from interface org.exist.dom.NodeSet

ANCESTOR, DESCENDANT, EMPTY_SET, FOLLOWING, PRECEDING

Fields inherited from interface org.exist.xquery.value.Sequence

EMPTY_SEQUENCE

Constructor Summary

ExtArrayNodeSet()

ExtArrayNodeSet(int initialArraySize)

ExtArrayNodeSet(int initialDocsCount, int initialArraySize)

Method Summary

void	add(NodeProxy proxy) Add a new proxy object to the node set.
void	add(NodeProxy proxy, int sizeHint) Add a new node to the set.
void	addAll(NodeSet other) Add all nodes from the given node set.
boolean	contains(DocumentImpl doc, long nodeId)
boolean	contains(NodeProxy proxy) Check if this node set contains a node matching the document and node-id of the given NodeProxy object.
boolean	containsDoc(DocumentImpl doc) Check if this node set contains nodes belonging to the given document.
NodeProxy	get(DocumentImpl doc, long nodeId) Get a node from this node set matching the document and node id.
NodeProxy	get(int pos) Get the node at position pos within this node set.
NodeProxy	get(NodeProxy p) Get a node from this node set matching the document and node id of the given NodeProxy.
DocumentSet	getDocumentSet() Returns the set of documents from which the node items in this sequence have been selected.
int	getIndexType() If all nodes in this set have an index, returns the common supertype used to build the index, e.g.
int	getItemType() Return the primary type to which all items in this sequence belong.
int	getLength() Return the number of nodes contained in this node set.
protected org.exist.dom.ExtArrayNodeSet.Part	getPart(DocumentImpl doc, boolean create, int sizeHint)
void	getRange(NodeSet result, DocumentImpl doc, long lower, long upper) Return a sub-range of this node set containing the range of nodes greater than or including the lower node and smaller than or including the upper node.
int	getSizeHint(DocumentImpl doc) Get a hint about how many nodes in this node set belong to the specified document.
int	getState()
boolean	hasChanged(int previousState)
protected NodeSet	hasChildrenInSet(NodeSet al, int mode, int contextId) Get all children of the given parent node contained in this node set.
org.w3c.dom.Node	item(int pos)
Item	itemAt(int pos) Returns the item located at the specified position within this sequence.
SequenceIterator	iterate() Returns an iterator over all items in the sequence.
NodeSetIterator	iterator() Return an iterator on the nodes in this list.
void	mergeDuplicates() Remove all duplicate nodes, but merge their contexts.
NodeProxy	parentWithChild(DocumentImpl doc, long gid, boolean directParent, boolean includeSelf, int level) Check if the node identified by its node id has an ancestor contained in this node set and return the ancestor found.
void	remove(NodeProxy node) Remove a node.
NodeSet	selectAncestorDescendant(NodeSet al, int mode, boolean includeSelf, int contextId) Check if any descendant nodes are found within this node set for a given set of potential ancestor nodes.
NodeSet	selectAncestors(NodeSet al, boolean includeSelf, int contextId) For a given set of potential ancestor nodes, return all ancestors having descendants in this node set.
NodeSet	selectFollowingSiblings(NodeSet siblings, int contextId) Select all nodes from the passed node set, which are following siblings of the nodes in this set.
NodeSet	selectParentChild(NodeSet al, int mode, int contextId) Check if any child nodes are found within this node set for a given set of potential ancestor nodes.
NodeSet	selectPrecedingSiblings(NodeSet siblings, int contextId) Select all nodes from the passed node set, which are preceding or following siblings of the nodes in this set.
void	setDocumentSet(DocumentSet docs)
void	setSelfAsContext(int contextId)
void	sort()
void	sort(boolean mergeContexts)
void	sortInDocumentOrder()
java.lang.String	toString()
SequenceIterator	unorderedIterator() Returns an iterator over all items in the sequence.

Methods inherited from class org.exist.dom.AbstractNodeSet

add, addAll, clearContext, deepIntersection, directSelectAttribute, except, getAncestors, getContextNodes, getParents, hasMixedContent, hasTextIndex, intersection, isCached, isPersistentSet, parentWithChild, parentWithChild, parentWithChild, removeDuplicates, selectFollowing, selectParentChild, selectPreceding, setIsCached, toNodeSet, union

Methods inherited from class org.exist.xquery.value.AbstractSequence

conversionPreference, convertTo, effectiveBooleanValue, getCardinality, getStringValue, toJavaObject

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.exist.xquery.value.Sequence

conversionPreference, convertTo, effectiveBooleanValue, getCardinality, getStringValue, toJavaObject

Field Detail

initalSize

protected int initalSize

size

protected int size

lastDoc

protected int lastDoc

lastPart

protected org.exist.dom.ExtArrayNodeSet.Part lastPart

Constructor Detail

ExtArrayNodeSet

public ExtArrayNodeSet()

ExtArrayNodeSet

public ExtArrayNodeSet(int initialDocsCount,
                       int initialArraySize)

ExtArrayNodeSet

public ExtArrayNodeSet(int initialArraySize)

Method Detail

getPart

protected org.exist.dom.ExtArrayNodeSet.Part getPart(DocumentImpl doc,
                                                     boolean create,
                                                     int sizeHint)

containsDoc

public boolean containsDoc(DocumentImpl doc)

Description copied from class: AbstractNodeSet

Check if this node set contains nodes belonging to the given document.

Specified by:

containsDoc in interface NodeSet

Overrides:

containsDoc in class AbstractNodeSet

Parameters:

doc -

Returns:

add

public void add(NodeProxy proxy)

Description copied from class: AbstractNodeSet

Add a new proxy object to the node set. Please note: node set implementations may allow duplicates.

Specified by:

add in interface NodeSet

Specified by:

add in class AbstractNodeSet

Parameters:

proxy -

add

public void add(NodeProxy proxy,
                int sizeHint)

Add a new node to the set. If a new array of nodes has to be allocated for the document, use the sizeHint parameter to determine the size of the newly allocated array. This will overwrite the default array size. If the size hint is correct, no further reallocations will be required.

Specified by:

add in interface NodeSet

Overrides:

add in class AbstractNodeSet

Parameters:

proxy -

sizeHint -

getItemType

public int getItemType()

Description copied from interface: Sequence

Return the primary type to which all items in this sequence belong. This is Type.NODE for node sets, Type.ITEM for other sequences with mixed items.

Specified by:

getItemType in interface Sequence

Overrides:

getItemType in class AbstractNodeSet

getSizeHint

public int getSizeHint(DocumentImpl doc)

Description copied from class: AbstractNodeSet

Get a hint about how many nodes in this node set belong to the specified document. This is just used for allocating new node sets. The information does not need to be exact. -1 is returned if the size cannot be determined (the default).

Specified by:

getSizeHint in interface NodeSet

Overrides:

getSizeHint in class AbstractNodeSet

Parameters:

doc -

Returns:

iterator

public NodeSetIterator iterator()

Description copied from class: AbstractNodeSet

Return an iterator on the nodes in this list. The iterator returns nodes according to the internal ordering of nodes (i.e. level first), not in document- order.

Specified by:

iterator in interface NodeSet

Specified by:

iterator in class AbstractNodeSet

Returns:

iterate

public SequenceIterator iterate()

Description copied from interface: Sequence

Returns an iterator over all items in the sequence. The items are returned in document order where applicable.

Specified by:

iterate in interface Sequence

Specified by:

iterate in class AbstractNodeSet

unorderedIterator

public SequenceIterator unorderedIterator()

Description copied from interface: Sequence

Returns an iterator over all items in the sequence. The returned items may - but need not - to be in document order.

Specified by:

unorderedIterator in interface Sequence

Specified by:

unorderedIterator in class AbstractNodeSet

contains

public boolean contains(DocumentImpl doc,
                        long nodeId)

contains

public boolean contains(NodeProxy proxy)

Description copied from class: AbstractNodeSet

Check if this node set contains a node matching the document and node-id of the given NodeProxy object.

Specified by:

contains in interface NodeSet

Specified by:

contains in class AbstractNodeSet

Parameters:

proxy -

Returns:

addAll

public void addAll(NodeSet other)

Description copied from class: AbstractNodeSet

Add all nodes from the given node set.

Specified by:

addAll in interface NodeSet

Specified by:

addAll in class AbstractNodeSet

Parameters:

other -

getLength

public int getLength()

Description copied from class: AbstractNodeSet

Return the number of nodes contained in this node set.

Specified by:

getLength in interface NodeSet

Specified by:

getLength in class AbstractNodeSet

item

public org.w3c.dom.Node item(int pos)

Specified by:

item in interface org.w3c.dom.NodeList

Specified by:

item in class AbstractNodeSet

get

public NodeProxy get(int pos)

Description copied from class: AbstractNodeSet

Get the node at position pos within this node set.

Specified by:

get in interface NodeSet

Specified by:

get in class AbstractNodeSet

Parameters:

pos -

Returns:

get

public NodeProxy get(NodeProxy p)

Description copied from class: AbstractNodeSet

Get a node from this node set matching the document and node id of the given NodeProxy.

Specified by:

get in interface NodeSet

Specified by:

get in class AbstractNodeSet

Parameters:

p -

Returns:

get

public NodeProxy get(DocumentImpl doc,
                     long nodeId)

Description copied from class: AbstractNodeSet

Get a node from this node set matching the document and node id.

Specified by:

get in interface NodeSet

Specified by:

get in class AbstractNodeSet

Parameters:

doc -

nodeId -

Returns:

itemAt

public Item itemAt(int pos)

Description copied from interface: Sequence

Returns the item located at the specified position within this sequence. Items are counted beginning at 0.

Specified by:

itemAt in interface Sequence

Specified by:

itemAt in class AbstractSequence

remove

public void remove(NodeProxy node)

Description copied from class: AbstractNodeSet

Remove a node. By default, this method throws a RuntimeException.

Overrides:

remove in class AbstractNodeSet

Parameters:

node -

getRange

public void getRange(NodeSet result,
                     DocumentImpl doc,
                     long lower,
                     long upper)

Description copied from class: AbstractNodeSet

Return a sub-range of this node set containing the range of nodes greater than or including the lower node and smaller than or including the upper node.

Specified by:

getRange in interface NodeSet

Overrides:

getRange in class AbstractNodeSet

Parameters:

doc -

lower -

upper -

Returns:

hasChildrenInSet

protected NodeSet hasChildrenInSet(NodeSet al,
                                   int mode,
                                   int contextId)

Description copied from class: AbstractNodeSet

Get all children of the given parent node contained in this node set. If mode is NodeSet.DESCENDANT, the returned node set will contain all children found in this node set. If mode is NodeSet.ANCESTOR, the parent itself will be returned if it has child nodes in this set.

Overrides:

hasChildrenInSet in class AbstractNodeSet

Parameters:

mode -

Returns:

mergeDuplicates

public void mergeDuplicates()

Remove all duplicate nodes, but merge their contexts.

sort

public void sort()

sort

public void sort(boolean mergeContexts)

sortInDocumentOrder

public final void sortInDocumentOrder()

setSelfAsContext

public void setSelfAsContext(int contextId)

Specified by:

setSelfAsContext in interface Sequence

Overrides:

setSelfAsContext in class AbstractSequence

selectParentChild

public NodeSet selectParentChild(NodeSet al,
                                 int mode,
                                 int contextId)

Description copied from class: AbstractNodeSet

Check if any child nodes are found within this node set for a given set of potential ancestor nodes. If mode is NodeSet.DESCENDANT, the returned node set will contain all child nodes found in this node set for each parent node. If mode is NodeSet.ANCESTOR, the returned set will contain those parent nodes, for which children have been found.

Specified by:

selectParentChild in interface NodeSet

Overrides:

selectParentChild in class AbstractNodeSet

Parameters:

al - a node set containing potential parent nodes

mode - selection mode

contextId - used to track context nodes when evaluating predicate expressions. If contextId != Expression.NO_CONTEXT_ID, the current context will be added to each result of the of the selection.

Returns:

selectAncestorDescendant

public NodeSet selectAncestorDescendant(NodeSet al,
                                        int mode,
                                        boolean includeSelf,
                                        int contextId)

Description copied from class: AbstractNodeSet

Check if any descendant nodes are found within this node set for a given set of potential ancestor nodes. If mode is NodeSet.DESCENDANT, the returned node set will contain all descendant nodes found in this node set for each ancestor. If mode is NodeSet.ANCESTOR, the returned set will contain those ancestor nodes, for which descendants have been found.

Specified by:

selectAncestorDescendant in interface NodeSet

Overrides:

selectAncestorDescendant in class AbstractNodeSet

Parameters:

al - a node set containing potential parent nodes

mode - selection mode

includeSelf - if true, check if the ancestor node itself is contained in the set of descendant nodes (descendant-or-self axis)

contextId - used to track context nodes when evaluating predicate expressions. If contextId != Expression.NO_CONTEXT_ID, the current context will be added to each result of the of the selection.

Returns:

selectPrecedingSiblings

public NodeSet selectPrecedingSiblings(NodeSet siblings,
                                       int contextId)

Description copied from class: AbstractNodeSet

Select all nodes from the passed node set, which are preceding or following siblings of the nodes in this set. If mode is NodeSet.FOLLOWING, only nodes following the context node are selected. NodeSet.PRECEDING selects preceding nodes.

Specified by:

selectPrecedingSiblings in interface NodeSet

Overrides:

selectPrecedingSiblings in class AbstractNodeSet

Parameters:

siblings - a node set containing potential siblings

contextId - used to track context nodes when evaluating predicate expressions. If contextId != Expression.NO_CONTEXT_ID, the current context will be added to each result of the of the selection.

Returns:

selectFollowingSiblings

public NodeSet selectFollowingSiblings(NodeSet siblings,
                                       int contextId)

Description copied from interface: NodeSet

Select all nodes from the passed node set, which are following siblings of the nodes in this set.

Specified by:

selectFollowingSiblings in interface NodeSet

Overrides:

selectFollowingSiblings in class AbstractNodeSet

selectAncestors

public NodeSet selectAncestors(NodeSet al,
                               boolean includeSelf,
                               int contextId)

Description copied from class: AbstractNodeSet

For a given set of potential ancestor nodes, return all ancestors having descendants in this node set.

Specified by:

selectAncestors in interface NodeSet

Overrides:

selectAncestors in class AbstractNodeSet

Parameters:

includeSelf - if true, check if the ancestor node itself is contained in this node set (ancestor-or-self axis)

Returns:

parentWithChild

public NodeProxy parentWithChild(DocumentImpl doc,
                                 long gid,
                                 boolean directParent,
                                 boolean includeSelf,
                                 int level)

Description copied from class: AbstractNodeSet

Check if the node identified by its node id has an ancestor contained in this node set and return the ancestor found. If directParent is true, only immediate ancestors (parents) are considered. Otherwise the method will call itself recursively for all the node's parents. If includeSelf is true, the method returns also true if the node itself is contained in the node set.

Specified by:

parentWithChild in interface NodeSet

Overrides:

parentWithChild in class AbstractNodeSet

getIndexType

public int getIndexType()

Description copied from class: AbstractNodeSet

If all nodes in this set have an index, returns the common supertype used to build the index, e.g. xs:integer or xs:string. If the nodes have different index types or no node has been indexed, returns Type.ITEM.

Specified by:

getIndexType in interface NodeSet

Overrides:

getIndexType in class AbstractNodeSet

Returns:

See Also:

GeneralComparison, ValueComparison

getDocumentSet

public DocumentSet getDocumentSet()

Description copied from interface: Sequence

Returns the set of documents from which the node items in this sequence have been selected. This is for internal use only.

Specified by:

getDocumentSet in interface NodeSet

Overrides:

getDocumentSet in class AbstractNodeSet

setDocumentSet

public void setDocumentSet(DocumentSet docs)

hasChanged

public boolean hasChanged(int previousState)

Specified by:

hasChanged in interface NodeSet

Overrides:

hasChanged in class AbstractNodeSet

getState

public int getState()

Specified by:

getState in interface NodeSet

Overrides:

getState in class AbstractNodeSet

toString

public java.lang.String toString()

Overrides:

toString in class AbstractNodeSet