/*

 ============================================================================
                   The Apache Software License, Version 1.1
 ============================================================================

 Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.

 Redistribution and use in source and binary forms, with or without modifica-
 tion, are permitted provided that the following conditions are met:

 1. Redistributions of  source code must  retain the above copyright  notice,
    this list of conditions and the following disclaimer.

 2. 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.

 3. The end-user documentation included with the redistribution, if any, must
    include  the following  acknowledgment:  "This product includes  software
    developed  by the  Apache Software Foundation  (http://www.apache.org/)."
    Alternately, this  acknowledgment may  appear in the software itself,  if
    and wherever such third-party acknowledgments normally appear.

 4. The names "Batik" and  "Apache Software Foundation" must  not  be
    used to  endorse or promote  products derived from  this software without
    prior written permission. For written permission, please contact
    apache@apache.org.

 5. Products  derived from this software may not  be called "Apache", nor may
    "Apache" appear  in their name,  without prior written permission  of the
    Apache Software Foundation.

 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED 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
 APACHE SOFTWARE  FOUNDATION  OR ITS CONTRIBUTORS  BE LIABLE FOR  ANY DIRECT,
 INDIRECT, INCIDENTAL, SPECIAL,  EXEMPLARY, OR CONSEQUENTIAL  DAMAGES (INCLU-
 DING, 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 Apache Software  Foundation. For more  information on the
 Apache Software Foundation, please see <http://www.apache.org/>.

*/

package org.apache.batik.dom;

import java.io.Serializable;

import org.w3c.dom.DOMException;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
import org.w3c.dom.events.DocumentEvent;
import org.w3c.dom.events.MutationEvent;

/**
 * This class implements the Node interface with support for children.
 *
 * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
 * @version $Id: AbstractParentNode.java,v 1.21 2003/08/09 16:58:41 deweese Exp $
 */

public abstract class AbstractParentNode extends AbstractNode {

    /**
     * The children.
     */
    protected ChildNodes childNodes;

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#getChildNodes()}.
     * @return {@link #childNodes}
     */
    public NodeList getChildNodes() {
	return (childNodes == null)
            ? childNodes = new ChildNodes()
            : childNodes;
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#getFirstChild()}.
     * @return {@link #childNodes}.firstChild
     */
    public Node getFirstChild() {
	return (childNodes == null) ? null : childNodes.firstChild;
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#getLastChild()}.
     * @return {@link #childNodes}.lastChild
     */
    public Node getLastChild() {
	return (childNodes == null) ? null : childNodes.lastChild;
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Node#insertBefore(Node, Node)}.
     */
    public Node insertBefore(Node newChild, Node refChild)
        throws DOMException {
	if (refChild != null && childNodes == null) {
	    throw createDOMException
		(DOMException.NOT_FOUND_ERR,
		 "child.missing",
		 new Object[] { new Integer(refChild.getNodeType()),
				refChild.getNodeName() });
	}
	checkAndRemove(newChild, false);

	if (newChild.getNodeType() == DOCUMENT_FRAGMENT_NODE) {
	    Node n = newChild.getFirstChild();
	    while (n != null) {
                Node ns = n.getNextSibling();
		insertBefore(n, refChild);
		n = ns;
	    }
	    return newChild;
	} else {
	    // Node modification
	    if (childNodes == null) {
	        childNodes = new ChildNodes();
	    }
	    ExtendedNode n = childNodes.insert((ExtendedNode)newChild,
					       (ExtendedNode)refChild);
	    n.setParentNode(this);

            nodeAdded(n);

	    // Mutation event
	    fireDOMNodeInsertedEvent(n);
	    fireDOMSubtreeModifiedEvent();
	    return n;
	}
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Node#replaceChild(Node, Node)}.
     */
    public Node replaceChild(Node newChild, Node oldChild)
        throws DOMException {
	if (childNodes == null) {
	    throw createDOMException
		(DOMException.NOT_FOUND_ERR,
		 "child.missing",
		 new Object[] { new Integer(oldChild.getNodeType()),
				oldChild.getNodeName() });
	}
	checkAndRemove(newChild, true);

	if (newChild.getNodeType() == DOCUMENT_FRAGMENT_NODE) {
	    Node n  = newChild.getLastChild();
	    Node ps = oldChild.getNextSibling();
	    if (n != null) {
		replaceChild(n, oldChild);
		n = n.getPreviousSibling();
	    }
	    while (n != null) {
		insertBefore(n, ps);
		n = n.getPreviousSibling();
	    }
	    return newChild;
	} else {
	    // Mutation event
	    fireDOMNodeRemovedEvent(oldChild);

            getCurrentDocument().nodeToBeRemoved(oldChild);
            nodeToBeRemoved(oldChild);

	    // Node modification
	    ExtendedNode n = (ExtendedNode)newChild;
	    ExtendedNode o = childNodes.replace(n, (ExtendedNode)oldChild);
	    n.setParentNode(this);
	    o.setParentNode(null);

            nodeAdded(n);

	    // Mutation event
	    fireDOMNodeInsertedEvent(n);
	    fireDOMSubtreeModifiedEvent();
	    return n;
	}
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#removeChild(Node)}.
     */
    public Node removeChild(Node oldChild) throws DOMException {
	if (childNodes == null || oldChild.getParentNode() != this) {
	    throw createDOMException
		(DOMException.NOT_FOUND_ERR,
		 "child.missing",
		 new Object[] { new Integer(oldChild.getNodeType()),
				oldChild.getNodeName() });
	}
	if (isReadonly()) {
	    throw createDOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR,
				     "readonly.node",
				     new Object[] { new Integer(getNodeType()),
						    getNodeName() });
	}

	// Mutation event
	fireDOMNodeRemovedEvent(oldChild);

        getCurrentDocument().nodeToBeRemoved(oldChild);
        nodeToBeRemoved(oldChild);

	// Node modification
	ExtendedNode result = childNodes.remove((ExtendedNode)oldChild);
	result.setParentNode(null);

	// Mutation event
	fireDOMSubtreeModifiedEvent();
	return result;
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#appendChild(Node)}.
     */
    public Node appendChild(Node newChild) throws DOMException {
	checkAndRemove(newChild, false);

	if (newChild.getNodeType() == DOCUMENT_FRAGMENT_NODE) {
	    Node n = newChild.getFirstChild();
	    while (n != null) {
                Node ns = n.getNextSibling();
		appendChild(n);
		n = ns;
	    }
	    return newChild;
	} else {
	    if (childNodes == null) {
		childNodes = new ChildNodes();
	    }
	    // Node modification
	    ExtendedNode n = childNodes.append((ExtendedNode)newChild);
	    n.setParentNode(this);

            nodeAdded(n);

	    // Mutation event
	    fireDOMNodeInsertedEvent(n);
	    fireDOMSubtreeModifiedEvent();
	    return n;
	}
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#hasChildNodes()}.
     * @return true if this node has children, false otherwise.
     */
    public boolean hasChildNodes() {
	return childNodes != null && childNodes.getLength() != 0;
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#normalize()}.
     */
    public void normalize() {
	Node p = getFirstChild();
	if (p != null) {
	    p.normalize();
	    Node n = p.getNextSibling();
	    while (n != null) {
		if (p.getNodeType() == TEXT_NODE &&
                    n.getNodeType() == TEXT_NODE) {
		    String s = p.getNodeValue() + n.getNodeValue();
		    AbstractText at = (AbstractText)p;
		    at.setNodeValue(s);
		    removeChild(n);
		    n = p.getNextSibling();
		} else {
		    n.normalize();
		    p = n;
		    n = n.getNextSibling();
		}
	    }
	}
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#getElementsByTagName(String)}.
     */
    public NodeList getElementsByTagName(String name) {
	if (name == null) {
	    return EMPTY_NODE_LIST;
	}
        AbstractDocument ad = getCurrentDocument();
        ElementsByTagName result = ad.getElementsByTagName(this, name);
        if (result == null) {
            result = new ElementsByTagName(name);
            ad.putElementsByTagName(this, name, result);
        }
        return result;
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#getElementsByTagNameNS(String,String)}.
     */
    public NodeList getElementsByTagNameNS(String namespaceURI,
                                           String localName) {
	if (localName == null) {
	    return EMPTY_NODE_LIST;
	}
        AbstractDocument ad = getCurrentDocument();
        ElementsByTagNameNS result =
            ad.getElementsByTagNameNS(this, namespaceURI,
                                      localName);
        if (result == null) {
            result = new ElementsByTagNameNS(namespaceURI, localName);
            ad.putElementsByTagNameNS(this, namespaceURI, localName, result);
        }
        return result;
    }

    /**
     * Recursively fires a DOMNodeInsertedIntoDocument event.
     */
    public void fireDOMNodeInsertedIntoDocumentEvent() {
	AbstractDocument doc = getCurrentDocument();
	if (doc.getEventsEnabled()) {
	    super.fireDOMNodeInsertedIntoDocumentEvent();
	    for (Node n = getFirstChild(); n != null; n = n.getNextSibling()) {
		((AbstractNode)n).fireDOMNodeInsertedIntoDocumentEvent();
	    }
	}
    }

    /**
     * Recursively fires a DOMNodeRemovedFromDocument event.
     */
    public void fireDOMNodeRemovedFromDocumentEvent() {
	AbstractDocument doc = getCurrentDocument();
	if (doc.getEventsEnabled()) {
	    super.fireDOMNodeRemovedFromDocumentEvent();
	    for (Node n = getFirstChild(); n != null; n = n.getNextSibling()) {
		((AbstractNode)n).fireDOMNodeRemovedFromDocumentEvent();
	    }
	}
    }

    /**
     * Called when a child node has been added.
     */
    protected void nodeAdded(Node n) {
    }

    /**
     * Called when a child node is going to be removed.
     */
    protected void nodeToBeRemoved(Node n) {
    }

    /**
     * Deeply exports this node to the given document.
     */
    protected Node deepExport(Node n, AbstractDocument d) {
	super.deepExport(n, d);
	for (Node p = getFirstChild(); p != null; p = p.getNextSibling()) {
	    Node t = ((AbstractNode)p).deepExport(p.cloneNode(false), d);
	    n.appendChild(t);
	}
	return n;
    }

    /**
     * Deeply copy the fields of the current node into the given node.
     * @param n a node of the type of this.
     */
    protected Node deepCopyInto(Node n) {
	super.deepCopyInto(n);
	for (Node p = getFirstChild(); p != null; p = p.getNextSibling()) {
	    Node t = p.cloneNode(true);
	    n.appendChild(t);
	}
	return n;
    }

    /**
     * Fires a DOMSubtreeModified event.
     */
    protected void fireDOMSubtreeModifiedEvent() {
	AbstractDocument doc = getCurrentDocument();
	if (doc.getEventsEnabled()) {
	    DocumentEvent de = (DocumentEvent)doc;
	    MutationEvent ev = (MutationEvent)de.createEvent("MutationEvents");
	    ev.initMutationEvent("DOMSubtreeModified",
				 true,   // canBubbleArg
				 false,  // cancelableArg
				 null,   // relatedNodeArg
				 null,   // prevValueArg
				 null,   // newValueArg
				 null,   // attrNameArg
                                 MutationEvent.MODIFICATION);
	    dispatchEvent(ev);
	}
    }

    /**
     * Fires a DOMNodeInserted event.
     */
    protected void fireDOMNodeInsertedEvent(Node node) {
	AbstractDocument doc = getCurrentDocument();
	if (doc.getEventsEnabled()) {
	    DocumentEvent de = (DocumentEvent)doc;
	    MutationEvent ev = (MutationEvent)de.createEvent("MutationEvents");
	    ev.initMutationEvent("DOMNodeInserted",
				 true,   // canBubbleArg
				 false,  // cancelableArg
				 this,   // relatedNodeArg
				 null,   // prevValueArg
				 null,   // newValueArg
				 null,   // attrNameArg
                                 MutationEvent.ADDITION);
	    AbstractNode n = (AbstractNode)node;
	    n.dispatchEvent(ev);
	    n.fireDOMNodeInsertedIntoDocumentEvent();
	}
    }

    /**
     * Fires a DOMNodeRemoved event.
     */
    protected void fireDOMNodeRemovedEvent(Node node) {
	AbstractDocument doc = getCurrentDocument();
	if (doc.getEventsEnabled()) {
	    DocumentEvent de = (DocumentEvent)doc;
	    MutationEvent ev = (MutationEvent)de.createEvent("MutationEvents");
	    ev.initMutationEvent("DOMNodeRemoved",
				 true,   // canBubbleArg
				 false,  // cancelableArg
				 this,   // relatedNodeArg
				 null,   // prevValueArg
				 null,   // newValueArg
				 null,   // attrNameArg
                                 MutationEvent.REMOVAL);
	    AbstractNode n = (AbstractNode)node;
	    n.dispatchEvent(ev);
	    n.fireDOMNodeRemovedFromDocumentEvent();
	}
    }

    /**
     * Checks the validity of a node to be inserted, and removes it from
     * the document if needed.
     */
    protected void checkAndRemove(Node n, boolean replace) {
	checkChildType(n, replace);
	if (isReadonly()) {
	    throw createDOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR,
				     "readonly.node",
				     new Object[] { new Integer(getNodeType()),
						    getNodeName() });
	}
	if (n.getOwnerDocument() != getCurrentDocument()) {
	    throw createDOMException(DOMException.WRONG_DOCUMENT_ERR,
				     "node.from.wrong.document",
				     new Object[] { new Integer(getNodeType()),
						    getNodeName() });
	}
	for (Node pn = getParentNode(); pn != null; pn = pn.getParentNode()) {
	    if (pn == n) {
		throw createDOMException
                    (DOMException.WRONG_DOCUMENT_ERR,
                     "add.ancestor",
                     new Object[] { new Integer(getNodeType()),
                                    getNodeName() });
	    }
	}

	// Remove the node from the tree
	Node np = n.getParentNode();
	if (np != null) {
	    np.removeChild(n);
	}
    }

    /**
     * To manage a list of nodes.
     */
    protected class ElementsByTagName implements NodeList {

	/**
	 * The table.
	 */
	protected Node[] table;

	/**
	 * The number of nodes.
	 */
	protected int size = -1;

        /**
         * The name identifier.
         */
        protected String name;

	/**
	 * Creates a new ElementsByTagName object.
	 */
	public ElementsByTagName(String n) {
            name = n;
	}

	/**
	 * <b>DOM</b>: Implements {@link NodeList#item(int)}.
	 */
	public Node item(int index) {
            if (size == -1) {
                initialize();
            }
	    if (table == null || index < 0 || index >= size) {
		return null;
	    }
	    return table[index];
	}

	/**
	 * <b>DOM</b>: Implements {@link NodeList#getLength()}.
	 * @return {@link #size}.
	 */
	public int getLength() {
            if (size == -1) {
                initialize();
            }
	    return size;
	}

        /**
         * Invalidates the list.
         */
        public void invalidate() {
            size = -1;
        }

	/**
	 * Appends a node to the list.
	 */
	protected void append(Node n) {
	    if (table == null) {
		table = new Node[11];
	    } else if (size == table.length - 1) {
		Node[] t = new Node[table.length * 2 + 1];
		for (int i = 0; i < size; i++) {
		    t[i] = table[i];
		}
		table = t;
	    }
	    table[size++] = n;
	}

        /**
         * Initializes the list.
         */
        protected void initialize() {
            size = 0;
            for (Node n = AbstractParentNode.this.getFirstChild();
                 n != null;
                 n = n.getNextSibling()) {
                initialize(n);
            }
        }

        private void initialize(Node node) {
            if (node.getNodeType() == ELEMENT_NODE) {
                String nm = node.getNodeName();
                if (name.equals("*") || name.equals(nm)) {
                    append(node);
                }
            }
            for (Node n = node.getFirstChild();
                 n != null;
                 n = n.getNextSibling()) {
                initialize(n);
            }
        } 
    }

    /**
     * To manage a list of nodes.
     */
    protected class ElementsByTagNameNS implements NodeList {

	/**
	 * The table.
	 */
	protected Node[] table;

	/**
	 * The number of nodes.
	 */
	protected int size = -1;

        /**
         * The namespace URI identifier.
         */
        protected String namespaceURI;

        /**
         * The local name identifier.
         */
        protected String localName;

	/**
	 * Creates a new ElementsByTagNameNS object.
	 */
	public ElementsByTagNameNS(String ns, String ln) {
            namespaceURI = ns;
            localName = ln;
	}

	/**
	 * <b>DOM</b>: Implements {@link NodeList#item(int)}.
	 */
	public Node item(int index) {
            if (size == -1) {
                initialize();
            }
	    if (table == null || index < 0 || index > size) {
		return null;
	    }
	    return table[index];
	}

	/**
	 * <b>DOM</b>: Implements {@link NodeList#getLength()}.
	 * @return {@link #size}.
	 */
	public int getLength() {
            if (size == -1) {
                initialize();
            }
	    return size;
	}

        /**
         * Invalidates the list.
         */
        public void invalidate() {
            size = -1;
        }

	/**
	 * Appends a node to the list.
	 */
	protected void append(Node n) {
	    if (table == null) {
		table = new Node[11];
	    } else if (size == table.length - 1) {
		Node[] t = new Node[table.length * 2 + 1];
		for (int i = 0; i < size; i++) {
		    t[i] = table[i];
		}
		table = t;
	    }
	    table[size++] = n;
	}

        /**
         * Initializes the list.
         */
        protected void initialize() {
            size = 0;
            for (Node n = AbstractParentNode.this.getFirstChild();
                 n != null;
                 n = n.getNextSibling()) {
                initialize(n);
            }
        }

        private void initialize(Node node) {
            if (node.getNodeType() == ELEMENT_NODE) {
                String ns = node.getNamespaceURI();
                String nm = (ns == null)
                    ? node.getNodeName()
                    : node.getLocalName();
                if (nsMatch(namespaceURI, node.getNamespaceURI()) &&
                    (localName.equals("*") || localName.equals(nm))) {
                    append(node);
                }
            }
            for (Node n = node.getFirstChild();
                 n != null;
                 n = n.getNextSibling()) {
                initialize(n);
            }
        } 

        private boolean nsMatch(String s1, String s2) {
            if (s1 == null && s2 == null) {
                return true;
            }
            if (s1 == null || s2 == null) {
                return false;
            }
            if (s1.equals("*")) {
                return true;
            }
            return s1.equals(s2);
        }
    }

    /**
     * To manage the children of this node.
     */
    protected class ChildNodes implements NodeList, Serializable {
	/**
	 * The first child.
	 */
	protected ExtendedNode firstChild;

	/**
	 * The last child.
	 */
	protected ExtendedNode lastChild;

	/**
	 * The number of children.
	 */
	protected int children;

	/**
	 * Creates a new ChildNodes object.
	 */
	public ChildNodes() {
	}

	/**
	 * <b>DOM</b>: Implements {@link org.w3c.dom.NodeList#item(int)}.
	 */
	public Node item(int index) {
	    if (index < 0 || index >= children) {
		return null;
	    }
	    if (index < (children >> 1)) {
		Node n = firstChild;
		for (int i = 0; i < index; i++) {
		    n = n.getNextSibling();
		}
		return n;
	    } else {
		Node n = lastChild;
		for (int i = children - 1; i > index; i--) {
		    n = n.getPreviousSibling();
		}
		return n;
	    }
	}

	/**
	 * <b>DOM</b>: Implements {@link org.w3c.dom.NodeList#getLength()}.
	 * @return {@link #children}.
	 */
	public int getLength() {
	    return children;
	}

	/**
	 * Appends a node to the tree.
	 * The node is assumed not to be a DocumentFragment instance.
	 */
	public ExtendedNode append(ExtendedNode n) {
	    if (lastChild == null) {
		firstChild = n;
		lastChild  = n;
		children++;
		return n;
	    }
	    lastChild.setNextSibling(n);
	    n.setPreviousSibling(lastChild);
	    lastChild = n;
	    children++;
	    return n;
	}

	/**
	 * Inserts a node in the tree.
	 */
	public ExtendedNode insert(ExtendedNode n, ExtendedNode r) {
	    if (r == null) {
		return append(n);
	    }

	    if (r == firstChild) {
		firstChild.setPreviousSibling(n);
		n.setNextSibling(firstChild);
		firstChild = n;
		children++;
		return n;
	    }
	    if (r == lastChild) {
                ExtendedNode ps = (ExtendedNode)r.getPreviousSibling();
                ps.setNextSibling(n);
                r.setPreviousSibling(n);
                n.setNextSibling(r);
                n.setPreviousSibling(ps);
                children++;
                return n;
	    }

            ExtendedNode ps = (ExtendedNode)r.getPreviousSibling();
            if ((ps.getNextSibling() == r) &&
                (ps.getParentNode() == r.getParentNode())) {
                ps.setNextSibling(n);
                n.setPreviousSibling(ps);
                n.setNextSibling(r);
                r.setPreviousSibling(n);
                children++;
                return n;
            }

	    throw createDOMException
		(DOMException.NOT_FOUND_ERR,
		 "child.missing",
		 new Object[] { new Integer(r.getNodeType()),
				r.getNodeName() });
	}

	/**
	 * Replaces a node in the tree by an other.
	 */
	public ExtendedNode replace(ExtendedNode n, ExtendedNode o) {
	    if (o == firstChild) {
                ExtendedNode t = (ExtendedNode)firstChild.getNextSibling();
		n.setNextSibling(t);
                if (o == lastChild) {
                    lastChild = n;
                } else {
                    t.setPreviousSibling(n);
                }
		firstChild.setNextSibling(null);
		firstChild = n;
		return o;
	    }

	    if (o == lastChild) {
                ExtendedNode t = (ExtendedNode)lastChild.getPreviousSibling();
		n.setPreviousSibling(t);
                t.setNextSibling(n);
		lastChild.setPreviousSibling(null);
		lastChild = n;
		return o;
	    }

            ExtendedNode ps = (ExtendedNode)o.getPreviousSibling();
            ExtendedNode ns = (ExtendedNode)o.getNextSibling();
            if ((ps.getNextSibling()     == o) &&
                (ns.getPreviousSibling() == o) &&
                (ps.getParentNode()      == o.getParentNode()) &&
                (ns.getParentNode()      == o.getParentNode())) {

                ps.setNextSibling(n);
                n.setPreviousSibling(ps);
                n.setNextSibling(ns);
                ns.setPreviousSibling(n);
                o.setPreviousSibling(null);
                o.setNextSibling(null);
                return o;
            }
	    throw createDOMException
		(DOMException.NOT_FOUND_ERR,
		 "child.missing",
		 new Object[] { new Integer(o.getNodeType()),
				o.getNodeName() });
	}

        /**
	 * Removes the given node from the tree.
	 */
        public ExtendedNode remove(ExtendedNode n) {
	    if (n == firstChild) {
		if (n == lastChild) {
		    firstChild = null;
		    lastChild  = null;
		    children--;
		    return n;
		}
		firstChild = (ExtendedNode)firstChild.getNextSibling();
		firstChild.setPreviousSibling(null);
		n.setNextSibling(null);
		children--;
		return n;
	    }

	    if (n == lastChild) {
		lastChild = (ExtendedNode)lastChild.getPreviousSibling();
		lastChild.setNextSibling(null);
		n.setPreviousSibling(null);
		children--;
		return n;
	    }

            ExtendedNode ps = (ExtendedNode)n.getPreviousSibling();
            ExtendedNode ns = (ExtendedNode)n.getNextSibling();
            if ((ps.getNextSibling()     == n) &&
                (ns.getPreviousSibling() == n) &&
                (ps.getParentNode()      == n.getParentNode()) &&
                (ns.getParentNode()      == n.getParentNode())) {
                ps.setNextSibling(ns);
                ns.setPreviousSibling(ps);
                n.setPreviousSibling(null);
                n.setNextSibling(null);
                children--;
                return n;
            }
	    throw createDOMException
		(DOMException.NOT_FOUND_ERR,
		 "child.missing",
		 new Object[] { new Integer(n.getNodeType()),
				n.getNodeName() });
	}
    }
}
