/*****************************************************************************
 * Copyright (C) The Apache Software Foundation. All rights reserved.        *
 * ------------------------------------------------------------------------- *
 * This software is published under the terms of the Apache Software License *
 * version 1.1, a copy of which has been included with this distribution in  *
 * the LICENSE file.                                                         *
 *****************************************************************************/

package org.apache.batik.dom;

import java.io.Serializable;

import org.apache.batik.dom.util.DOMUtilities;
import org.w3c.dom.Attr;
import org.w3c.dom.DOMException;
import org.w3c.dom.Element;
import org.w3c.dom.NamedNodeMap;
import org.w3c.dom.Node;
import org.w3c.dom.events.DocumentEvent;
import org.w3c.dom.events.MutationEvent;

/**
 * This class implements the {@link org.w3c.dom.Element} interface.
 *
 * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
 * @version $Id: AbstractElement.java,v 1.21 2003/06/30 12:36:45 vhardy Exp $
 */
public abstract class AbstractElement
    extends    AbstractParentChildNode
    implements Element {

    /**
     * The attributes of this element.
     */
    protected NamedNodeMap attributes;

    /**
     * Creates a new AbstractElement object.
     */
    protected AbstractElement() {
    }

    /**
     * Creates a new AbstractElement object.
     * @param name  The element name for validation purposes.
     * @param owner The owner document.
     * @exception DOMException
     *   INVALID_CHARACTER_ERR: if name contains invalid characters,
     */
    protected AbstractElement(String name, AbstractDocument owner) {
	ownerDocument = owner;
	if (!DOMUtilities.isValidName(name)) {
	    throw createDOMException(DOMException.INVALID_CHARACTER_ERR,
				     "xml.name",
				     new Object[] { name });
	}
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#getNodeType()}.
     * @return {@link org.w3c.dom.Node#ELEMENT_NODE}
     */
    public short getNodeType() {
	return ELEMENT_NODE;
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#hasAttributes()}.
     */
    public boolean hasAttributes() {
	return attributes != null && attributes.getLength() != 0;
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#getAttributes()}.
     */
    public NamedNodeMap getAttributes() {
	return (attributes == null)
            ? attributes = createAttributes()
            : attributes;
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Element#getTagName()}.
     * @return {@link #getNodeName()}.
     */
    public String getTagName() {
	return getNodeName();
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Element#hasAttribute(String)}.
     */
    public boolean hasAttribute(String name) {
	return attributes != null && attributes.getNamedItem(name) != null;
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Element#getAttribute(String)}.
     */
    public String getAttribute(String name) {
	if (attributes == null) {
	    return "";
	}
	Attr attr = (Attr)attributes.getNamedItem(name);
	return (attr == null) ? "" : attr.getValue();
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#setAttribute(String,String)}.
     */
    public void setAttribute(String name, String value) throws DOMException {
	if (attributes == null) {
	    attributes = createAttributes();
	}
        Attr attr = getAttributeNode(name);
        if (attr == null) {
            attr = getOwnerDocument().createAttribute(name);
            attr.setValue(value);
            attributes.setNamedItem(attr);
        } else {
            attr.setValue(value);
        }
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#removeAttribute(String)}.
     */
    public void removeAttribute(String name) throws DOMException {
	if (!hasAttribute(name)) {
            return;
	}
	attributes.removeNamedItem(name);
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#getAttributeNode(String)}.
     */
    public Attr getAttributeNode(String name) {
	if (attributes == null) {
	    return null;
	}
	return (Attr)attributes.getNamedItem(name);
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#setAttributeNode(Attr)}.
     */
    public Attr setAttributeNode(Attr newAttr) throws DOMException {
	if (newAttr == null) {
	    return null;
	}
	if (attributes == null) {
	    attributes = createAttributes();
	}
	return (Attr)attributes.setNamedItemNS(newAttr);
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#removeAttributeNode(Attr)}.
     */
    public Attr removeAttributeNode(Attr oldAttr) throws DOMException {
	if (oldAttr == null) {
	    return null;
	}
	if (attributes == null) {
	    throw createDOMException(DOMException.NOT_FOUND_ERR,
				     "attribute.missing",
				     new Object[] { oldAttr.getName() });
	}
	return (Attr)attributes.removeNamedItemNS(oldAttr.getNamespaceURI(),
                                                  oldAttr.getLocalName());
    }

    /**
     * <b>DOM</b>: Implements {@link org.w3c.dom.Node#normalize()}.
     */
    public void normalize() {
	super.normalize();
	if (attributes != null) {
	    NamedNodeMap map = getAttributes();
	    for (int i = map.getLength() - 1; i >= 0; i--) {
		map.item(i).normalize();
	    }
	}
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#hasAttributeNS(String,String)}.
     */
    public boolean hasAttributeNS(String namespaceURI, String localName) {
	return attributes != null &&
	       attributes.getNamedItemNS(namespaceURI, localName) != null;
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#getAttributeNS(String,String)}.
     */
    public String getAttributeNS(String namespaceURI, String localName) {
	if (attributes == null) {
	    return "";
	}
	Attr attr = (Attr)attributes.getNamedItemNS(namespaceURI, localName);
	return (attr == null) ? "" : attr.getValue();
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#setAttributeNS(String,String,String)}.
     */
    public void setAttributeNS(String namespaceURI, 
			       String qualifiedName, 
			       String value) throws DOMException {
	if (attributes == null) {
	    attributes = createAttributes();
	}
        Attr attr = getAttributeNodeNS(namespaceURI, qualifiedName);
        if (attr == null) {
            attr = getOwnerDocument().createAttributeNS(namespaceURI,
                                                        qualifiedName);
            attr.setValue(value);
            attributes.setNamedItemNS(attr);
        } else {
            attr.setValue(value);
        }
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#removeAttributeNS(String,String)}.
     */
    public void removeAttributeNS(String namespaceURI, 
				  String localName) throws DOMException {
	if (!hasAttributeNS(namespaceURI, localName)) {
            return;
	}
	attributes.removeNamedItemNS(namespaceURI, localName);
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#getAttributeNodeNS(String,String)}.
     */
    public Attr getAttributeNodeNS(String namespaceURI, 
				   String localName) {
	if (attributes == null) {
	    return null;
	}
	return (Attr)attributes.getNamedItemNS(namespaceURI, localName);
    }

    /**
     * <b>DOM</b>: Implements {@link
     * org.w3c.dom.Element#setAttributeNodeNS(Attr)}.
     */
    public Attr setAttributeNodeNS(Attr newAttr) throws DOMException {
	if (newAttr == null) {
	    return null;
	}
	if (attributes == null) {
	    attributes = createAttributes();
	}
	return (Attr)attributes.setNamedItemNS(newAttr);
    }

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

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

    /**
     * Invalidates the ElementsByTagName objects of this node and its parents.
     */
    private void invalidateElementsByTagName(Node node) {
        if (node.getNodeType() != ELEMENT_NODE) {
            return;
        }
        AbstractDocument ad = getCurrentDocument();
        String ns = node.getNamespaceURI();
        String nm = node.getNodeName();
        String ln = (ns == null) ? node.getNodeName() : node.getLocalName();
        for (Node n = this; n != null; n = n.getParentNode()) {
            switch (n.getNodeType()) {
            case ELEMENT_NODE:
            case DOCUMENT_NODE:
                ElementsByTagName l = ad.getElementsByTagName(n, nm);
                if (l != null) {
                    l.invalidate();
                }
                l = ad.getElementsByTagName(n, "*");
                if (l != null) {
                    l.invalidate();
                }
                ElementsByTagNameNS lns = ad.getElementsByTagNameNS(n, ns, ln);

                if (lns != null) {
                    lns.invalidate();
                }
                lns = ad.getElementsByTagNameNS(n, "*", ln);
                if (lns != null) {
                    lns.invalidate();
                }
                lns = ad.getElementsByTagNameNS(n, ns, "*");
                if (lns != null) {
                    lns.invalidate();
                }
                lns = ad.getElementsByTagNameNS(n, "*", "*");
                if (lns != null) {
                    lns.invalidate();
                }
            }
        }

        //
        // Invalidate children
        //
        Node c = node.getFirstChild();
        while (c != null) {
            invalidateElementsByTagName(c);
            c = c.getNextSibling();
        }
            
    }

    /**
     * Creates the attribute list.
     */
    protected NamedNodeMap createAttributes() {
	return new NamedNodeHashMap();
    }

    /**
     * Exports this node to the given document.
     * @param n The clone node.
     * @param d The destination document.
     */
    protected Node export(Node n, AbstractDocument d) {
	super.export(n, d);
	AbstractElement ae = (AbstractElement)n;
	if (attributes != null) {
	    NamedNodeMap map = attributes;
	    for (int i = map.getLength() - 1; i >= 0; i--) {
		AbstractAttr aa = (AbstractAttr)map.item(i);
		if (aa.getSpecified()) {
		    Attr attr = (Attr)aa.deepExport(aa.cloneNode(false), d);
		    if (aa instanceof AbstractAttrNS) {
			ae.setAttributeNodeNS(attr);
		    } else {
			ae.setAttributeNode(attr);
		    }
		}
	    }
	}
	return n;
    }

    /**
     * Deeply exports this node to the given document.
     * @param n The clone node.
     * @param d The destination document.
     */
    protected Node deepExport(Node n, AbstractDocument d) {
	super.deepExport(n, d);
	AbstractElement ae = (AbstractElement)n;
	if (attributes != null) {
	    NamedNodeMap map = attributes;
	    for (int i = map.getLength() - 1; i >= 0; i--) {
		AbstractAttr aa = (AbstractAttr)map.item(i);
		if (aa.getSpecified()) {
		    Attr attr = (Attr)aa.deepExport(aa.cloneNode(false), d);
		    if (aa instanceof AbstractAttrNS) {
			ae.setAttributeNodeNS(attr);
		    } else {
			ae.setAttributeNode(attr);
		    }
		}
	    }
	}
	return n;
    }

    /**
     * Copy the fields of the current node into the given node.
     * @param n a node of the type of this.
     */
    protected Node copyInto(Node n) {
	super.copyInto(n);
	AbstractElement ae = (AbstractElement)n;
	if (attributes != null) {
	    NamedNodeMap map = attributes;
	    for (int i = map.getLength() - 1; i >= 0; i--) {
		AbstractAttr aa = (AbstractAttr)map.item(i).cloneNode(true);
		if (aa instanceof AbstractAttrNS) {
		    ae.setAttributeNodeNS(aa);
		} else {
		    ae.setAttributeNode(aa);
		}
	    }
	}
	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);
	AbstractElement ae = (AbstractElement)n;
	if (attributes != null) {
	    NamedNodeMap map = attributes;
	    for (int i = map.getLength() - 1; i >= 0; i--) {
		AbstractAttr aa = (AbstractAttr)map.item(i).cloneNode(true);
		if (aa instanceof AbstractAttrNS) {
		    ae.setAttributeNodeNS(aa);
		} else {
		    ae.setAttributeNode(aa);
		}
	    }
	}
	return n;
    }

    /**
     * Checks the validity of a node to be inserted.
     * @param n The node to be inserted.
     */
    protected void checkChildType(Node n, boolean replace) {
	switch (n.getNodeType()) {
	case ELEMENT_NODE:
	case PROCESSING_INSTRUCTION_NODE:
	case COMMENT_NODE:
	case TEXT_NODE:
	case CDATA_SECTION_NODE:
	case ENTITY_REFERENCE_NODE:
	case DOCUMENT_FRAGMENT_NODE:
	    break;
	default:
	    throw createDOMException
                (DOMException.HIERARCHY_REQUEST_ERR,
                 "child.type",
                 new Object[] { new Integer(getNodeType()),
                                getNodeName(),
                                new Integer(n.getNodeType()),
                                n.getNodeName() });
	}
    }

    /**
     * Fires a DOMAttrModified event.
     * <!> WARNING: public accessor because of compilation problems
     *     on Solaris. Do not change.
     *
     * @param name The attribute's name.
     * @param node The attribute's node.
     * @param oldv The old value of the attribute.
     * @param newv The new value of the attribute.
     * @param change The modification type.
     */
    public void fireDOMAttrModifiedEvent(String name, Attr node, String oldv,
                                         String newv, short change) {
        switch (change) {
        case MutationEvent.ADDITION:
            attrAdded(node, newv);
            break;

        case MutationEvent.MODIFICATION:
            attrModified(node, oldv, newv);
            break;

        default: // MutationEvent.REMOVAL:
            attrRemoved(node, oldv);
        }
	AbstractDocument doc = getCurrentDocument();
	if (doc.getEventsEnabled() && !oldv.equals(newv)) {
	    DocumentEvent de = (DocumentEvent)doc;
	    MutationEvent ev = (MutationEvent)de.createEvent("MutationEvents");
	    ev.initMutationEvent("DOMAttrModified",
				 true,    // canBubbleArg
				 false,   // cancelableArg
				 node,    // relatedNodeArg
				 oldv,    // prevValueArg
				 newv,    // newValueArg
				 name,    // attrNameArg
                                 change); // attrChange
	    dispatchEvent(ev);
	}
    }

    /**
     * Called when an attribute has been added.
     */
    protected void attrAdded(Attr node, String newv) {
    }

    /**
     * Called when an attribute has been modified.
     */
    protected void attrModified(Attr node, String oldv, String newv) {
    }

    /**
     * Called when an attribute has been removed.
     */
    protected void attrRemoved(Attr node, String oldv) {
    }

    /**
     * An implementation of the {@link org.w3c.dom.NamedNodeMap}.
     */
    public class NamedNodeHashMap implements NamedNodeMap, Serializable {

        /**
         * The initial capacity
         */
        protected final static int INITIAL_CAPACITY = 3;

        /**
         * The underlying array
         */
        protected Entry[] table;
	    
        /**
         * The number of entries
         */
        protected int count;
	    
	/**
	 * Creates a new NamedNodeHashMap object.
	 */
	public NamedNodeHashMap() {
            table = new Entry[INITIAL_CAPACITY];
	}

	/**
	 * <b>DOM</b>: Implements {@link
         * org.w3c.dom.NamedNodeMap#getNamedItem(String)}.
	 */
	public Node getNamedItem(String name) {
	    if (name == null) {
		return null;
	    }
	    return get(null, name);
	}

	/**
	 * <b>DOM</b>: Implements {@link
         * org.w3c.dom.NamedNodeMap#setNamedItem(Node)}.
	 */
	public Node setNamedItem(Node arg) throws DOMException {
	    if (arg == null) {
		return null;
	    }
	    checkNode(arg);

	    return setNamedItem(null, arg.getNodeName(), arg);
	}

	/**
	 * <b>DOM</b>: Implements {@link
	 * org.w3c.dom.NamedNodeMap#removeNamedItem(String)}.
	 */
	public Node removeNamedItem(String name) throws DOMException {
	    return removeNamedItemNS(null, name);
	}

	/**
	 * <b>DOM</b>: Implements {@link org.w3c.dom.NamedNodeMap#item(int)}.
	 */
	public Node item(int index) {
            if (index < 0 || index >= count) {
                return null;
            }
            int j = 0;
            for (int i = 0; i < table.length; i++) {
                Entry e = table[i];
                if (e == null) {
                    continue;
                }
                do {
                    if (j++ == index) {
                        return e.value;
                    }
                    e = e.next;
                } while (e != null);
            }
            return null;
	}

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

	/**
	 * <b>DOM</b>: Implements {@link
	 * org.w3c.dom.NamedNodeMap#getNamedItemNS(String,String)}.
	 */
	public Node getNamedItemNS(String namespaceURI, String localName) {
            return get(namespaceURI, localName);
	}

	/**
	 * <b>DOM</b>: Implements {@link
         * org.w3c.dom.NamedNodeMap#setNamedItemNS(Node)}.
	 */
	public Node setNamedItemNS(Node arg) throws DOMException {
	    if (arg == null) {
		return null;
	    }
	    String nsURI = arg.getNamespaceURI();
            return setNamedItem(nsURI,
                                (nsURI == null) 
                                ? arg.getNodeName()
                                : arg.getLocalName(), arg);
	}

	/**
	 * <b>DOM</b>: Implements {@link
	 * org.w3c.dom.NamedNodeMap#removeNamedItemNS(String,String)}.
	 */
	public Node removeNamedItemNS(String namespaceURI, String localName)
	    throws DOMException {
	    if (isReadonly()) {
		throw createDOMException
                    (DOMException.NO_MODIFICATION_ALLOWED_ERR,
                     "readonly.node.map",
                     new Object[] {});
	    }
	    if (localName == null) {
		throw createDOMException(DOMException.NOT_FOUND_ERR,
					 "attribute.missing",
					 new Object[] { "" });
	    }
	    AbstractAttr n = (AbstractAttr)remove(namespaceURI, localName);
	    if (n == null) {
		throw createDOMException(DOMException.NOT_FOUND_ERR,
					 "attribute.missing",
					 new Object[] { localName });
	    }
	    n.setOwnerElement(null);
	    
	    // Mutation event
	    fireDOMAttrModifiedEvent(n.getNodeName(), n, n.getNodeValue(), "",
                                     MutationEvent.REMOVAL);
	    return n;
	}

	/**
	 * Adds a node to the map.
 	 */
	public Node setNamedItem(String ns, String name, Node arg)
            throws DOMException {
	    ((AbstractAttr)arg).setOwnerElement(AbstractElement.this);
	    AbstractAttr result = (AbstractAttr)put(ns, name, arg);

	    if (result != null) {
		result.setOwnerElement(null);
		fireDOMAttrModifiedEvent(name,
                                         result,
					 result.getNodeValue(),
					 "",
                                         MutationEvent.REMOVAL);
	    }
            fireDOMAttrModifiedEvent(name,
                                     (Attr)arg,
                                     "",
                                     arg.getNodeValue(),
                                     MutationEvent.ADDITION);
	    return result;
	}

	/**
	 * Checks the validity of a node to add.
	 */
	protected void checkNode(Node arg) {
	    if (isReadonly()) {
		throw createDOMException
                    (DOMException.NO_MODIFICATION_ALLOWED_ERR,
                     "readonly.node.map",
                     new Object[] {});
	    }
	    if (getOwnerDocument() != arg.getOwnerDocument()) {
		throw createDOMException(DOMException.WRONG_DOCUMENT_ERR,
					 "node.from.wrong.document",
					 new Object[] { new Integer
                                                         (arg.getNodeType()),
		                                        arg.getNodeName() });
	    }
	    if (arg.getNodeType() == ATTRIBUTE_NODE &&
		((Attr)arg).getOwnerElement() != null) {
		throw createDOMException(DOMException.WRONG_DOCUMENT_ERR,
					 "inuse.attribute",
					 new Object[] { arg.getNodeName() });
	    }
	}

        /**
         * Gets the value of a variable
         * @return the value or null
         */
        protected Node get(String ns, String nm) {
            int hash  = hashCode(ns, nm) & 0x7FFFFFFF;
            int index = hash % table.length;
	
            for (Entry e = table[index]; e != null; e = e.next) {
                if ((e.hash == hash) && e.match(ns, nm)) {
                    return e.value;
                }
            }
            return null;
        }
    
        /**
         * Sets a new value for the given variable
         * @return the old value or null
         */
        protected Node put(String ns, String nm, Node value) {
            int hash  = hashCode(ns, nm) & 0x7FFFFFFF;
            int index = hash % table.length;
	
            for (Entry e = table[index]; e != null; e = e.next) {
                if ((e.hash == hash) && e.match(ns, nm)) {
                    Node old = e.value;
                    e.value = value;
                    return old;
                }
            }
	
            // The key is not in the hash table
            int len = table.length;
            if (count++ >= (len * 3) >>> 2) {
                rehash();
                index = hash % table.length;
            }
            
            Entry e = new Entry(hash, ns, nm, value, table[index]);
            table[index] = e;
            return null;
        }

        /**
         * Removes an entry from the table.
         * @return the value or null.
         */
        protected Node remove(String ns, String nm) {
            int hash  = hashCode(ns, nm) & 0x7FFFFFFF;
            int index = hash % table.length;
	
            Entry p = null;
            for (Entry e = table[index]; e != null; e = e.next) {
                if ((e.hash == hash) && e.match(ns, nm)) {
                    Node result = e.value;
                    if (p == null) {
                        table[index] = e.next;
                    } else {
                        p.next = e.next;
                    }
                    count--;
                    return result;
                }
                p = e;
            }
            return null;
        }

        /**
         * Rehash the table
         */
        protected void rehash () {
            Entry[] oldTable = table;
	
            table = new Entry[oldTable.length * 2 + 1];
	
            for (int i = oldTable.length-1; i >= 0; i--) {
                for (Entry old = oldTable[i]; old != null;) {
                    Entry e = old;
                    old = old.next;
                    
                    int index = e.hash % table.length;
                    e.next = table[index];
                    table[index] = e;
                }
            }
        }

        /**
         * Computes a hash code corresponding to the given strings. 
         */
        protected int hashCode(String ns, String nm) {
            int result = (ns == null) ? 0 : ns.hashCode();
            return result ^ nm.hashCode();
        }
    }

    /**
     * To manage collisions in the attributes map.
     */
    protected static class Entry implements Serializable {

        /**
         * The hash code
         */
        public int hash;
	
        /**
         * The namespace URI
         */
        public String namespaceURI;
	
        /**
         * The node name.
         */
        public String name;
        
        /**
         * The value
         */
        public Node value;
	
        /**
         * The next entry
         */
        public Entry next;
	
        /**
         * Creates a new entry
         */
        public Entry(int hash, String ns, String nm, Node value, Entry next) {
            this.hash = hash;
            this.namespaceURI = ns;
            this.name = nm;
            this.value = value;
            this.next = next;
        }
        
        /**
         * Whether this entry match the given keys.
         */
        public boolean match(String ns, String nm) {
            if (namespaceURI != null) {
                if (!namespaceURI.equals(ns)) {
                    return false;
                }
            } else if (ns != null) {
                return false;
            }
            return name.equals(nm);
        }
    }

}
