/* DomNode.java -- 
   Copyright (C) 1999,2000,2001,2004 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */

package gnu.xml.dom;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import org.w3c.dom.Document;
import org.w3c.dom.DOMException;
import org.w3c.dom.DOMImplementation;
import org.w3c.dom.NamedNodeMap;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
import org.w3c.dom.Text;
import org.w3c.dom.UserDataHandler;
import org.w3c.dom.events.DocumentEvent;
import org.w3c.dom.events.Event;
import org.w3c.dom.events.EventException;
import org.w3c.dom.events.EventListener;
import org.w3c.dom.events.EventTarget;
import org.w3c.dom.events.MutationEvent;
import org.w3c.dom.traversal.NodeFilter;
import org.w3c.dom.traversal.NodeIterator;

/**
 * <p> "Node", "EventTarget", and "DocumentEvent" implementation.
 * This provides most of the core DOM functionality; only more
 * specialized features are provided by subclasses.  Those subclasses may
 * have some particular constraints they must implement, by overriding
 * methods defined here.  Such constraints are noted here in the method
 * documentation. </p>
 *
 * <p> Note that you can create events with type names prefixed with "USER-",
 * and pass them through this DOM.  This lets you use the DOM event scheme
 * for application specific purposes, although you must use a predefined event
 * structure (such as MutationEvent) to pass data along with those events.
 * Test for existence of this feature with the "USER-Events" DOM feature
 * name.</p>
 *
 * <p> Other kinds of events you can send include the "html" events,
 * like "load", "unload", "abort", "error", and "blur"; and the mutation
 * events.  If this DOM has been compiled with mutation event support
 * enabled, it will send mutation events when you change parts of the
 * tree; otherwise you may create and send such events yourself, but
 * they won't be generated by the DOM itself. </p>
 *
 * <p> Note that there is a namespace-aware name comparison method,
 * <em>nameAndTypeEquals</em>, which compares the names (and types) of
 * two nodes in conformance with the "Namespaces in XML" specification.
 * While mostly intended for use with elements and attributes, this should
 * also be helpful for ProcessingInstruction nodes and some others which
 * do not have namespace URIs.
 *
 * @author David Brownell
 * @author <a href='mailto:dog@gnu.org'>Chris Burdess</a>
 */
public abstract class DomNode
  implements Node, NodeList, EventTarget, DocumentEvent, Cloneable, Comparable
{

  // package private
  //final static String xmlNamespace = "http://www.w3.org/XML/1998/namespace";
  //final static String xmlnsURI = "http://www.w3.org/2000/xmlns/";

  // tunable
  //	NKIDS_* affects arrays of children (which grow)
  // (currently) fixed size:
  //	ANCESTORS_* is for event capture/bubbling, # ancestors
  //	NOTIFICATIONS_* is for per-node event delivery, # events
  private static final int NKIDS_DELTA = 8;
  private static final int ANCESTORS_INIT = 20;
  private static final int NOTIFICATIONS_INIT = 10;

  // tunable: enable mutation events or not?  Enabling it costs about
  // 10-15% in DOM construction time, last time it was measured.

  // package private !!!
  static final boolean reportMutations = true;

  // locking protocol changeable only within this class
  private static final Object lockNode = new Object();

  // NON-FINAL class data

  // Optimize event dispatch by not allocating memory each time
  private static boolean dispatchDataLock;
  private static DomNode[] ancestors = new DomNode[ANCESTORS_INIT];
  private static ListenerRecord[] notificationSet
    = new ListenerRecord[NOTIFICATIONS_INIT];

  // Ditto for the (most common) event object itself!
  private static boolean eventDataLock;
  private static DomEvent.DomMutationEvent mutationEvent
    = new DomEvent.DomMutationEvent(null);

  //
  // PER-INSTANCE DATA
  //

  DomDocument owner;
  DomNode parent; // parent node;
  DomNode previous; // previous sibling node
  DomNode next; // next sibling node
  DomNode first; // first child node
  DomNode last; // last child node
  int index; // index of this node in its parent's children
  int depth; // depth of the node in the document
  int length; // number of children
  final short nodeType;

  // Bleech ... "package private" so a builder can populate entity refs.
  // writable during construction.  DOM spec is nasty.
  boolean readonly;

  // event registrations
  private ListenerRecord[] listeners;
  private int nListeners;

  // DOM Level 3 userData dictionary.
  private HashMap userData;
  private HashMap userDataHandlers;

  //
  // Some of the methods here are declared 'final' because
  // knowledge about their implementation is built into this
  // class -- for both integrity and performance.
  //

  /**
   * Reduces space utilization for this node.
   */
  public void compact()
  {
    if (listeners != null && listeners.length != nListeners)
      {
        if (nListeners == 0)
          {
            listeners = null;
          }
        else
          {
            ListenerRecord[] l = new ListenerRecord[nListeners];
            System.arraycopy(listeners, 0, l, 0, nListeners);
            listeners = l;
          }
      }
  }

  /**
   * Constructs a node and associates it with its owner.  Only
   * Document and DocumentType nodes may be created with no owner,
   * and DocumentType nodes get an owner as soon as they are
   * associated with a document.
   */
  protected DomNode(short nodeType, DomDocument owner)
  {
    this.nodeType = nodeType;

    if (owner == null)
      {
        // DOM calls never go down this path
        if (nodeType != DOCUMENT_NODE && nodeType != DOCUMENT_TYPE_NODE)
          {
            throw new IllegalArgumentException ("no owner!");
          }
      }
    this.owner = owner;
  }
  

  /**
   * <b>DOM L1</b>
   * Returns null; Element subclasses must override this method.
   */
  public NamedNodeMap getAttributes()
  {
    return null;
  }

  /**
   * <b>DOM L2></b>
   * Returns true iff this is an element node with attributes.
   */
  public boolean hasAttributes()
  {
    return false;
  }

  /**
   * <b>DOM L1</b>
   * Returns a list, possibly empty, of the children of this node.
   * In this implementation, to conserve memory, nodes are the same
   * as their list of children.  This can have ramifications for
   * subclasses, which may need to provide their own getLength method
   * for reasons unrelated to the NodeList method of the same name.
   */
  public NodeList getChildNodes()
  {
    return this;
  }

  /**
   * <b>DOM L1</b>
   * Returns the first child of this node, or null if there are none.
   */
  public Node getFirstChild()
  {
    return first;
  }

  /**
   * <b>DOM L1</b>
   * Returns the last child of this node, or null if there are none.
   */
  public Node getLastChild()
  {
    return last;
  }

  /**
   * <b>DOM L1</b>
   * Returns true if this node has children.
   */
  public boolean hasChildNodes()
  {
    return length != 0;
  }


  /**
   * Exposes the internal "readonly" flag.  In DOM, children of
   * entities and entity references are readonly, as are the
   * objects associated with DocumentType objets.
   */
  public final boolean isReadonly()
  {
    return readonly;
  }

  /**
   * Sets the internal "readonly" flag so this subtree can't be changed.
   * Subclasses need to override this method for any associated content
   * that's not a child node, such as an element's attributes or the
   * (few) declarations associated with a DocumentType.
   */
  public void makeReadonly()
  {
    readonly = true;
    for (DomNode child = first; child != null; child = child.next)
      {
        child.makeReadonly();
      }
  }

  /**
   * Used to adopt a node to a new document.
   */
  void setOwner(DomDocument doc)
  {
    this.owner = doc;
    for (DomNode ctx = first; ctx != null; ctx = ctx.next)
      {
        ctx.setOwner(doc);
      }
  }

  // just checks the node for inclusion -- may be called many
  // times (docfrag) before anything is allowed to change
  private void checkMisc(DomNode child)
  {
    if (readonly && !owner.building)
      {
        throw new DomDOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR,
                                  null, this, 0);
      }
    for (DomNode ctx = this; ctx != null; ctx = ctx.parent)
      {
        if (child == ctx)
          {
            throw new DomDOMException(DOMException.HIERARCHY_REQUEST_ERR,
                                      "can't make ancestor into a child",
                                      this, 0);
          }
      }

    DomDocument owner = (nodeType == DOCUMENT_NODE) ? (DomDocument) this :
      this.owner;
    DomDocument childOwner = child.owner;
    short childNodeType = child.nodeType;
    
    if (childOwner != owner)
      {
        // new in DOM L2, this case -- patch it up later, in reparent()
        if (!(childNodeType == DOCUMENT_TYPE_NODE && childOwner == null))
          {
            throw new DomDOMException(DOMException.WRONG_DOCUMENT_ERR,
                                      null, child, 0);
          }
      }

    // enforce various structural constraints
    switch (nodeType)
      {
      case DOCUMENT_NODE:
        switch (childNodeType)
          {
          case ELEMENT_NODE:
          case PROCESSING_INSTRUCTION_NODE:
          case COMMENT_NODE:
          case DOCUMENT_TYPE_NODE:
            return;
          }
        break;
        
      case ATTRIBUTE_NODE:
        switch (childNodeType)
          {
          case TEXT_NODE:
          case ENTITY_REFERENCE_NODE:
            return;
          }
        break;
        
      case DOCUMENT_FRAGMENT_NODE:
      case ENTITY_REFERENCE_NODE:
      case ELEMENT_NODE:
      case ENTITY_NODE:
        switch (childNodeType)
          {
          case ELEMENT_NODE:
          case TEXT_NODE:
          case COMMENT_NODE:
          case PROCESSING_INSTRUCTION_NODE:
          case CDATA_SECTION_NODE:
          case ENTITY_REFERENCE_NODE:
            return;
          }
        break;
      }
    if (owner.checkingWellformedness)
      {
        throw new DomDOMException(DOMException.HIERARCHY_REQUEST_ERR,
                                  "can't append " +
                                  nodeTypeToString(childNodeType) +
                                  " to node of type " +
                                  nodeTypeToString(nodeType),
                                  this, 0);
      }
  }
  
  // Here's hoping a good optimizer will detect the case when the
  // next several methods are never called, and won't allocate
  // object code space of any kind.  (Case:  not reporting any
  // mutation events.  We can also remove some static variables
  // listed above.)

  private void insertionEvent(DomEvent.DomMutationEvent event,
                              DomNode target)
  {
    if (owner == null || owner.building)
      {
        return;
      }
    boolean doFree = false;
    
    if (event == null)
      {
        event = getMutationEvent();
      }
    if (event != null)
      {
        doFree = true;
      }
    else
      {
        event = new DomEvent.DomMutationEvent(null);
      }
    event.initMutationEvent("DOMNodeInserted",
                            true /* bubbles */, false /* nocancel */,
                            this /* related */, null, null, null, (short) 0);
    target.dispatchEvent(event);

    // XXX should really visit every descendant of 'target'
    // and sent a DOMNodeInsertedIntoDocument event to it...
    // bleech, there's no way to keep that acceptably fast.

    if (doFree)
      {
        event.target = null;
        event.relatedNode = null;
        event.currentNode = null;
        eventDataLock = false;
      } // else we created work for the GC
  }

  private void removalEvent(DomEvent.DomMutationEvent event,
                            DomNode target)
  {
    if (owner == null || owner.building)
      {
        return;
      }
    boolean doFree = false;

    if (event == null)
      {
        event = getMutationEvent();
      }
    if (event != null)
      {
        doFree = true;
      }
    else
      {
        event = new DomEvent.DomMutationEvent(null);
      }
    event.initMutationEvent("DOMNodeRemoved",
                            true /* bubbles */, false /* nocancel */,
                            this /* related */, null, null, null, (short) 0);
    target.dispatchEvent(event);

    // XXX should really visit every descendant of 'target'
    // and sent a DOMNodeRemovedFromDocument event to it...
    // bleech, there's no way to keep that acceptably fast.

    event.target = null;
    event.relatedNode = null;
    event.currentNode = null;
    if (doFree)
      {
        eventDataLock = false;
      }
    // else we created more work for the GC
  }

  //
  // Avoid creating lots of memory management work, by using a simple
  // allocation strategy for the mutation event objects that get used
  // at least once per tree modification.  We can't use stack allocation,
  // so we do the next simplest thing -- more or less, static allocation.
  // Concurrent notifications should be rare, anyway.
  //
  // Returns the preallocated object, which needs to be carefully freed,
  // or null to indicate the caller needs to allocate their own.
  //
  static private DomEvent.DomMutationEvent getMutationEvent()
  {
    synchronized (lockNode)
      {
        if (eventDataLock)
          {
            return null;
          }
        eventDataLock = true;
        return mutationEvent;
      }
  }

  // NOTE:  this is manually inlined in the insertion
  // and removal event methods above; change in sync.
  static private void freeMutationEvent()
  {
    // clear fields to enable GC
    mutationEvent.clear();
    eventDataLock = false;
  }

  void setDepth(int depth)
  {
    this.depth = depth;
    for (DomNode ctx = first; ctx != null; ctx = ctx.next)
      {
        ctx.setDepth(depth + 1);
      }
  }

  /**
   * <b>DOM L1</b>
   * Appends the specified node to this node's list of children.
   * Document subclasses must override this to enforce the restrictions
   * that there be only one element and document type child.
   *
   * <p> Causes a DOMNodeInserted mutation event to be reported.
   * Will first cause a DOMNodeRemoved event to be reported if the
   * parameter already has a parent.  If the new child is a document
   * fragment node, both events will be reported for each child of
   * the fragment; the order in which children are removed and
   * inserted is implementation-specific.
   *
   * <p> If this DOM has been compiled without mutation event support,
   * these events will not be reported.
   */
  public Node appendChild(Node newChild)
  {
    try
      {
        DomNode	child = (DomNode) newChild;

        if (child.nodeType == DOCUMENT_FRAGMENT_NODE)
          {
            // Append all nodes in the fragment to this node
            for (DomNode ctx = child.first; ctx != null; ctx = ctx.next)
              {
                checkMisc(ctx);
              }
            for (DomNode ctx = child.first; ctx != null; )
              {
                DomNode ctxNext = ctx.next;
                appendChild(ctx);
                ctx = ctxNext;
              }
          }
        else
          {
            checkMisc(child);
            if (child.parent != null)
              {
                child.parent.removeChild(child);
              }
            child.parent = this;
            child.index = length++;
            child.setDepth(depth + 1);
            child.next = null;
            if (last == null)
              {
                first = child;
                child.previous = null;
              }
            else
              {
                last.next = child;
                child.previous = last;
              }
            last = child;

            if (reportMutations)
              {
                insertionEvent(null, child);
              }
          }

        return child;
      }
    catch (ClassCastException e)
      {
        throw new DomDOMException(DOMException.WRONG_DOCUMENT_ERR,
                                  null, newChild, 0);
    }
  }

  /**
   * <b>DOM L1</b>
   * Inserts the specified node in this node's list of children.
   * Document subclasses must override this to enforce the restrictions
   * that there be only one element and document type child.
   *
   * <p> Causes a DOMNodeInserted mutation event to be reported.  Will
   * first cause a DOMNodeRemoved event to be reported if the newChild
   * parameter already has a parent. If the new child is a document
   * fragment node, both events will be reported for each child of
   * the fragment; the order in which children are removed and inserted
   * is implementation-specific.
   *
   * <p> If this DOM has been compiled without mutation event support,
   * these events will not be reported.
   */
  public Node insertBefore(Node newChild, Node refChild)
  {
    if (refChild == null)
      {
        return appendChild(newChild);
      }

    try
      {
        DomNode	child = (DomNode) newChild;
        DomNode ref = (DomNode) refChild;
        
        if (child.nodeType == DOCUMENT_FRAGMENT_NODE)
          {
            // Append all nodes in the fragment to this node
            for (DomNode ctx = child.first; ctx != null; ctx = ctx.next)
              {
                checkMisc(ctx);
              }
            for (DomNode ctx = child.first; ctx != null; )
              {
                DomNode ctxNext = ctx.next;
                insertBefore(ctx, ref);
                ctx = ctxNext;
              }
          }
        else
          {
            checkMisc(child);
            if (ref == null || ref.parent != this)
              {
                throw new DomDOMException(DOMException.NOT_FOUND_ERR,
                                          null, ref, 0);
              }
            if (ref == child)
              {
                throw new DomDOMException(DOMException.HIERARCHY_REQUEST_ERR,
                                          "can't insert node before itself",
                                          ref, 0);
              }
        
            if (child.parent != null)
              {
                child.parent.removeChild(child);
              }
            child.parent = this;
            int i = ref.index;
            child.setDepth(depth + 1);
            child.next = ref;
            if (ref.previous != null)
              {
                ref.previous.next = child;
              }
            child.previous = ref.previous;
            ref.previous = child;
            if (first == ref)
              {
                first = child;
              }
            // index renumbering
            for (DomNode ctx = child; ctx != null; ctx = ctx.next)
              {
                ctx.index = i++;
              }

            if (reportMutations)
              {
                insertionEvent(null, child);
              }
          }
        
        return child;
      }
    catch (ClassCastException e)
      {
        throw new DomDOMException(DOMException.WRONG_DOCUMENT_ERR,
                                  null, newChild, 0);
      }
  }

  /**
   * <b>DOM L1</b>
   * Replaces the specified node in this node's list of children.
   * Document subclasses must override this to test the restrictions
   * that there be only one element and document type child.
   *
   * <p> Causes DOMNodeRemoved and DOMNodeInserted mutation event to be
   * reported.  Will cause another DOMNodeRemoved event to be reported if
   * the newChild parameter already has a parent.  These events may be
   * delivered in any order, except that the event reporting removal
   * from such an existing parent will always be delivered before the
   * event reporting its re-insertion as a child of some other node.
   * The order in which children are removed and inserted is implementation
   * specific.
   *
   * <p> If your application needs to depend on the in which those removal
   * and insertion events are delivered, don't use this API.  Instead,
   * invoke the removeChild and insertBefore methods directly, to guarantee
   * a specific delivery order.  Similarly, don't use document fragments,
   * Otherwise your application code may not work on a DOM which implements
   * this method differently.
   *
   * <p> If this DOM has been compiled without mutation event support,
   * these events will not be reported.
   */
  public Node replaceChild(Node newChild, Node refChild)
  {
    try
      {
        DomNode child = (DomNode) newChild;
        DomNode ref = (DomNode) refChild;
        
        DomEvent.DomMutationEvent event = getMutationEvent();
        boolean doFree = (event != null);
            
        if (child.nodeType == DOCUMENT_FRAGMENT_NODE)
          {
            // Append all nodes in the fragment to this node
            for (DomNode ctx = child.first; ctx != null; ctx = ctx.next)
              {
                checkMisc(ctx);
              }
            if (ref == null || ref.parent != this)
              {
                throw new DomDOMException(DOMException.NOT_FOUND_ERR,
                                          null, ref, 0);
              }
            
            if (reportMutations)
              {
                removalEvent(event, ref);
              }
            length--;
            length += child.length;
            
            if (child.length == 0)
              {
                // Removal
                if (ref.previous != null)
                  {
                    ref.previous.next = ref.next;
                  }
                if (ref.next != null)
                  {
                    ref.next.previous = ref.previous;
                  }
                if (first == ref)
                  {
                    first = ref.next;
                  }
                if (last == ref)
                  {
                    last = ref.previous;
                  }
              }
            else
              {
                int i = ref.index;
                for (DomNode ctx = child.first; ctx != null; ctx = ctx.next)
                  {
                    // Insertion
                    ctx.parent = this;
                    ctx.index = i++;
                    ctx.setDepth(ref.depth);
                    if (ctx == child.first)
                      {
                        ctx.previous = ref.previous;
                      }
                    if (ctx == child.last)
                      {
                        ctx.next = ref.next;
                      }
                  }
                if (first == ref)
                  {
                    first = child.first;
                  }
                if (last == ref)
                  {
                    last = child.last;
                  }
              }
          }
        else
          {
            checkMisc(child);
            if (ref == null || ref.parent != this)
              {
                throw new DomDOMException(DOMException.NOT_FOUND_ERR,
                                          null, ref, 0);
              }
        
            if (reportMutations)
              {
                removalEvent(event, ref);
              }
            
            if (child.parent != null)
              {
                child.parent.removeChild(child);
              }
            child.parent = this;
            child.index = ref.index;
            child.setDepth(ref.depth);
            if (ref.previous != null)
              {
                ref.previous.next = child;
              }
            child.previous = ref.previous;
            if (ref.next != null)
              {
                ref.next.previous = child;
              }
            child.next = ref.next;
            if (first == ref)
              {
                first = child;
              }
            if (last == ref)
              {
                last = child;
              }

            if (reportMutations)
              {
                insertionEvent(event, child);
              }
            if (doFree)
              {
                freeMutationEvent();
              }
          }
        ref.parent = null;
        ref.index = 0;
        ref.setDepth(0);
        ref.previous = null;
        ref.next = null;
        
        return ref;
      }
    catch (ClassCastException e)
      {
        throw new DomDOMException(DOMException.WRONG_DOCUMENT_ERR,
                                  null, newChild, 0);
      }
  }

  /**
   * <b>DOM L1</b>
   * Removes the specified child from this node's list of children,
   * or else reports an exception.
   *
   * <p> Causes a DOMNodeRemoved mutation event to be reported.
   *
   * <p> If this DOM has been compiled without mutation event support,
   * these events will not be reported.
   */
  public Node removeChild(Node refChild)
  {
    try
      {
        DomNode ref = (DomNode) refChild;

        if (ref == null || ref.parent != this)
          {
            throw new DomDOMException(DOMException.NOT_FOUND_ERR,
                                      null, ref, 0);
          }
        if (readonly && !owner.building)
          {
            throw new DomDOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR,
                                      null, this, 0);
          }
        
        for (DomNode child = first; child != null; child = child.next)
          {
            if (child == ref)
              {
                if (reportMutations)
                  {
                    removalEvent(null, child);
                  }

                length--;
                if (ref.previous != null)
                  {
                    ref.previous.next = ref.next;
                  }
                if (ref.next != null)
                  {
                    ref.next.previous = ref.previous;
                  }
                if (first == ref)
                  {
                    first = ref.next;
                  }
                if (last == ref)
                  {
                    last = ref.previous;
                  }
                // renumber indices
                int i = 0;
                for (DomNode ctx = first; ctx != null; ctx = ctx.next)
                  {
                    ctx.index = i++;
                  }
                ref.parent = null;
                ref.setDepth(0);
                ref.index = 0;
                ref.previous = null;
                ref.next = null;
                
                return ref;
              }
          }
        throw new DomDOMException(DOMException.NOT_FOUND_ERR,
                                  "that's no child of mine", refChild, 0);
      }
    catch (ClassCastException e)
      {
        throw new DomDOMException(DOMException.WRONG_DOCUMENT_ERR,
                                  null, refChild, 0);
      }
  }

  /**
   * <b>DOM L1 (NodeList)</b>
   * Returns the item with the specified index in this NodeList,
   * else null.
   */
  public Node item(int index)
  {
    DomNode child = first;
    int count = 0;
    while (child != null && count < index)
      {
        child = child.next;
        count++;
      }
    return child;
  }

  /**
   * <b>DOM L1 (NodeList)</b>
   * Returns the number of elements in this NodeList.
   * (Note that many interfaces have a "Length" property, not just
   * NodeList, and if a node subtype must implement one of those,
   * it will also need to override getChildNodes.)
   */
  public int getLength()
  {
    return length;
  }

  /**
   * Minimize extra space consumed by this node to hold children and event
   * listeners.
   */
  public void trimToSize()
  {
    if (listeners != null && listeners.length != nListeners)
      {
        ListenerRecord[] newKids = new ListenerRecord[length];
        System.arraycopy(listeners, 0, newKids, 0, nListeners);
        listeners = newKids;
      }
  }

  /**
   * <b>DOM L1</b>
   * Returns the previous sibling, if one is known.
   */
  public Node getNextSibling()
  {
    return next;
  }

  /**
   * <b>DOM L1</b>
   * Returns the previous sibling, if one is known.
   */
  public Node getPreviousSibling()
  {
    return previous;
  }

  /**
   * <b>DOM L1</b>
   * Returns the parent node, if one is known.
   */
  public Node getParentNode()
  {
    return parent;
  }

  /**
   * <b>DOM L2</b>
   * Consults the DOM implementation to determine if the requested
   * feature is supported.  DocumentType subclasses must override
   * this method, and associate themselves directly with the
   * DOMImplementation node used.  (This method relies on being able
   * to access the DOMImplementation from the owner document, but
   * DocumentType nodes can be created without an owner.)
   */
  public boolean isSupported(String feature, String version)
  {
    Document		doc = owner;
    DOMImplementation	impl = null;
    
    if (doc == null && nodeType == DOCUMENT_NODE)
      {
        doc = (Document) this;
      }

    if (doc == null)
      {
        // possible for DocumentType
        throw new IllegalStateException ("unbound ownerDocument");
      }

    impl = doc.getImplementation();
    return impl.hasFeature(feature, version);
  }

  /**
   * <b>DOM L1 (modified in L2)</b>
   * Returns the owner document.  This is only null for Document nodes,
   * and (new in L2) for DocumentType nodes which have not yet been
   * associated with the rest of their document.
   */
  final public Document getOwnerDocument()
  {
    return owner;
  }

  /**
   * <b>DOM L1</b>
   * Does nothing; this must be overridden (along with the
   * getNodeValue method) for nodes with a non-null defined value.
   */
  public void setNodeValue(String value)
  {
  }

  /**
   * <b>DOM L1</b>
   * Returns null; this must be overridden for nodes types with
   * a defined value, along with the setNodeValue method.
   */
  public String getNodeValue()
  {
    return null;
  }

  /** This forces GCJ compatibility.
   * Without this method GCJ is unable to compile to byte code.
   */
  public final short getNodeType()
  {
    return nodeType;
  }

  /** This forces GCJ compatibility.
   * Without this method GCJ seems unable to natively compile GNUJAXP.
   */
  public abstract String getNodeName();

  /**
   * <b>DOM L2</b>
   * Does nothing; this must be overridden (along with the
   * getPrefix method) for element and attribute nodes.
   */
  public void setPrefix(String prefix)
  {
  }

  /**
   * <b>DOM L2</b>
   * Returns null; this must be overridden for element and
   * attribute nodes.
   */
  public String getPrefix()
  {
    return null;
  }

  /**
   * <b>DOM L2</b>
   * Returns null; this must be overridden for element and
   * attribute nodes.
   */
  public String getNamespaceURI()
  {
    return null;
  }

  /**
   * <b>DOM L2</b>
   * Returns the node name; this must be overridden for element and
   * attribute nodes.
   */
  public String getLocalName()
  {
    return null;
  }

  /**
   * <b>DOM L1</b>
   * Returns a clone of this node which optionally includes cloned
   * versions of child nodes.  Clones are always mutable, except for
   * entity reference nodes.
   */
  public Node cloneNode(boolean deep)
  {
    DomNode node = (DomNode) clone();
    
    if (deep)
      {
        DomDocument doc = (nodeType == DOCUMENT_NODE) ?
          (DomDocument) node : node.owner;
        for (DomNode ctx = first; ctx != null; ctx = ctx.next)
          {
            DomNode newChild = (DomNode) ctx.cloneNode(deep);
            newChild.setOwner(doc);
            node.appendChild(newChild);
          }
      }
    
    if (nodeType == ENTITY_REFERENCE_NODE)
      {
        node.makeReadonly();
      }
    notifyUserDataHandlers(UserDataHandler.NODE_CLONED, this, node);
    return node;
  }

  void notifyUserDataHandlers(short op, Node src, Node dst)
  {
    if (userDataHandlers != null)
      {
        for (Iterator i = userDataHandlers.entrySet().iterator(); i.hasNext(); )
          {
            Map.Entry entry = (Map.Entry) i.next();
            String key = (String) entry.getKey();
            UserDataHandler handler = (UserDataHandler) entry.getValue();
            Object data = userData.get(key);
            handler.handle(op, key, data, src, dst);
          }
      }
  }

  /**
   * Clones this node; roughly equivalent to cloneNode(false).
   * Element subclasses must provide a new implementation which
   * invokes this method to handle the basics, and then arranges
   * to clone any element attributes directly.  Attribute subclasses
   * must make similar arrangements, ensuring that existing ties to
   * elements are broken by cloning.
   */
  public Object clone()
  {
    try
      {
        DomNode node = (DomNode) super.clone();
        
        node.parent = null;
        node.depth = 0;
        node.index = 0;
        node.length = 0;
        node.first = null;
        node.last = null;
        node.previous = null;
        node.next = null;
        
        node.readonly = false;
        node.listeners = null;
        node.nListeners = 0;
        return node;

      }
    catch (CloneNotSupportedException x)
      {
        throw new Error("clone didn't work");
      }
  }

  // the elements-by-tagname stuff is needed for both
  // elements and documents ... this is in lieu of a
  // common base class between Node and NodeNS.

  /**
   * <b>DOM L1</b>
   * Creates a NodeList giving array-style access to elements with
   * the specified name.  Access is fastest if indices change by
   * small values, and the DOM is not modified.
   */
  public NodeList getElementsByTagName(String tag)
  {
    return new ShadowList(null, tag);
  }

  /**
   * <b>DOM L2</b>
   * Creates a NodeList giving array-style access to elements with
   * the specified namespace and local name.  Access is fastest if
   * indices change by small values, and the DOM is not modified.
   */
  public NodeList getElementsByTagNameNS(String namespace, String local)
  {
    return new ShadowList(namespace, local);
  }


  //
  // This shadow class is GC-able even when the live list it shadows
  // can't be, because of event registration hookups.  Its finalizer
  // makes that live list become GC-able.
  //
  final class ShadowList
    implements NodeList
  {

    private LiveNodeList liveList;
    
    ShadowList(String ns, String local)
    {
      liveList = new LiveNodeList(ns, local);
    }

    public void finalize()
    {
      liveList.detach();
      liveList = null;
    }

    public Node item(int index)
    {
      return liveList.item(index);
    }

    public int getLength()
    {
      return liveList.getLength();
    }
  }

  final class LiveNodeList
    implements NodeList, EventListener, NodeFilter
  {
 
    private final boolean matchAnyURI;
    private final boolean matchAnyName; 
    private final String elementURI;
    private final String elementName;
    
    private DomIterator current;
    private int lastIndex;
    
    LiveNodeList(String uri, String name)
    {
      elementURI = uri;
      elementName = name;
      matchAnyURI = "*".equals(uri);
      matchAnyName = "*".equals(name);
      
      DomNode.this.addEventListener("DOMNodeInserted", this, true);
      DomNode.this.addEventListener("DOMNodeRemoved", this, true);
    }

    void detach()
    {
      if (current != null)
        current.detach();
      current = null;
      
      DomNode.this.removeEventListener("DOMNodeInserted", this, true);
      DomNode.this.removeEventListener("DOMNodeRemoved", this, true);
    }

    public short acceptNode(Node element)
    {
      if (element == DomNode.this)
        {
          return FILTER_SKIP;
        }

      // use namespace-aware matching ...
      if (elementURI != null)
        {
          if (!(matchAnyURI
                || elementURI.equals(element.getNamespaceURI())))
            {
              return FILTER_SKIP;
            }
          if (!(matchAnyName
                || elementName.equals(element.getLocalName())))
            {
              return FILTER_SKIP;
            }

          // ... or qName-based kind.
        }
      else
        {
          if (!(matchAnyName
                || elementName.equals(element.getNodeName())))
            {
              return FILTER_SKIP;
            }
        }
      return FILTER_ACCEPT;
    }

    private DomIterator createIterator()
    {
      return new DomIterator(DomNode.this,
                             NodeFilter.SHOW_ELEMENT,
                             this,	/* filter */
                             true	/* expand entity refs */
                            );
    }

    public void handleEvent(Event e)
    {
      MutationEvent	mutation = (MutationEvent) e;
      Node		related = mutation.getRelatedNode();
      
      // XXX if it's got children ... check all kids too, they
      // will invalidate our saved index
      
      if (related.getNodeType() != Node.ELEMENT_NODE ||
          related.getNodeName() != elementName ||
          related.getNamespaceURI() != elementURI)
        {
          return;
        }
      
      current = null;
    }

    public Node item(int index)
    {
      if (current == null)
        {
          current = createIterator();
          lastIndex = -1;
        }
      
      // last node or before?  go backwards
      if (index <= lastIndex) {
        while (index != lastIndex) {
          current.previousNode ();
          lastIndex--;
        }
        Node ret = current.previousNode ();
        current = null;
        return ret;
      } 
      
      // somewhere after last node
      while (++lastIndex != index)
        current.nextNode ();
        Node ret = current.nextNode ();
        current = null;
        return ret;
    }
    
    public int getLength()
    {
      int retval = 0;
      NodeIterator iter = createIterator();
      
      while (iter.nextNode() != null)
        {
          retval++;
        }
      current = null;
      return retval;
    }
    
  }

  //
  // EventTarget support
  //
  static final class ListenerRecord
  {
  
    String type;
    EventListener listener;
    boolean useCapture;

    // XXX use JDK 1.2 java.lang.ref.WeakReference to listener,
    // and we can both get rid of "shadow" classes and remove
    // the need for applications to apply similar trix ... but
    // JDK 1.2 support isn't generally available yet

    ListenerRecord(String type, EventListener listener, boolean useCapture)
    {
      this.type = type.intern();
      this.listener = listener;
      this.useCapture = useCapture;
    }

    boolean equals(ListenerRecord rec)
    {
      return listener == rec.listener
        && useCapture == rec.useCapture
        && type == rec.type;
    }
    
  }

  /**
   * <b>DOM L2 (Events)</b>
   * Returns an instance of the specified type of event object.
   * Understands about DOM Mutation, HTML, and UI events.
   *
   * <p>If the name of the event type begins with "USER-", then an object
   * implementing the "Event" class will be returned; this provides a
   * limited facility for application-defined events to use the DOM event
   * infrastructure.  Alternatively, use one of the standard DOM event
   * classes and initialize it using use such a "USER-" event type name;
   * or defin, instantiate, and initialize an application-specific subclass
   * of DomEvent and pass that to dispatchEvent().
   *
   * @param eventType Identifies the particular DOM feature module
   *	defining the type of event, such as "MutationEvents".
   *	<em>The event "name" is a different kind of "type".</em>
   */
  public Event createEvent(String eventType)
  {
    eventType = eventType.toLowerCase();
    
    if ("mutationevents".equals(eventType))
      {
        return new DomEvent.DomMutationEvent(null);
      }
    
    if ("htmlevents".equals(eventType)
        || "events".equals(eventType)
        || "user-events".equals(eventType))
      {
        return new DomEvent(null);
      }
    
    if ("uievents".equals(eventType))
      {
        return new DomEvent.DomUIEvent(null);
      }

    // mouse events 
    
    throw new DomDOMException(DOMException.NOT_SUPPORTED_ERR,
                              eventType, null, 0);
  }

  /**
   * <b>DOM L2 (Events)</b>
   * Registers an event listener's interest in a class of events.
   */
  public final void addEventListener(String type,
                                     EventListener listener,
                                     boolean useCapture)
  {
    if (listeners == null)
      {
        listeners = new ListenerRecord[1];
      }
    else if (nListeners == listeners.length)
      {
        ListenerRecord[] newListeners =
          new ListenerRecord[listeners.length + NKIDS_DELTA];
        System.arraycopy(listeners, 0, newListeners, 0, nListeners);
        listeners = newListeners;
      }

    // prune duplicates
    ListenerRecord record;

    record = new ListenerRecord(type, listener, useCapture);
    for (int i = 0; i < nListeners; i++)
      {
        if (record.equals(listeners[i]))
          {
            return;
          }
      }
    listeners [nListeners++] = record;
  }

  // XXX this exception should be discarded from DOM

  // this class can be instantiated, unlike the one in the spec
  static final class DomEventException
    extends EventException
  {
   
    DomEventException()
    {
      super(UNSPECIFIED_EVENT_TYPE_ERR, "unspecified event type");
    }
    
  }

  /**
   * <b>DOM L2 (Events)</b>
   * Delivers an event to all relevant listeners, returning true if the
   * caller should perform their default action.  Note that the event
   * must have been provided by the createEvent() method on this
   * class, else it can't be dispatched.
   *
   * @see #createEvent
   *
   * @exception NullPointerException When a null event is passed.
   * @exception ClassCastException When the event wasn't provided by
   *	the createEvent method, or otherwise isn't a DomEvent.
   * @exception EventException If the event type wasn't specified
   */
  public final boolean dispatchEvent(Event event)
    throws EventException
  {
    DomEvent e = (DomEvent) event;
    DomNode[] ancestors = null;
    int ancestorMax = 0;
    boolean haveDispatchDataLock = false;
    
    if (e.type == null)
      {
        throw new DomEventException();
      }

    e.doDefault = true;
    e.target = this;
    
    //
    // Typical case:  one nonrecursive dispatchEvent call at a time
    // for this class.  If that's our case, we can avoid allocating
    // garbage, which is overall a big win.  Even with advanced GCs
    // that deal well with short-lived garbage, and wayfast allocators,
    // it still helps.
    //
    // Remember -- EVERY mutation goes though here at least once.
    //
    // When populating a DOM tree, trying to send mutation events is
    // the primary cost; this dominates the critical path.
    //
    try
      {
        DomNode current;
        int index;
        boolean haveAncestorRegistrations = false;
        ListenerRecord[] notificationSet;
        int ancestorLen;
        
        synchronized (lockNode)
          {
            if (!dispatchDataLock)
              {
                haveDispatchDataLock = dispatchDataLock = true;
                notificationSet = DomNode.notificationSet;
                ancestors = DomNode.ancestors;
              }
            else
              {
                notificationSet = new ListenerRecord[NOTIFICATIONS_INIT];
                ancestors = new DomNode[ANCESTORS_INIT];
              }
            ancestorLen = ancestors.length;
          }
        
        // XXX autogrow ancestors ... based on statistics
        
        // Climb to the top of this subtree and handle capture, letting
        // each node (from the top down) capture until one stops it or
        // until we get to this one.
        
        for (index = 0, current = parent;
             current != null && index < ancestorLen;
             index++, current = current.parent)
          {
            if (current.nListeners != 0)
              {
                haveAncestorRegistrations = true;
              }
            ancestors [index] = current;
          }
        if (current != null)
          {
            throw new RuntimeException("dispatchEvent capture stack size");
          }
        
        ancestorMax = index;
        e.stop = false;
        
        if (haveAncestorRegistrations)
          {
            e.eventPhase = Event.CAPTURING_PHASE;
            while (!e.stop && index-- > 0)
              {
                current = ancestors [index];
                if (current.nListeners != 0)
                  {
                    notifyNode(e, current, true, notificationSet);
                  }
              }
          }
        
        // Always deliver events to the target node (this)
        // unless stopPropagation was called.  If we saw
        // no registrations yet (typical!), we never will.
        if (!e.stop && nListeners != 0)
          {
            e.eventPhase = Event.AT_TARGET;
            notifyNode (e, this, false, notificationSet);
          }
        else if (!haveAncestorRegistrations)
          {
            e.stop = true;
          }
        
        // If the event bubbles and propagation wasn't halted,
        // walk back up the ancestor list.  Stop bubbling when
        // any bubbled event handler stops it.
        
        if (!e.stop && e.bubbles)
          {
            e.eventPhase = Event.BUBBLING_PHASE;
            for (index = 0;
                 !e.stop
                 && index < ancestorMax
                 && (current = ancestors[index]) != null;
                 index++)
              {
                if (current.nListeners != 0)
                  {
                    notifyNode(e, current, false, notificationSet);
                  }
              }
          }
        e.eventPhase = 0;
        
        // Caller chooses whether to perform the default
        // action based on return from this method.
        return e.doDefault;
        
      }
    finally
      {
        if (haveDispatchDataLock)
          {
            // synchronize to force write ordering
            synchronized (lockNode)
              {
                // null out refs to ensure they'll be GC'd
                for (int i = 0; i < ancestorMax; i++)
                  {
                    ancestors [i] = null;
                  }
                // notificationSet handled by notifyNode
                
                dispatchDataLock = false;
              }
          }
      }
  }
  
  private void notifyNode(DomEvent e,
                          DomNode current,
                          boolean capture,
                          ListenerRecord[] notificationSet)
  {
    int count = 0;

    // do any of this set of listeners get notified?
    for (int i = 0; i < current.nListeners; i++)
      {
        ListenerRecord rec = current.listeners[i];

        if (rec.useCapture != capture)
          {
            continue;
          }
        if (!e.type.equals (rec.type)) 
          {
            continue;
          }
        if (count >= notificationSet.length)
          {
            // very simple growth algorithm
            int len = Math.max(notificationSet.length, 1);
            ListenerRecord[] tmp = new ListenerRecord[len * 2];
            System.arraycopy(notificationSet, 0, tmp, 0,
                             notificationSet.length);
            notificationSet = tmp;
          }
        notificationSet[count++] = rec;
      }

    // Notify just those listeners
    e.currentNode = current; 
    for (int i = 0; i < count; i++)
      {
        try
          {
            // Late in the DOM CR process (3rd or 4th CR?) the
            // removeEventListener spec became asymmetric with respect
            // to addEventListener ... effect is now immediate.
            for (int j = 0; j < current.nListeners; j++)
              {
                if (current.listeners[j].equals(notificationSet[i]))
                  {
                    notificationSet[i].listener.handleEvent(e);
                    break;
                  }
              }
            
          }
        catch (Exception x)
          {
            // ignore all exceptions
          }
        notificationSet[i] = null;		// free for GC
      }
  }

  /**
   * <b>DOM L2 (Events)</b>
   * Unregisters an event listener.
   */
  public final void removeEventListener(String type,
                                        EventListener listener,
                                        boolean useCapture)
  {
    for (int i = 0; i < nListeners; i++)
      {
        if (listeners[i].listener != listener)
          {
            continue;
          }
        if (listeners[i].useCapture != useCapture)
          {
            continue;
          }
        if (!listeners[i].type.equals(type))
          {
            continue;
          }

        if (nListeners == 1)
          {
            listeners = null;
            nListeners = 0;
          }
        else
          {
            for (int j = i + 1; j < nListeners; j++)
              {
                listeners[i++] = listeners[j++];
              }
            listeners[--nListeners] = null;
          }
        break;
      }
    // no exceptions reported
  }

  /**
   * <b>DOM L1 (relocated in DOM L2)</b>
   * In this node and all contained nodes (including attributes if
   * relevant) merge adjacent text nodes.  This is done while ignoring
   * text which happens to use CDATA delimiters).
   */
  public final void normalize()
  {
    // Suspend readonly status
    boolean saved = readonly;
    readonly = false;
    for (DomNode ctx = first; ctx != null; ctx = ctx.next)
      {
        switch (ctx.nodeType)
          {
          case TEXT_NODE:
            while (ctx.next != null && ctx.next.nodeType == TEXT_NODE)
              {
                Text text = (Text) ctx;
                text.appendData(ctx.next.getNodeValue());
                removeChild(ctx.next);
              }
            break;
          case ELEMENT_NODE:
            NamedNodeMap attrs = ctx.getAttributes();
            int len = attrs.getLength();
            for (int i = 0; i < len; i++)
              {
                attrs.item(i).normalize();
              }
            // Fall through
          case DOCUMENT_NODE:
          case DOCUMENT_FRAGMENT_NODE:
          case ATTRIBUTE_NODE:
          case ENTITY_REFERENCE_NODE:
            ctx.normalize();
            break;
          }
      }
    readonly = saved;
  }

  /**
   * Returns true iff node types match, and either (a) both nodes have no
   * namespace and their getNodeName() values are the same, or (b) both
   * nodes have the same getNamespaceURI() and same getLocalName() values.
   *
   * <p>Note that notion of a "Per-Element-Type" attribute name scope, as
   * found in a non-normative appendix of the XML Namespaces specification,
   * is not supported here.  Your application must implement that notion,
   * typically by not bothering to check nameAndTypeEquals for attributes
   * without namespace URIs unless you already know their elements are
   * nameAndTypeEquals.
   */
  public boolean nameAndTypeEquals(Node other)
  {
    if (other == this)
      {
        return true;
      }
    // node types must match
    if (nodeType != other.getNodeType())
      {
        return false;
      }

    // if both have namespaces, do a "full" comparision
    // this is a "global" partition
    String ns1 = this.getNamespaceURI();
    String ns2 = other.getNamespaceURI();

    if (ns1 != null && ns2 != null)
      {
        return ns1.equals(ns2) &&
          equal(getLocalName(), other.getLocalName());
      }

    // if neither has a namespace, this is a "no-namespace" name.
    if (ns1 == null && ns2 == null)
      {
        if (!getNodeName().equals(other.getNodeName()))
          {
            return false;
          }
        // can test the non-normative "per-element-type" scope here.
        // if this is an attribute node and both nodes have been bound
        // to elements (!!), then return the nameAndTypeEquals()
        // comparison of those elements.
        return true;
      }

    // otherwise they're unequal: one scoped, one not.
    return false;
  }

  // DOM Level 3 methods

  public String getBaseURI()
  {
    return (parent != null) ? parent.getBaseURI() : null;
  }

  public short compareDocumentPosition(Node other)
    throws DOMException
  {
    return (short) compareTo(other);
  }

  /**
   * DOM nodes have a natural ordering: document order.
   */
  public final int compareTo(Object other)
  {
    if (other instanceof DomNode)
      {
        DomNode n1 = this;
        DomNode n2 = (DomNode) other;
        if (n1.owner != n2.owner)
          {
            return 0;
          }
        int d1 = n1.depth, d2 = n2.depth;
        int delta = d1 - d2;
        while (d1 > d2)
          {
            n1 = n1.parent;
            d1--;
          }
        while (d2 > d1)
          {
            n2 = n2.parent;
            d2--;
          }
        int c = compareTo2(n1, n2);
        return (c != 0) ? c : delta;
      }
    return 0;
  }

  /**
   * Compare two nodes at the same depth.
   */
  final int compareTo2(DomNode n1, DomNode n2)
  {
    if (n1 == n2 || n1.depth == 0 || n2.depth == 0)
      {
        return 0;
      }
    int c = compareTo2(n1.parent, n2.parent);
    return (c != 0) ? c : n1.index - n2.index;
  }

  public final String getTextContent()
    throws DOMException
  {
    return getTextContent(true);
  }

  final String getTextContent(boolean topLevel)
    throws DOMException
  {
    switch (nodeType)
      {
      case ELEMENT_NODE:
      case ENTITY_NODE:
      case ENTITY_REFERENCE_NODE:
      case DOCUMENT_FRAGMENT_NODE:
        StringBuffer buffer = new StringBuffer();
        for (DomNode ctx = first; ctx != null; ctx = ctx.next)
          {
            String textContent = ctx.getTextContent(false);
            if (textContent != null)
              {
                buffer.append(textContent);
              }
          }
        return buffer.toString();
      case TEXT_NODE:
      case CDATA_SECTION_NODE:
        if (((Text) this).isElementContentWhitespace())
          {
            return "";
          }
        return getNodeValue();
      case ATTRIBUTE_NODE:
        return getNodeValue();
      case COMMENT_NODE:
      case PROCESSING_INSTRUCTION_NODE:
        return topLevel ? getNodeValue() : "";
      default:
        return null;
      }
  }

  public void setTextContent(String textContent)
    throws DOMException
  {
    switch (nodeType)
      {
      case ELEMENT_NODE:
      case ATTRIBUTE_NODE:
      case ENTITY_NODE:
      case ENTITY_REFERENCE_NODE:
      case DOCUMENT_FRAGMENT_NODE:
        for (DomNode ctx = first; ctx != null; )
          {
            DomNode n = ctx.next;
            removeChild(ctx);
            ctx = n;
          }
        if (textContent != null)
          {
            Text text = owner.createTextNode(textContent);
            appendChild(text);
          }
        break;
      case TEXT_NODE:
      case CDATA_SECTION_NODE:
      case COMMENT_NODE:
      case PROCESSING_INSTRUCTION_NODE:
        setNodeValue(textContent);
        break;
      }
  }

  public boolean isSameNode(Node other)
  {
    return this == other;
  }

  public String lookupPrefix(String namespaceURI)
  {
    return (parent == null || parent == owner) ? null :
      parent.lookupPrefix(namespaceURI);
  }

  public boolean isDefaultNamespace(String namespaceURI)
  {
    return (parent == null || parent == owner) ? false :
      parent.isDefaultNamespace(namespaceURI);
  }

  public String lookupNamespaceURI(String prefix)
  {
    return (parent == null || parent == owner) ? null :
      parent.lookupNamespaceURI(prefix);
  }

  public boolean isEqualNode(Node arg)
  {
    if (this == arg)
      {
        return true;
      }
    if (arg == null)
      {
        return false;
      }
    if (nodeType != arg.getNodeType() ||
        !equal(getNodeName(), arg.getNodeName()) ||
        !equal(getLocalName(), arg.getLocalName()) ||
        !equal(getNamespaceURI(), arg.getNamespaceURI()) ||
        !equal(getPrefix(), arg.getPrefix()) ||
        !equal(getNodeValue(), arg.getNodeValue()))
      {
        return false;
      }
    // Children
    Node argCtx = arg.getFirstChild();
    getFirstChild(); // because of DomAttr lazy children
    for (DomNode ctx = first; ctx != null; ctx = ctx.next)
      {
        if (!ctx.isEqualNode(argCtx))
          {
            return false;
          }
        argCtx = argCtx.getNextSibling();
      }
    if (argCtx != null)
      {
        return false;
      }
    
    // TODO Attr NamedNodeMap
    // TODO DocumentType
    return true;
  }

  boolean equal(String arg1, String arg2)
  {
    return ((arg1 == null && arg2 == null) ||
            (arg1 != null && arg1.equals(arg2))); 
  }
  
  public Object getFeature(String feature, String version)
  {
    DOMImplementation impl = (nodeType == DOCUMENT_NODE) ?
      ((Document) this).getImplementation() : owner.getImplementation();
    if (impl.hasFeature(feature, version))
      {
        return this;
      }
    return null;
  }

  public Object setUserData(String key, Object data, UserDataHandler handler)
  {
    if (userData == null)
      {
        userData = new HashMap();
      }
    if (handler != null)
      {
        if (userDataHandlers == null)
          {
            userDataHandlers = new HashMap();
          }
        userDataHandlers.put(key, handler);
      }
    return userData.put(key, data);
  }

  public Object getUserData(String key)
  {
    if (userData == null)
      {
        return null;
      }
    return userData.get(key);
  }

  public String toString()
  {
    String nodeName = getNodeName();
    String nodeValue = getNodeValue();
    StringBuffer buf = new StringBuffer(getClass().getName());
    buf.append('[');
    if (nodeName != null)
      {
        buf.append(nodeName);
      }
    if (nodeValue != null)
      {
        if (nodeName != null)
          {
            buf.append('=');
          }
        buf.append('\'');
        buf.append(encode(nodeValue));
        buf.append('\'');
      }
    buf.append(']');
    return buf.toString();
  }
  
  String encode(String value)
  {
    StringBuffer buf = null;
    int len = value.length();
    for (int i = 0; i < len; i++)
      {
        char c = value.charAt(i);
        if (c == '\n')
          {
            if (buf == null)
              {
                buf = new StringBuffer(value.substring(0, i));
              }
            buf.append("\\n");
          }
        else if (c == '\r')
          {
            if (buf == null)
              {
                buf = new StringBuffer(value.substring(0, i));
              }
            buf.append("\\r");
          }
        else if (buf != null)
          {
            buf.append(c);
          }
      }
    return (buf != null) ? buf.toString() : value;
  }

  String nodeTypeToString(short nodeType)
  {
    switch (nodeType)
      {
      case ELEMENT_NODE:
        return "ELEMENT_NODE";
      case ATTRIBUTE_NODE:
        return "ATTRIBUTE_NODE";
      case TEXT_NODE:
        return "TEXT_NODE";
      case CDATA_SECTION_NODE:
        return "CDATA_SECTION_NODE";
      case DOCUMENT_NODE:
        return "DOCUMENT_NODE";
      case DOCUMENT_TYPE_NODE:
        return "DOCUMENT_TYPE_NODE";
      case COMMENT_NODE:
        return "COMMENT_NODE";
      case PROCESSING_INSTRUCTION_NODE:
        return "PROCESSING_INSTRUCTION_NODE";
      case DOCUMENT_FRAGMENT_NODE:
        return "DOCUMENT_FRAGMENT_NODE";
      case ENTITY_NODE:
        return "ENTITY_NODE";
      case ENTITY_REFERENCE_NODE:
        return "ENTITY_REFERENCE_NODE";
      case NOTATION_NODE:
        return "NOTATION_NODE";
      default:
        return "UNKNOWN";
      }
  }

}