0001: /*
0002: * Copyright 1999-2004 The Apache Software Foundation.
0003: *
0004: * Licensed under the Apache License, Version 2.0 (the "License");
0005: * you may not use this file except in compliance with the License.
0006: * You may obtain a copy of the License at
0007: *
0008: * http://www.apache.org/licenses/LICENSE-2.0
0009: *
0010: * Unless required by applicable law or agreed to in writing, software
0011: * distributed under the License is distributed on an "AS IS" BASIS,
0012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013: * See the License for the specific language governing permissions and
0014: * limitations under the License.
0015: */
0016: /*
0017: * $Id: NodeSet.java,v 1.22 2005/01/23 01:02:10 mcnamara Exp $
0018: */
0019: package org.apache.xpath;
0020:
0021: import org.apache.xalan.res.XSLMessages;
0022: import org.apache.xml.utils.DOM2Helper;
0023: import org.apache.xpath.axes.ContextNodeList;
0024: import org.apache.xpath.res.XPATHErrorResources;
0025:
0026: import org.w3c.dom.DOMException;
0027: import org.w3c.dom.Node;
0028: import org.w3c.dom.NodeList;
0029: import org.w3c.dom.traversal.NodeFilter;
0030: import org.w3c.dom.traversal.NodeIterator;
0031:
0032: /**
0033: * <p>The NodeSet class can act as either a NodeVector,
0034: * NodeList, or NodeIterator. However, in order for it to
0035: * act as a NodeVector or NodeList, it's required that
0036: * setShouldCacheNodes(true) be called before the first
0037: * nextNode() is called, in order that nodes can be added
0038: * as they are fetched. Derived classes that implement iterators
0039: * must override runTo(int index), in order that they may
0040: * run the iteration to the given index. </p>
0041: *
0042: * <p>Note that we directly implement the DOM's NodeIterator
0043: * interface. We do not emulate all the behavior of the
0044: * standard NodeIterator. In particular, we do not guarantee
0045: * to present a "live view" of the document ... but in XSLT,
0046: * the source document should never be mutated, so this should
0047: * never be an issue.</p>
0048: *
0049: * <p>Thought: Should NodeSet really implement NodeList and NodeIterator,
0050: * or should there be specific subclasses of it which do so? The
0051: * advantage of doing it all here is that all NodeSets will respond
0052: * to the same calls; the disadvantage is that some of them may return
0053: * less-than-enlightening results when you do so.</p>
0054: * @xsl.usage advanced
0055: */
0056: public class NodeSet implements NodeList, NodeIterator, Cloneable,
0057: ContextNodeList {
0058:
0059: /**
0060: * Create an empty nodelist.
0061: */
0062: public NodeSet() {
0063: m_blocksize = 32;
0064: m_mapSize = 0;
0065: }
0066:
0067: /**
0068: * Create an empty, using the given block size.
0069: *
0070: * @param blocksize Size of blocks to allocate
0071: */
0072: public NodeSet(int blocksize) {
0073: m_blocksize = blocksize;
0074: m_mapSize = 0;
0075: }
0076:
0077: /**
0078: * Create a NodeSet, and copy the members of the
0079: * given nodelist into it.
0080: *
0081: * @param nodelist List of Nodes to be made members of the new set.
0082: */
0083: public NodeSet(NodeList nodelist) {
0084:
0085: this (32);
0086:
0087: addNodes(nodelist);
0088: }
0089:
0090: /**
0091: * Create a NodeSet, and copy the members of the
0092: * given NodeSet into it.
0093: *
0094: * @param nodelist Set of Nodes to be made members of the new set.
0095: */
0096: public NodeSet(NodeSet nodelist) {
0097:
0098: this (32);
0099:
0100: addNodes((NodeIterator) nodelist);
0101: }
0102:
0103: /**
0104: * Create a NodeSet, and copy the members of the
0105: * given NodeIterator into it.
0106: *
0107: * @param ni Iterator which yields Nodes to be made members of the new set.
0108: */
0109: public NodeSet(NodeIterator ni) {
0110:
0111: this (32);
0112:
0113: addNodes(ni);
0114: }
0115:
0116: /**
0117: * Create a NodeSet which contains the given Node.
0118: *
0119: * @param node Single node to be added to the new set.
0120: */
0121: public NodeSet(Node node) {
0122:
0123: this (32);
0124:
0125: addNode(node);
0126: }
0127:
0128: /**
0129: * @return The root node of the Iterator, as specified when it was created.
0130: * For non-Iterator NodeSets, this will be null.
0131: */
0132: public Node getRoot() {
0133: return null;
0134: }
0135:
0136: /**
0137: * Get a cloned Iterator, and reset its state to the beginning of the
0138: * iteration.
0139: *
0140: * @return a new NodeSet of the same type, having the same state...
0141: * except that the reset() operation has been called.
0142: *
0143: * @throws CloneNotSupportedException if this subclass of NodeSet
0144: * does not support the clone() operation.
0145: */
0146: public NodeIterator cloneWithReset()
0147: throws CloneNotSupportedException {
0148:
0149: NodeSet clone = (NodeSet) clone();
0150:
0151: clone.reset();
0152:
0153: return clone;
0154: }
0155:
0156: /**
0157: * Reset the iterator. May have no effect on non-iterator Nodesets.
0158: */
0159: public void reset() {
0160: m_next = 0;
0161: }
0162:
0163: /**
0164: * This attribute determines which node types are presented via the
0165: * iterator. The available set of constants is defined in the
0166: * <code>NodeFilter</code> interface. For NodeSets, the mask has been
0167: * hardcoded to show all nodes except EntityReference nodes, which have
0168: * no equivalent in the XPath data model.
0169: *
0170: * @return integer used as a bit-array, containing flags defined in
0171: * the DOM's NodeFilter class. The value will be
0172: * <code>SHOW_ALL & ~SHOW_ENTITY_REFERENCE</code>, meaning that
0173: * only entity references are suppressed.
0174: */
0175: public int getWhatToShow() {
0176: return NodeFilter.SHOW_ALL & ~NodeFilter.SHOW_ENTITY_REFERENCE;
0177: }
0178:
0179: /**
0180: * The filter object used to screen nodes. Filters are applied to
0181: * further reduce (and restructure) the NodeIterator's view of the
0182: * document. In our case, we will be using hardcoded filters built
0183: * into our iterators... but getFilter() is part of the DOM's
0184: * NodeIterator interface, so we have to support it.
0185: *
0186: * @return null, which is slightly misleading. True, there is no
0187: * user-written filter object, but in fact we are doing some very
0188: * sophisticated custom filtering. A DOM purist might suggest
0189: * returning a placeholder object just to indicate that this is
0190: * not going to return all nodes selected by whatToShow.
0191: */
0192: public NodeFilter getFilter() {
0193: return null;
0194: }
0195:
0196: /**
0197: * The value of this flag determines whether the children of entity
0198: * reference nodes are visible to the iterator. If false, they will be
0199: * skipped over.
0200: * <br> To produce a view of the document that has entity references
0201: * expanded and does not expose the entity reference node itself, use the
0202: * whatToShow flags to hide the entity reference node and set
0203: * expandEntityReferences to true when creating the iterator. To produce
0204: * a view of the document that has entity reference nodes but no entity
0205: * expansion, use the whatToShow flags to show the entity reference node
0206: * and set expandEntityReferences to false.
0207: *
0208: * @return true for all iterators based on NodeSet, meaning that the
0209: * contents of EntityRefrence nodes may be returned (though whatToShow
0210: * says that the EntityReferences themselves are not shown.)
0211: */
0212: public boolean getExpandEntityReferences() {
0213: return true;
0214: }
0215:
0216: /**
0217: * Returns the next node in the set and advances the position of the
0218: * iterator in the set. After a NodeIterator is created, the first call
0219: * to nextNode() returns the first node in the set.
0220: * @return The next <code>Node</code> in the set being iterated over, or
0221: * <code>null</code> if there are no more members in that set.
0222: * @throws DOMException
0223: * INVALID_STATE_ERR: Raised if this method is called after the
0224: * <code>detach</code> method was invoked.
0225: */
0226: public Node nextNode() throws DOMException {
0227:
0228: if ((m_next) < this .size()) {
0229: Node next = this .elementAt(m_next);
0230:
0231: m_next++;
0232:
0233: return next;
0234: } else
0235: return null;
0236: }
0237:
0238: /**
0239: * Returns the previous node in the set and moves the position of the
0240: * iterator backwards in the set.
0241: * @return The previous <code>Node</code> in the set being iterated over,
0242: * or<code>null</code> if there are no more members in that set.
0243: * @throws DOMException
0244: * INVALID_STATE_ERR: Raised if this method is called after the
0245: * <code>detach</code> method was invoked.
0246: * @throws RuntimeException thrown if this NodeSet is not of
0247: * a cached type, and hence doesn't know what the previous node was.
0248: */
0249: public Node previousNode() throws DOMException {
0250:
0251: if (!m_cacheNodes)
0252: throw new RuntimeException(
0253: XSLMessages
0254: .createXPATHMessage(
0255: XPATHErrorResources.ER_NODESET_CANNOT_ITERATE,
0256: null)); //"This NodeSet can not iterate to a previous node!");
0257:
0258: if ((m_next - 1) > 0) {
0259: m_next--;
0260:
0261: return this .elementAt(m_next);
0262: } else
0263: return null;
0264: }
0265:
0266: /**
0267: * Detaches the iterator from the set which it iterated over, releasing
0268: * any computational resources and placing the iterator in the INVALID
0269: * state. After<code>detach</code> has been invoked, calls to
0270: * <code>nextNode</code> or<code>previousNode</code> will raise the
0271: * exception INVALID_STATE_ERR.
0272: * <p>
0273: * This operation is a no-op in NodeSet, and will not cause
0274: * INVALID_STATE_ERR to be raised by later operations.
0275: * </p>
0276: */
0277: public void detach() {
0278: }
0279:
0280: /**
0281: * Tells if this NodeSet is "fresh", in other words, if
0282: * the first nextNode() that is called will return the
0283: * first node in the set.
0284: *
0285: * @return true if nextNode() would return the first node in the set,
0286: * false if it would return a later one.
0287: */
0288: public boolean isFresh() {
0289: return (m_next == 0);
0290: }
0291:
0292: /**
0293: * If an index is requested, NodeSet will call this method
0294: * to run the iterator to the index. By default this sets
0295: * m_next to the index. If the index argument is -1, this
0296: * signals that the iterator should be run to the end.
0297: *
0298: * @param index Position to advance (or retreat) to, with
0299: * 0 requesting the reset ("fresh") position and -1 (or indeed
0300: * any out-of-bounds value) requesting the final position.
0301: * @throws RuntimeException thrown if this NodeSet is not
0302: * one of the types which supports indexing/counting.
0303: */
0304: public void runTo(int index) {
0305:
0306: if (!m_cacheNodes)
0307: throw new RuntimeException(XSLMessages.createXPATHMessage(
0308: XPATHErrorResources.ER_NODESET_CANNOT_INDEX, null)); //"This NodeSet can not do indexing or counting functions!");
0309:
0310: if ((index >= 0) && (m_next < m_firstFree))
0311: m_next = index;
0312: else
0313: m_next = m_firstFree - 1;
0314: }
0315:
0316: /**
0317: * Returns the <code>index</code>th item in the collection. If
0318: * <code>index</code> is greater than or equal to the number of nodes in
0319: * the list, this returns <code>null</code>.
0320: *
0321: * TODO: What happens if index is out of range?
0322: *
0323: * @param index Index into the collection.
0324: * @return The node at the <code>index</code>th position in the
0325: * <code>NodeList</code>, or <code>null</code> if that is not a valid
0326: * index.
0327: */
0328: public Node item(int index) {
0329:
0330: runTo(index);
0331:
0332: return (Node) this .elementAt(index);
0333: }
0334:
0335: /**
0336: * The number of nodes in the list. The range of valid child node indices is
0337: * 0 to <code>length-1</code> inclusive. Note that this operation requires
0338: * finding all the matching nodes, which may defeat attempts to defer
0339: * that work.
0340: *
0341: * @return integer indicating how many nodes are represented by this list.
0342: */
0343: public int getLength() {
0344:
0345: runTo(-1);
0346:
0347: return this .size();
0348: }
0349:
0350: /**
0351: * Add a node to the NodeSet. Not all types of NodeSets support this
0352: * operation
0353: *
0354: * @param n Node to be added
0355: * @throws RuntimeException thrown if this NodeSet is not of
0356: * a mutable type.
0357: */
0358: public void addNode(Node n) {
0359:
0360: if (!m_mutable)
0361: throw new RuntimeException(XSLMessages.createXPATHMessage(
0362: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0363:
0364: this .addElement(n);
0365: }
0366:
0367: /**
0368: * Insert a node at a given position.
0369: *
0370: * @param n Node to be added
0371: * @param pos Offset at which the node is to be inserted,
0372: * with 0 being the first position.
0373: * @throws RuntimeException thrown if this NodeSet is not of
0374: * a mutable type.
0375: */
0376: public void insertNode(Node n, int pos) {
0377:
0378: if (!m_mutable)
0379: throw new RuntimeException(XSLMessages.createXPATHMessage(
0380: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0381:
0382: insertElementAt(n, pos);
0383: }
0384:
0385: /**
0386: * Remove a node.
0387: *
0388: * @param n Node to be added
0389: * @throws RuntimeException thrown if this NodeSet is not of
0390: * a mutable type.
0391: */
0392: public void removeNode(Node n) {
0393:
0394: if (!m_mutable)
0395: throw new RuntimeException(XSLMessages.createXPATHMessage(
0396: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0397:
0398: this .removeElement(n);
0399: }
0400:
0401: /**
0402: * Copy NodeList members into this nodelist, adding in
0403: * document order. If a node is null, don't add it.
0404: *
0405: * @param nodelist List of nodes which should now be referenced by
0406: * this NodeSet.
0407: * @throws RuntimeException thrown if this NodeSet is not of
0408: * a mutable type.
0409: */
0410: public void addNodes(NodeList nodelist) {
0411:
0412: if (!m_mutable)
0413: throw new RuntimeException(XSLMessages.createXPATHMessage(
0414: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0415:
0416: if (null != nodelist) // defensive to fix a bug that Sanjiva reported.
0417: {
0418: int nChildren = nodelist.getLength();
0419:
0420: for (int i = 0; i < nChildren; i++) {
0421: Node obj = nodelist.item(i);
0422:
0423: if (null != obj) {
0424: addElement(obj);
0425: }
0426: }
0427: }
0428:
0429: // checkDups();
0430: }
0431:
0432: /**
0433: * <p>Copy NodeList members into this nodelist, adding in
0434: * document order. Only genuine node references will be copied;
0435: * nulls appearing in the source NodeSet will
0436: * not be added to this one. </p>
0437: *
0438: * <p> In case you're wondering why this function is needed: NodeSet
0439: * implements both NodeIterator and NodeList. If this method isn't
0440: * provided, Java can't decide which of those to use when addNodes()
0441: * is invoked. Providing the more-explicit match avoids that
0442: * ambiguity.)</p>
0443: *
0444: * @param ns NodeSet whose members should be merged into this NodeSet.
0445: * @throws RuntimeException thrown if this NodeSet is not of
0446: * a mutable type.
0447: */
0448: public void addNodes(NodeSet ns) {
0449:
0450: if (!m_mutable)
0451: throw new RuntimeException(XSLMessages.createXPATHMessage(
0452: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0453:
0454: addNodes((NodeIterator) ns);
0455: }
0456:
0457: /**
0458: * Copy NodeList members into this nodelist, adding in
0459: * document order. Null references are not added.
0460: *
0461: * @param iterator NodeIterator which yields the nodes to be added.
0462: * @throws RuntimeException thrown if this NodeSet is not of
0463: * a mutable type.
0464: */
0465: public void addNodes(NodeIterator iterator) {
0466:
0467: if (!m_mutable)
0468: throw new RuntimeException(XSLMessages.createXPATHMessage(
0469: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0470:
0471: if (null != iterator) // defensive to fix a bug that Sanjiva reported.
0472: {
0473: Node obj;
0474:
0475: while (null != (obj = iterator.nextNode())) {
0476: addElement(obj);
0477: }
0478: }
0479:
0480: // checkDups();
0481: }
0482:
0483: /**
0484: * Copy NodeList members into this nodelist, adding in
0485: * document order. If a node is null, don't add it.
0486: *
0487: * @param nodelist List of nodes to be added
0488: * @param support The XPath runtime context.
0489: * @throws RuntimeException thrown if this NodeSet is not of
0490: * a mutable type.
0491: */
0492: public void addNodesInDocOrder(NodeList nodelist,
0493: XPathContext support) {
0494:
0495: if (!m_mutable)
0496: throw new RuntimeException(XSLMessages.createXPATHMessage(
0497: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0498:
0499: int nChildren = nodelist.getLength();
0500:
0501: for (int i = 0; i < nChildren; i++) {
0502: Node node = nodelist.item(i);
0503:
0504: if (null != node) {
0505: addNodeInDocOrder(node, support);
0506: }
0507: }
0508: }
0509:
0510: /**
0511: * Copy NodeList members into this nodelist, adding in
0512: * document order. If a node is null, don't add it.
0513: *
0514: * @param iterator NodeIterator which yields the nodes to be added.
0515: * @param support The XPath runtime context.
0516: * @throws RuntimeException thrown if this NodeSet is not of
0517: * a mutable type.
0518: */
0519: public void addNodesInDocOrder(NodeIterator iterator,
0520: XPathContext support) {
0521:
0522: if (!m_mutable)
0523: throw new RuntimeException(XSLMessages.createXPATHMessage(
0524: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0525:
0526: Node node;
0527:
0528: while (null != (node = iterator.nextNode())) {
0529: addNodeInDocOrder(node, support);
0530: }
0531: }
0532:
0533: /**
0534: * Add the node list to this node set in document order.
0535: *
0536: * @param start index.
0537: * @param end index.
0538: * @param testIndex index.
0539: * @param nodelist The nodelist to add.
0540: * @param support The XPath runtime context.
0541: *
0542: * @return false always.
0543: * @throws RuntimeException thrown if this NodeSet is not of
0544: * a mutable type.
0545: */
0546: private boolean addNodesInDocOrder(int start, int end,
0547: int testIndex, NodeList nodelist, XPathContext support) {
0548:
0549: if (!m_mutable)
0550: throw new RuntimeException(XSLMessages.createXPATHMessage(
0551: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0552:
0553: boolean foundit = false;
0554: int i;
0555: Node node = nodelist.item(testIndex);
0556:
0557: for (i = end; i >= start; i--) {
0558: Node child = (Node) elementAt(i);
0559:
0560: if (child == node) {
0561: i = -2; // Duplicate, suppress insert
0562:
0563: break;
0564: }
0565:
0566: if (!DOM2Helper.isNodeAfter(node, child)) {
0567: insertElementAt(node, i + 1);
0568:
0569: testIndex--;
0570:
0571: if (testIndex > 0) {
0572: boolean foundPrev = addNodesInDocOrder(0, i,
0573: testIndex, nodelist, support);
0574:
0575: if (!foundPrev) {
0576: addNodesInDocOrder(i, size() - 1, testIndex,
0577: nodelist, support);
0578: }
0579: }
0580:
0581: break;
0582: }
0583: }
0584:
0585: if (i == -1) {
0586: insertElementAt(node, 0);
0587: }
0588:
0589: return foundit;
0590: }
0591:
0592: /**
0593: * Add the node into a vector of nodes where it should occur in
0594: * document order.
0595: * @param node The node to be added.
0596: * @param test true if we should test for doc order
0597: * @param support The XPath runtime context.
0598: * @return insertIndex.
0599: * @throws RuntimeException thrown if this NodeSet is not of
0600: * a mutable type.
0601: */
0602: public int addNodeInDocOrder(Node node, boolean test,
0603: XPathContext support) {
0604:
0605: if (!m_mutable)
0606: throw new RuntimeException(XSLMessages.createXPATHMessage(
0607: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0608:
0609: int insertIndex = -1;
0610:
0611: if (test) {
0612:
0613: // This needs to do a binary search, but a binary search
0614: // is somewhat tough because the sequence test involves
0615: // two nodes.
0616: int size = size(), i;
0617:
0618: for (i = size - 1; i >= 0; i--) {
0619: Node child = (Node) elementAt(i);
0620:
0621: if (child == node) {
0622: i = -2; // Duplicate, suppress insert
0623:
0624: break;
0625: }
0626:
0627: if (!DOM2Helper.isNodeAfter(node, child)) {
0628: break;
0629: }
0630: }
0631:
0632: if (i != -2) {
0633: insertIndex = i + 1;
0634:
0635: insertElementAt(node, insertIndex);
0636: }
0637: } else {
0638: insertIndex = this .size();
0639:
0640: boolean foundit = false;
0641:
0642: for (int i = 0; i < insertIndex; i++) {
0643: if (this .item(i).equals(node)) {
0644: foundit = true;
0645:
0646: break;
0647: }
0648: }
0649:
0650: if (!foundit)
0651: addElement(node);
0652: }
0653:
0654: // checkDups();
0655: return insertIndex;
0656: } // end addNodeInDocOrder(Vector v, Object obj)
0657:
0658: /**
0659: * Add the node into a vector of nodes where it should occur in
0660: * document order.
0661: * @param node The node to be added.
0662: * @param support The XPath runtime context.
0663: *
0664: * @return The index where it was inserted.
0665: * @throws RuntimeException thrown if this NodeSet is not of
0666: * a mutable type.
0667: */
0668: public int addNodeInDocOrder(Node node, XPathContext support) {
0669:
0670: if (!m_mutable)
0671: throw new RuntimeException(XSLMessages.createXPATHMessage(
0672: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0673:
0674: return addNodeInDocOrder(node, true, support);
0675: } // end addNodeInDocOrder(Vector v, Object obj)
0676:
0677: /** If this node is being used as an iterator, the next index that nextNode()
0678: * will return. */
0679: transient protected int m_next = 0;
0680:
0681: /**
0682: * Get the current position, which is one less than
0683: * the next nextNode() call will retrieve. i.e. if
0684: * you call getCurrentPos() and the return is 0, the next
0685: * fetch will take place at index 1.
0686: *
0687: * @return The the current position index.
0688: */
0689: public int getCurrentPos() {
0690: return m_next;
0691: }
0692:
0693: /**
0694: * Set the current position in the node set.
0695: * @param i Must be a valid index.
0696: * @throws RuntimeException thrown if this NodeSet is not of
0697: * a cached type, and thus doesn't permit indexed access.
0698: */
0699: public void setCurrentPos(int i) {
0700:
0701: if (!m_cacheNodes)
0702: throw new RuntimeException(XSLMessages.createXPATHMessage(
0703: XPATHErrorResources.ER_NODESET_CANNOT_INDEX, null)); //"This NodeSet can not do indexing or counting functions!");
0704:
0705: m_next = i;
0706: }
0707:
0708: /**
0709: * Return the last fetched node. Needed to support the UnionPathIterator.
0710: *
0711: * @return the last fetched node.
0712: * @throws RuntimeException thrown if this NodeSet is not of
0713: * a cached type, and thus doesn't permit indexed access.
0714: */
0715: public Node getCurrentNode() {
0716:
0717: if (!m_cacheNodes)
0718: throw new RuntimeException(XSLMessages.createXPATHMessage(
0719: XPATHErrorResources.ER_NODESET_CANNOT_INDEX, null)); //"This NodeSet can not do indexing or counting functions!");
0720:
0721: int saved = m_next;
0722: Node n = (m_next < m_firstFree) ? elementAt(m_next) : null;
0723: m_next = saved; // HACK: I think this is a bit of a hack. -sb
0724: return n;
0725: }
0726:
0727: /** True if this list can be mutated. */
0728: transient protected boolean m_mutable = true;
0729:
0730: /** True if this list is cached.
0731: * @serial */
0732: transient protected boolean m_cacheNodes = true;
0733:
0734: /**
0735: * Get whether or not this is a cached node set.
0736: *
0737: *
0738: * @return True if this list is cached.
0739: */
0740: public boolean getShouldCacheNodes() {
0741: return m_cacheNodes;
0742: }
0743:
0744: /**
0745: * If setShouldCacheNodes(true) is called, then nodes will
0746: * be cached. They are not cached by default. This switch must
0747: * be set before the first call to nextNode is made, to ensure
0748: * that all nodes are cached.
0749: *
0750: * @param b true if this node set should be cached.
0751: * @throws RuntimeException thrown if an attempt is made to
0752: * request caching after we've already begun stepping through the
0753: * nodes in this set.
0754: */
0755: public void setShouldCacheNodes(boolean b) {
0756:
0757: if (!isFresh())
0758: throw new RuntimeException(
0759: XSLMessages
0760: .createXPATHMessage(
0761: XPATHErrorResources.ER_CANNOT_CALL_SETSHOULDCACHENODE,
0762: null)); //"Can not call setShouldCacheNodes after nextNode has been called!");
0763:
0764: m_cacheNodes = b;
0765: m_mutable = true;
0766: }
0767:
0768: transient private int m_last = 0;
0769:
0770: public int getLast() {
0771: return m_last;
0772: }
0773:
0774: public void setLast(int last) {
0775: m_last = last;
0776: }
0777:
0778: /** Size of blocks to allocate.
0779: * @serial */
0780: private int m_blocksize;
0781:
0782: /** Array of nodes this points to.
0783: * @serial */
0784: Node m_map[];
0785:
0786: /** Number of nodes in this NodeVector.
0787: * @serial */
0788: protected int m_firstFree = 0;
0789:
0790: /** Size of the array this points to.
0791: * @serial */
0792: private int m_mapSize; // lazy initialization
0793:
0794: /**
0795: * Get a cloned LocPathIterator.
0796: *
0797: * @return A clone of this
0798: *
0799: * @throws CloneNotSupportedException
0800: */
0801: public Object clone() throws CloneNotSupportedException {
0802:
0803: NodeSet clone = (NodeSet) super .clone();
0804:
0805: if ((null != this .m_map) && (this .m_map == clone.m_map)) {
0806: clone.m_map = new Node[this .m_map.length];
0807:
0808: System.arraycopy(this .m_map, 0, clone.m_map, 0,
0809: this .m_map.length);
0810: }
0811:
0812: return clone;
0813: }
0814:
0815: /**
0816: * Get the length of the list.
0817: *
0818: * @return Number of nodes in this NodeVector
0819: */
0820: public int size() {
0821: return m_firstFree;
0822: }
0823:
0824: /**
0825: * Append a Node onto the vector.
0826: *
0827: * @param value Node to add to the vector
0828: */
0829: public void addElement(Node value) {
0830: if (!m_mutable)
0831: throw new RuntimeException(XSLMessages.createXPATHMessage(
0832: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
0833:
0834: if ((m_firstFree + 1) >= m_mapSize) {
0835: if (null == m_map) {
0836: m_map = new Node[m_blocksize];
0837: m_mapSize = m_blocksize;
0838: } else {
0839: m_mapSize += m_blocksize;
0840:
0841: Node newMap[] = new Node[m_mapSize];
0842:
0843: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
0844:
0845: m_map = newMap;
0846: }
0847: }
0848:
0849: m_map[m_firstFree] = value;
0850:
0851: m_firstFree++;
0852: }
0853:
0854: /**
0855: * Append a Node onto the vector.
0856: *
0857: * @param value Node to add to the vector
0858: */
0859: public final void push(Node value) {
0860:
0861: int ff = m_firstFree;
0862:
0863: if ((ff + 1) >= m_mapSize) {
0864: if (null == m_map) {
0865: m_map = new Node[m_blocksize];
0866: m_mapSize = m_blocksize;
0867: } else {
0868: m_mapSize += m_blocksize;
0869:
0870: Node newMap[] = new Node[m_mapSize];
0871:
0872: System.arraycopy(m_map, 0, newMap, 0, ff + 1);
0873:
0874: m_map = newMap;
0875: }
0876: }
0877:
0878: m_map[ff] = value;
0879:
0880: ff++;
0881:
0882: m_firstFree = ff;
0883: }
0884:
0885: /**
0886: * Pop a node from the tail of the vector and return the result.
0887: *
0888: * @return the node at the tail of the vector
0889: */
0890: public final Node pop() {
0891:
0892: m_firstFree--;
0893:
0894: Node n = m_map[m_firstFree];
0895:
0896: m_map[m_firstFree] = null;
0897:
0898: return n;
0899: }
0900:
0901: /**
0902: * Pop a node from the tail of the vector and return the
0903: * top of the stack after the pop.
0904: *
0905: * @return The top of the stack after it's been popped
0906: */
0907: public final Node popAndTop() {
0908:
0909: m_firstFree--;
0910:
0911: m_map[m_firstFree] = null;
0912:
0913: return (m_firstFree == 0) ? null : m_map[m_firstFree - 1];
0914: }
0915:
0916: /**
0917: * Pop a node from the tail of the vector.
0918: */
0919: public final void popQuick() {
0920:
0921: m_firstFree--;
0922:
0923: m_map[m_firstFree] = null;
0924: }
0925:
0926: /**
0927: * Return the node at the top of the stack without popping the stack.
0928: * Special purpose method for TransformerImpl, pushElemTemplateElement.
0929: * Performance critical.
0930: *
0931: * @return Node at the top of the stack or null if stack is empty.
0932: */
0933: public final Node peepOrNull() {
0934: return ((null != m_map) && (m_firstFree > 0)) ? m_map[m_firstFree - 1]
0935: : null;
0936: }
0937:
0938: /**
0939: * Push a pair of nodes into the stack.
0940: * Special purpose method for TransformerImpl, pushElemTemplateElement.
0941: * Performance critical.
0942: *
0943: * @param v1 First node to add to vector
0944: * @param v2 Second node to add to vector
0945: */
0946: public final void pushPair(Node v1, Node v2) {
0947:
0948: if (null == m_map) {
0949: m_map = new Node[m_blocksize];
0950: m_mapSize = m_blocksize;
0951: } else {
0952: if ((m_firstFree + 2) >= m_mapSize) {
0953: m_mapSize += m_blocksize;
0954:
0955: Node newMap[] = new Node[m_mapSize];
0956:
0957: System.arraycopy(m_map, 0, newMap, 0, m_firstFree);
0958:
0959: m_map = newMap;
0960: }
0961: }
0962:
0963: m_map[m_firstFree] = v1;
0964: m_map[m_firstFree + 1] = v2;
0965: m_firstFree += 2;
0966: }
0967:
0968: /**
0969: * Pop a pair of nodes from the tail of the stack.
0970: * Special purpose method for TransformerImpl, pushElemTemplateElement.
0971: * Performance critical.
0972: */
0973: public final void popPair() {
0974:
0975: m_firstFree -= 2;
0976: m_map[m_firstFree] = null;
0977: m_map[m_firstFree + 1] = null;
0978: }
0979:
0980: /**
0981: * Set the tail of the stack to the given node.
0982: * Special purpose method for TransformerImpl, pushElemTemplateElement.
0983: * Performance critical.
0984: *
0985: * @param n Node to set at the tail of vector
0986: */
0987: public final void setTail(Node n) {
0988: m_map[m_firstFree - 1] = n;
0989: }
0990:
0991: /**
0992: * Set the given node one position from the tail.
0993: * Special purpose method for TransformerImpl, pushElemTemplateElement.
0994: * Performance critical.
0995: *
0996: * @param n Node to set
0997: */
0998: public final void setTailSub1(Node n) {
0999: m_map[m_firstFree - 2] = n;
1000: }
1001:
1002: /**
1003: * Return the node at the tail of the vector without popping
1004: * Special purpose method for TransformerImpl, pushElemTemplateElement.
1005: * Performance critical.
1006: *
1007: * @return Node at the tail of the vector
1008: */
1009: public final Node peepTail() {
1010: return m_map[m_firstFree - 1];
1011: }
1012:
1013: /**
1014: * Return the node one position from the tail without popping.
1015: * Special purpose method for TransformerImpl, pushElemTemplateElement.
1016: * Performance critical.
1017: *
1018: * @return Node one away from the tail
1019: */
1020: public final Node peepTailSub1() {
1021: return m_map[m_firstFree - 2];
1022: }
1023:
1024: /**
1025: * Inserts the specified node in this vector at the specified index.
1026: * Each component in this vector with an index greater or equal to
1027: * the specified index is shifted upward to have an index one greater
1028: * than the value it had previously.
1029: *
1030: * @param value Node to insert
1031: * @param at Position where to insert
1032: */
1033: public void insertElementAt(Node value, int at) {
1034: if (!m_mutable)
1035: throw new RuntimeException(XSLMessages.createXPATHMessage(
1036: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
1037:
1038: if (null == m_map) {
1039: m_map = new Node[m_blocksize];
1040: m_mapSize = m_blocksize;
1041: } else if ((m_firstFree + 1) >= m_mapSize) {
1042: m_mapSize += m_blocksize;
1043:
1044: Node newMap[] = new Node[m_mapSize];
1045:
1046: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
1047:
1048: m_map = newMap;
1049: }
1050:
1051: if (at <= (m_firstFree - 1)) {
1052: System
1053: .arraycopy(m_map, at, m_map, at + 1, m_firstFree
1054: - at);
1055: }
1056:
1057: m_map[at] = value;
1058:
1059: m_firstFree++;
1060: }
1061:
1062: /**
1063: * Append the nodes to the list.
1064: *
1065: * @param nodes NodeVector to append to this list
1066: */
1067: public void appendNodes(NodeSet nodes) {
1068:
1069: int nNodes = nodes.size();
1070:
1071: if (null == m_map) {
1072: m_mapSize = nNodes + m_blocksize;
1073: m_map = new Node[m_mapSize];
1074: } else if ((m_firstFree + nNodes) >= m_mapSize) {
1075: m_mapSize += (nNodes + m_blocksize);
1076:
1077: Node newMap[] = new Node[m_mapSize];
1078:
1079: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + nNodes);
1080:
1081: m_map = newMap;
1082: }
1083:
1084: System.arraycopy(nodes.m_map, 0, m_map, m_firstFree, nNodes);
1085:
1086: m_firstFree += nNodes;
1087: }
1088:
1089: /**
1090: * Inserts the specified node in this vector at the specified index.
1091: * Each component in this vector with an index greater or equal to
1092: * the specified index is shifted upward to have an index one greater
1093: * than the value it had previously.
1094: */
1095: public void removeAllElements() {
1096:
1097: if (null == m_map)
1098: return;
1099:
1100: for (int i = 0; i < m_firstFree; i++) {
1101: m_map[i] = null;
1102: }
1103:
1104: m_firstFree = 0;
1105: }
1106:
1107: /**
1108: * Removes the first occurrence of the argument from this vector.
1109: * If the object is found in this vector, each component in the vector
1110: * with an index greater or equal to the object's index is shifted
1111: * downward to have an index one smaller than the value it had
1112: * previously.
1113: *
1114: * @param s Node to remove from the list
1115: *
1116: * @return True if the node was successfully removed
1117: */
1118: public boolean removeElement(Node s) {
1119: if (!m_mutable)
1120: throw new RuntimeException(XSLMessages.createXPATHMessage(
1121: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
1122:
1123: if (null == m_map)
1124: return false;
1125:
1126: for (int i = 0; i < m_firstFree; i++) {
1127: Node node = m_map[i];
1128:
1129: if ((null != node) && node.equals(s)) {
1130: if (i < m_firstFree - 1)
1131: System.arraycopy(m_map, i + 1, m_map, i,
1132: m_firstFree - i - 1);
1133:
1134: m_firstFree--;
1135: m_map[m_firstFree] = null;
1136:
1137: return true;
1138: }
1139: }
1140:
1141: return false;
1142: }
1143:
1144: /**
1145: * Deletes the component at the specified index. Each component in
1146: * this vector with an index greater or equal to the specified
1147: * index is shifted downward to have an index one smaller than
1148: * the value it had previously.
1149: *
1150: * @param i Index of node to remove
1151: */
1152: public void removeElementAt(int i) {
1153:
1154: if (null == m_map)
1155: return;
1156:
1157: if (i >= m_firstFree)
1158: throw new ArrayIndexOutOfBoundsException(i + " >= "
1159: + m_firstFree);
1160: else if (i < 0)
1161: throw new ArrayIndexOutOfBoundsException(i);
1162:
1163: if (i < m_firstFree - 1)
1164: System.arraycopy(m_map, i + 1, m_map, i, m_firstFree - i
1165: - 1);
1166:
1167: m_firstFree--;
1168: m_map[m_firstFree] = null;
1169: }
1170:
1171: /**
1172: * Sets the component at the specified index of this vector to be the
1173: * specified object. The previous component at that position is discarded.
1174: *
1175: * The index must be a value greater than or equal to 0 and less
1176: * than the current size of the vector.
1177: *
1178: * @param node Node to set
1179: * @param index Index of where to set the node
1180: */
1181: public void setElementAt(Node node, int index) {
1182: if (!m_mutable)
1183: throw new RuntimeException(XSLMessages.createXPATHMessage(
1184: XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
1185:
1186: if (null == m_map) {
1187: m_map = new Node[m_blocksize];
1188: m_mapSize = m_blocksize;
1189: }
1190:
1191: m_map[index] = node;
1192: }
1193:
1194: /**
1195: * Get the nth element.
1196: *
1197: * @param i Index of node to get
1198: *
1199: * @return Node at specified index
1200: */
1201: public Node elementAt(int i) {
1202:
1203: if (null == m_map)
1204: return null;
1205:
1206: return m_map[i];
1207: }
1208:
1209: /**
1210: * Tell if the table contains the given node.
1211: *
1212: * @param s Node to look for
1213: *
1214: * @return True if the given node was found.
1215: */
1216: public boolean contains(Node s) {
1217: runTo(-1);
1218:
1219: if (null == m_map)
1220: return false;
1221:
1222: for (int i = 0; i < m_firstFree; i++) {
1223: Node node = m_map[i];
1224:
1225: if ((null != node) && node.equals(s))
1226: return true;
1227: }
1228:
1229: return false;
1230: }
1231:
1232: /**
1233: * Searches for the first occurence of the given argument,
1234: * beginning the search at index, and testing for equality
1235: * using the equals method.
1236: *
1237: * @param elem Node to look for
1238: * @param index Index of where to start the search
1239: * @return the index of the first occurrence of the object
1240: * argument in this vector at position index or later in the
1241: * vector; returns -1 if the object is not found.
1242: */
1243: public int indexOf(Node elem, int index) {
1244: runTo(-1);
1245:
1246: if (null == m_map)
1247: return -1;
1248:
1249: for (int i = index; i < m_firstFree; i++) {
1250: Node node = m_map[i];
1251:
1252: if ((null != node) && node.equals(elem))
1253: return i;
1254: }
1255:
1256: return -1;
1257: }
1258:
1259: /**
1260: * Searches for the first occurence of the given argument,
1261: * beginning the search at index, and testing for equality
1262: * using the equals method.
1263: *
1264: * @param elem Node to look for
1265: * @return the index of the first occurrence of the object
1266: * argument in this vector at position index or later in the
1267: * vector; returns -1 if the object is not found.
1268: */
1269: public int indexOf(Node elem) {
1270: runTo(-1);
1271:
1272: if (null == m_map)
1273: return -1;
1274:
1275: for (int i = 0; i < m_firstFree; i++) {
1276: Node node = m_map[i];
1277:
1278: if ((null != node) && node.equals(elem))
1279: return i;
1280: }
1281:
1282: return -1;
1283: }
1284:
1285: }
|