content: /*
   *  This file is part of AndroidIDE.
   *
   *  AndroidIDE 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 3 of the License, or
   *  (at your option) any later version.
   *
   *  AndroidIDE 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 AndroidIDE.  If not, see <https://www.gnu.org/licenses/>.
   */
  
  /*
   * reserved comment block
   * DO NOT REMOVE OR ALTER!
   */
  /*
   * Copyright 1999-2002,2004,2005 The Apache Software Foundation.
   *
   * Licensed 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 jaxp.sun.org.apache.xerces.internal.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.
   * <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 Vector 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,v 1.8 2010-11-01 04:39:39 joehw Exp $
   * @since  PR-DOM-Level-1-19980818.
   */
  public class NamedNodeMapImpl
      implements NamedNodeMap, Serializable {
  
      //
      // Constants
      //
  
      /** 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. */
      protected List nodes;
  
      protected NodeImpl ownerNode; // the node this map belongs to
  
      //
      // Constructors
      //
  
      /** 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).
       */
      public int getLength() {
          return (nodes != null) ? nodes.size() : 0;
      }
  
      /**
       * 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.
       *
       * @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. <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.
       * @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.
       * @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. <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.
       */
  
      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
       *
       * @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.
       *
       */
      boolean getReadOnly() {
          return isReadOnly();
      } // getReadOnly()
  
  
      //
      // Protected methods
      //
  
      /**
       * 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.
       *
       * @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.
       */
      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
        */
      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
       *
       * @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
        */
      public void removeAll (){
          if (nodes != null) {
              nodes.clear();
          }
      }
  
      private void readObject(ObjectInputStream in)
          throws IOException, ClassNotFoundException {
          in.defaultReadObject();
          if (nodes != null) {
              nodes = new ArrayList(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
  