/*
 * 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.
 */
/*
 * $Id: ExpandedNameTable.java 1225372 2011-12-28 22:58:27Z mrglavas $
 */
package org.apache.xml.dtm.ref;

import org.apache.xml.dtm.DTM;

This is a default implementation of a table that manages mappings from
expanded names to expandedNameIDs.
%OPT% The performance of the getExpandedTypeID() method is very important 
to DTM building. To get the best performance out of this class, we implement
a simple hash algorithm directly into this class, instead of using the
inefficient java.util.Hashtable. The code for the get and put operations
are combined in getExpandedTypeID() method to share the same hash calculation
code. We only need to implement the rehash() interface which is used to
expand the hash table.
/**
 * This is a default implementation of a table that manages mappings from
 * expanded names to expandedNameIDs.
 *
 * %OPT% The performance of the getExpandedTypeID() method is very important 
 * to DTM building. To get the best performance out of this class, we implement
 * a simple hash algorithm directly into this class, instead of using the
 * inefficient java.util.Hashtable. The code for the get and put operations
 * are combined in getExpandedTypeID() method to share the same hash calculation
 * code. We only need to implement the rehash() interface which is used to
 * expand the hash table.
 */
public class ExpandedNameTable
{

  
Array of extended types for this document   /** Array of extended types for this document   */
  private ExtendedType[] m_extendedTypes;

  
The initial size of the m_extendedTypes array /** The initial size of the m_extendedTypes array */
  private static int m_initialSize = 128;
  
  
Next available extended type   /** Next available extended type   */
  // %REVIEW% Since this is (should be) always equal 
  // to the length of m_extendedTypes, do we need this? 
  private int m_nextType;

  // These are all the types prerotated, for caller convenience.
  public static final int ELEMENT = ((int)DTM.ELEMENT_NODE) ;
  public static final int ATTRIBUTE = ((int)DTM.ATTRIBUTE_NODE) ;
  public static final int TEXT = ((int)DTM.TEXT_NODE) ;
  public static final int CDATA_SECTION = ((int)DTM.CDATA_SECTION_NODE) ;
  public static final int ENTITY_REFERENCE = ((int)DTM.ENTITY_REFERENCE_NODE) ;
  public static final int ENTITY = ((int)DTM.ENTITY_NODE) ;
  public static final int PROCESSING_INSTRUCTION = ((int)DTM.PROCESSING_INSTRUCTION_NODE) ;
  public static final int COMMENT = ((int)DTM.COMMENT_NODE) ;
  public static final int DOCUMENT = ((int)DTM.DOCUMENT_NODE) ;
  public static final int DOCUMENT_TYPE = ((int)DTM.DOCUMENT_TYPE_NODE) ;
  public static final int DOCUMENT_FRAGMENT =((int)DTM.DOCUMENT_FRAGMENT_NODE) ;
  public static final int NOTATION = ((int)DTM.NOTATION_NODE) ;
  public static final int NAMESPACE = ((int)DTM.NAMESPACE_NODE) ;

  
Workspace for lookup. NOT THREAD SAFE!
/** Workspace for lookup. NOT THREAD SAFE!
   * */
  ExtendedType hashET = new ExtendedType(-1, "", "");

  
The array to store the default extended types. /** The array to store the default extended types. */
  private static ExtendedType[] m_defaultExtendedTypes;

  
The default load factor of the Hashtable.
This is used to calcualte the threshold.
/**
   * The default load factor of the Hashtable.
   * This is used to calcualte the threshold.
   */
  private static float m_loadFactor = 0.75f;
    
  
The initial capacity of the hash table. Use a bigger number
to avoid the cost of expanding the table.
/**
   * The initial capacity of the hash table. Use a bigger number
   * to avoid the cost of expanding the table.
   */ 
  private static int m_initialCapacity = 203;
  
  
The capacity of the hash table, i.e. the size of the
internal HashEntry array.
/**
   * The capacity of the hash table, i.e. the size of the
   * internal HashEntry array.
   */ 
  private int m_capacity;
  
  
The threshold of the hash table, which is equal to capacity * loadFactor.
If the number of entries in the hash table is bigger than the threshold,
the hash table needs to be expanded.
/** 
   * The threshold of the hash table, which is equal to capacity * loadFactor.
   * If the number of entries in the hash table is bigger than the threshold,
   * the hash table needs to be expanded.
   */
  private int m_threshold;
  
  
The internal array to store the hash entries.
Each array member is a slot for a hash bucket.
/**
   * The internal array to store the hash entries.
   * Each array member is a slot for a hash bucket.
   */
  private HashEntry[] m_table;

  
Init default values
/**
   * Init default values
   */
  static {
    m_defaultExtendedTypes = new ExtendedType[DTM.NTYPES];

    for (int i = 0; i < DTM.NTYPES; i++)
    {
      m_defaultExtendedTypes[i] = new ExtendedType(i, "", "");
    }
  }

  
Create an expanded name table.
/**
   * Create an expanded name table.
   */
  public ExpandedNameTable()
  {
    m_capacity = m_initialCapacity;
    m_threshold = (int)(m_capacity * m_loadFactor);
    m_table = new HashEntry[m_capacity];
    
    initExtendedTypes();
  }


  
 Initialize the vector of extended types with the
 basic DOM node types.
/**
   *  Initialize the vector of extended types with the
   *  basic DOM node types.
   */
  private void initExtendedTypes()
  {    
    m_extendedTypes = new ExtendedType[m_initialSize];
    for (int i = 0; i < DTM.NTYPES; i++) {
        m_extendedTypes[i] = m_defaultExtendedTypes[i];
        m_table[i] = new HashEntry(m_defaultExtendedTypes[i], i, i, null);
    }
    
    m_nextType = DTM.NTYPES;
  }

  
Given an expanded name represented by namespace, local name and node type,
return an ID.  If the expanded-name does not exist in the internal tables,
the entry will be created, and the ID will be returned.  Any additional 
nodes that are created that have this expanded name will use this ID.
Params:
namespace – The namespace
localName – The local name
type – The node type
Returns:
the expanded-name id of the node./**
   * Given an expanded name represented by namespace, local name and node type,
   * return an ID.  If the expanded-name does not exist in the internal tables,
   * the entry will be created, and the ID will be returned.  Any additional 
   * nodes that are created that have this expanded name will use this ID.
   *
   * @param namespace The namespace
   * @param localName The local name
   * @param type The node type
   *
   * @return the expanded-name id of the node.
   */
  public int getExpandedTypeID(String namespace, String localName, int type)
  {
    return getExpandedTypeID(namespace, localName, type, false);
  }
  
  
Given an expanded name represented by namespace, local name and node type,
return an ID.  If the expanded-name does not exist in the internal tables,
the entry will be created, and the ID will be returned.  Any additional 
nodes that are created that have this expanded name will use this ID.

If searchOnly is true, we will return -1 if the name is not found in the 
table, otherwise the name is added to the table and the expanded name id
of the new entry is returned.
Params:
namespace – The namespace
localName – The local name
type – The node type
searchOnly – If it is true, we will only search for the expanded name.
-1 is return is the name is not found.
Returns:
the expanded-name id of the node./**
   * Given an expanded name represented by namespace, local name and node type,
   * return an ID.  If the expanded-name does not exist in the internal tables,
   * the entry will be created, and the ID will be returned.  Any additional 
   * nodes that are created that have this expanded name will use this ID.
   * <p>
   * If searchOnly is true, we will return -1 if the name is not found in the 
   * table, otherwise the name is added to the table and the expanded name id
   * of the new entry is returned.
   *
   * @param namespace The namespace
   * @param localName The local name
   * @param type The node type
   * @param searchOnly If it is true, we will only search for the expanded name.
   * -1 is return is the name is not found.
   *
   * @return the expanded-name id of the node.
   */
  public int getExpandedTypeID(String namespace, String localName, int type, boolean searchOnly)
  {
    if (null == namespace)
      namespace = "";
    if (null == localName)
      localName = "";
    
    // Calculate the hash code
    int hash = type + namespace.hashCode() + localName.hashCode();
    
    // Redefine the hashET object to represent the new expanded name.
    hashET.redefine(type, namespace, localName, hash);
    
    // Calculate the index into the HashEntry table.
    int index = hash % m_capacity;
    if (index < 0)
      index = -index;

    // Look up the expanded name in the hash table. Return the id if
    // the expanded name is already in the hash table.
    for (HashEntry e = m_table[index]; e != null; e = e.next)
    {
      if (e.hash == hash && e.key.equals(hashET))
        return e.value;
    }
    
    if (searchOnly)
    {
      return DTM.NULL;
    }

    // Expand the internal HashEntry array if necessary.
    if (m_nextType > m_threshold) {
      rehash();
      index = hash % m_capacity;
      if (index < 0)
        index = -index;
    }
    
    // Create a new ExtendedType object
    ExtendedType newET = new ExtendedType(type, namespace, localName, hash);
    
    // Expand the m_extendedTypes array if necessary.
    if (m_extendedTypes.length == m_nextType) {
        ExtendedType[] newArray = new ExtendedType[m_extendedTypes.length * 2];
        System.arraycopy(m_extendedTypes, 0, newArray, 0,
                         m_extendedTypes.length);
        m_extendedTypes = newArray;
    }
    
    m_extendedTypes[m_nextType] = newET;
    
    // Create a new hash entry for the new ExtendedType and put it into 
    // the table.
    HashEntry entry = new HashEntry(newET, m_nextType, hash, m_table[index]);
    m_table[index] = entry;

    return m_nextType++;
  }

  
Increases the capacity of and internally reorganizes the hashtable, 
in order to accommodate and access its entries more efficiently. 
This method is called when the number of keys in the hashtable exceeds
this hashtable's capacity and load factor.
/**
   * Increases the capacity of and internally reorganizes the hashtable, 
   * in order to accommodate and access its entries more efficiently. 
   * This method is called when the number of keys in the hashtable exceeds
   * this hashtable's capacity and load factor.
   */
  private void rehash()
  {
    int oldCapacity = m_capacity;
    HashEntry[] oldTable = m_table;
      
    int newCapacity = 2 * oldCapacity + 1;
    m_capacity = newCapacity;
    m_threshold = (int)(newCapacity * m_loadFactor);
      
    m_table = new HashEntry[newCapacity];
    for (int i = oldCapacity-1; i >=0 ; i--)
    {
      for (HashEntry old = oldTable[i]; old != null; )
      {
        HashEntry e = old;
        old = old.next;
          
        int newIndex = e.hash % newCapacity;
        if (newIndex < 0)
          newIndex = -newIndex;
          
        e.next = m_table[newIndex];
        m_table[newIndex] = e;
      }
    }
  }

  
Given a type, return an expanded name ID.Any additional nodes that are
created that have this expanded name will use this ID.
Returns:
the expanded-name id of the node./**
   * Given a type, return an expanded name ID.Any additional nodes that are
   * created that have this expanded name will use this ID.
   *
   * @return the expanded-name id of the node.
   */
  public int getExpandedTypeID(int type)
  {
    return type;
  }

  
Given an expanded-name ID, return the local name part.
Params:
ExpandedNameID – an ID that represents an expanded-name.
Returns:
String Local name of this node, or null if the node has no name./**
   * Given an expanded-name ID, return the local name part.
   *
   * @param ExpandedNameID an ID that represents an expanded-name.
   * @return String Local name of this node, or null if the node has no name.
   */
  public String getLocalName(int ExpandedNameID)
  {
    return m_extendedTypes[ExpandedNameID].getLocalName();
  }

  
Given an expanded-name ID, return the local name ID.
Params:
ExpandedNameID – an ID that represents an expanded-name.
Returns:
The id of this local name./**
   * Given an expanded-name ID, return the local name ID.
   *
   * @param ExpandedNameID an ID that represents an expanded-name.
   * @return The id of this local name.
   */
  public final int getLocalNameID(int ExpandedNameID)
  {
    // ExtendedType etype = m_extendedTypes[ExpandedNameID];
    if (m_extendedTypes[ExpandedNameID].getLocalName().length() == 0)
      return 0;
    else
    return ExpandedNameID;
  }


  
Given an expanded-name ID, return the namespace URI part.
Params:
ExpandedNameID – an ID that represents an expanded-name.
Returns:
String URI value of this node's namespace, or null if no
namespace was resolved./**
   * Given an expanded-name ID, return the namespace URI part.
   *
   * @param ExpandedNameID an ID that represents an expanded-name.
   * @return String URI value of this node's namespace, or null if no
   * namespace was resolved.
   */
  public String getNamespace(int ExpandedNameID)
  {
    String namespace = m_extendedTypes[ExpandedNameID].getNamespace();
    return (namespace.length() == 0 ? null : namespace);
  }

  
Given an expanded-name ID, return the namespace URI ID.
Params:
ExpandedNameID – an ID that represents an expanded-name.
Returns:
The id of this namespace./**
   * Given an expanded-name ID, return the namespace URI ID.
   *
   * @param ExpandedNameID an ID that represents an expanded-name.
   * @return The id of this namespace.
   */
  public final int getNamespaceID(int ExpandedNameID)
  {
    //ExtendedType etype = m_extendedTypes[ExpandedNameID];
    if (m_extendedTypes[ExpandedNameID].getNamespace().length() == 0)
      return 0;
    else
    return ExpandedNameID;
  }

  
Given an expanded-name ID, return the local name ID.
Params:
ExpandedNameID – an ID that represents an expanded-name.
Returns:
The id of this local name./**
   * Given an expanded-name ID, return the local name ID.
   *
   * @param ExpandedNameID an ID that represents an expanded-name.
   * @return The id of this local name.
   */
  public final short getType(int ExpandedNameID)
  {
    //ExtendedType etype = m_extendedTypes[ExpandedNameID];
    return (short)m_extendedTypes[ExpandedNameID].getNodeType();
  }
  
  
Return the size of the ExpandedNameTable
Returns:
The size of the ExpandedNameTable/**
   * Return the size of the ExpandedNameTable
   *
   * @return The size of the ExpandedNameTable
   */
  public int getSize()
  {
    return m_nextType;
  }
  
  
Return the array of extended types
Returns:
The array of extended types/**
   * Return the array of extended types
   *
   * @return The array of extended types
   */
  public ExtendedType[] getExtendedTypes()
  {
    return m_extendedTypes;
  }

  
Inner class which represents a hash table entry.
The field next points to the next entry which is hashed into
the same bucket in the case of "hash collision".
/**
   * Inner class which represents a hash table entry.
   * The field next points to the next entry which is hashed into
   * the same bucket in the case of "hash collision".
   */
  private static final class HashEntry
  {
    ExtendedType key;
    int value;
    int hash;
    HashEntry next;
      
    protected HashEntry(ExtendedType key, int value, int hash, HashEntry next)
    {
      this.key = key;
      this.value = value;
      this.hash = hash;
      this.next = next;
    }
  }
  
}