001: /*
002: * The Apache Software License, Version 1.1
003: *
004: *
005: * Copyright (c) 1999 The Apache Software Foundation. All rights
006: * reserved.
007: *
008: * Redistribution and use in source and binary forms, with or without
009: * modification, are permitted provided that the following conditions
010: * are met:
011: *
012: * 1. Redistributions of source code must retain the above copyright
013: * notice, this list of conditions and the following disclaimer.
014: *
015: * 2. Redistributions in binary form must reproduce the above copyright
016: * notice, this list of conditions and the following disclaimer in
017: * the documentation and/or other materials provided with the
018: * distribution.
019: *
020: * 3. The end-user documentation included with the redistribution,
021: * if any, must include the following acknowledgment:
022: * "This product includes software developed by the
023: * Apache Software Foundation (http://www.apache.org/)."
024: * Alternately, this acknowledgment may appear in the software itself,
025: * if and wherever such third-party acknowledgments normally appear.
026: *
027: * 4. The names "Xerces" and "Apache Software Foundation" must
028: * not be used to endorse or promote products derived from this
029: * software without prior written permission. For written
030: * permission, please contact apache@apache.org.
031: *
032: * 5. Products derived from this software may not be called "Apache",
033: * nor may "Apache" appear in their name, without prior written
034: * permission of the Apache Software Foundation.
035: *
036: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
037: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
038: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
039: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
040: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
041: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
042: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
043: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
044: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
045: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
046: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
047: * SUCH DAMAGE.
048: * ====================================================================
049: *
050: * This software consists of voluntary contributions made by many
051: * individuals on behalf of the Apache Software Foundation and was
052: * originally based on software copyright (c) 1999, International
053: * Business Machines, Inc., http://www.apache.org. For more
054: * information on the Apache Software Foundation, please see
055: * <http://www.apache.org/>.
056: */
057:
058: package org.apache.xerces.dom;
059:
060: import org.w3c.dom.Node;
061: import org.w3c.dom.NodeList;
062:
063: import java.util.Vector;
064:
065: /**
066: * This class implements the DOM's NodeList behavior for
067: * Element.getElementsByTagName()
068: * <P>
069: * The DOM describes NodeList as follows:
070: * <P>
071: * 1) It may represent EITHER nodes scattered through a subtree (when
072: * returned by Element.getElementsByTagName), or just the immediate
073: * children (when returned by Node.getChildNodes). The latter is easy,
074: * but the former (which this class addresses) is more challenging.
075: * <P>
076: * 2) Its behavior is "live" -- that is, it always reflects the
077: * current state of the document tree. To put it another way, the
078: * NodeLists obtained before and after a series of insertions and
079: * deletions are effectively identical (as far as the user is
080: * concerned, the former has been dynamically updated as the changes
081: * have been made).
082: * <P>
083: * 3) Its API accesses individual nodes via an integer index, with the
084: * listed nodes numbered sequentially in the order that they were
085: * found during a preorder depth-first left-to-right search of the tree.
086: * (Of course in the case of getChildNodes, depth is not involved.) As
087: * nodes are inserted or deleted in the tree, and hence the NodeList,
088: * the numbering of nodes that follow them in the NodeList will
089: * change.
090: * <P>
091: * It is rather painful to support the latter two in the
092: * getElementsByTagName case. The current solution is for Nodes to
093: * maintain a change count (eventually that may be a Digest instead),
094: * which the NodeList tracks and uses to invalidate itself.
095: * <P>
096: * Unfortunately, this does _not_ respond efficiently in the case that
097: * the dynamic behavior was supposed to address: scanning a tree while
098: * it is being extended. That requires knowing which subtrees have
099: * changed, which can become an arbitrarily complex problem.
100: * <P>
101: * We save some work by filling the vector only as we access the
102: * item()s... but I suspect the same users who demanded index-based
103: * access will also start by doing a getLength() to control their loop,
104: * blowing this optimization out of the water.
105: * <P>
106: * NOTE: Level 2 of the DOM will probably _not_ use NodeList for its
107: * extended search mechanisms, partly for the reasons just discussed.
108: *
109: * @version
110: * @since PR-DOM-Level-1-19980818.
111: */
112: public class DeepNodeListImpl implements NodeList {
113:
114: //
115: // Data
116: //
117:
118: protected NodeImpl rootNode; // Where the search started
119: protected String tagName; // Or "*" to mean all-tags-acceptable
120: protected int changes = 0;
121: protected Vector nodes;
122:
123: protected String nsName;
124: protected boolean enableNS = false;
125:
126: //
127: // Constructors
128: //
129:
130: /** Constructor. */
131: public DeepNodeListImpl(NodeImpl rootNode, String tagName) {
132: this .rootNode = rootNode;
133: this .tagName = tagName;
134: nodes = new Vector();
135: }
136:
137: /** Constructor for Namespace support. */
138: public DeepNodeListImpl(NodeImpl rootNode, String nsName,
139: String tagName) {
140: this (rootNode, tagName);
141: this .nsName = (nsName != null && !nsName.equals("")) ? nsName
142: : null;
143: enableNS = true;
144: }
145:
146: //
147: // NodeList methods
148: //
149:
150: /** Returns the length of the node list. */
151: public int getLength() {
152: // Preload all matching elements. (Stops when we run out of subtree!)
153: item(java.lang.Integer.MAX_VALUE);
154: return nodes.size();
155: }
156:
157: /** Returns the node at the specified index. */
158: public Node item(int index) {
159: Node this Node;
160:
161: // Tree changed. Do it all from scratch!
162: if (rootNode.changes() != changes) {
163: nodes = new Vector();
164: changes = rootNode.changes();
165: }
166:
167: // In the cache
168: if (index < nodes.size())
169: return (Node) nodes.elementAt(index);
170:
171: // Not yet seen
172: else {
173:
174: // Pick up where we left off (Which may be the beginning)
175: if (nodes.size() == 0)
176: this Node = rootNode;
177: else
178: this Node = (NodeImpl) (nodes.lastElement());
179:
180: // Add nodes up to the one we're looking for
181: while (this Node != null && index >= nodes.size()) {
182: this Node = nextMatchingElementAfter(this Node);
183: if (this Node != null)
184: nodes.addElement(this Node);
185: }
186:
187: // Either what we want, or null (not avail.)
188: return this Node;
189: }
190:
191: } // item(int):Node
192:
193: //
194: // Protected methods (might be overridden by an extending DOM)
195: //
196:
197: /**
198: * Iterative tree-walker. When you have a Parent link, there's often no
199: * need to resort to recursion. NOTE THAT only Element nodes are matched
200: * since we're specifically supporting getElementsByTagName().
201: */
202: protected Node nextMatchingElementAfter(Node current) {
203:
204: Node next;
205: while (current != null) {
206: // Look down to first child.
207: if (current.hasChildNodes()) {
208: current = (current.getFirstChild());
209: }
210:
211: // Look right to sibling (but not from root!)
212: else if (current != rootNode
213: && null != (next = current.getNextSibling())) {
214: current = next;
215: }
216:
217: // Look up and right (but not past root!)
218: else {
219: next = null;
220: for (; current != rootNode; // Stop when we return to starting point
221: current = current.getParentNode()) {
222:
223: next = current.getNextSibling();
224: if (next != null)
225: break;
226: }
227: current = next;
228: }
229:
230: // Have we found an Element with the right tagName?
231: // ("*" matches anything.)
232: if (current != rootNode && current != null
233: && current.getNodeType() == Node.ELEMENT_NODE) {
234: if (!enableNS) {
235: if (tagName.equals("*")
236: || ((ElementImpl) current).getTagName()
237: .equals(tagName)) {
238: return current;
239: }
240: } else {
241: // DOM2: Namespace logic.
242: if (tagName.equals("*")) {
243: if (nsName != null && nsName.equals("*")) {
244: return current;
245: } else {
246: ElementImpl el = (ElementImpl) current;
247: if ((nsName == null && el.getNamespaceURI() == null)
248: || (nsName != null && nsName
249: .equals(el
250: .getNamespaceURI()))) {
251: return current;
252: }
253: }
254: } else {
255: ElementImpl el = (ElementImpl) current;
256: if (el.getLocalName() != null
257: && el.getLocalName().equals(tagName)) {
258: if (nsName != null && nsName.equals("*")) {
259: return current;
260: } else {
261: if ((nsName == null && el
262: .getNamespaceURI() == null)
263: || (nsName != null && nsName
264: .equals(el
265: .getNamespaceURI()))) {
266: return current;
267: }
268: }
269: }
270: }
271: }
272: }
273:
274: // Otherwise continue walking the tree
275: }
276:
277: // Fell out of tree-walk; no more instances found
278: return null;
279:
280: } // nextMatchingElementAfter(int):Node
281:
282: } // class DeepNodeListImpl
|