1 /*
2 * reserved comment block
3 * DO NOT REMOVE OR ALTER!
4 */
5 /*
6 * Copyright 1999-2002,2004 The Apache Software Foundation.
7 *
8 * Licensed under the Apache License, Version 2.0 (the "License");
9 * you may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
11 *
12 * http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing, software
15 * distributed under the License is distributed on an "AS IS" BASIS,
16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17 * See the License for the specific language governing permissions and
18 * limitations under the License.
19 */
20
21 package com.sun.org.apache.xerces.internal.dom;
22
23 import org.w3c.dom.Node;
24 import org.w3c.dom.NodeList;
25
26 import java.util.Vector;
27
28 /**
29 * This class implements the DOM's NodeList behavior for
30 * Element.getElementsByTagName()
31 * <P>
32 * The DOM describes NodeList as follows:
33 * <P>
34 * 1) It may represent EITHER nodes scattered through a subtree (when
35 * returned by Element.getElementsByTagName), or just the immediate
36 * children (when returned by Node.getChildNodes). The latter is easy,
37 * but the former (which this class addresses) is more challenging.
38 * <P>
39 * 2) Its behavior is "live" -- that is, it always reflects the
40 * current state of the document tree. To put it another way, the
41 * NodeLists obtained before and after a series of insertions and
42 * deletions are effectively identical (as far as the user is
43 * concerned, the former has been dynamically updated as the changes
44 * have been made).
45 * <P>
46 * 3) Its API accesses individual nodes via an integer index, with the
47 * listed nodes numbered sequentially in the order that they were
48 * found during a preorder depth-first left-to-right search of the tree.
49 * (Of course in the case of getChildNodes, depth is not involved.) As
50 * nodes are inserted or deleted in the tree, and hence the NodeList,
51 * the numbering of nodes that follow them in the NodeList will
52 * change.
53 * <P>
54 * It is rather painful to support the latter two in the
55 * getElementsByTagName case. The current solution is for Nodes to
56 * maintain a change count (eventually that may be a Digest instead),
57 * which the NodeList tracks and uses to invalidate itself.
58 * <P>
59 * Unfortunately, this does _not_ respond efficiently in the case that
60 * the dynamic behavior was supposed to address: scanning a tree while
61 * it is being extended. That requires knowing which subtrees have
62 * changed, which can become an arbitrarily complex problem.
63 * <P>
64 * We save some work by filling the vector only as we access the
65 * item()s... but I suspect the same users who demanded index-based
66 * access will also start by doing a getLength() to control their loop,
67 * blowing this optimization out of the water.
68 * <P>
69 * NOTE: Level 2 of the DOM will probably _not_ use NodeList for its
70 * extended search mechanisms, partly for the reasons just discussed.
71 *
72 * @xerces.internal
73 *
74 * @since PR-DOM-Level-1-19980818.
75 */
76 public class DeepNodeListImpl
77 implements NodeList {
78
79 //
80 // Data
81 //
82
83 protected NodeImpl rootNode; // Where the search started
84 protected String tagName; // Or "*" to mean all-tags-acceptable
85 protected int changes=0;
86 protected Vector nodes;
87
88 protected String nsName;
89 protected boolean enableNS = false;
90
91 //
92 // Constructors
93 //
94
95 /** Constructor. */
96 public DeepNodeListImpl(NodeImpl rootNode, String tagName) {
97 this.rootNode = rootNode;
98 this.tagName = tagName;
99 nodes = new Vector();
100 }
101
102 /** Constructor for Namespace support. */
103 public DeepNodeListImpl(NodeImpl rootNode,
104 String nsName, String tagName) {
105 this(rootNode, tagName);
106 this.nsName = (nsName != null && !nsName.equals("")) ? nsName : null;
107 enableNS = true;
108 }
109
110 //
111 // NodeList methods
112 //
113
114 /** Returns the length of the node list. */
115 public int getLength() {
116 // Preload all matching elements. (Stops when we run out of subtree!)
117 item(java.lang.Integer.MAX_VALUE);
118 return nodes.size();
119 }
120
121 /** Returns the node at the specified index. */
122 public Node item(int index) {
123 Node thisNode;
124
125 // Tree changed. Do it all from scratch!
126 if(rootNode.changes() != changes) {
127 nodes = new Vector();
128 changes = rootNode.changes();
129 }
130
131 // In the cache
132 if (index < nodes.size())
133 return (Node)nodes.elementAt(index);
134
135 // Not yet seen
136 else {
137
138 // Pick up where we left off (Which may be the beginning)
139 if (nodes.size() == 0)
140 thisNode = rootNode;
141 else
142 thisNode=(NodeImpl)(nodes.lastElement());
143
144 // Add nodes up to the one we're looking for
145 while(thisNode != null && index >= nodes.size()) {
146 thisNode=nextMatchingElementAfter(thisNode);
147 if (thisNode != null)
148 nodes.addElement(thisNode);
149 }
150
151 // Either what we want, or null (not avail.)
152 return thisNode;
153 }
154
155 } // item(int):Node
156
157 //
158 // Protected methods (might be overridden by an extending DOM)
159 //
160
161 /**
162 * Iterative tree-walker. When you have a Parent link, there's often no
163 * need to resort to recursion. NOTE THAT only Element nodes are matched
164 * since we're specifically supporting getElementsByTagName().
165 */
166 protected Node nextMatchingElementAfter(Node current) {
167
168 Node next;
169 while (current != null) {
170 // Look down to first child.
171 if (current.hasChildNodes()) {
172 current = (current.getFirstChild());
173 }
174
175 // Look right to sibling (but not from root!)
176 else if (current != rootNode && null != (next = current.getNextSibling())) {
177 current = next;
178 }
179
180 // Look up and right (but not past root!)
181 else {
182 next = null;
183 for (; current != rootNode; // Stop when we return to starting point
184 current = current.getParentNode()) {
185
186 next = current.getNextSibling();
187 if (next != null)
188 break;
189 }
190 current = next;
191 }
192
193 // Have we found an Element with the right tagName?
194 // ("*" matches anything.)
195 if (current != rootNode
196 && current != null
197 && current.getNodeType() == Node.ELEMENT_NODE) {
198 if (!enableNS) {
199 if (tagName.equals("*") ||
200 ((ElementImpl) current).getTagName().equals(tagName))
201 {
202 return current;
203 }
204 } else {
205 // DOM2: Namespace logic.
206 if (tagName.equals("*")) {
207 if (nsName != null && nsName.equals("*")) {
208 return current;
209 } else {
210 ElementImpl el = (ElementImpl) current;
211 if ((nsName == null
212 && el.getNamespaceURI() == null)
213 || (nsName != null
214 && nsName.equals(el.getNamespaceURI())))
215 {
216 return current;
217 }
218 }
219 } else {
220 ElementImpl el = (ElementImpl) current;
221 if (el.getLocalName() != null
222 && el.getLocalName().equals(tagName)) {
223 if (nsName != null && nsName.equals("*")) {
224 return current;
225 } else {
226 if ((nsName == null
227 && el.getNamespaceURI() == null)
228 || (nsName != null &&
229 nsName.equals(el.getNamespaceURI())))
230 {
231 return current;
232 }
233 }
234 }
235 }
236 }
237 }
238
239 // Otherwise continue walking the tree
240 }
241
242 // Fell out of tree-walk; no more instances found
243 return null;
244
245 } // nextMatchingElementAfter(int):Node
246
247 } // class DeepNodeListImpl