DeepNodeListImpl


1   /*
2    * The Apache Software License, Version 1.1
3    *
4    *
5    * Copyright (c) 1999-2002 The Apache Software Foundation.  All rights 
6    * reserved.
7    *
8    * Redistribution and use in source and binary forms, with or without
9    * modification, are permitted provided that the following conditions
10   * are met:
11   *
12   * 1. Redistributions of source code must retain the above copyright
13   *    notice, this list of conditions and the following disclaimer. 
14   *
15   * 2. Redistributions in binary form must reproduce the above copyright
16   *    notice, this list of conditions and the following disclaimer in
17   *    the documentation and/or other materials provided with the
18   *    distribution.
19   *
20   * 3. The end-user documentation included with the redistribution,
21   *    if any, must include the following acknowledgment:  
22   *       "This product includes software developed by the
23   *        Apache Software Foundation (http://www.apache.org/)."
24   *    Alternately, this acknowledgment may appear in the software itself,
25   *    if and wherever such third-party acknowledgments normally appear.
26   *
27   * 4. The names "Xerces" and "Apache Software Foundation" must
28   *    not be used to endorse or promote products derived from this
29   *    software without prior written permission. For written 
30   *    permission, please contact apache@apache.org.
31   *
32   * 5. Products derived from this software may not be called "Apache",
33   *    nor may "Apache" appear in their name, without prior written
34   *    permission of the Apache Software Foundation.
35   *
36   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47   * SUCH DAMAGE.
48   * ====================================================================
49   *
50   * This software consists of voluntary contributions made by many
51   * individuals on behalf of the Apache Software Foundation and was
52   * originally based on software copyright (c) 1999, International
53   * Business Machines, Inc., http://www.apache.org.  For more
54   * information on the Apache Software Foundation, please see
55   * <http://www.apache.org/>.
56   */
57  
58  package com.sun.org.apache.xerces.internal.dom;
59  
60  import org.w3c.dom.Node  ;
61  import org.w3c.dom.NodeList  ;
62  
63  import java.util.Vector  ;
64  
65  /**
66   * This class implements the DOM's NodeList behavior for
67   * Element.getElementsByTagName()
68   * <P>
69   * The DOM describes NodeList as follows:
70   * <P>
71   * 1) It may represent EITHER nodes scattered through a subtree (when
72   * returned by Element.getElementsByTagName), or just the immediate
73   * children (when returned by Node.getChildNodes). The latter is easy,
74   * but the former (which this class addresses) is more challenging.
75   * <P>
76   * 2) Its behavior is "live" -- that is, it always reflects the
77   * current state of the document tree. To put it another way, the
78   * NodeLists obtained before and after a series of insertions and
79   * deletions are effectively identical (as far as the user is
80   * concerned, the former has been dynamically updated as the changes
81   * have been made).
82   * <P>
83   * 3) Its API accesses individual nodes via an integer index, with the
84   * listed nodes numbered sequentially in the order that they were
85   * found during a preorder depth-first left-to-right search of the tree.
86   * (Of course in the case of getChildNodes, depth is not involved.) As
87   * nodes are inserted or deleted in the tree, and hence the NodeList,
88   * the numbering of nodes that follow them in the NodeList will
89   * change.
90   * <P>
91   * It is rather painful to support the latter two in the
92   * getElementsByTagName case. The current solution is for Nodes to
93   * maintain a change count (eventually that may be a Digest instead),
94   * which the NodeList tracks and uses to invalidate itself.
95   * <P>
96   * Unfortunately, this does _not_ respond efficiently in the case that
97   * the dynamic behavior was supposed to address: scanning a tree while
98   * it is being extended. That requires knowing which subtrees have
99   * changed, which can become an arbitrarily complex problem.
100  * <P>
101  * We save some work by filling the vector only as we access the
102  * item()s... but I suspect the same users who demanded index-based
103  * access will also start by doing a getLength() to control their loop,
104  * blowing this optimization out of the water.
105  * <P>
106  * NOTE: Level 2 of the DOM will probably _not_ use NodeList for its
107  * extended search mechanisms, partly for the reasons just discussed.
108  *
109  * @version $Id: DeepNodeListImpl.java,v 1.7 2002/01/29 01:15:07 lehors Exp $
110  * @since  PR-DOM-Level-1-19980818.
111  */
112 public class DeepNodeListImpl 
113     implements NodeList   {
114 
115     //
116     // Data
117     //
118 
119     protected NodeImpl rootNode; // Where the search started
120     protected String   tagName;   // Or "*" to mean all-tags-acceptable
121     protected int changes=0;
122     protected Vector   nodes;
123     
124     protected String   nsName;
125     protected boolean enableNS = false;
126 
127     //
128     // Constructors
129     //
130 
131     /** Constructor. */
132     public DeepNodeListImpl(NodeImpl rootNode, String   tagName) {
133         this.rootNode = rootNode;
134         this.tagName  = tagName;
135         nodes = new Vector  ();
136     }  
137 
138     /** Constructor for Namespace support. */
139     public DeepNodeListImpl(NodeImpl rootNode,
140                             String   nsName, String   tagName) {
141         this(rootNode, tagName);
142         this.nsName = (nsName != null && !nsName.equals("")) ? nsName : null;
143         enableNS = true;
144     }
145     
146     //
147     // NodeList methods
148     //
149 
150     /** Returns the length of the node list. */
151     public int getLength() {
152         // Preload all matching elements. (Stops when we run out of subtree!)
153         item(java.lang.Integer.MAX_VALUE);
154         return nodes.size();
155     }  
156 
157     /** Returns the node at the specified index. */
158     public Node   item(int index) {
159         Node   thisNode;
160 
161         // Tree changed. Do it all from scratch!
162         if(rootNode.changes() != changes) {
163             nodes   = new Vector  ();     
164             changes = rootNode.changes();
165         }
166     
167         // In the cache
168         if (index < nodes.size())      
169             return (Node  )nodes.elementAt(index);
170     
171         // Not yet seen
172         else {
173     
174             // Pick up where we left off (Which may be the beginning)
175             if (nodes.size() == 0)     
176                 thisNode = rootNode;
177             else
178                 thisNode=(NodeImpl)(nodes.lastElement());
179     
180             // Add nodes up to the one we're looking for
181             while(thisNode != null && index >= nodes.size()) {
182                 thisNode=nextMatchingElementAfter(thisNode);
183                 if (thisNode != null)
184                     nodes.addElement(thisNode);
185                 }
186 
187             // Either what we want, or null (not avail.)
188             return thisNode;           
189         }
190 
191     } // item(int):Node
192 
193     //
194     // Protected methods (might be overridden by an extending DOM)
195     //
196 
197     /** 
198      * Iterative tree-walker. When you have a Parent link, there's often no
199      * need to resort to recursion. NOTE THAT only Element nodes are matched
200      * since we're specifically supporting getElementsByTagName().
201      */
202     protected Node   nextMatchingElementAfter(Node   current) {
203 
204         Node   next;
205         while (current != null) {
206             // Look down to first child.
207             if (current.hasChildNodes()) {
208                 current = (current.getFirstChild());
209             }
210 
211             // Look right to sibling (but not from root!)
212             else if (current != rootNode && null != (next = current.getNextSibling())) {
213                 current = next;
214             }
215 
216             // Look up and right (but not past root!)
217             else {
218                 next = null;
219                 for (; current != rootNode; // Stop when we return to starting point
220                     current = current.getParentNode()) {
221 
222                     next = current.getNextSibling();
223                     if (next != null)
224                         break;
225                 }
226                 current = next;
227             }
228 
229             // Have we found an Element with the right tagName?
230             // ("*" matches anything.)
231             if (current != rootNode 
232                 && current != null
233                 && current.getNodeType() ==  Node.ELEMENT_NODE) {
234             if (!enableNS) {
235                 if (tagName.equals("*") ||
236                 ((ElementImpl) current).getTagName().equals(tagName))
237                 {
238                 return current;
239                 }
240             } else {
241                 // DOM2: Namespace logic. 
242                 if (tagName.equals("*")) {
243                 if (nsName != null && nsName.equals("*")) {
244                     return current;
245                 } else {
246                     ElementImpl el = (ElementImpl) current;
247                     if ((nsName == null
248                      && el.getNamespaceURI() == null)
249                     || (nsName != null
250                         && nsName.equals(el.getNamespaceURI())))
251                     {
252                     return current;
253                     }
254                 }
255                 } else {
256                 ElementImpl el = (ElementImpl) current;
257                 if (el.getLocalName() != null
258                     && el.getLocalName().equals(tagName)) {
259                     if (nsName != null && nsName.equals("*")) {
260                     return current;
261                     } else {
262                     if ((nsName == null
263                          && el.getNamespaceURI() == null)
264                         || (nsName != null &&
265                         nsName.equals(el.getNamespaceURI())))
266                     {
267                         return current;
268                     }
269                     }
270                 }
271                 }
272             }
273             }
274 
275         // Otherwise continue walking the tree
276         }
277 
278         // Fell out of tree-walk; no more instances found
279         return null;
280 
281     } // nextMatchingElementAfter(int):Node
282 
283 } // class DeepNodeListImpl
284
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags