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