content: package org.jaxen.dom;
  
  /*
   * $Header$
   * $Revision$
   * $Date$
   *
   * ====================================================================
   *
   * Copyright 2000-2005 bob mcwhirter & James Strachan.
   * All rights reserved.
   *
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions are
   * met:
   * 
   *   * Redistributions of source code must retain the above copyright
   *     notice, this list of conditions and the following disclaimer.
   * 
   *   * Redistributions in binary form must reproduce the above copyright
   *     notice, this list of conditions and the following disclaimer in the
   *     documentation and/or other materials provided with the distribution.
   * 
   *   * Neither the name of the Jaxen Project nor the names of its
   *     contributors may be used to endorse or promote products derived 
   *     from this software without specific prior written permission.
   * 
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
   * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
   * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
   * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   *
   * ====================================================================
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Jaxen Project and was originally
   * created by bob mcwhirter <bob@werken.com> and
   * James Strachan <jstrachan@apache.org>.  For more information on the
   * Jaxen Project, please see <http://www.jaxen.org/>.
   *
   * $Id$
  */
  
  import javax.xml.parsers.DocumentBuilder;
  import javax.xml.parsers.DocumentBuilderFactory;
  import javax.xml.parsers.ParserConfigurationException;
  
  import java.io.IOException;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.NoSuchElementException;
  
  import org.jaxen.DefaultNavigator;
  import org.jaxen.FunctionCallException;
  import org.jaxen.Navigator;
  import org.jaxen.XPath;
  import org.jaxen.JaxenConstants;
  import org.w3c.dom.Attr;
  import org.w3c.dom.Document;
  import org.w3c.dom.NamedNodeMap;
  import org.w3c.dom.Node;
  import org.w3c.dom.NodeList;
  import org.w3c.dom.ProcessingInstruction;
  import org.xml.sax.SAXException;
  
  /** Interface for navigating around the W3C DOM Level 2 object model.
   *
   *  <p>
   *  This class is not intended for direct usage, but is
   *  used by the Jaxen engine during evaluation.
   *  </p>
   *
   *  <p>This class implements the {@link org.jaxen.DefaultNavigator} interface
   *  for the Jaxen XPath library.  This adapter allows the Jaxen
   *  library to be used to execute XPath queries against any object tree
   *  that implements the DOM level 2 interfaces.</p>
   *
   *  <p>Note: DOM level 2 does not include a node representing an XPath
   *  namespace node.  This navigator will return namespace nodes
   *  as instances of the custom {@link NamespaceNode} class, and
   *  users will have to check result sets to locate and isolate
   *  these.</p>
   *
   *  @author David Megginson
   *  @author James Strachan
   *
   *  @see XPath
   *  @see NamespaceNode
   */
  public class DocumentNavigator extends DefaultNavigator
  {
  
      
      ////////////////////////////////////////////////////////////////////
      // Constants.
      ////////////////////////////////////////////////////////////////////
  
      /**
       * 
       */
      private static final long serialVersionUID = 8460943068889528115L; 
      
      private final static DocumentNavigator SINGLETON = new DocumentNavigator();
  
  
      
      ////////////////////////////////////////////////////////////////////
      // Constructor.
      ////////////////////////////////////////////////////////////////////
  
  
      /**
       * Default constructor.
       */
      public DocumentNavigator ()
      {
      }
  
  
      /**
       * Get a constant DocumentNavigator for efficiency.
       *
       * @return a constant instance of a DocumentNavigator.
       */
      public static Navigator getInstance ()
      {
          return SINGLETON;
      }
  
  
      
      ////////////////////////////////////////////////////////////////////
      // Implementation of org.jaxen.DefaultNavigator.
      ////////////////////////////////////////////////////////////////////
  
  
      /**
       * Get an iterator over all of this node's children.
       *
       * @param contextNode the context node for the child axis.
       * @return a possibly-empty iterator (not null)
       */
      public Iterator getChildAxisIterator (Object contextNode)
      {
          Node node = (Node) contextNode;
  
          if ( node.getNodeType() == Node.ELEMENT_NODE || node.getNodeType() == Node.DOCUMENT_NODE)
          {
              return new NodeIterator ((Node)contextNode) {
                  protected Node getFirstNode (Node node)
                  {
                      return node.getFirstChild();
                  }
                  protected Node getNextNode (Node node)
                  {
                      return node.getNextSibling();
                  }
              };
          }
  
          return JaxenConstants.EMPTY_ITERATOR;
  
      }
  
  
      /**
       * Get a (single-member) iterator over this node's parent.
       *
       * @param contextNode the context node for the parent axis
       * @return a possibly-empty iterator (not null)
       */
      public Iterator getParentAxisIterator (Object contextNode)
      {
          Node node = (Node)contextNode;
  
          if (node.getNodeType() == Node.ATTRIBUTE_NODE) {
              return new NodeIterator (node) {
                      protected Node getFirstNode (Node n)
                      {
                          // We can assume castability here because we've already
                          // tested the node type.
                          return ((Attr)n).getOwnerElement();
                      }
                      protected Node getNextNode (Node n) {
                          return null;
                      }
                  };
          } else {
              return new NodeIterator (node) {
                      protected Node getFirstNode (Node n)
                      {
                          return n.getParentNode();
                      }
                      protected Node getNextNode (Node n) {
                          return null;
                      }
                  };
          }
      }
      
      
      /** 
       * Return the XPath parent of the supplied DOM node.
       * XPath has slightly different definition of parent than DOM does.
       * In particular, the parent of an attribute is not null.
       * 
       * @param child the child node
       * 
       * @return the parent of the specified node; or null if
       *     the node does not have a parent
       */
      public Object getParentNode(Object child) {
          Node node = (Node) child;
          if (node.getNodeType() == Node.ATTRIBUTE_NODE) {
              return ((Attr) node).getOwnerElement();
          }
          return node.getParentNode();
      }
  
  
      /**
       * Get an iterator over all following siblings.
       *
       * @param contextNode the context node for the sibling iterator
       * @return a possibly-empty iterator (not null)
       */
      public Iterator getFollowingSiblingAxisIterator (Object contextNode)
      {
          return new NodeIterator ((Node)contextNode) {
                  protected Node getFirstNode (Node node)
                  {
                      return getNextNode(node);
                  }
                  protected Node getNextNode (Node node) {
                      return node.getNextSibling();
                  }
              };
      }
  
  
      /**
       * Get an iterator over all preceding siblings.
       *
       * @param contextNode the context node for the preceding sibling axis
       * @return a possibly-empty iterator (not null)
       */
      public Iterator getPrecedingSiblingAxisIterator (Object contextNode)
      {
          return new NodeIterator ((Node)contextNode) {
                  protected Node getFirstNode (Node node)
                  {
                      return getNextNode(node);
                  }
                  protected Node getNextNode (Node node) {
                      return node.getPreviousSibling();
                  }
              };
      }
  
  
      /**
       * Get an iterator over all following nodes, depth-first.
       *
       * @param contextNode the context node for the following axis
       * @return a possibly-empty iterator (not null)
       */
      public Iterator getFollowingAxisIterator (Object contextNode)
      {
          return new NodeIterator ((Node)contextNode) {
                  protected Node getFirstNode (Node node)
                  {
                      if (node == null) {
                          return null;
                      }
                      else {
                          Node sibling = node.getNextSibling();
                          if (sibling == null) {
                              return getFirstNode(node.getParentNode());
                          }
                          else {
                              return sibling;
                          }
                      }
                  }
                  protected Node getNextNode (Node node) {
                      if (node == null) {
                          return null;
                      }
                      else {
                          Node n = node.getFirstChild();
                          if (n == null) n = node.getNextSibling();
                          if (n == null) return getFirstNode(node.getParentNode());
                          else return n;
                      }
                  }
              };
      }
  
  
      /**
       * Get an iterator over all attributes.
       *
       * @param contextNode the context node for the attribute axis
       * @return a possibly-empty iterator (not null)
       */
      public Iterator getAttributeAxisIterator (Object contextNode)
      {
          if (isElement(contextNode)) {
              return new AttributeIterator((Node)contextNode);
          } 
          else {
              return JaxenConstants.EMPTY_ITERATOR;
          }
      }
  
  
      /**
       * Get an iterator over all declared namespaces.
       *
       * <p>Note: this iterator is not live: it takes a snapshot
       * and that snapshot remains static during the life of
       * the iterator (i.e. it won't reflect subsequent changes
       * to the DOM).</p>
       * 
       * <p>
       * In the event that the DOM is inconsistent; for instance a 
       * <code>pre:foo</code> element is declared by DOM to be in the 
       * http://www.a.com/ namespace but also has an 
       * <code>xmlns:pre="http://www.b.com"</code> attribute; then only 
       * one of the namespaces will be counted. This will be the intrinsic
       * namespace of the <code>Element</code> or <code>Attr</code> object
       * rather than the one provide by the contradictory namespace 
       * declaration attribute. In the event of a contradiction between two
       * attributes on the same element--e.g. <code>pre:foo</code> in the
       * http://www.a.com/ namespace and <code>pre:bar</code> in the 
       * http://www.b.com/ namespace--it is undefined which namespace
       * will be returned. 
       * </p>
       *
       * @param contextNode the context node for the namespace axis
       * @return a possibly-empty iterator (not null)
       */
      public Iterator getNamespaceAxisIterator (Object contextNode)
      {
          // Only elements have namespace nodes
          if (isElement(contextNode)) {
  
              HashMap nsMap = new HashMap();
  
              // Starting at the current node, walk
              // up to the root, noting the namespace
              // declarations in scope.
              for (Node n = (Node) contextNode;
                   n != null;
                   n = n.getParentNode()) {
                  
                  // 1. Look for the namespace of the element itself
                  String myNamespace = n.getNamespaceURI();
                  if (myNamespace != null && ! "".equals(myNamespace)) {
                      String myPrefix = n.getPrefix();
                      if (!nsMap.containsKey(myPrefix)) {
                          NamespaceNode ns = new NamespaceNode((Node) contextNode, myPrefix, myNamespace);
                          nsMap.put(myPrefix, ns);
                      }
                  }
  
                  if (n.hasAttributes()) {
                      NamedNodeMap atts = n.getAttributes();
                      int length = atts.getLength();
                      // 2. Look for namespaces of attributes
                      for (int i = 0; i < length; i++) {
                          Attr att = (Attr) atts.item(i);
                          // Work around Crimson bug by testing URI rather than name
                          String attributeNamespace = att.getNamespaceURI();
                          if ("http://www.w3.org/2000/xmlns/".equals(attributeNamespace)) {
                          }
                          else if (attributeNamespace != null) {
                              String prefix = att.getPrefix();
                              NamespaceNode ns =
                                  new NamespaceNode((Node)contextNode, prefix, attributeNamespace);
                              // Add only if there's not a closer declaration in force.
                              if (!nsMap.containsKey(prefix)) nsMap.put(prefix, ns);
                              
                          }
                      }
                      
                      // 3. Look for namespace declaration attributes
                      for (int i = 0; i < length; i++) {
                          Attr att = (Attr) atts.item(i);
                          // work around crimson bug by testing URI rather than name
                          String attributeNamespace = att.getNamespaceURI();
                          if ("http://www.w3.org/2000/xmlns/".equals(attributeNamespace)) {
                              NamespaceNode ns =
                                new NamespaceNode( (Node)contextNode, att);
                              // Add only if there's not a closer declaration in force.
                              String name = ns.getNodeName();
                              if (!nsMap.containsKey(name)) nsMap.put(name, ns);
                          }
                      }
                      
                  }
                  
              }
              // Section 5.4 of the XPath rec requires
              // this to be present.
              nsMap.put("xml",
                        new
                        NamespaceNode((Node)contextNode,
                                      "xml",
                                      "http://www.w3.org/XML/1998/namespace"));
  
              // An empty default namespace cancels
              // any previous default.
              NamespaceNode defaultNS = (NamespaceNode)nsMap.get("");
              if (defaultNS != null && defaultNS.getNodeValue().length() == 0) {
                  nsMap.remove("");
              }
              return nsMap.values().iterator();
          } 
          else {
              return JaxenConstants.EMPTY_ITERATOR;
          }
      }
  
      /** Returns a parsed form of the given XPath string, which will be suitable
       *  for queries on DOM documents.
       *  
       * @param xpath the XPath expression
       * @return a parsed form of the given XPath string
       * @throws org.jaxen.saxpath.SAXPathException if the string is syntactically incorrect
       */
      public XPath parseXPath (String xpath) throws org.jaxen.saxpath.SAXPathException
      {
          return new DOMXPath(xpath);
      }
  
      /**
       * Get the top-level document node.
       *
       * @param contextNode any node in the document
       * @return the root node
       */
      public Object getDocumentNode (Object contextNode)
      {
          if (isDocument(contextNode)) return contextNode;
          else return ((Node)contextNode).getOwnerDocument();
      }
  
      // Why are there separate methods for getElementNamespaceURI and 
      // getAttributeNamespaceURI when they do exactly the same thing?
      // This should be combined in a future version.
      /**
       * Get the namespace URI of an element.
       *
       * @param element the target node
       * @return a string (possibly empty) if the node is an element,
       * and null otherwise
       */
      public String getElementNamespaceUri (Object element)
      {
          try {
              Node node = (Node) element;
              if (node.getNodeType() == Node.ELEMENT_NODE) {
                  return node.getNamespaceURI();
              }
          }
          catch (ClassCastException ex) {
          }
          return null;
      }
  
  
      /**
       * Get the local name of an element.
       *
       * @param element the target node
       * @return a string representing the unqualified local name
       *     if the node is an element, or null otherwise
       */
      public String getElementName (Object element)
      {
          if (isElement(element)) {
              String name = ((Node)element).getLocalName();
              if (name == null) name = ((Node)element).getNodeName();
              return name;
          }
          return null;
      }
  
  
      /**
       * Get the qualified name of an element.
       *
       * @param element the target node
       * @return a string representing the qualified (i.e. possibly
       *   prefixed) name if the argument is an element, or null otherwise
       */
      public String getElementQName (Object element)
      {
          try {
              Node node = (Node) element;
              if (node.getNodeType() == Node.ELEMENT_NODE) {
                  return node.getNodeName();
              }
          }
          catch (ClassCastException ex) {
          }
          return null;
      }
  
  
      /**
       * Get the namespace URI of an attribute.
       *
       * @param attribute the target node
       * 
       * @return the namespace name of the specified node
       * 
       */
      public String getAttributeNamespaceUri (Object attribute)
      {
          try {
              Node node = (Node) attribute;
              if (node.getNodeType() == Node.ATTRIBUTE_NODE) {
                  return node.getNamespaceURI();
              }
          }
          catch (ClassCastException ex) {
          }
          return null;
      }
  
  
      /**
       * Get the local name of an attribute.
       *
       * @param attribute the target node
       * @return a string representing the unqualified local name
       * if the node is an attribute, or null otherwise
       */
      public String getAttributeName (Object attribute)
      {
          if (isAttribute(attribute)) {
              String name = ((Node)attribute).getLocalName();
              if (name == null) name = ((Node)attribute).getNodeName();
              return name;
          }
          return null;
      }
  
  
      /**
       * Get the qualified name of an attribute.
       *
       * @param attribute the target node
       * 
       * @return a string representing the qualified (i.e. possibly
       * prefixed) name if the argument is an attribute, or null otherwise
       */
      public String getAttributeQName (Object attribute)
      {
          try {
              Node node = (Node) attribute;
              if (node.getNodeType() == Node.ATTRIBUTE_NODE) {
                  return node.getNodeName();
              }
          }
          catch (ClassCastException ex) {
          }
          return null;
      }
  
  
      /**
       * Test if a node is a top-level document.
       *
       * @param object the target node
       * @return true if the node is the document root, false otherwise
       */
      public boolean isDocument (Object object)
      {
          return (object instanceof Node) &&
              (((Node)object).getNodeType() == Node.DOCUMENT_NODE);
      }
  
  
      /**
       * Test if a node is a namespace.
       *
       * @param object the target node
       * @return true if the node is a namespace, false otherwise
       */
      public boolean isNamespace (Object object)
      {
          return (object instanceof NamespaceNode);
      }
  
  
      /**
       * Test if a node is an element.
       *
       * @param object the target node
       * @return true if the node is an element, false otherwise
       */
      public boolean isElement (Object object)
      {
          return (object instanceof Node) &&
              (((Node)object).getNodeType() == Node.ELEMENT_NODE);
      }
  
  
      /**
       * Test if a node is an attribute. <code>xmlns</code> and 
       * <code>xmlns:pre</code> attributes do not count as attributes
       * for the purposes of XPath. 
       *
       * @param object the target node
       * @return true if the node is an attribute, false otherwise
       */
      public boolean isAttribute (Object object)
      {
          return (object instanceof Node) &&
              (((Node)object).getNodeType() == Node.ATTRIBUTE_NODE)
              && ! "http://www.w3.org/2000/xmlns/".equals(((Node) object).getNamespaceURI());
      }
  
  
      /**
       * Test if a node is a comment.
       *
       * @param object the target node
       * @return true if the node is a comment, false otherwise
       */
      public boolean isComment (Object object)
      {
          return (object instanceof Node) &&
              (((Node)object).getNodeType() == Node.COMMENT_NODE);
      }
  
  
      /**
       * Test if a node is plain text.
       *
       * @param object the target node
       * @return true if the node is a text node, false otherwise
       */
      public boolean isText (Object object)
      {
          if (object instanceof Node) {
              switch (((Node)object).getNodeType()) {
                  case Node.TEXT_NODE:
                  case Node.CDATA_SECTION_NODE:
                      return true;
                  default:
                      return false;
              }
          } else {
              return false;
          }
      }
  
  
      /**
       * Test if a node is a processing instruction.
       *
       * @param object the target node
       * @return true if the node is a processing instruction, false otherwise
       */
      public boolean isProcessingInstruction (Object object)
      {
          return (object instanceof Node) &&
              (((Node)object).getNodeType() == Node.PROCESSING_INSTRUCTION_NODE);
      }
  
  
      /**
       * Get the string value of an element node.
       *
       * @param object the target node
       * @return the text inside the node and its descendants if the node
       * is an element, null otherwise
       */
      public String getElementStringValue (Object object)
      {
          if (isElement(object)) {
              return getStringValue((Node)object, new StringBuffer()).toString();
          }
          else {
              return null;
          }
      }
  
  
      /**
       * Construct a node's string value recursively.
       *
       * @param node the current node
       * @param buffer the buffer for building the text
       * @return the buffer passed as a parameter (for convenience)
       */
      private StringBuffer getStringValue (Node node, StringBuffer buffer)
      {
          if (isText(node)) {
              buffer.append(node.getNodeValue());
          } else {
              NodeList children = node.getChildNodes();
              int length = children.getLength();
              for (int i = 0; i < length; i++) {
                  getStringValue(children.item(i), buffer);
              }
          }
          return buffer;
      }
  
  
      /**
       * Get the string value of an attribute node.
       *
       * @param object the target node
       * @return the text of the attribute value if the node is an
       *     attribute, null otherwise
       */
      public String getAttributeStringValue (Object object)
      {
          if (isAttribute(object)) return ((Node)object).getNodeValue();
          else return null;
      }
  
  
      /**
       * Get the string value of text.
       *
       * @param object the target node
       * @return the string of text if the node is text, null otherwise
       */
      public String getTextStringValue (Object object)
      {
          if (isText(object)) return ((Node)object).getNodeValue();
          else return null;
      }
  
  
      /**
       * Get the string value of a comment node.
       *
       * @param object the target node
       * @return the text of the comment if the node is a comment, null otherwise
       */
      public String getCommentStringValue (Object object)
      {
          if (isComment(object)) return ((Node)object).getNodeValue();
          else return null;
      }
  
  
      /**
       * Get the string value of a namespace node.
       *
       * @param object the target node
       * @return the namespace URI as a (possibly empty) string if the
       *     node is a namespace node, null otherwise
       */
      public String getNamespaceStringValue (Object object)
      {
          if (isNamespace(object)) return ((NamespaceNode)object).getNodeValue();
          else return null;
      }
  
      /**
       * Get the prefix value of a namespace node.
       *
       * @param object the target node
       * @return the namespace prefix a (possibly empty) string if the
       *     node is a namespace node, null otherwise
       */
      public String getNamespacePrefix (Object object)
      {
          if (isNamespace(object)) return ((NamespaceNode)object).getLocalName();
          else return null;
      }
  
      /**
       * Translate a namespace prefix to a URI.
       * 
       * @param prefix the namespace prefix
       * @param element the namespace context
       * @return the namespace URI bound to the prefix in the scope of <code>element</code>;
       *     null if the prefix is not bound
       */
      public String translateNamespacePrefixToUri (String prefix, Object element)
      {
          Iterator it = getNamespaceAxisIterator(element);
          while (it.hasNext()) {
              NamespaceNode ns = (NamespaceNode)it.next();
              if (prefix.equals(ns.getNodeName())) return ns.getNodeValue();
          }
          return null;
      }
  
      /**
       * Use JAXP to load a namespace aware document from a given URI.
       *
       * @param uri the URI of the document to load
       * @return the new W3C DOM Level 2 Document instance
       * @throws FunctionCallException containing a nested exception
       *      if a problem occurs trying to parse the given document
       *
       * @todo Possibly we could make the factory a thread local.
       */
      public Object getDocument(String uri) throws FunctionCallException
      {
          try
          {
              // We really do need to construct a new factory here each time.
              // DocumentBuilderFactory is not guaranteed to be thread safe? 
              DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
              factory.setNamespaceAware(true);
              DocumentBuilder builder = factory.newDocumentBuilder();
              return builder.parse( uri );
          }
          catch (ParserConfigurationException e) {
              throw new FunctionCallException("JAXP setup error in document() function: " + e.getMessage(), e);
          }
          catch (SAXException e) {
             throw new FunctionCallException("XML error in document() function: " + e.getMessage(), e);
          }
          catch (IOException e) {
             throw new FunctionCallException("I/O error in document() function: " + e.getMessage(), e);
          }
          
      }
      
      /**
       * Get the target of a processing instruction node.
       * 
       * @param obj the processing instruction
       * @return the target of the processing instruction
       * @throws ClassCastException if obj is not a processing instruction
       * 
       */
      public String getProcessingInstructionTarget(Object obj)
      {      
          if (isProcessingInstruction(obj)) {
              ProcessingInstruction pi = (ProcessingInstruction) obj;
              return pi.getTarget();
          }
          throw new ClassCastException(obj + " is not a processing instruction");
      }
  
      /**
       * Get the data of a processing instruction node.
       * 
       * @param obj the processing instruction
       * @return the target of the processing instruction
       * @throws ClassCastException if obj is not a processing instruction
       * 
       */
      public String getProcessingInstructionData(Object obj)
      {
          if (isProcessingInstruction(obj)) {
              ProcessingInstruction pi = (ProcessingInstruction) obj;
              return pi.getData();
          }
          throw new ClassCastException(obj + " is not a processing instruction");
      }
  
      
      ////////////////////////////////////////////////////////////////////
      // Inner class: iterate over DOM nodes.
      ////////////////////////////////////////////////////////////////////
  
  
      // FIXME: needs to recurse into
      // DocumentFragment and EntityReference
      // to use their children.
  
      /**
       * A generic iterator over DOM nodes.
       *
       * <p>Concrete subclasses must implement the {@link #getFirstNode}
       * and {@link #getNextNode} methods for a specific iteration
       * strategy.</p>
       */
      abstract class NodeIterator
      implements Iterator
      {
  
  
          /**
           * Constructor.
           *
           * @param contextNode the starting node
           */
          public NodeIterator (Node contextNode)
          {
              node = getFirstNode(contextNode);
              while (!isXPathNode(node)) {
                  node = getNextNode(node);
              }
          }
  
          public boolean hasNext ()
          {
              return (node != null);
          }
  
          public Object next ()
          {
              if (node == null) throw new NoSuchElementException();
              Node ret = node;
              node = getNextNode(node);
              while (!isXPathNode(node)) {
                  node = getNextNode(node);
              }
              return ret;
          }
  
          public void remove ()
          {
              throw new UnsupportedOperationException();
          }
  
  
          /**
           * Get the first node for iteration.
           *
           * <p>This method must derive an initial node for iteration
           * from a context node.</p>
           *
           * @param contextNode the starting node
           * @return the first node in the iteration
           * @see #getNextNode
           */
          protected abstract Node getFirstNode (Node contextNode);
  
  
          /**
           * Get the next node for iteration.
           *
           * <p>This method must locate a following node from the
           * current context node.</p>
           *
           * @param contextNode the current node in the iteration
           * @return the following node in the iteration, or null
           * if there is none
           * @see #getFirstNode
           */
          protected abstract Node getNextNode (Node contextNode);
  
  
          /**
           * Test whether a DOM node is usable by XPath.
           *
           * @param node the DOM node to test
           * @return true if the node is usable, false if it should be skipped
           */
          private boolean isXPathNode (Node node)
          {
              // null is usable, because it means end
              if (node == null) return true;
  
              switch (node.getNodeType()) {
                  case Node.DOCUMENT_FRAGMENT_NODE:
                  case Node.DOCUMENT_TYPE_NODE:
                  case Node.ENTITY_NODE:
                  case Node.ENTITY_REFERENCE_NODE:
                  case Node.NOTATION_NODE:
                      return false;
                  default:
                      return true;
              }
          }
  
          private Node node;
      }
  
  
      
      ////////////////////////////////////////////////////////////////////
      // Inner class: iterate over a DOM named node map.
      ////////////////////////////////////////////////////////////////////
  
  
      /**
       * An iterator over an attribute list.
       */
      private static class AttributeIterator implements Iterator
      {
  
          /**
           * Constructor.
           *
           * @param parent the parent DOM element for the attributes.
           */
          AttributeIterator (Node parent)
          {
              this.map = parent.getAttributes();
              this.pos = 0;
              for (int i = this.map.getLength()-1; i >= 0; i--) {
                  Node node = map.item(i);
                  if (! "http://www.w3.org/2000/xmlns/".equals(node.getNamespaceURI())) {
                      this.lastAttribute  = i;
                      break;
                  }
              }
          }
  
          public boolean hasNext ()
          {
              return pos <= lastAttribute;
          }
  
          public Object next ()
          {
              Node attr = map.item(pos++);
              if (attr == null) throw new NoSuchElementException();
              else if ("http://www.w3.org/2000/xmlns/".equals(attr.getNamespaceURI())) {
                // XPath doesn't consider namespace declarations to be attributes 
                // so skip it and go to the next one
                return next();
              }
              else return attr;
          }
  
          public void remove ()
          {
              throw new UnsupportedOperationException();
          }
  
  
          private NamedNodeMap map;
          private int pos;
          private int lastAttribute = -1;
  
      }
  
      /**
       *  Returns the element whose ID is given by elementId.
       *  If no such element exists, returns null.
       *  Attributes with the name "ID" are not of type ID unless so defined.
       *  Attribute types are only known if when the parser understands DTD's or
       *  schemas that declare attributes of type ID. When JAXP is used, you
       *  must call <code>setValidating(true)</code> on the
       *  DocumentBuilderFactory.
       *
       *  @param object   a node from the document in which to look for the id
       *  @param elementId   id to look for
       *
       *  @return   element whose ID is given by elementId, or null if no such
       *            element exists in the document or if the implementation
       *            does not know about attribute types
       *  @see   javax.xml.parsers.DocumentBuilderFactory
       *  
       *  @throws ClassCastException if object is not an <code>org.w3c.dom.Node</code> object
       *  
       */
      public Object getElementById(Object object, String elementId)
      {
          Document doc = (Document)getDocumentNode(object);
          if (doc != null) return doc.getElementById(elementId);
          else return null;
      }
  
  }
  
  // end of DocumentNavigator.java
  