/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.xerces.dom;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

import org.w3c.dom.DOMException;
import org.w3c.dom.NamedNodeMap;
import org.w3c.dom.Node;

NamedNodeMaps represent collections of Nodes that can be accessed
by name. Entity and Notation nodes are stored in NamedNodeMaps
attached to the DocumentType. Attributes are placed in a NamedNodeMap
attached to the elem they're related too. However, because attributes
require more work, such as firing mutation events, they are stored in
a subclass of NamedNodeMapImpl.

Only one Node may be stored per name; attempting to
store another will replace the previous value.

NOTE: The "primary" storage key is taken from the NodeName attribute of the
node. The "secondary" storage key is the namespaceURI and localName, when
accessed by DOM level 2 nodes. All nodes, even DOM Level 2 nodes are stored
in a single ArrayList sorted by the primary "nodename" key.

NOTE: item()'s integer index does _not_ imply that the named nodes
must be stored in an array; that's only an access method. Note too
that these indices are "live"; if someone changes the map's
contents, the indices associated with nodes may change.

@xerces.internal
Version:
$Id: NamedNodeMapImpl.java 1829683 2018-04-21 03:09:46Z mukulg $
Since:
 PR-DOM-Level-1-19980818./**
 * NamedNodeMaps represent collections of Nodes that can be accessed
 * by name. Entity and Notation nodes are stored in NamedNodeMaps
 * attached to the DocumentType. Attributes are placed in a NamedNodeMap
 * attached to the elem they're related too. However, because attributes
 * require more work, such as firing mutation events, they are stored in
 * a subclass of NamedNodeMapImpl.
 * <P>
 * Only one Node may be stored per name; attempting to
 * store another will replace the previous value.
 * <P>
 * NOTE: The "primary" storage key is taken from the NodeName attribute of the
 * node. The "secondary" storage key is the namespaceURI and localName, when
 * accessed by DOM level 2 nodes. All nodes, even DOM Level 2 nodes are stored
 * in a single ArrayList sorted by the primary "nodename" key.
 * <P>
 * NOTE: item()'s integer index does _not_ imply that the named nodes
 * must be stored in an array; that's only an access method. Note too
 * that these indices are "live"; if someone changes the map's
 * contents, the indices associated with nodes may change.
 * <P>
 *
 * @xerces.internal

 *
 * @version $Id: NamedNodeMapImpl.java 1829683 2018-04-21 03:09:46Z mukulg $
 * @since  PR-DOM-Level-1-19980818.
 */
public class NamedNodeMapImpl
    implements NamedNodeMap, Serializable {

    //
    // Constants
    //

    
Serialization version. /** Serialization version. */
    static final long serialVersionUID = -7039242451046758020L;

    //
    // Data
    //

    protected short flags;

    protected final static short READONLY     = 0x1<<0;
    protected final static short CHANGED      = 0x1<<1;
    protected final static short HASDEFAULTS  = 0x1<<2;

    
Nodes. /** Nodes. */
    protected List nodes;

    protected NodeImpl ownerNode; // the node this map belongs to

    //
    // Constructors
    //

    
Constructs a named node map. /** Constructs a named node map. */
    protected NamedNodeMapImpl(NodeImpl ownerNode) {
        this.ownerNode = ownerNode;
    }

    //
    // NamedNodeMap methods
    //

    
Report how many nodes are currently stored in this NamedNodeMap.
Caveat: This is a count rather than an index, so the
highest-numbered node at any time can be accessed via
item(getLength()-1).
/**
     * Report how many nodes are currently stored in this NamedNodeMap.
     * Caveat: This is a count rather than an index, so the
     * highest-numbered node at any time can be accessed via
     * item(getLength()-1).
     */
    public int getLength() {
    	return (nodes != null) ? nodes.size() : 0;
    }

    
Retrieve an item from the map by 0-based index.
Params:
index – Which item to retrieve. Note that indices are just an
enumeration of the current contents; they aren't guaranteed to be
stable, nor do they imply any promises about the order of the
NamedNodeMap's contents. In other words, DO NOT assume either that
index(i) will always refer to the same entry, or that there is any
stable ordering of entries... and be prepared for double-reporting
or skips as insertion and deletion occur.
Returns:
the node which currenly has the specified index, or null if index
is greater than or equal to getLength()./**
     * Retrieve an item from the map by 0-based index.
     *
     * @param index Which item to retrieve. Note that indices are just an
     * enumeration of the current contents; they aren't guaranteed to be
     * stable, nor do they imply any promises about the order of the
     * NamedNodeMap's contents. In other words, DO NOT assume either that
     * index(i) will always refer to the same entry, or that there is any
     * stable ordering of entries... and be prepared for double-reporting
     * or skips as insertion and deletion occur.
     *
     * @return the node which currenly has the specified index, or null if index
     * is greater than or equal to getLength().
     */
    public Node item(int index) {
    	return (nodes != null && index < nodes.size()) ?
                    (Node)(nodes.get(index)) : null;
    }

    
Retrieve a node by name.
Params:
name – Name of a node to look up.
Returns:
the Node (of unspecified sub-class) stored with that name, or
null if no value has been assigned to that name./**
     * Retrieve a node by name.
     *
     * @param name Name of a node to look up.
     * @return the Node (of unspecified sub-class) stored with that name, or
     * null if no value has been assigned to that name.
     */
    public Node getNamedItem(String name) {

    	int i = findNamePoint(name,0);
        return (i < 0) ? null : (Node)(nodes.get(i));

    } // getNamedItem(String):Node

    
Introduced in DOM Level 2. 

Retrieves a node specified by local name and namespace URI.
Params:
namespaceURI –  The namespace URI of the node to retrieve.
                     When it is null or an empty string, this
                     method behaves like getNamedItem.
localName –     The local name of the node to retrieve.
Returns:
Node         A Node (of any type) with the specified name, or null if the specified
                     name did not identify any node in the map./**
     * Introduced in DOM Level 2. <p>
     * Retrieves a node specified by local name and namespace URI.
     *
     * @param namespaceURI  The namespace URI of the node to retrieve.
     *                      When it is null or an empty string, this
     *                      method behaves like getNamedItem.
     * @param localName     The local name of the node to retrieve.
     * @return Node         A Node (of any type) with the specified name, or null if the specified
     *                      name did not identify any node in the map.
     */
    public Node getNamedItemNS(String namespaceURI, String localName) {

    	int i = findNamePoint(namespaceURI, localName);
        return (i < 0) ? null : (Node)(nodes.get(i));

    } // getNamedItemNS(String,String):Node

    
Adds a node using its nodeName attribute.
As the nodeName attribute is used to derive the name which the node must be
stored under, multiple nodes of certain types (those that have a "special" string
value) cannot be stored as the names would clash. This is seen as preferable to
allowing nodes to be aliased.
Params:
arg – 
     A node to store in a named node map. The node will later be
     accessible using the value of the namespaceURI and localName
     attribute of the node. If a node with those namespace URI and
     local name is already present in the map, it is replaced by the new
     one.
Throws:
DOMException – The exception description.
See Also:
setNamedItem.setNamedItem
Returns:
If the new Node replaces an existing node the replaced Node is returned,
     otherwise null is returned./**
     * Adds a node using its nodeName attribute.
     * As the nodeName attribute is used to derive the name which the node must be
     * stored under, multiple nodes of certain types (those that have a "special" string
     * value) cannot be stored as the names would clash. This is seen as preferable to
     * allowing nodes to be aliased.
     * @see org.w3c.dom.NamedNodeMap#setNamedItem
     * @return If the new Node replaces an existing node the replaced Node is returned,
     *      otherwise null is returned. 
     * @param arg 
     *      A node to store in a named node map. The node will later be
     *      accessible using the value of the namespaceURI and localName
     *      attribute of the node. If a node with those namespace URI and
     *      local name is already present in the map, it is replaced by the new
     *      one.
     * @exception org.w3c.dom.DOMException The exception description.
     */
    public Node setNamedItem(Node arg)
    throws DOMException {
        
        CoreDocumentImpl ownerDocument = ownerNode.ownerDocument();
        if (ownerDocument.errorChecking) {
            if (isReadOnly()) {
                String msg = DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NO_MODIFICATION_ALLOWED_ERR", null);
                throw new DOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR, msg);
            }
            if (arg.getOwnerDocument() != ownerDocument) {
                String msg = DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null);
                throw new DOMException(DOMException.WRONG_DOCUMENT_ERR, msg);
            }
        }
        
        int i = findNamePoint(arg.getNodeName(),0);
        NodeImpl previous = null;
        if (i >= 0) {
            previous = (NodeImpl) nodes.get(i);
            nodes.set(i, arg);
        } else {
            i = -1 - i; // Insert point (may be end of list)
            if (null == nodes) {
                nodes = new ArrayList(5);
            }
            nodes.add(i, arg);
        }
        return previous;
        
    } // setNamedItem(Node):Node

    
Adds a node using its namespaceURI and localName.
Params:
arg – A node to store in a named node map. The node will later be
     accessible using the value of the namespaceURI and localName
     attribute of the node. If a node with those namespace URI and
     local name is already present in the map, it is replaced by the new
     one.
See Also:
setNamedItem.setNamedItem
Returns:
If the new Node replaces an existing node the replaced Node is returned,
     otherwise null is returned./**
     * Adds a node using its namespaceURI and localName.
     * @see org.w3c.dom.NamedNodeMap#setNamedItem
     * @return If the new Node replaces an existing node the replaced Node is returned,
     *      otherwise null is returned. 
     * @param arg A node to store in a named node map. The node will later be
     *      accessible using the value of the namespaceURI and localName
     *      attribute of the node. If a node with those namespace URI and
     *      local name is already present in the map, it is replaced by the new
     *      one.
     */
    public Node setNamedItemNS(Node arg)
    throws DOMException {
        
        CoreDocumentImpl ownerDocument = ownerNode.ownerDocument();
        if (ownerDocument.errorChecking) {
            if (isReadOnly()) {
                String msg = DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NO_MODIFICATION_ALLOWED_ERR", null);
                throw new DOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR, msg);
            }
            
            if(arg.getOwnerDocument() != ownerDocument) {
                String msg = DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null);
                throw new DOMException(DOMException.WRONG_DOCUMENT_ERR, msg);
            }
        }
        
        int i = findNamePoint(arg.getNamespaceURI(), arg.getLocalName());
        NodeImpl previous = null;
        if (i >= 0) {
            previous = (NodeImpl) nodes.get(i);
            nodes.set(i, arg);
        } else {
            // If we can't find by namespaceURI, localName, then we find by
            // nodeName so we know where to insert.
            i = findNamePoint(arg.getNodeName(),0);
            if (i >= 0) {
                previous = (NodeImpl) nodes.get(i);
                nodes.add(i, arg);
            } else {
                i = -1 - i; // Insert point (may be end of list)
                if (null == nodes) {
                    nodes = new ArrayList(5);
                }
                nodes.add(i, arg);
            }
        }
        return previous;
        
    } // setNamedItemNS(Node):Node
   
    /**
     * Removes a node specified by name.
     * @param name The name of a node to remove.
     * @return The node removed from the map if a node with such a name exists.
     */
    /***/
    public Node removeNamedItem(String name)
        throws DOMException {

    	if (isReadOnly()) {
            String msg = DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NO_MODIFICATION_ALLOWED_ERR", null);
            throw
                new DOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR,
                msg);
        }
    	int i = findNamePoint(name,0);
    	if (i < 0) {
            String msg = DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NOT_FOUND_ERR", null);
            throw new DOMException(DOMException.NOT_FOUND_ERR, msg);
        }

        NodeImpl n = (NodeImpl)nodes.get(i);
        nodes.remove(i);

        return n;

    } // removeNamedItem(String):Node
    
    
Introduced in DOM Level 2. 

Removes a node specified by local name and namespace URI.
Params:
namespaceURI – 
                     The namespace URI of the node to remove.
                     When it is null or an empty string, this
                     method behaves like removeNamedItem.
name –          The local name of the node to remove.
Throws:
NOT_FOUND_ERR – : Raised if there is no node named
                     name in the map.
Returns:
Node         The node removed from the map if a node with such
                     a local name and namespace URI exists./**
     * Introduced in DOM Level 2. <p>
     * Removes a node specified by local name and namespace URI.
     * @param namespaceURI
     *                      The namespace URI of the node to remove.
     *                      When it is null or an empty string, this
     *                      method behaves like removeNamedItem.
     * @param name          The local name of the node to remove.
     * @return Node         The node removed from the map if a node with such
     *                      a local name and namespace URI exists.
     * @throws              NOT_FOUND_ERR: Raised if there is no node named
     *                      name in the map.

     */
     public Node removeNamedItemNS(String namespaceURI, String name)
        throws DOMException {

    	if (isReadOnly()) {
            String msg = DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NO_MODIFICATION_ALLOWED_ERR", null);
            throw
                new DOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR,
                msg);
        }
    	int i = findNamePoint(namespaceURI, name);
    	if (i < 0) {
            String msg = DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NOT_FOUND_ERR", null);
            throw new DOMException(DOMException.NOT_FOUND_ERR, msg);
        }

        NodeImpl n = (NodeImpl)nodes.get(i);
        nodes.remove(i);

        return n;

    } // removeNamedItem(String):Node

    //
    // Public methods
    //

    
Cloning a NamedNodeMap is a DEEP OPERATION; it always clones
all the nodes contained in the map.
/**
     * Cloning a NamedNodeMap is a DEEP OPERATION; it always clones
     * all the nodes contained in the map.
     */
     
    public NamedNodeMapImpl cloneMap(NodeImpl ownerNode) {
    	NamedNodeMapImpl newmap = new NamedNodeMapImpl(ownerNode);
        newmap.cloneContent(this);
    	return newmap;
    }

    protected void cloneContent(NamedNodeMapImpl srcmap) {
        List srcnodes = srcmap.nodes;
        if (srcnodes != null) {
            int size = srcnodes.size();
            if (size != 0) {
                if (nodes == null) {
                    nodes = new ArrayList(size);
                }
                else {
                    nodes.clear();
                }
                for (int i = 0; i < size; ++i) {
                    NodeImpl n = (NodeImpl) srcmap.nodes.get(i);
                    NodeImpl clone = (NodeImpl) n.cloneNode(true);
                    clone.isSpecified(n.isSpecified());
                    nodes.add(clone);
                }
            }
        }
    } // cloneMap():NamedNodeMapImpl

    //
    // Package methods
    //

    
Internal subroutine to allow read-only Nodes to make their contained
NamedNodeMaps readonly too. I expect that in fact the shallow
version of this operation will never be
Params:
readOnly – boolean true to make read-only, false to permit editing.
deep – boolean true to pass this request along to the contained
nodes, false to only toggle the NamedNodeMap itself. I expect that
the shallow version of this operation will never be used, but I want
to design it in now, while I'm thinking about it./**
     * Internal subroutine to allow read-only Nodes to make their contained
     * NamedNodeMaps readonly too. I expect that in fact the shallow
     * version of this operation will never be
     *
     * @param readOnly boolean true to make read-only, false to permit editing.
     * @param deep boolean true to pass this request along to the contained
     * nodes, false to only toggle the NamedNodeMap itself. I expect that
     * the shallow version of this operation will never be used, but I want
     * to design it in now, while I'm thinking about it.
     */
    void setReadOnly(boolean readOnly, boolean deep) {
        isReadOnly(readOnly);
    	if (deep && nodes != null) {
            for (int i = nodes.size() - 1; i >= 0; i--) {
                ((NodeImpl) nodes.get(i)).setReadOnly(readOnly,deep);
            }
    	}
    } // setReadOnly(boolean,boolean)
    
    
Internal subroutine returns this NodeNameMap's (shallow) readOnly value.
/**
     * Internal subroutine returns this NodeNameMap's (shallow) readOnly value.
     *
     */
    boolean getReadOnly() {
    	return isReadOnly();
    } // getReadOnly()
    

    //
    // Protected methods
    //

    
NON-DOM
set the ownerDocument of this node, and the attributes it contains
/**
     * NON-DOM
     * set the ownerDocument of this node, and the attributes it contains
     */
    protected void setOwnerDocument(CoreDocumentImpl doc) {
        if (nodes != null) {
            final int size = nodes.size();
            for (int i = 0; i < size; ++i) {
                ((NodeImpl)item(i)).setOwnerDocument(doc);
            }
        }
    }

    final boolean isReadOnly() {
        return (flags & READONLY) != 0;
    }

    final void isReadOnly(boolean value) {
        flags = (short) (value ? flags | READONLY : flags & ~READONLY);
    }

    final boolean changed() {
        return (flags & CHANGED) != 0;
    }

    final void changed(boolean value) {
        flags = (short) (value ? flags | CHANGED : flags & ~CHANGED);
    }

    final boolean hasDefaults() {
        return (flags & HASDEFAULTS) != 0;
    }

    final void hasDefaults(boolean value) {
        flags = (short) (value ? flags | HASDEFAULTS : flags & ~HASDEFAULTS);
    }

    //
    // Private methods
    //

    
Subroutine: Locate the named item, or the point at which said item
should be added. 
Params:
name – Name of a node to look up.
Returns:
If positive or zero, the index of the found item.
If negative, index of the appropriate point at which to insert
the item, encoded as -1-index and hence reconvertable by subtracting
it from -1. (Encoding because I don't want to recompare the strings
but don't want to burn bytes on a datatype to hold a flagged value.)/**
     * Subroutine: Locate the named item, or the point at which said item
     * should be added. 
     *
     * @param name Name of a node to look up.
     *
     * @return If positive or zero, the index of the found item.
     * If negative, index of the appropriate point at which to insert
     * the item, encoded as -1-index and hence reconvertable by subtracting
     * it from -1. (Encoding because I don't want to recompare the strings
     * but don't want to burn bytes on a datatype to hold a flagged value.)
     */
    protected int findNamePoint(String name, int start) {

    	// Binary search
    	int i = 0;
    	if (nodes != null) {
            int first = start;
            int last  = nodes.size() - 1;

            while (first <= last) {
                i = (first + last) / 2;
                int test = name.compareTo(((Node)(nodes.get(i))).getNodeName());
                if (test == 0) {
                    return i; // Name found
                }
                else if (test < 0) {
                    last = i - 1;
                }
                else {
                    first = i + 1;
                }
            }

            if (first > i) {
                i = first;
            }
    	}

    	return -1 - i; // not-found has to be encoded.

    } // findNamePoint(String):int

    
    
This findNamePoint is for DOM Level 2 Namespaces.
/** This findNamePoint is for DOM Level 2 Namespaces.
     */
    protected int findNamePoint(String namespaceURI, String name) {
        
        if (nodes == null) return -1;
        if (name == null) return -1;
        
        // This is a linear search through the same nodes ArrayList.
        // The ArrayList is sorted on the DOM Level 1 nodename.
        // The DOM Level 2 NS keys are namespaceURI and Localname, 
        // so we must linear search thru it.
        // In addition, to get this to work with nodes without any namespace
        // (namespaceURI and localNames are both null) we then use the nodeName
        // as a secondary key.
        final int size = nodes.size();
        for (int i = 0; i < size; ++i) {
            NodeImpl a = (NodeImpl)nodes.get(i);
            String aNamespaceURI = a.getNamespaceURI();
            String aLocalName = a.getLocalName();
            if (namespaceURI == null) {
              if (aNamespaceURI == null
                  &&
                  (name.equals(aLocalName)
                   ||
                   (aLocalName == null && name.equals(a.getNodeName()))))
                return i;
            } else {
              if (namespaceURI.equals(aNamespaceURI)
                  &&
                  name.equals(aLocalName))
                return i;
            }
        }
        return -1;
    }

    // compare 2 nodes in the map.  If a precedes b, return true, otherwise 
    // return false
    protected boolean precedes(Node a, Node b) {

        if (nodes != null) {
            final int size = nodes.size();
            for (int i = 0; i < size; ++i) {
                Node n = (Node)nodes.get(i);
                if (n==a) return true;
                if (n==b) return false;
            }
        }
        return false;
    }


    
NON-DOM: Remove attribute at specified index
/**
      * NON-DOM: Remove attribute at specified index
      */
    protected void removeItem(int index) {
       if (nodes != null && index < nodes.size()){
           nodes.remove(index);
       }
    }


    protected Object getItem (int index){
        if (nodes != null) {
            return nodes.get(index);
        }
        return null;
    }

    protected int addItem (Node arg) {
    	int i = findNamePoint(arg.getNamespaceURI(), arg.getLocalName());
    	if (i >= 0) {
            nodes.set(i, arg);
    	} 
        else {
    	    // If we can't find by namespaceURI, localName, then we find by
    	    // nodeName so we know where to insert.
    	    i = findNamePoint(arg.getNodeName(),0);
            if (i >= 0) {
                nodes.add(i, arg);
            } 
            else {
                i = -1 - i; // Insert point (may be end of list)
                if (null == nodes) {
                    nodes = new ArrayList(5);
                }
                nodes.add(i, arg);
            }
        }
        return i;        
    }

    
NON-DOM: copy content of this map into the specified ArrayList
Params:
list –   ArrayList to copy information into.
Returns:
A copy of this node named map/**
     * NON-DOM: copy content of this map into the specified ArrayList
     * 
     * @param list   ArrayList to copy information into.
     * @return A copy of this node named map
     */
    protected ArrayList cloneMap(ArrayList list) {
        if (list == null) {
            list = new ArrayList(5);
        }
        list.clear();
        if (nodes != null) {
            final int size = nodes.size();
            for (int i = 0; i < size; ++i) {
                list.add(nodes.get(i));
            }
        }
        return list;
    }
    
     protected int getNamedItemIndex(String namespaceURI, String localName) {
        return findNamePoint(namespaceURI, localName);
     }

    
NON-DOM remove all elements from this map
/**
      * NON-DOM remove all elements from this map
      */
    public void removeAll (){
        if (nodes != null) {
            nodes.clear();
        }
    }
    
    private void readObject(ObjectInputStream in)
        throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        if (nodes != null) {
            // cast to Vector is required
            nodes = new ArrayList((Vector)nodes);
        }
    }

    private void writeObject(ObjectOutputStream out) throws IOException {
        List oldNodes = this.nodes;
        try {
            if (oldNodes != null) {
                this.nodes = new Vector(oldNodes);
            }
            out.defaultWriteObject();
        }
        // If the write fails for some reason ensure 
        // that we restore the original object.
        finally {
            this.nodes = oldNodes;
        }
    }
    
} // class NamedNodeMapImpl