001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package org.apache.xerces.dom;
019:
020: import org.w3c.dom.Node;
021: import org.w3c.dom.NodeList;
022:
023: import java.util.Vector;
024:
025: /**
026: * This class implements the DOM's NodeList behavior for
027: * Element.getElementsByTagName()
028: * <P>
029: * The DOM describes NodeList as follows:
030: * <P>
031: * 1) It may represent EITHER nodes scattered through a subtree (when
032: * returned by Element.getElementsByTagName), or just the immediate
033: * children (when returned by Node.getChildNodes). The latter is easy,
034: * but the former (which this class addresses) is more challenging.
035: * <P>
036: * 2) Its behavior is "live" -- that is, it always reflects the
037: * current state of the document tree. To put it another way, the
038: * NodeLists obtained before and after a series of insertions and
039: * deletions are effectively identical (as far as the user is
040: * concerned, the former has been dynamically updated as the changes
041: * have been made).
042: * <P>
043: * 3) Its API accesses individual nodes via an integer index, with the
044: * listed nodes numbered sequentially in the order that they were
045: * found during a preorder depth-first left-to-right search of the tree.
046: * (Of course in the case of getChildNodes, depth is not involved.) As
047: * nodes are inserted or deleted in the tree, and hence the NodeList,
048: * the numbering of nodes that follow them in the NodeList will
049: * change.
050: * <P>
051: * It is rather painful to support the latter two in the
052: * getElementsByTagName case. The current solution is for Nodes to
053: * maintain a change count (eventually that may be a Digest instead),
054: * which the NodeList tracks and uses to invalidate itself.
055: * <P>
056: * Unfortunately, this does _not_ respond efficiently in the case that
057: * the dynamic behavior was supposed to address: scanning a tree while
058: * it is being extended. That requires knowing which subtrees have
059: * changed, which can become an arbitrarily complex problem.
060: * <P>
061: * We save some work by filling the vector only as we access the
062: * item()s... but I suspect the same users who demanded index-based
063: * access will also start by doing a getLength() to control their loop,
064: * blowing this optimization out of the water.
065: * <P>
066: * NOTE: Level 2 of the DOM will probably _not_ use NodeList for its
067: * extended search mechanisms, partly for the reasons just discussed.
068: *
069: * @xerces.internal
070: *
071: * @version $Id: DeepNodeListImpl.java 447266 2006-09-18 05:57:49Z mrglavas $
072: * @since PR-DOM-Level-1-19980818.
073: */
074: public class DeepNodeListImpl implements NodeList {
075:
076: //
077: // Data
078: //
079:
080: protected NodeImpl rootNode; // Where the search started
081: protected String tagName; // Or "*" to mean all-tags-acceptable
082: protected int changes = 0;
083: protected Vector nodes;
084:
085: protected String nsName;
086: protected boolean enableNS = false;
087:
088: //
089: // Constructors
090: //
091:
092: /** Constructor. */
093: public DeepNodeListImpl(NodeImpl rootNode, String tagName) {
094: this .rootNode = rootNode;
095: this .tagName = tagName;
096: nodes = new Vector();
097: }
098:
099: /** Constructor for Namespace support. */
100: public DeepNodeListImpl(NodeImpl rootNode, String nsName,
101: String tagName) {
102: this (rootNode, tagName);
103: this .nsName = (nsName != null && !nsName.equals("")) ? nsName
104: : null;
105: enableNS = true;
106: }
107:
108: //
109: // NodeList methods
110: //
111:
112: /** Returns the length of the node list. */
113: public int getLength() {
114: // Preload all matching elements. (Stops when we run out of subtree!)
115: item(java.lang.Integer.MAX_VALUE);
116: return nodes.size();
117: }
118:
119: /** Returns the node at the specified index. */
120: public Node item(int index) {
121: Node this Node;
122:
123: // Tree changed. Do it all from scratch!
124: if (rootNode.changes() != changes) {
125: nodes = new Vector();
126: changes = rootNode.changes();
127: }
128:
129: // In the cache
130: if (index < nodes.size())
131: return (Node) nodes.elementAt(index);
132:
133: // Not yet seen
134: else {
135:
136: // Pick up where we left off (Which may be the beginning)
137: if (nodes.size() == 0)
138: this Node = rootNode;
139: else
140: this Node = (NodeImpl) (nodes.lastElement());
141:
142: // Add nodes up to the one we're looking for
143: while (this Node != null && index >= nodes.size()) {
144: this Node = nextMatchingElementAfter(this Node);
145: if (this Node != null)
146: nodes.addElement(this Node);
147: }
148:
149: // Either what we want, or null (not avail.)
150: return this Node;
151: }
152:
153: } // item(int):Node
154:
155: //
156: // Protected methods (might be overridden by an extending DOM)
157: //
158:
159: /**
160: * Iterative tree-walker. When you have a Parent link, there's often no
161: * need to resort to recursion. NOTE THAT only Element nodes are matched
162: * since we're specifically supporting getElementsByTagName().
163: */
164: protected Node nextMatchingElementAfter(Node current) {
165:
166: Node next;
167: while (current != null) {
168: // Look down to first child.
169: if (current.hasChildNodes()) {
170: current = (current.getFirstChild());
171: }
172:
173: // Look right to sibling (but not from root!)
174: else if (current != rootNode
175: && null != (next = current.getNextSibling())) {
176: current = next;
177: }
178:
179: // Look up and right (but not past root!)
180: else {
181: next = null;
182: for (; current != rootNode; // Stop when we return to starting point
183: current = current.getParentNode()) {
184:
185: next = current.getNextSibling();
186: if (next != null)
187: break;
188: }
189: current = next;
190: }
191:
192: // Have we found an Element with the right tagName?
193: // ("*" matches anything.)
194: if (current != rootNode && current != null
195: && current.getNodeType() == Node.ELEMENT_NODE) {
196: if (!enableNS) {
197: if (tagName.equals("*")
198: || ((ElementImpl) current).getTagName()
199: .equals(tagName)) {
200: return current;
201: }
202: } else {
203: // DOM2: Namespace logic.
204: if (tagName.equals("*")) {
205: if (nsName != null && nsName.equals("*")) {
206: return current;
207: } else {
208: ElementImpl el = (ElementImpl) current;
209: if ((nsName == null && el.getNamespaceURI() == null)
210: || (nsName != null && nsName
211: .equals(el
212: .getNamespaceURI()))) {
213: return current;
214: }
215: }
216: } else {
217: ElementImpl el = (ElementImpl) current;
218: if (el.getLocalName() != null
219: && el.getLocalName().equals(tagName)) {
220: if (nsName != null && nsName.equals("*")) {
221: return current;
222: } else {
223: if ((nsName == null && el
224: .getNamespaceURI() == null)
225: || (nsName != null && nsName
226: .equals(el
227: .getNamespaceURI()))) {
228: return current;
229: }
230: }
231: }
232: }
233: }
234: }
235:
236: // Otherwise continue walking the tree
237: }
238:
239: // Fell out of tree-walk; no more instances found
240: return null;
241:
242: } // nextMatchingElementAfter(int):Node
243:
244: } // class DeepNodeListImpl
|