1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.xerces.dom;
19
20 import org.w3c.dom.Node;
21 import org.w3c.dom.NodeList;
22
23 import java.util.Vector;
24
25 /**
26 * This class implements the DOM's NodeList behavior for
27 * Element.getElementsByTagName()
28 * <P>
29 * The DOM describes NodeList as follows:
30 * <P>
31 * 1) It may represent EITHER nodes scattered through a subtree (when
32 * returned by Element.getElementsByTagName), or just the immediate
33 * children (when returned by Node.getChildNodes). The latter is easy,
34 * but the former (which this class addresses) is more challenging.
35 * <P>
36 * 2) Its behavior is "live" -- that is, it always reflects the
37 * current state of the document tree. To put it another way, the
38 * NodeLists obtained before and after a series of insertions and
39 * deletions are effectively identical (as far as the user is
40 * concerned, the former has been dynamically updated as the changes
41 * have been made).
42 * <P>
43 * 3) Its API accesses individual nodes via an integer index, with the
44 * listed nodes numbered sequentially in the order that they were
45 * found during a preorder depth-first left-to-right search of the tree.
46 * (Of course in the case of getChildNodes, depth is not involved.) As
47 * nodes are inserted or deleted in the tree, and hence the NodeList,
48 * the numbering of nodes that follow them in the NodeList will
49 * change.
50 * <P>
51 * It is rather painful to support the latter two in the
52 * getElementsByTagName case. The current solution is for Nodes to
53 * maintain a change count (eventually that may be a Digest instead),
54 * which the NodeList tracks and uses to invalidate itself.
55 * <P>
56 * Unfortunately, this does _not_ respond efficiently in the case that
57 * the dynamic behavior was supposed to address: scanning a tree while
58 * it is being extended. That requires knowing which subtrees have
59 * changed, which can become an arbitrarily complex problem.
60 * <P>
61 * We save some work by filling the vector only as we access the
62 * item()s... but I suspect the same users who demanded index-based
63 * access will also start by doing a getLength() to control their loop,
64 * blowing this optimization out of the water.
65 * <P>
66 * NOTE: Level 2 of the DOM will probably _not_ use NodeList for its
67 * extended search mechanisms, partly for the reasons just discussed.
68 *
69 * @xerces.internal
70 *
71 * @version $Id: DeepNodeListImpl.java 447266 2006-09-18 05:57:49Z mrglavas $
72 * @since PR-DOM-Level-1-19980818.
73 */
74 public class DeepNodeListImpl
75 implements NodeList {
76
77 //
78 // Data
79 //
80
81 protected NodeImpl rootNode; // Where the search started
82 protected String tagName; // Or "*" to mean all-tags-acceptable
83 protected int changes=0;
84 protected Vector nodes;
85
86 protected String nsName;
87 protected boolean enableNS = false;
88
89 //
90 // Constructors
91 //
92
93 /** Constructor. */
94 public DeepNodeListImpl(NodeImpl rootNode, String tagName) {
95 this.rootNode = rootNode;
96 this.tagName = tagName;
97 nodes = new Vector();
98 }
99
100 /** Constructor for Namespace support. */
101 public DeepNodeListImpl(NodeImpl rootNode,
102 String nsName, String tagName) {
103 this(rootNode, tagName);
104 this.nsName = (nsName != null && !nsName.equals("")) ? nsName : 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 thisNode;
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 thisNode = rootNode;
139 else
140 thisNode=(NodeImpl)(nodes.lastElement());
141
142 // Add nodes up to the one we're looking for
143 while(thisNode != null && index >= nodes.size()) {
144 thisNode=nextMatchingElementAfter(thisNode);
145 if (thisNode != null)
146 nodes.addElement(thisNode);
147 }
148
149 // Either what we want, or null (not avail.)
150 return thisNode;
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 && null != (next = current.getNextSibling())) {
175 current = next;
176 }
177
178 // Look up and right (but not past root!)
179 else {
180 next = null;
181 for (; current != rootNode; // Stop when we return to starting point
182 current = current.getParentNode()) {
183
184 next = current.getNextSibling();
185 if (next != null)
186 break;
187 }
188 current = next;
189 }
190
191 // Have we found an Element with the right tagName?
192 // ("*" matches anything.)
193 if (current != rootNode
194 && current != null
195 && current.getNodeType() == Node.ELEMENT_NODE) {
196 if (!enableNS) {
197 if (tagName.equals("*") ||
198 ((ElementImpl) current).getTagName().equals(tagName))
199 {
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
210 && el.getNamespaceURI() == null)
211 || (nsName != null
212 && nsName.equals(el.getNamespaceURI())))
213 {
214 return current;
215 }
216 }
217 } else {
218 ElementImpl el = (ElementImpl) current;
219 if (el.getLocalName() != null
220 && el.getLocalName().equals(tagName)) {
221 if (nsName != null && nsName.equals("*")) {
222 return current;
223 } else {
224 if ((nsName == null
225 && el.getNamespaceURI() == null)
226 || (nsName != null &&
227 nsName.equals(el.getNamespaceURI())))
228 {
229 return current;
230 }
231 }
232 }
233 }
234 }
235 }
236
237 // Otherwise continue walking the tree
238 }
239
240 // Fell out of tree-walk; no more instances found
241 return null;
242
243 } // nextMatchingElementAfter(int):Node
244
245 } // class DeepNodeListImpl