DeepNodeListImpl


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