View Javadoc
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